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