Boolean Operations on Polygons with Holes

Boolean operations on polygons with holes

Source code that computes the union, difference or intersection of polygons with Fade2D is often requested. Therefore, C++ example code that computes the union of polygons is provided here: The algorithm handles arbitrary shapes (convex/non-convex, with or without holes) and it is numerically robust. Download example code here and feel free to adapt it to your project. Let’s go through this small but powerful C++-example now:

The main() function

The main() function creates random input data using the createShape() function: The 8 ShapeStructs consist of line segments for the boundary and the holes. Then it uses insertZone() to turn each ShapeStruct into a Zone2 object (an area) in the same Delaunay triangulation. Finally, it computes the union of the zones. The used helpers ShapeStruct, createShape() and insertZone() are described further below.


int main(int,char**)
{
	// Create random ShapeStruct's: Each one contains a vector of
	// Segment2's for the boundary and $NUMHOLES vectors for the holes.
	const int NUMHOLES(2);
	vector<ShapeStruct> vShapes({
									ShapeStruct("ShapeA"),
									ShapeStruct("ShapeB"),
									ShapeStruct("ShapeC"),
									ShapeStruct("ShapeD"),
									ShapeStruct("ShapeE"),
									ShapeStruct("ShapeF"),
									ShapeStruct("ShapeG"),
									ShapeStruct("ShapeH"),
									});
	for(ShapeStruct& oneShape:vShapes) createShape(oneShape,NUMHOLES);


	// Define the zones (inner area of the shapes) and visualize
	Fade_2D dt;
	vector<Zone2*> vZones;
	for(ShapeStruct& shape:vShapes)
	{
		Zone2* pZone=insertZone(dt,shape);
		VERIFY(pZone!=NULL);
		vZones.push_back(pZone);
		pZone->show("zone_of_"+shape.name+".ps",false,false);
	}

	// Draw the triangulation
	dt.show("dt.ps");

	// Boolean union operation: Form the union of the zones
	Zone2* pResultZone(vZones[0]);
	for(size_t i=1;i<vZones.size();++i) 
	{
		pResultZone=zoneUnion(pResultZone,vZones[i]);
	}

	// Visualize and print the result
	bool bShowSegments(true);
	bool bShowAllTriangles(false);
	pResultZone->show("union.ps",bShowAllTriangles,bShowSegments);
	vector<Triangle2*> vTriangles;
	pResultZone->getTriangles(vTriangles);
	cout<<"pResultZone, Number of triangles: "<<vTriangles.size()<<endl;
	cout<<"pResultZone, 2D-area: "<<pResultZone->getArea2D()<<endl;

	return 0;
}

The result is printed and drawn:

Visualizer2:: Writing union.ps
pResultZone, Number of triangles: 624
pResultZone, 2D-area: 7310.81
Result: Union of 8 Polygons with Holes

Result: The Union of 8 Polygons with Holes

ShapeStruct

One ShapeStruct corresponds to one polygon with optional holes. Thus a ShapeStruct holds at least one vector<Segment2> for the boundary plus optional ones for the holes.

struct ShapeStruct
{
	ShapeStruct(const std::string& name_):name(name_)
	{}
	// Data
	std::string name; // Shape name
	vector<Segment2> vBoundarySegments; // Shape boundary
	vector<vector<Segment2> > vvHoles; // vectors of segments for n holes
};

Creating random Shapes

The createShape() function fills a ShapeStruct with segments for demonstration purposes. Don’t waste time reading it unless you are interested. You will use your own polygon data anyway.


void createShape(
						ShapeStruct& shape,
						int numHoles
						)
{
	static int seed(1); // Seed for the random number generator

	// Create random numbers for the outer boundary
	vector<double> vRand;
	generateRandomNumbers(4,10,100,vRand,++seed);
	double xmin(vRand[0]),ymin(vRand[1]),xrange(vRand[2]),yrange(vRand[3]);

	// Create p0,...,p3 and the segments between
	Point2 p0(xmin,ymin);
	Point2 p1(xmin,ymin+yrange);
	Point2 p2(xmin+xrange,ymin);
	Point2 p3(xmin+xrange,ymin+yrange);
	shape.vBoundarySegments.emplace_back(Segment2(p0,p1));
	shape.vBoundarySegments.emplace_back(Segment2(p1,p3));
	shape.vBoundarySegments.emplace_back(Segment2(p3,p2));
	shape.vBoundarySegments.emplace_back(Segment2(p0,p2));

	// Create n holes and radii
	for(int i=0;i<numHoles;++i)
	{
		vector<double> vCenterX,vCenterY,vRadius;
		vector<Point2> vPoints;
		generateRandomNumbers(1,xmin+0.1*xrange,xmin+0.9*xrange,vCenterX,++seed);
		generateRandomNumbers(1,ymin+0.1*yrange,ymin+0.9*yrange,vCenterY,++seed);
		double radiusX(min({vCenterX[0]-xmin,xmin+xrange-vCenterX[0]}));
		double radiusY(min({vCenterY[0]-ymin,ymin+yrange-vCenterY[0]}));
		generateCircle(15,vCenterX[0],vCenterY[0],0.9*radiusX,0.9*radiusY,vPoints);
		shape.vvHoles.emplace_back(vector<Segment2>());
		for(size_t i=0;i<vPoints.size();++i)
		{
			shape.vvHoles.back().emplace_back(Segment2(vPoints[i],vPoints[(i+1)%vPoints.size()]));
		}
	}
}

Defining an Area (Zone2)

A ShapeStruct consists only of segments. The insertZone() function uses these segments to define an area (Zone2) in a Delaunay triangulation. When you adapt this code you should continue to use either our VERIFY macro or assert() or something similar from your own toolbox to make sure that certain states in the software are as expected. It really saves time during development.


Zone2* insertZone(Fade_2D& dt,ShapeStruct& shape)
{
	// Create the boundary zone
	VERIFY(!shape.vBoundarySegments.empty());
	ConstraintGraph2* pBoundaryCG=dt.createConstraint(shape.vBoundarySegments,CIS_CONSTRAINED_DELAUNAY);
	VERIFY(pBoundaryCG!=NULL);
	VERIFY(pBoundaryCG->isPolygon());
	Zone2* pZone(dt.createZone(pBoundaryCG,ZL_INSIDE));
	VERIFY(pZone!=NULL);

	// Create and subtract the holes (if any)
	for(vector<Segment2>& vHole : shape.vvHoles)
	{
		if(vHole.empty()) continue; // Unusable
		ConstraintGraph2* pHoleCG=dt.createConstraint(vHole,CIS_CONSTRAINED_DELAUNAY);
		VERIFY(pHoleCG->isPolygon());
		Zone2* pHoleZone(dt.createZone(pHoleCG,ZL_INSIDE));
		VERIFY(pHoleZone!=NULL);
		pZone=zoneDifference(pZone,pHoleZone);
		VERIFY(pZone!=NULL);
	}
	return pZone;
}

Spread the word. Share this post!

Leave A Reply

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

*

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close