This is the right article if you want to triangulate a polygon. Zones are among the most powerful concepts in Fade. A zone defines an area in a (Constrained) Delaunay triangulation. Zones can be combined using boolean set operations such as union and difference, a quality mesh can be constructed inside a zone and the triangles of a zone can be extracted. Zones can be defined in several ways:

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

The code examples below demonstrate that.

Preparing the initial situation

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.