Categories
Fade2D Examples

Practical Boolean Operations on Polygons with Holes – Example 6

The previous Example5 showed already how to create shapes i.e., Zone2 objects out of polygons and also how to carry out Boolean operations with them. Nevertheless, there might be questions about the practical implementation, especially when your polygons have holes. For this reason, the present Example6 consists of ready-made C++ source code that handles arbitrary shapes (convex or non-convex, with or without holes) in a numerically robust manner. You can find the source code in examples_2D/ex6_booleanOps2.cpp in the Fade2D-Download. Feel free to use it in your project. Let’s go through this small but powerful C++-example now:

“By the way: You may already have noticed GASSEX() statements in the examples. GASSEX() is a more flexible assert(). Have a look at “someTools.h” for details. Use this macro frequently in your code to quickly find unexpected runtime conditions and also to make your code more verbose.”

The ShapeStruct

The simple struct ShapeStruct holds one vector of boundary segments that describe a shape and a vector of vector<Segment2> that describes holes in this shape.

// A ShapeStruct holds its name, boundary segments and
// optionally hole segments
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
};

The main() function

  1. The main() function below creates three random ShapeStructs using the createShape() function which serves as a placeholer for your real polygon data.
  2. Then it uses insertZone() to turn each ShapeStruct into a Zone2 object.
  3. It computes the union of the zones.
  4. Output
// * 1 *   Create 3 random ShapeStructs
const int NUMHOLES(2);
vector<ShapeStruct> vShapes({	ShapeStruct("Alpha"),
								ShapeStruct("Beta"),
								ShapeStruct("Gamma")});
for(size_t i=0;i<vShapes.size();++i)
{
	createShape(vShapes[i],NUMHOLES);
}

// * 2 *   Convert the ShapeStructs to Zones 
Fade_2D dt;
vector<Zone2*> vZones;
for(size_t i=0;i<vShapes.size();++i)
{
	ShapeStruct& shape(vShapes[i]);
	Zone2* pZone=insertZone(dt,shape);
	GASSEX(pZone!=NULL);
	vZones.push_back(pZone);
	pZone->show(("example6_zone"+shape.name+".ps").c_str(),false,false);
}

dt.show("example6_constrainedDelaunay.ps");

// * 3 *   Boolean union operation
Zone2* pResultZone(vZones[0]);
for(size_t i=1;i<vZones.size();++i) pResultZone=zoneUnion(pResultZone,vZones[i]);

// * 4 *   Visualize the result
pResultZone->show("example6_union.ps",false,true);
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:

Zone Alpha
Input Alpha
Zone Beta
Input Beta
Zone Gamma
Input Gamma
Constrained Delaunay Triangulation of 3 Zone Boundaries
Constrained Delaunay Triangulation of 3 Zone Boundaries
Union of 3 Zones
Union of 3 Zones

Visualizer2:: Writing example6_union.ps
pResultZone, Number of triangles: 195
pResultZone, 2D-area: 2083.77

insertZone()

This is the most interesting part: A Shapestruct is not yet a surface, but only a collection of line segments. The function insertZone() inserts these segments into a Delaunay triangulation, makes a defined surface out of it and returns it as a Zone2 object

Zone2* insertZone(Fade_2D& dt,ShapeStruct& shape)
{
	// Create the boundary zone
	ConstraintGraph2* pBoundaryCG=\
      dt.createConstraint(shape.vBoundarySegments,CIS_CONSTRAINED_DELAUNAY);
	Zone2* pZone(dt.createZone(pBoundaryCG,ZL_INSIDE));
	
	// 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);
		Zone2* pHoleZone(dt.createZone(pHoleCG,ZL_INSIDE));
		pZone=zoneDifference(pZone,pHoleZone);
	}
	return pZone;
}

Leave a Reply

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