Categories
Fade2D Examples

Practical Boolean Operations on Polygons with Holes – Example 6

Boolean operations on Polygons with Holes can be difficult to implement. Thus the present example examples_2D/ex6_booleanOps2.cpp consists of ready-made C++ source code that handles arbitrary shapes (convex or non-convex, with or without holes). So feel free to use it in your project.

You might also want to check the previous Example5. For example, it demonstrates with simple shapes how to create Zone2 objects and shows first boolean operations.

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.

Certainly you have already noticed GASSEX() statements in the examples. GASSEX() is a more flexible assert() and you can find it in “someTools.h”. Use it frequently in your code: First to find unexpected runtime conditions automatically and second to make your code more verbose.”

The main() function

// * 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;
  1. Step 1 in the above listing calls the createShape() function to create three random polygons with holes. More precisely, these are tentatively stored as ShapeStructs. You do not need to study the createShape() function because it is only a placeholer for your real polygon data.
  2. Next, Step 2 uses insertZone() to turn each ShapeStruct into a Zone2 object.
  3. The third step computes the union of the zones.
  4. 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 example6_union.ps
pResultZone, Number of triangles: 195
pResultZone, 2D-area: 2083.77

The insertZone() function

The Shapestruct defined above is not yet a surface, but only a collection of line segments. Therefore insertZone()is the most interesting function because it 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 *