This is the right article if you want to triangulate a polygon. The area inside a polygon is a Zone. Zones are among the most powerful concepts in Fade. You can combine Zones through the boolean set operations union, difference, symmetric difference and intersection. This is also known as Polygon Clipping. You can create a quality mesh inside a Zone or simply use it to extract its triangles conventiently. There are several ways to define a Zone:

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

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

Preparing two initial Polygons

Two polygons (ConstraintGraph2 objects) are made, then applyConstraintsAndZones() is called and the triangulation is drawn.

	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 and insert two constraint graphs
	std::vector<Point2> vConstraintPoints;
	vConstraintPoints.push_back(Point2(80,0));
	vConstraintPoints.push_back(Point2(49.8,62.5));
	vConstraintPoints.push_back(Point2(-17.8,78));
	vConstraintPoints.push_back(Point2(-72,34.7));
	vConstraintPoints.push_back(Point2(-72,-34.7));
	vConstraintPoints.push_back(Point2(-17.8,-78));
	vConstraintPoints.push_back(Point2(49.8,-62.5));

	std::vector<Segment2> vSegments1;
	std::vector<Segment2> vSegments2;
	
	for(size_t i=0;i<vConstraintPoints.size();++i) 
	{ 
		Point2& p0(vConstraintPoints[i]); 
		Point2& p1(vConstraintPoints[(i+1)%vConstraintPoints.size()]); 

		vSegments1.push_back(Segment2(p0,p1)); 
		Point2 p0a(p0.x(),p0.y()+170); 
		Point2 p1a(p1.x(),p1.y()+170); 
		vSegments2.push_back(Segment2(p0a,p1a)); 
	} 
	ConstraintGraph2* pCG1(NULL); 
	ConstraintGraph2* pCG2(NULL); 
	pCG1=dt.createConstraint(vSegments1,CIS_CONSTRAINED_DELAUNAY); 
	pCG2=dt.createConstraint(vSegments2,CIS_CONSTRAINED_DELAUNAY); 

	// 3) Apply and show the triangulation and constraints 
	dt.applyConstraintsAndZones(); 
	dt.show("example4_constraints.ps"); 

	// Verify that the ConstraintGraph2 objects pCG1 and pCG2 are closed if(!pCG1->isPolygon() || !pCG2->isPolygon() )
	{
		cout<<"pCG1 and pCG2 must be closed polygons"<<endl;
		return 1;
	}

Two polygons in a triangulation

Creating an inside and outside zone

ConstraintGraph pCG1 is the lower polygon in the above image. The two code lines below create one zone inside this circle and one zone outside.

	Zone2* pZoneInside(dt.createZone(pCG1,ZL_INSIDE));
	Zone2* pZoneOutside(dt.createZone(pCG1,ZL_OUTSIDE));

Inside Zone

Outside Zone

Zone growing from a seed point

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

	vector<ConstraintGraph2*> vCG;
	vCG.push_back(pCG1);
	vCG.push_back(pCG2);
	Point2 seedPoint(-99,-99); // near the lower left corner
	Zone2* pZoneGrow(dt.createZone(vCG,ZL_GROW,seedPoint));

Zone growing from a seed point

The global zone

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

	Zone2* pZoneGlobal(dt.createZone(NULL,ZL_GLOBAL));

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 a random sample of them and uses it to create a zone.

	vector<Triangle2*> vT;
	dt.getTrianglePointers(vT);
	random_shuffle(vT.begin(),vT.end());
	vT.resize(vT.size()/2);
	Zone2* pZoneRandomTriangles(dt.createZone(vT));

A Zone defined by triangles

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.