2D Delaunay Triangulation Examples in C++

Practical Boolean Operations on Polygons with Holes – Example 6

Implementing Boolean operations on Polygons with Holes can be challenging. Therefore, in the present example, examples_2D/ex6_booleanOps2.cpp, you’ll find C++ source code already prepared to handle arbitrary shapes, whether they are convex or non-convex, with or without holes. Feel free to use this code in your project.

Additionally, it’s advisable to review the previous Example 5. This example demonstrates how to create Zone2 objects and introduces initial boolean operations using simple shapes.

The ShapeStruct

// 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 above struct ShapeStruct holds one vector of boundary segments that describe the outer boundary of a shape and a vector of vector<Segment2> that describes holes in this shape.

You may have noticed the presence of GASSEX() statements in the examples. The GASSEX macro serves as a more flexible alternative to assert() and can be found in “someTools.h”. Its use is optional, but it is strongly recommended to use GASSEX frequently in your code for two primary purposes: First, to automatically detect unexpected runtime conditions, and second, to enhance the verbosity of your code.

The main() function

// * 1 *   Create 3 random ShapeStructs
const int NUMHOLES(2);
vector<ShapeStruct> vShapes({	ShapeStruct("Alpha"),
for(size_t i=0;i<vShapes.size();++i)

// * 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);

// * 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
vector<Triangle2*> vTriangles;
cout<<"pResultZone, Number of triangles: "<<vTriangles.size()<<endl;
cout<<"pResultZone, 2D-area: "<<pResultZone->getArea2D()<<endl;

return 0;
  • In Step 1 of the listing above, the createShape() function is invoked to generate three random polygons with holes. These polygons are stored as ShapeStructs. There’s no need to delve into the details of the createShape() function because it simply acts as a placeholder for your actual polygon data.
  • Moving on to Step 2, the insertZone() function is used to transform each ShapeStruct into a Zone2 object.Next, Step 2 uses insertZone() to turn each ShapeStruct into a Zone2 object.
  • The third step computes the union of the zones.
  • Finally, in Step 4, the result is drawn and printed:
Zone Alpha - a zone with two holes
Input Alpha
Zone Beta - a zone with two holes
Input Beta
Zone Gamma - a zone with two holes
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
pResultZone, Number of triangles: 195
pResultZone, 2D-area: 2083.77

The insertZone() function

The Shapestruct defined above is only a collection of line segments. Therefore, insertZone() becomes particularly relevant as it takes these segments, inserts them into a Delaunay triangulation, transforms them into a Zone2, and then returns a pointer to it.

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

Leave a Reply

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