Categories
Fade2D Examples

Access Triangulation Elements and draw Postscript – Example2

Traversing a triangulation and its elements
Accessing triangulation elements

This article has two goals: First, it shows how you can access the elements of a triangulation. Second, it shows how you can draw them. Because development is much easier when you can visualize your work.

Preparing a triangulation

Let’s prepare and draw a simple triangulation for this demo:

int example2_main()
{
	std::cout<<"\nexample2: Access elements of a triangulation\n";
	// * 1 *   Create points on a circle
	std::vector<Point2> vPoints;
	int numPoints(6);
	double centerX(5),centerY(5),radiusX(5),radiusY(5);
	generateCircle( numPoints,centerX,centerY,radiusX,radiusY,vPoints);
	vPoints.push_back(Point2(centerX,centerY)); // Add the center point
  
	// * 2 *   Optional step: You can add custom indices to relate
	//         the points to your own data structures. But you do
	//         not need to use this feature.
	int myStartIndex(77); // An arbitrary value
	for(size_t i=0;i<vPoints.size();++i)
	{
		vPoints[i].setCustomIndex(myStartIndex++);
	}
  
	// * 3 *   Insert the vertices
	Fade_2D dt; // The Delaunay triangulation
	std::vector<Point2*> vVertexHandles; // Pointers to the vertices inside Fade
	dt.insert(vPoints,vVertexHandles); // Fastest method: insert all points at once
	// * 4 *   Draw the triangulation
	dt.show("triangulation.ps");
...
}
  1. In Step 1 we fill the vector vPoints with 6 points on a circle plus the center point. Hint: Fade provides generators for circles and for random points, segments, polygons and surfaces).
  2. Step 2 assigns indices to the points. These are thought to let you link Fade points with your own datastructures. This is of course completely optional.
  3. Step 3 inserts the points. Internally, Fade keeps a copy of the points and returns pointers to them (in the same order) in vVertexHandles. Inserting all points at once is most efficient. But there is also a method to insert the points one by one.
  4. The fourth step draws the triangulation using Fade_2D::show("triangulation.ps")
Triangulation of 7 points, created by example2_main()

Accessing Elements

Access to elements in a triangulation is often required. For example, you may want to access the neighboring triangles of a particular triangle. Or you may want to create a custom visualization instead of the ready-made visualization. So let’s discuss the below manualDraw() function: 

void manualDraw(Fade_2D& dt)
{
	// * 1 *   Create a postscript visualizer and define some colors
	Visualizer2 vis("manualDraw.ps");
	Color cBlack(CBLACK);
	Color cBlue(CBLUE);
	Color cRed(CRED);
	Color cPurple(CPURPLE);
	vis.addObject(Label(Point2(1.5,12.4),"BLACK: triangle edges",false,15),cBlack);
	vis.addObject(Label(Point2(1.5,11.6),"RED: neighbor-triangle labels",false,15),cRed);
	vis.addObject(Label(Point2(1.5,10.8),"BLUE: intra-triangle-indices",false,15),cBlue);
	vis.addObject(Label(Point2(1.5,10.0),"PURPLE: custom vertex indices",false,15),cPurple);
  
	// * 2 *   Get and draw the vertices with their custom index
	std::vector<Point2*> vAllPoints;
	dt.getVertexPointers(vAllPoints);
	std::cout<<"vAllPoints.size()="<<vAllPoints.size()<<std::endl;
	for(std::vector<Point2*>::iterator it(vAllPoints.begin());it!=vAllPoints.end();++it)
	{
		Point2* currentPoint(*it);
		int customIndex(currentPoint->getCustomIndex());
		std::string text(toString(customIndex));
		vis.addObject(Label(*currentPoint,text.c_str(),true,12),cPurple);
	}
	// * 3 *   Get and draw the triangles
	std::vector<Triangle2*> vAllDelaunayTriangles;
	dt.getTrianglePointers(vAllDelaunayTriangles);
	for(std::vector<Triangle2*>::iterator it=vAllDelaunayTriangles.begin();it!=vAllDelaunayTriangles.end();++it)
	{
		Triangle2* pT(*it);
		vis.addObject(*pT,cBlack);
	}
	// * 4 *   Choose one triangle and color it green
	Triangle2* pT(vAllDelaunayTriangles[0]);
	Color cGreenFill(CPALEGREEN,0.001f,true);
	vis.addObject(*pT,cGreenFill);
	// * 5 *   The corners of pT can be accessed through the so called intra-
	// triangle-indices 0,1,2. They are counterclockwise oriented (CCW).
	// Let's write intra-triangle-index labels beside the corners.
	for(int intraTriangleIndex=0;intraTriangleIndex<3;++intraTriangleIndex)
	{
		Point2* pCorner(pT->getCorner(intraTriangleIndex));
		std::string text("\nidx="+toString(intraTriangleIndex));
		vis.addObject(Label(*pCorner,text.c_str(),true,15),cBlue);
	}
	// * 6 *   Each triangle has three neighbor triangles (or NULL
	// pointers at border edges). They are accessed through the
	// intra-triangle-indices. The i'th opposite triangle of pT is
	// the one that is opposite to the i'th vertex. Let's draw that:
	Label label_pT(pT->getBarycenter()," pT",true,15);
	vis.addObject(label_pT,cBlue);
	for(int intraTriangleIndex=0;intraTriangleIndex<3;++intraTriangleIndex)
	{
		Triangle2* pNeigT(pT->getOppositeTriangle(intraTriangleIndex));
		if(pNeigT==NULL) continue; // No adjacent triangle at this edge
		// Compute the barycenter and write a label there
		Point2 barycenter(pNeigT->getBarycenter());
		std::string text(" =pT->getOppositeTriangle("+toString(intraTriangleIndex)+")");
		Label neigLabel(barycenter,text.c_str(),true,15);
		vis.addObject(neigLabel,cRed);
	}
	// Write the postscript file to disk
	vis.writeFile();
}
  1. Step 1 creates a Visualizer2 object with the postscript-filename “manualDraw.ps”. Next it defines a few colors and then it adds labels to the visualizer.
  2. The second step retrieves pointers to all triangulation vertices. It draws them along with the custom indices set before.
  3. The third step fetches all triangle pointers and then adds them them to the visualizer.
  4. Step 4 chooses an arbitrary triangle pT and fills it with green color
  5. Step 5 shows how to access the corners of pT through the so called intra-triangle-indices {0,1,2}. These are always counterclockwise. We write the intra-triangle-indices in blue color.
  6. Each triangle pT has three pointers to its neighboring triangles (or NULL in case of border edges): The i-th neighbor triangle is always the one opposite the vertex with intra-triangle-index i. Step 6 draws red labels at the barycenters of the neighbor triangles.
  7. The writeFile() method is called to finalize the postscript drawing.
Manual visualization created by manualDraw() of example2

More Visualization

It is unlikely that you will need it soon, but for completeness, the demo ex2_access_draw.cpp also includes the moreDraw() function, which demonstrates additional functions of the Visualizer2 class. It’s source code below is certainly self-explanatory.

Postscript demo made by the moreDraw() function
void moreDraw()
{
	// * 1 *   Defining color
	// Define red by values (red,green,blue,linewidth,bFill)
	Color cRed(1,0,0,0.001,false);
	// Or simply use a color name and the defaults linewidth=0.001 and bFill=false
	Color cBlue(CBLUE);
	Color cGreen(CGREEN);
	Color cPurple(CPURPLE);
	// Specify a bolt green color (linewidth=1.0) and another one with
	// bFill=true to fill the area of an object which is drawn using
	// that color. In case that a segment is drawn with bFill=true,
	// marks for its endpoints are added.
	Color cGreenBolt(CGREEN,1.0,false);
	Color cGreenFill(CGREEN,.001f,true);
	// Postscript writer
	Visualizer2 vis("moreDraw.ps");
	// Create a label and add it to the Visualizer
	Label headLabel(Point2(20,60),	// Position
					"This is the Fade2D\nPostscript Visualizer",
					false,			// Don't write an x-mark
					30);			// Font size
	vis.addObject(headLabel,cRed); 	// Add the label
	// Add a row of points
	for(int x=0;x<100;x+=5)
	{
		Point2 p(x,50);
		vis.addObject(p,cPurple); // Add the point
	}
	// Draw a segment with cGreen
	Point2 p0(0,0);
	Point2 p1(100,0);
	Segment2 seg0(p0,p1);
	vis.addObject(seg0,cGreen); // Add the segment
	// Draw a segment with cGreenFill (with marks at the endpoints)
	Point2 p2(0,10);
	Point2 p3(100,10);
	Segment2 seg1(p2,p3);
	vis.addObject(seg1,cGreenFill); // Add the segment
	// Draw a segment with cGreenBolt
	Point2 p4(0,20);
	Point2 p5(100,20);
	Segment2 seg2(p4,p5);
	vis.addObject(seg2,cGreenBolt); // Add the segment
	// Draw labels
	Label lab0(Point2(20,2),"Segment in cGreen",false,15);
	vis.addObject(lab0,cBlue); // Add the label
	Label lab1(Point2(20,12),"Segment in cGreenFill",false,15);
	vis.addObject(lab1,cBlue); // Add the label
	Label lab2(Point2(20,22),"Segment in cGreenBolt",false,15);
	vis.addObject(lab2,cBlue); // Add the label
	// Add three circles with radius=4 (squared radius 16)
	double sqRadius(4.0*4.0);
	Circle2 circ0(50,40,sqRadius);
	Circle2 circ1(60,40,sqRadius);
	Circle2 circ2(70,40,sqRadius);
	vis.addObject(circ0,cGreen);	// Add the circle
	vis.addObject(circ1,cGreenBolt);// Add the circle
	vis.addObject(circ2,cGreenFill);// Add the circle
	// The postscript file is only written when writeFile() is called.
	vis.writeFile();
}

This is all you need to know to traverse a Fade triangulation and to draw a postscript visualization of it. Make sure you understand this example, play around with the source code, adapt it and see what happens. Then proceed to Example3 – Constraint Edges which treats triangulations of segments.

2 replies on “Access Triangulation Elements and draw Postscript – Example2”

A triangulation can be iteratively created and modified i.e., triangles appear and disappear dynamically, thus there are no built-in indices for triangles. But you can create indices. Simply add this code at the end of exampes_2D/ex0_helloTriangulation.cpp:

// * 1 * Map triangles to indices
std::vector vT;
dt.getTrianglePointers(vT);
std::map < Triangle2*,int > mT2Idx;
int ctr(0);
for(Triangle2* pT:vT) mT2Idx[pT]=ctr++;
//
// * 2 * Fetch the indices as you need them
for(Triangle2* pT:vT)
{
int idx=mT2Idx[pT];
...
}

Leave a Reply

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