Categories
2D Delaunay Triangulation Examples in C++

Polygons and Zones – Example4

If you want to perform polygon triangulation or work with polygon clipping, you’re in the right place. In Fade, a Zone2 object defines a specific area within a triangulation. You can define a zone in the following ways:

  • The area inside or outside a polygon
  • A region obtained by growing from a seed point up to predefined boundaries
  • The entire triangulation (global zone)
  • Consisting of arbitrary triangles

It allows you to combine shapes using the Boolean set operations union, difference, symmetric difference, and intersection. The result is, once again, a Zone2 from which you can compute the area, extract boundaries, and individual triangles.

For a practical demonstration of this concept, refer to the code snippet below (located also in examples_2D/ex4_zones.cpp in the download package).

Preparing two initial polygons

Delaunay triangulation with two polygons (constraint edges)
Delaunay triangulation with two constraint graphs

This code snippet creates two polygons within a rectangular area, as depicted in the image above.

// * Step 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));

// * Step 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);

// * Step 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);
}

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

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

  • In Step 1, we insert four points into a new Fade_2D object.
  • Step 2 creates points on two circles (vCircle0,vCircle1)
  • In the third step, we create vectors of segments (vSegment0,vSegment1)
  • Afterward, we create the two ConstraintGraph2 objects, pCG0 and pCG1
  • Finally, in Step 5, we visualize the triangulation.

Creating zones inside and outside of polygons

The ConstraintGraph2 object pCG1 represents the left polygon circle in the image above. Now, let’s proceed to create a Zone2 inside this polygon and another one outside of it.

// + 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 inside a polygon
Zone inside the left polygon
Zone outside a polygon
Zone outside the left polygon

Growing a zone from a seed point

In addition to zones inside and outside polygons, zones can also expand from a specific seed point.

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 provided code utilizes a vector containing pCG0 and pCG1 (representing the two polygonal circles). It establishes a seed point near the lower-left corner of the image displayed below and proceeds to grow a Zone2 from this seed point. The edges of the ConstraintGraph2 objects act as limiting edges, effectively stopping the growing process.

Zone grown from a seed point until the constraint edges of the two polygons stop the growing process
Zone (yellow area) grown from a seed point. The constraint edges (red) act as a fence that stops the growing process

The global zone

A global zone consists of all existing triangles.

Zone2* pZoneGlobal(dt.createZone(NULL,ZL_GLOBAL));
pZoneGlobal->show("example4_zoneGlobal.ps",true,true);
Global zone consisting of all triangles
The global zone consist of all triangles

Zone creation from arbitrary triangles

You can also create a Zone2 from arbitrary triangles, whether connected or not. To illustrate this, the code below initially retrieves all triangles from the triangulation. It then selects only half of them to create a Zone2.

// + 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);
A Zone that has been created from a certain set of triangles.
A zone that consists just of a selected set of triangles

This article covered creation of zones while the next post Zone Operations computes the union, the intersection, the difference and symmetric difference of such zones.

Leave a Reply

Your email address will not be published. Required fields are marked *