Blog

Using Voronoi Diagrams to Equally Divide Adjoining Space Between Polygons

Problem description

Given a set of arbitrary polygons belonging to different categories, we would like to equally divide the space between polygons and compute the square footage of each category.

The following images show a set of polygons in different color-coded categories. Last image shows what the goal is: a set of shapes representing each category and whose square footage can easily be computed.

Introduction

After exploring different approaches to compute the square footage, we found that the simplest and most optimal way was to compute the individual polygon contribution (Area of polygon + 1/2 surrounding space) then sum up all the individual contributions in the same category. A new question then arose, how to divide space occupied by a certain polygon and its neighbors?

Following image shows a set of polygons with the shared space equally divided between each polygon and its neighbors.

Computing area contribution for each polygon

To find area contribution for each polygon, we need to find the midpoints between the polygon and its direct neighbors. What we’re referring to as centerline in this post is, in fact, the shape that spans all the midpoints between each polygon and its neighbors. We’re using a concept in Computational Geometry called Voronoi Diagrams to find these centerlines.

Voronoi Diagrams

The simplest definition of Voronoi Diagrams is it being the partition of a plane into a set of regions close to each of a set of objects. In other words, given a set of points in a plane, a Voronoi Region/Cell of a point A is an area encompassing points closer to A than any other points in the plane. To use Voronoi Diagrams with a set of polygons, we need to compute a cell for each segment of a given polygon. By performing a union on the resulting Voronoi Cells, we find the centerlines between the polygon and its neighbors (See example below). Please note that these centerlines can also be used for other purposes such as indoor navigation or robot motion.

Following image shows a Voronoi Cell for each segment with matching colors for the cell/segment:

Following images show the Voronoi Cells (in red) associated with the two polygons and the final centerlines in purple after performing the union of the Voronoi Cells:

Step-by-step process of finding the centerlines

• Extract segments from each polygon and assign them an id to associate them with their original polygon.
• Find the Voronoi Cell for each segment passed. We’re using Boost library to perform this operation.
• Union the Voronoi Cells for segments in each polygon.

The Boost library provides a very efficient and easy-to-use function to compute the Voronoi Diagrams of any set of non-intersecting segments (except endpoints of consecutive segments). By passing the segments of each polygon to the Boost, we’re computing the Voronoi Cell for each segment then we’re performing a boolean union of all resulting Voronoi Cells. As mentioned before, the union will be a shape representing the centerlines between the polygon and its direct neighbors.

Please note that in the following C++ example, our polygons are stored in a collection called vRanges. Also, segments are instances of the Segment_vd class which takes the coordinates of the segment endpoints and the index of the containing polygon as inputs to the constructor.

// building a collection of segments from each polygon 
	for (unsigned index_range=0; index_range<vRanges.size(); index_range++)
	{
		SpecialGondolaRange range = vRanges[index_range];

		vRanges[index_range].bVoronoi_points_found = FALSE;
		if (range.bIgnore)
			continue;

		for (int i=0; i< range.numPnts; i++)
		{
			int curr = i, next = i==range.numPnts-1?0:i+1;
			DPoint3d currP=range.shapePnts[curr];
			DPoint3d nextP=range.shapePnts[next];

			currP.x = currP.x;
			currP.y = currP.y;
			currP.z = 0;

			nextP.x = nextP.x;
			nextP.y = nextP.y;
			nextP.z = 0;

			double dist = mdlVec_distanceXY(&currP, &nextP);

			segments.push_back(Segment_vd(currP.x, currP.y, nextP.x, nextP.y, index_range));	
		}
	}

	printf("--");

	std::vector<Segment_vd> segments_no_intersections;

	// Construction of the Voronoi Diagram.
	voronoi_diagram<double> vd;
	construct_voronoi(points.begin(), points.end(),
		segments.begin(), segments.end(),
		&vd);
	printf("--");

Conclusion

As shown above, Voronoi Diagrams were very essential in resolving our problem of area contribution by generating the midpoints between polygons in our file. Please note that, for this tutorial we’ve used VS2005 and Boost library v1.74.0. The newer versions of Boost (+1.82) require at least C++11 and a more recent release of Visual Studio.

Helpful links:

https://www.boost.org/doc/libs/1_80_0/libs/polygon/doc/voronoi_diagram.htm

https://alexbeutel.com/webgl/voronoi.html

https://mathworld.wolfram.com/VoronoiDiagram.html