Using Voronoi Diagrams to find area contributions and centerlines between a set of polygons

Problem description

Given a CAD file containing a set of elements belonging to different departments. Compute square footage of areas occupied by elements and their surrounding areas in each department.

The images below show a set of elements in different departments. Each department is assigned a color for visual clarity.

Introduction

After exploring different approaches to compute the square footage, we found that the simplest and most optimal one was to compute the individual areas (element+surrounding space) then sum up all areas in the same department. A new question arises, how to divide space occupied by an element(polygon) and all its neighbors?

Computing area contribution for each polygon

First thing to do is to find a bounding box around each element and get a set of polygons to work with. Next is to find the midpoints between every polygon and all its direct neighbors. What we’re referring to as centerline in this post is, in fact, the shape that spans all the midpoints between a polygon and its neighbors. We’re using a concept in computational geometry called Voronoi Diagrams to find the 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.

Voronoi Cell for each segment (with matching colors)

Voronoi Cells(in red) + Union of Voronoi Cells resulting in centerlines(purple)

Step-by-step process of finding the centerlines

Build a bounding box (polygon) around each element.
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 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 all 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 elements 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

Using collision detection in a CAD Drawing to place non-intersecting elements.

Overview

The goal is to automate the placement of a label/cell in a CAD file without collision with preexisting items for legibility and presentation purposes. We will focus on CAD in this post and we’ll be using a light version of a concept in Computational Geometry called Minkowski Sums to detect obstacles. Please note that the application of this concept can extend beyond CAD and collision detection. It is also used in numerous other fields such as robot motion, 3D modeling, … etc

Illustrative Example

Given a CAD drawing of a cell with multiple labels placed on the side. Programmatically place a new label “001” without intersecting any preexisting labels/objects.

Collision between the “001” label and obstacle1

No collision between the “001” label and existing obstacles

Introduction

To achieve a collision-free placement of the new label for the example above, we’re using a concept in Computational Geometry called Minkowski Sums. Minkowski Sums of two polygons is defined as a set of points extracted by summing all pairs of points from the 2 polygons.

By creating a concave hull for each obstacle and the new label, we’re convolving the new label with each obstacle at 0,0 origin and 180°. The result of the convolution will represent the collision space for each obstacle and the new label can be placed anywhere outside of the collision space.

Quick Definitions

Please check out Boost library Minkowski Sums tutorial here

The center of the green shape (robot) in the illustration above has been overlapped with each vertex of the blue shape (obstacle). The resulting red shape is the space that the robot cannot cross to avoid colliding with the obstacle. The area outside of the red shape is the configuration space, the collision-free space where the robot can roam without colliding with the obstacles.

Computing the collision-free space for the “001” label in the example above

First step is to extract the main placement line (shown in white below) that represents all possible placement points, with or without collision with any existing objects. Then compute the Minkowski Sums of the “001” label with each obstacle at zero origin and at 180°. Results are shown in dashed polygons below. As explained before, the resulting shapes represent the collision space therefore they need to be clipped out of the white line. All the other points on the main placement line will be valid candidates for collision-free placement. For simplicity, we will pick the point closest to beginning of the side line.

Here’s a summary of the steps:

Extract the main placement line
Compute Minkowski Sums between label and obstacles at 0,0 org and at 180°
Clip the resulting polygons from Minkowski Sums from the main placement line

Main placement line shown in White

Dashed polygons representing Minkowski Sums of label and each obstacle

Collision-free placement segments shown in blue

Sample code

/***************************************
  Descr: Returns the Minkowski Sums between a robot and and set of obstacles
****************************************/
int mcs_minkowskiSums 
(
 VecMsPoints			vRobotPts,		//  => flag hull pts [MU]
 vector<VecMsPoints>	vvObstaclePts,  //  => obstacle pts [MU]
 vector<VecMsPoints>&	rvvMinSums		// <= 
)
{
	polygon_set a, b, c;
	polygon poly;
	std::vector<point> pts_robot;

	removeObstacleIntersections(vvObstaclePts);

  // Convert robot points to UORs only necessary if you're using MDL (Bentley uStation)
	int index =0;
	for each (DPoint3d pt in vRobotPts) // convert to UORs
	{
		DPoint3d	dPt;
		Point3d		iPt;
		
		dPt.x = mdlCnv_masterUnitsToUors(pt.x);
		dPt.y = mdlCnv_masterUnitsToUors(pt.y);
		dPt.z = 0.0;

		mdlCnv_DPointToIPoint (&iPt, &dPt); 
		pts_robot.push_back(point(iPt.x,iPt.y));
	}

	boost::polygon::set_points(poly, pts_robot.begin(), pts_robot.end());
	//boost::geometry::correct(poly);
	poly.size();
	a += poly;

	for each (VecMsPoints vObstaclePts in vvObstaclePts)
	{
	  // Convert obtscale points to UORs. ** only necessary if you're using MDL (Bentley uStation)
		polygon poly1;
		std::vector<point> pts;
		for each (DPoint3d pt in vObstaclePts) // convert to UORs and * -1 for Mink Diff
		{
			DPoint3d	dPt;
			Point3d		iPt;
			
			dPt.x = mdlCnv_masterUnitsToUors(pt.x) * -1.0;
			dPt.y = mdlCnv_masterUnitsToUors(pt.y) * -1.0;
			dPt.z = 0.0;

			mdlCnv_DPointToIPoint (&iPt, &dPt); 
			
			pts.push_back(point(iPt.x,iPt.y));
		}

		boost::polygon::set_points(poly1, pts.begin(), pts.end());
		//boost::geometry::correct(poly1);
		poly1.size();
		b += poly1;
	}

	convolve_two_polygon_sets(c, a, b); // From Boost

	if (c.size() == 0)
		return FALSE;
	if (c.empty())
		return FALSE;

	//printf("\n BEFORE SIMPLE POLYGONS");
	//SimplePolygons simplePolygons;
	using namespace boost::polygon;
	vector<polygon> resultPolygons;
	c.get(resultPolygons);
	
	//for each(SimplePolygon poly in simplePolygons)
	for each(polygon poly in resultPolygons)
		rvvMinSums.push_back(mcs_get_points_poly(begin_points(poly), end_points(poly)));
	
	return TRUE;
}

Author Archives Nabil Kherouf

Recent Posts

Recent Comments

Archives

Categories

Meta

About Nabil Kherouf

Using Voronoi Diagrams to find area contributions and centerlines between a set of polygons

Using Voronoi Diagrams to find area contributions and centerlines between a set of polygons

Problem description

Introduction

Computing area contribution for each polygon

Voronoi Diagrams

Step-by-step process of finding the centerlines

Conclusion

Collision detection inside CAD files

Using collision detection in a CAD Drawing to place non-intersecting elements.

Overview

Illustrative Example

Introduction

Quick Definitions

Computing the collision-free space for the “001” label in the example above

Sample code