Categories

# 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"),
ShapeStruct("Beta"),
ShapeStruct("Gamma")});
for(size_t i=0;i<vShapes.size();++i)
{
createShape(vShapes[i],NUMHOLES);
}

// * 2 *   Convert the ShapeStructs to Zones
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);
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;
```
• 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:
``````
Visualizer2:: Writing example6_union.ps
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=\
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;
}```