Categories

# 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
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;
```
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:
``````
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;
}```