## Boolean Operations on Polygons

Fade provides polygon clipping and functions to combine polygons through the boolean operations:

- Union (A OR B)
- Intersection (A AND B)
- Difference (A NOT B)
- Symmetric Difference (A XOR B)

The demo source code described below is contained in the example5.cpp file in the Fade2D download.

## Creating two Shapes (Zones)

A Zone represents a polygonal area in a triangulation. We set up two (intersecting) polygons:

- Four bounding box points are inserted (just to improve the visual appearance)
- Two vectors of Segment2 objects (intersecting shapes) are created
- Two ConstraintGraph2 objects are made
- Two Zone2 objects are made

// * 1 * Insert 4 bounding box points around the data // Not necessary, just to get a nicer visualization Fade_2D dt; dt.insert(Point2(-100,-100)); dt.insert(Point2(+100,-100)); dt.insert(Point2(+100,+270)); dt.insert(Point2(-100,+270)); // * 2 * Prepare two vectors of Segments int numPoints(10); std::vector<Point2> vConstraintPoints0; std::vector<Point2> vConstraintPoints1; generateCircle(numPoints,0,150,80,80,vConstraintPoints0); generateCircle(numPoints,0,40,60,130,vConstraintPoints1); std::vector<Segment2> vSegments1; std::vector<Segment2> vSegments2; for(size_t i=0;i<vConstraintPoints0.size();++i) { Point2& p0(vConstraintPoints0[i]); Point2& p1(vConstraintPoints0[(i+1)%vConstraintPoints0.size()]); vSegments1.push_back(Segment2(p0,p1)); Point2& p2(vConstraintPoints1[i]); Point2& p3(vConstraintPoints1[(i+1)%vConstraintPoints1.size()]); vSegments2.push_back(Segment2(p2,p3)); } // * 3 * Use the segments to create two ConstraintGraphs. ConstraintGraph2* pCG1=dt.createConstraint(vSegments1,CIS_CONSTRAINED_DELAUNAY); ConstraintGraph2* pCG2=dt.createConstraint(vSegments2,CIS_CONSTRAINED_DELAUNAY); dt.show("example5_constraints.ps"); // Make sure pCG1 and pCG2 are closed if(!pCG1->isPolygon() || !pCG2->isPolygon() ) { std::cout<<"pCG1 and pCG2 must be closed polygons, stop"<<std::endl; return 1; } // * 4 * Create two Zone2 objects using ZL_INSIDE: Zone2* pZone0(dt.createZone(pCG1,ZL_INSIDE)); pZone0->show("example5_zone0.ps",true,true); // all triangles=true, show constraints=true Zone2* pZone1(dt.createZone(pCG2,ZL_INSIDE)); pZone1->show("example5_zone1.ps",true,true);

Below the intersecting polygons and the two zones are shown.

## Boolean operations with polygons (zones)

Once the two Zones have been made a boolean operation is carried out with just one more line of code. See the result images below:

// a) Union operation Zone2* pZoneUnion(zoneUnion(pZone0,pZone1)); // b) Intersection operation Zone2* pZoneIntersection(zoneIntersection(pZone0,pZone1)); // c) Difference operation Zone2* pZoneDifference(zoneDifference(pZone0,pZone1)); // d) Symmetric Difference operation Zone2* pZoneSymDifference(zoneSymmetricDifference(pZone0,pZone1));

## Extracting triangles and Border Polygons

The triangles of a Zone2 object can be conveniently extracted using Zone2::getTriangles() while Zone2::getBorderEdges() can be used to extract a vector of border edges. Edge2 objects are always counterclockwise oriented with respect to their triangle but Zone2::getBorderEdges() does not deliver them in a specific order, thus they do not form a polygon yet. The code below demonstrates how to use the function edgesToPolygons() to extract polygons.

// * 6 * Retrieve the border edges of pZoneSymmetricDifference vector<Edge2> vBorders; pZoneSymmetricDifference->getBorderEdges(vBorders); Visualizer2 v("example5_symDiffBorders.ps"); dt.show(&v,false); // show only the triangles v.addObject(vBorders,Color(CGREEN,0.5,true)); v.writeFile(); // * 7 * Turn the border edges into polygons vector<Edge2> vRemainingEdges; vector<vector<Edge2> > vvEdges; edgesToPolygons(vBorders,vvEdges,vRemainingEdges); assert(vRemainingEdges.empty()); // All edges belong to polygons // * 8 * Draw Visualizer2 polyVis("example5_polygons.ps"); pZoneSymmetricDifference->show(&polyVis,false,false); // show only the triangles for(size_t poly=0;poly<vvEdges.size();++poly) { const vector<Edge2>& vPolygon(vvEdges[poly]); Color c(Color::getNextColorName(),1.0,false); // Next color from a (repeating) sequence for(size_t j=0;j<vPolygon.size();++j) { const Edge2& edge(vPolygon[j]); polyVis.addObject(edge,c); Point2* pSourcePoint(edge.getSrc()); Label lab(*pSourcePoint,toString(j),true,16); polyVis.addObject(lab,c); } } polyVis.writeFile();

This post has shown how to combine polygonal areas through set operations and how to extract the boundary polygons of the resulting area. But Zone2 objects can also be defined in order to create high quality triangular meshes. See Example6 – Mesh Generation and the article about Advanced Mesh Generation.

## 4 Comments