Access Triangulation Elements – Example2

Development is so much easier when you can visualize geometric situations. Lern how to draw geometric primitives using Fade’s Postscript writer class Visualizer2. The present Example2 will go over a triangulation and access specific elements like triangles, their neighbors, opposite points or Voronoi cells and draw them. You can find the source code in examples_2D/example2.cpp.

Lern to draw postscript graphics

Using the Visualizer2 class is very easy, see the code below: It demonstrates the different ways to use predefined or custom colors. Then it creates a Visualizer2 and uses Visualizer2::addObject(..) to add labels, points, segments and circles. When the drawing is complete it calls Visualizer2::writeFile() to write the file to disk.

C++ Postscript graphic with Fade2D

Postscript output

// *** COLORS ***
// Define color red by r,g,b values, linewidth and bFill
Color cRed(1,0,0,0.001,false);
// Or use a color name with defaults (linewidth=0.001, 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 are added at its endpoints.
Color cGreenBolt(CGREEN,1.0,false);
Color cGreenFill(CGREEN,.001f,true);

// Postscript writer
Visualizer2 vis("");

// Create a label and add it to the Visualizer
Label headLabel(Point2(10,80), // Position
                "This is the Fade2D\nPostscript Visualizer",
                false, // Don't write an x-mark
                40);   // 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,65);
	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
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,0),"Segment in cGreen",false,11);
vis.addObject(lab0,cBlue); // Add the label

Label lab1(Point2(20,10),"Segment in cGreenFill",false,11);
vis.addObject(lab1,cBlue); // Add the label

Label lab2(Point2(20,20),"Segment in cGreenBolt",false,11);
vis.addObject(lab2,cBlue); // Add the label

// Draw 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.

That’s it. Under Windows you can use Evince, GSView or some other software to view Postscript files. GV, Evince and many others exist for Linux and for a quick atempt you can even try one of the many web postscript viewers that exist online.

Create points and set an index

Let’s continue creating a few input points for a triangulation. Then carry out an optional step: Points have a field to store an arbitrary integer number. You can use this field freely, for example to index an entry in an array of your program’s data structures. The related methods are:

  • void Point2::setCustomIndex(int idx)
  • int Point2::getCustomIndex()

You can use this feature but you do not need to.

int example2_main()
	std::vector<Point2> vInputPoints;

	int someCustomIndex(77); // 77 is just an arbitrary number
	for(size_t i=0;i<vInputPoints.size();++i)

Triangulate the points

There are two basic insert methods. You can insert all points at once (which is faster) or you can insert them one-by-one which makes sense when not all points are available at the beginning.

Insert all points at once

Internally Fade keeps copies of the input points and returns their pointers in the same order. Duplicate input points are automatically detected and in such cases only one Point2 is created internally while its pointer is returned multiple times, namely at all positions of the duplicate input point. This way the number and order of the returned pointers does always correspond to the input points.

	Fade_2D dt; 
	std::vector<Point2*> vDelaunayVertexPointers; 

Insert the points one-by-one

This method inserts one point at a time. It returns a Point2 pointer that can be stored for later use. When a duplicate input point is inserted then a pointer to the already existing vertex is returned.

	for(std::vector<Point2>::const_iterator p_it=vInputPoints.begin();
		Point2* pDelaunayVertex=dt.insert(*p_it); 

Draw the points and triangles

You know already how to draw Postscript files. Now see how to access elements of a triangulation. The following code gets the points of a triangulation and draws them along with the previously set custom indices (77, 78, 79, …). Then it adds the triangles to the Visualizer.

void accessAndDraw(Fade_2D& dt)
	Visualizer2 vis("");

	// Some colors.
	Color cBlack(CBLACK);
	Color cBlue(CBLUE);
	Color cGreen(CGREEN);
	Color cRed(CRED);

	// 1) Get the points of the triangulation
	std::vector<Point2*> vAllPoints;

	// 2) Draw the points together with their (optional) custom index
	for(std::vector<Point2*>::iterator it(vAllPoints.begin());it!=vAllPoints.end();++it)
		Point2* currentPoint(*it);
		int customIndex(currentPoint->getCustomIndex());
		std::string customIndexString(toString(customIndex));

	// 3) Get and draw the triangles
	std::vector<Triangle2*> vAllDelaunayTriangles;
	for(std::vector<Triangle2*>::iterator it=vAllDelaunayTriangles.begin();it!=vAllDelaunayTriangles.end();++it)
		Triangle2* pT(*it);
		vis.addObject(*pT,cBlack); // Add the triangle

		// An alternative method (just to show how to access the vertices) would be:
		//Point2* p0=pT->getCorner(0);
		//Point2* p1=pT->getCorner(1);
		//Point2* p2=pT->getCorner(2);

Visualizer2 stores all added elements but the Postscript file is not written until the Visualizer2::writeFile() method is called. Below we will add more geometric objects before we call writeFile().

Access specific elements (Corners and Neighbor Triangles)

The following code snippet chooses a triangle pT and fills it with color CPALEGREEN. Then it demonstrates how the corners of pT can be accessed through the intra-triangle-indices {0,1,2} of pT. Intra-triangle-indices are always counterclockwise (CCW) oriented.

Each triangle has three neighbor triangles (or NULL pointers!) at its edges. These are also accessed through the the intra-triangle-indices: pT->getOppositeTriangle(idx) returns the neighbor triangles opposite to the vertex at idx: For idx=0 this is the neighbor triangle at the edge (1,2), for idx=1 at the edge (2,0) and for idx=2 at the edge (0,1).

Access Elements of a Delaunay Triangulation

Triangle pT, the IntraTriangleIndices {0,1,2} and the neighbor triangles

	// 4) Choose some triangle and fill it green
	Triangle2* pT(vAllDelaunayTriangles[0]);
	Color cGreenFill(CPALEGREEN,0.001f,true);

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

	// Each triangle has three neighbor triangles (or NULL pointers at
	// the the outer border). They are accessed through the described
	// 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(),"This is pT",true,12);
	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("This is\npT->getOppositeTriangle("+toString(intraTriangleIndex)+")");
		Label neigLabel(barycenter,text,true,12);

	// Write the postscript file to disk

Draw the dual Voronoi diagram

The Voronoi diagram is the dual graph of the Delaunay triangulation. The below function getVoronoiCell(..) uses a TriangleAroundVertexIterator to visit all triangles around a certain vertex pVtx and calls the method Triangle2::getDual() to compute the circumcenters of these triangles which are the vertices of the Voronoi cell around pVtx. The function returns false when the Voronoi cell of pVtx is infinite.

bool getVoronoiCell(Point2* pVtx,vector<Point2>& vVoronoiVerticesOut)
	TriangleAroundVertexIterator start_it(pVtx);
	TriangleAroundVertexIterator end_it=start_it;
		if(*start_it==NULL) // Infinite cell
			return false;
	} while(++start_it!=end_it);
	return true;

Draw the Voronoi diagram

The first loop in the following function voronoiDraw(..) uses the above getVoronoiCell(..) function to draw the finite Voronoi cells in red. This example contains only one finite Voronoi cell, the other ones are infinite and ignored. The second loop iterates over all triangles and draws their circumcircles (whose circumcenters are just the Vertices of the finite part of the Voronoi diagram).

Finite Voronoi Cells in the Delaunay Triangulation

Finite Voronoi Cells in the Delaunay Triangulation

void voronoiDraw(Fade_2D& dt)
	// Drawing a triangulation is a frequent task. Therefore a quick
	// method to draw the triangles exists:
	Visualizer2 vis("");;

	// For all vertices of the triangulation: Draw the finite Voronoi
	// cells. In the present example only one cell is finite.
	Color cRed(CRED,1,true);
	std::vector<Point2*> vAllPoints;
	for(std::vector<Point2*>::iterator it( vAllPoints.begin());it!=vAllPoints.end();++it)
		Point2* pVtx(*it);
		vector<Point2> vVoronoiVertices;
		bool bFiniteCell(getVoronoiCell(pVtx,vVoronoiVertices));
			for(size_t i=0;i<vVoronoiVertices.size();++i)
				Point2& p0(vVoronoiVertices[i]);
				Point2& p1(vVoronoiVertices[(i+1)%vVoronoiVertices.size()]);
				Segment2 seg(p0,p1);

	// Draw the circumcircles of the triangles
	Color cGreen(CGREEN);
	vector<Triangle2*> vAllT;
	for(vector<Triangle2*>::iterator it(vAllT.begin());it!=vAllT.end();++it)
		Triangle2* pT(*it);
		Point2 circumCenter(pT->getDual().first);
		Point2* pCorner0(pT->getCorner(0));
		double sqRadius=sqDistance2D(circumCenter,*pCorner0);
		Circle2 circ(circumCenter,sqRadius);

	// Finally, write the postscript file to disk
When you adapt the code above please be aware that only finite Voronoi cells can be drawn this way. Also keep in mind that the Voronoi diagram is the dual graph of the Delaunay Triangulation but not the dual graph of a Constrained Delaunay Triangulation (the cells would selfintersect).

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

Spread the word. Share this post!

Leave A Reply

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


By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.