codersnotes

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 !