Welding vertices April 27th, 2009
To summarise the problem -- welding vertices means you want to find all pairs of vertices with N distance of each other, and join them into one. There's many uses for this kind of stuff.
The trouble is you often see it implemented using a O(n^2) algorithm, like such -
void WeldVerticesSlow(vertex *verts, int vertCount) { for (int a=0;a<vertCount;a++) { for (int b=0;b<vertCount;b++) { if (Distance(verts[a], verts[b]) < THRESHOLD) Join(a, b); } } }
Now I'm not claiming that this one below is the fastest algorithm, but it's kind of somewhere around O(n-log-n) I think.
void WeldVerticesFast(vertex *verts, int vertCount) { SortAlongXAxis(verts, vertCount); for (int a=0;a<vertCount;a++) { int b = a; while(b--) { if (verts[b].x < verts[a].x - THRESHOLD) break; if (Distance(verts[a], verts[b]) < THRESHOLD) Join(a, b); } } }
It tends to do massively better than the naive algorithm in the real world, as the slow way can thrash the cache like mad -- if your full vertex set doesn't fit in the L2 cache, you'll basically get a cache miss on every iteration.
So stop using n^2 !
Note
There's an even faster way to do this, by using a hashtable. But I wanted to post this simple to show a way that requires almost no changes an existing routine.
Written by Richard Mitton,
software engineer and travelling wizard.
Follow me on twitter: http://twitter.com/grumpygiant