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 diagram 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]);
      }
   }

   // Draw Seeds
   for (int i = 0; i < vPoints.size(); ++i)
   {
      CPoint a = vPoints[i];
      pDC->FillSolidRect(a.x - 1, a.y - 1, 3, 3, 0x0);
   }
}

Output1

 Output 2 (B/W)

Output 3 (Manhattan Distance)

Output 4 ( Max(x,y) )