Categories
Fade2D Examples

Voronoi Diagram 2D in C++, Example 12

The Voronoi diagram (Wikipedia) of a point set is the dual graph of its Delaunay triangulation. It divides the plane into convex regions, so that each region is closest to one point of the set. There is an incredible number of applications for the Voronoi diagram so many scientists and engineers are familiar with this basic concept.

But a C++ Voronoi library must have fast point location, it must be robust to degenerate settings and it must deal with infinite cells so that it is easy to use. The C++ demo in [examples_2D/ex12_voronoi.cpp] shows that Fade has all these properties. Let’s discuss this example:

A Voronoi diagram in C++

The following code creates a Delaunay triangulation, similarly as in many of the previous examples. Then it fetches its dual graph.

std::cout<<"* Example12: Voronoi - Point location in a Voronoi diagram"<<std::endl;
// * Step 1 *   Create input points (on circles and on a grid). Each
//              of these plays two roles: It is a Delaunay-Vertex
//              AND a site of one Voronoi cell.
std::vector<Point2> vPoints;
generateCircle( 20,25,75,20,20,vPoints);
generateCircle( 10,25,75,10,10,vPoints);
generateCircle( 20,75,35,10,30,vPoints);
for(double x=0;x<41.0;x+=10)
{
	for(double y=0.0;y<41;y+=10)
	{
		vPoints.push_back(Point2(x+.5,y+.5));
	}
}

// * Step 2 *   Draw the Voronoi diagram and Delaunay triangulation
//              Infinite Voronoi cells are automatically clipped.
Fade_2D dt;
dt.insert(vPoints);
Voronoi2* pVoro(dt.getVoronoiDiagram());
pVoro->show("voronoi_and_delaunay.ps",true,false,true,true,false); // Options: Voro=true,Fill-Colors=false,Sites=true,Delaunay=true,Labels=false
pVoro->show("voronoi_and_sites.ps",true,true,true,false,false);  // Options: Voro=true,Fill-Colors=true,Sites=true,Delaunay=false,Labels=false
...
  • Step 1 creates a few input points on a circle and on a grid.
  • Step 2 triangulates the input. Afterwards it fetches the dual graph using Fade_2D::getVoronoiDiagram() and then makes two postscript visualizations. That’s it, see the resulting images below…
A Voronoi diagram and its dual Delaunay triangulation
Voronoi edges (magenta) and Delaunay triangles (blue)
2D Voronoi diagram with sites
The same diagram: Voronoi cells and their sites

“Hint: If you find it more convenient to deal only with finite Voronoi cells, here’s a simple trick: Compute the bounding box of your sites, inflate the box by factor 10 and then add its 4 corner points to the sites to make all previous cells finite.”

Nearest neighbor search / cell search

The below code snippet finds the Voronoi cell of an arbitrary query point. Then it makes another visualization.

// * Step 3 *   Assign arbitrary indices to the Voronoi cells. This
//              is completely optional. You can use this feature
//              for visualization OR to associate Voronoi cells with
//              your own data structures.
std::vector<VoroCell2*> vVoronoiCells;
pVoro->getVoronoiCells(vVoronoiCells);
for(size_t i=0;i<vVoronoiCells.size();++i)
{
	VoroCell2* pVoro(vVoronoiCells[i]);
	pVoro->setCustomCellIndex(int(i));
}

// * Step 4 *   Locate the cell of an arbitrary query point.
Point2 queryPoint(67,95);
VoroCell2* pVoroCell(pVoro->locateVoronoiCell(queryPoint));

Visualizer2 v("located_cell.ps");
Bbox2 bbx(dt.computeBoundingBox());
bbx.enlargeRanges(1.5);
v.setLimit(bbx); // Manually set a limit to clip the viewport.
pVoro->show(&v,true,false,true,false,false); // Options: Voro=true,Fill-Colors=false,Sites=true,Delaunay=false,Labels=false
v.addObject(Label(queryPoint," queryPoint"),Color(CBLUE));
if(pVoroCell!=NULL)
{
	int cellIdx(pVoroCell->getCustomCellIndex());
	std::cout<<"Found the voronoi cell no. "<<cellIdx<<std::endl;
	// Color the located cell red
	v.addObject(pVoroCell,Color(CPALEGREEN,1.0,true));
	// Write a label that shows its custom cell-index
	Label l(*pVoroCell->getSite(),
			(" Voronoi\n Cell "+toString(cellIdx)).c_str(),false);
	v.addObject(l,Color(CBLACK));
	Point2 centroid;
	double area=pVoroCell->getCentroid(centroid);
	if(area<0)
	{
		std::cout<<"Cell "<<cellIdx<<" is infinite: No area, no centroid"<<std::endl;
	}
	else
	{
		std::cout<<"Cell "<<cellIdx<<": area="<<area<<", centroid="<<centroid<<std::endl;
		v.addObject(Label(centroid,"Centroid"),Color(CPURPLE));
	}
	v.writeFile();
}
  • Step 3 is optional: It fetches all Voronoi cells and assigns each an arbitrary integer. This is useful to relate the cells with your own data structures. Moreover you can use these integers as labels for a visualization.
  • The first two lines in Step 4 locate the Voronoi cell of the query point (x=67.0, y=95.0). The remaining lines from Step 4 draw the diagram again, highlighting the cell. Furthermore, they mark the site, the centroid and the queryPoint.

“Observe that only finite cells have a centroid and a finite area. Fade returns -1 for the area of infinite cells.

Located Voronoi cell
The Voronoi cell with label 61 (green), it’s site (black), it’s centroid (purple) and the queryPoint (blue)

“Note: The Voronoi diagram is the dual graph of the Delaunay triangulation. But it is NOT the dual graph of a constrained Delaunay triangulation. Thus, if there are constraint edges in the Delaunay triangulation then you should make them conforming using the method ConstraintGraph2::makeDelaunay() before using the Voronoi diagram.”

Point location benchmark

The 2D Delaunay Triangulation Benchmark shows that Delaunay triangulations are very fast. Due to the duality constructing a Voronoi diagram is similarly fast. This is important because in many applications the diagram is only beneficial if it can be constructed quickly and if cells can be located quickly. But we must still benchmark nearest neighbor queries, see the code below:

// * Step 5 *   Benchmark mass point location (typ. 0.2 s for 1 mio queries)
std::vector<Point2> vRandomPoints;
generateRandomPoints(1000,0,100,vRandomPoints,1);
Fade_2D dt2;
dt2.insert(vRandomPoints);
Voronoi2* pVoro2(dt2.getVoronoiDiagram());
pVoro2->show("mass_location.ps",true,true,false,false,false);  // Options: Voro=true,Fill-Colors=true,Sites=false,Delaunay=false,Labels=false

timer("massLocate");
for(int i=0;i<1000000;++i)
{
	double x(100.0 * double(rand())/RAND_MAX);
	double y(100.0 * double(rand())/RAND_MAX);
	Point2 q(x,y);
	VoroCell2* pVoroCell(pVoro2->locateVoronoiCell(q));
	unusedValue(pVoroCell); // Avoids an unused-warning
}
timer("massLocate");


return 0;
  • Step 5 triangulates 1000 points. Afterwards it retrieves the dual graph pVoro2. Then it enters the “massLocate” timer-section where it finds for 1 million random query points the containing Voronoi cell. This takes only around 0.3 seconds and the time consumption grows only logarithmically in the number of existing cells.

Feel free to link to this site if you find it useful and want to support it!

Leave a Reply

Your email address will not be published. Required fields are marked *