Polygons and Zones – Example4

This is the right article if you want to triangulate polygons or carry out polygon clipping. In Fade, a zone defines a specific area of a triangulation. You can use zones to combine shapes with the boolean set operations union, difference,symmetric difference and intersection. From the result zone you can easily calculate the total area, obtain its triangles or its contour.

You can define a zone as

• the area inside or outside a polygon
• the area grown from a seed point
• the area of the whole triangulation (global zone)
• the area of arbitrary triangles

The below example code (examples_2D/ex4_zones.cpp in the download) demonstrates that.

Preparing two initial Polygons

1. A Fade_2D object is created and 4 bounding box points are inserted
2. Points on two circles are created (vCircle0,vCircle1)
3. Segments are created (vSegment0,vSegment1)
4. Two polygons (ConstraintGraph2 pCG0, pCG1) are made
5. The triangulation is drawn.

// * 1 *   Insert 4 bounding box points
Fade_2D dt;
dt.insert(Point2(0,0));
dt.insert(Point2(+100,0));
dt.insert(Point2(100,50));
dt.insert(Point2(0,50));

// * 2 *   Create points on two circles
std::vector<Point2> vCircle0;
std::vector<Point2> vCircle1;
int numPoints(8);
double radius(22);
//generateCircle( num,centerX,centerY,radiusX,radiusY,vOut);
generateCircle(numPoints,25.0,25.0,radius,radius,vCircle0);
generateCircle(numPoints,75.0,25.0,radius,radius,vCircle1);

// * 3 *   Create segments
std::vector<Segment2> vSegments0;
std::vector<Segment2> vSegments1;
for(int i=0;i<numPoints;++i)
{
	Segment2 seg0(vCircle0[i],vCircle0[(i+1)%numPoints]);
	Segment2 seg1(vCircle1[i],vCircle1[(i+1)%numPoints]);
	vSegments0.push_back(seg0);
	vSegments1.push_back(seg1);
}

// * 4 *   Insert the segments as constraint graphs
ConstraintGraph2* pCG0=dt.createConstraint(vSegments0,CIS_CONSTRAINED_DELAUNAY);
ConstraintGraph2* pCG1=dt.createConstraint(vSegments1,CIS_CONSTRAINED_DELAUNAY);

// * 5 *  Visualize
dt.show("example4_constraints.ps",true);

Creating an inside and outside zone

ConstraintGraph pCG1 is the left polygon circle in the above image. let’s create a Zone2 inside and another one outside this polygon now.

// + Zone inside pCG0:
Zone2* pZoneInside(dt.createZone(pCG0,ZL_INSIDE));
pZoneInside->show("example4_zoneInside.ps",true,true); 

// + Zone outside pCG0:
Zone2* pZoneOutside(dt.createZone(pCG0,ZL_OUTSIDE));
pZoneOutside->show("example4_zoneOutside.ps",true,true);

Zone grown from a seed point

A Zone2 object can not only be made inside or outside a specific polygon. The code below uses a vector of ConstraintGraph objects (polygons in our case) and a point seedPoint near the lower left corner of the below image. It grows a zone from this seed point. The edges of the ConstraintGraph2 objects in vCG (in our case the two polygon circles) act as fence which stops the growing process.

vector<ConstraintGraph2*> vCG;
vCG.push_back(pCG0);
vCG.push_back(pCG1);
Point2 seedPoint(5.0,5.0); // Point near the lower left corner
Zone2* pZoneGrow(dt.createZone(vCG,ZL_GROW,seedPoint));
pZoneGrow->show("example4_zoneGrow.ps",true,true);

The global zone

The global zone is a zone consisting of all existing triangles.

Zone2* pZoneGlobal(dt.createZone(NULL,ZL_GLOBAL));
pZoneGlobal->show("example4_zoneGlobal.ps",true,true);

Zone creation from arbitrary triangles

A zone can be created from an arbitrary set of triangles. This set does not need to be connected. The example code below first fetches all triangles from the triangulation. Then it chooses only half of them to create a zone.

// + Zone defined by specific triangles
vector<Triangle2*> vT;
dt.getTrianglePointers(vT);
vT.resize(vT.size()/2);
Zone2* pZoneRandomTriangles(dt.createZone(vT));
pZoneRandomTriangles->show("example4_zoneFromTriangles.ps",true,true);

This article covered creation of zones. The next post Zone Operations shows how the union, the intersection, the difference and symmetric difference of two zones can be computed.