Tracing Voronoi Diagrams – The Greedy Approach

Voronoi Diagrams are pretty and useful. I use them for PCB isolation milling. This piece of code (C++/MFC) traces the voronoi diagrom of some random points. The algorithm is the most simple, lowest performing greedy method.

void TraceVoronoi(CDC* pDC, std::vector<CPoint>& vPoints, std::vector<COLORREF>& vColors)
{
    for (int x = 0; x < 600; ++x)
    {
        for (int y = 0; y < 400; ++y)
        {
            double dMinDist = 100000000;
            CPoint pt;
            int n = 0;
            for (int i = 0; i < vPoints.size(); ++i)
            {
                CPoint a = vPoints[i];
                double d = (x - a.x) * (x - a.x) + (y - a.y) * (y - a.y);
                //double d = abs(x - a.x) + abs(y - a.y); // Manhattan distance
                //double d = max(abs(x - a.x), abs(y - a.y)); // ?? distance
                if (d < dMinDist)
                {
                    pt = a;
                    n = i;
                    dMinDist = d;
                }
           }
           pDC->SetPixelV(x, y, vColors[n]);
       }
   }
   // Points
   for (int i = 0; i < vPoints.size(); ++i)
   {
       CPoint a = vPoints[i];
       pDC->FillSolidRect(a.x - 1, a.y - 1, 3, 3, 0x0);
   }
}

Output 1

Image

Output 2 (B/W)

Image

Output 3 (Manhattan Distance)

Image

Output 4 (?? Distance)

Image

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s