# Boolean operations on polygons with holes

Source code that computes the union, difference or intersection of polygons with Fade2D is often requested. Therefore, C++ example code that computes the union of polygons is provided here: The algorithm handles arbitrary shapes (convex/non-convex, with or without holes) and it is numerically robust. Download example code here and feel free to adapt it to your project. Let’s go through this small but powerful C++-example now:

## The main() function

The main() function creates random input data using the createShape() function: The 8 ShapeStructs consist of line segments for the boundary and the holes. Then it uses insertZone() to turn each ShapeStruct into a Zone2 object (an area) in the same Delaunay triangulation. Finally, it computes the union of the zones. The used helpers ShapeStruct, createShape() and insertZone() are described further below.

```
int main(int,char**)
{
// Create random ShapeStruct's: Each one contains a vector of
// Segment2's for the boundary and \$NUMHOLES vectors for the holes.
const int NUMHOLES(2);
vector<ShapeStruct> vShapes({
ShapeStruct("ShapeA"),
ShapeStruct("ShapeB"),
ShapeStruct("ShapeC"),
ShapeStruct("ShapeD"),
ShapeStruct("ShapeE"),
ShapeStruct("ShapeF"),
ShapeStruct("ShapeG"),
ShapeStruct("ShapeH"),
});
for(ShapeStruct& oneShape:vShapes) createShape(oneShape,NUMHOLES);

// Define the zones (inner area of the shapes) and visualize
vector<Zone2*> vZones;
for(ShapeStruct& shape:vShapes)
{
Zone2* pZone=insertZone(dt,shape);
VERIFY(pZone!=NULL);
vZones.push_back(pZone);
pZone->show("zone_of_"+shape.name+".ps",false,false);
}

// Draw the triangulation
dt.show("dt.ps");

// Boolean union operation: Form the union of the zones
Zone2* pResultZone(vZones);
for(size_t i=1;i<vZones.size();++i)
{
pResultZone=zoneUnion(pResultZone,vZones[i]);
}

// Visualize and print the result
bool bShowSegments(true);
bool bShowAllTriangles(false);
pResultZone->show("union.ps",bShowAllTriangles,bShowSegments);
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:

Visualizer2:: Writing union.ps
pResultZone, Number of triangles: 624
pResultZone, 2D-area: 7310.81

## ShapeStruct

One ShapeStruct corresponds to one polygon with optional holes. Thus a ShapeStruct holds at least one vector<Segment2> for the boundary plus optional ones for the holes.

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

## Creating random Shapes

The createShape() function fills a ShapeStruct with segments for demonstration purposes. Don’t waste time reading it unless you are interested. You will use your own polygon data anyway.

```
void createShape(
ShapeStruct& shape,
int numHoles
)
{
static int seed(1); // Seed for the random number generator

// Create random numbers for the outer boundary
vector<double> vRand;
generateRandomNumbers(4,10,100,vRand,++seed);
double xmin(vRand),ymin(vRand),xrange(vRand),yrange(vRand);

// Create p0,...,p3 and the segments between
Point2 p0(xmin,ymin);
Point2 p1(xmin,ymin+yrange);
Point2 p2(xmin+xrange,ymin);
Point2 p3(xmin+xrange,ymin+yrange);
shape.vBoundarySegments.emplace_back(Segment2(p0,p1));
shape.vBoundarySegments.emplace_back(Segment2(p1,p3));
shape.vBoundarySegments.emplace_back(Segment2(p3,p2));
shape.vBoundarySegments.emplace_back(Segment2(p0,p2));

// Create n holes and radii
for(int i=0;i<numHoles;++i)
{
vector<Point2> vPoints;
generateRandomNumbers(1,xmin+0.1*xrange,xmin+0.9*xrange,vCenterX,++seed);
generateRandomNumbers(1,ymin+0.1*yrange,ymin+0.9*yrange,vCenterY,++seed);
shape.vvHoles.emplace_back(vector<Segment2>());
for(size_t i=0;i<vPoints.size();++i)
{
shape.vvHoles.back().emplace_back(Segment2(vPoints[i],vPoints[(i+1)%vPoints.size()]));
}
}
}

```

## Defining an Area (Zone2)

A ShapeStruct consists only of segments. The insertZone() function uses these segments to define an area (Zone2) in a Delaunay triangulation. When you adapt this code you should continue to use either our VERIFY macro or assert() or something similar from your own toolbox to make sure that certain states in the software are as expected. It really saves time during development.

```
{
// Create the boundary zone
VERIFY(!shape.vBoundarySegments.empty());
ConstraintGraph2* pBoundaryCG=dt.createConstraint(shape.vBoundarySegments,CIS_CONSTRAINED_DELAUNAY);
VERIFY(pBoundaryCG!=NULL);
VERIFY(pBoundaryCG->isPolygon());
Zone2* pZone(dt.createZone(pBoundaryCG,ZL_INSIDE));
VERIFY(pZone!=NULL);

// 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);
VERIFY(pHoleCG->isPolygon());
Zone2* pHoleZone(dt.createZone(pHoleCG,ZL_INSIDE));
VERIFY(pHoleZone!=NULL);
pZone=zoneDifference(pZone,pHoleZone);
VERIFY(pZone!=NULL);
}
return pZone;
}

```