Example2 – Traversing

Example2 – Traversing

Lern how to access specific elements of your triangulation like triangles, their neighbors, opposite points and so on. During development it is extremely helpful to visualize geometric situations. In this example we will go over a triangulation, retrieve its elements and draw them.

Create input points and set an index

We start creating a few input points. Then we carry out an optional step: Points can store an arbitrary integer number. This number can for example be used to index an array in your own program (to associate points of Fade with your own data structures), or you may want to use this number to encode properties like colors. You can freely 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)

Inserting 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.

Insert all points at once

Internally Fade creates copies of the input points and returns Point2 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 insert method inserts one point at a time. It returns a Point2 pointer that can be stored for later use. Duplicte input points are automatically detected and a pointer to the existing vertex is returned in such a case.

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

Retrieve elements and visualize them

The Visualizer2 class is an easy to use postscript writer. Under Windows you can use Evince, GSView or some other product to view Postscript files. GV, Evince and many others exist under Linux. For a quick atempt you can also try one of the many web postscript viewers that exist online.

Draw the points

The code below creates a postscript writer, fetches all points from the triangulation and draws them. Then the previously defined custom indices are retrieved and drawn as labels.

	// Postscript writer
	Visualizer2 vis("example2a.ps");

	// Define some colors. The parameters are (red,green,blue,linewidth)
	Color colorBlack(0.0,0.0,0.0,0.01);
	Color colorBlue(0.0,0.0,1.0,0.01);
	Color colorGreen(0.0,1.0,0.0,0.01);
	Color colorRed(1.0,0.0,0.0,0.01);

	// 1) Retrieve the points from the triangulation
	std::vector<Point2*> vAllPoints;

	// 2) Draw the points together with the initially set custom indices
	for(std::vector<Point2*>::iterator it(vAllPoints.begin());
		// Visualize the point
		Point2* currentPoint(*it);

		// Write the custom index as label
		int customIndex=currentPoint->getCustomIndex();
		std::string customIndexString(toString(customIndex));

Note: The Visualizer2 remembers all added elements but the postscript file is not written until you call its writeFile() method.

Draw the triangles

We fetch and draw the triangles. Additionally the circumcircle of one triangle is drawn.

	std::vector<Triangle2*> vAllDelaunayTriangles;
	for(vector<Triangle2*>::iterator it=vAllDelaunayTriangles.begin();
		Triangle2* pT(*it);

	// Show the circumcircle
	Triangle2* pT(vAllDelaunayTriangles[0]);
	Point2 circumCenter(pT->getDual().first);
	Point2* pCorner0(pT->getCorner(0));
	double sqRadius=sqDistance2D(circumCenter,*pCorner0);
	Circle2 c(circumCenter,sqRadius);

Visit incident triangles of a point to draw its Voronoi cell

A Delaunay triangulation with one Voronoi cell

A Delaunay triangulation with one Voronoi cell

We draw the Voronoi cell of the first inserted vertex (the one with custom index 77) like shown above. To this end we use a TriangleAroundVertexIterator to visit all incident triangles of a point. Then we compute their dual Voronoi vertices. When you adapt the code below please keep in mind that only finite Voronoi cells can be drawn this way.

	Point2* p(vDelaunayVertexPointers[0]);
	std::vector<Point2> vVoronoi;
	TriangleAroundVertexIterator start_it(p);
	TriangleAroundVertexIterator end_it=start_it;
		if(*start_it==NULL) // Infinite cell
			// An infinite cell can't be drawn this way, stop
	} while(++start_it!=end_it);

	//    b) Draw the Voronoi cell of p
	for(unsigned i=0;i<vVoronoi.size();++i)
		unsigned j=(i+1)%vVoronoi.size();
		Segment2 seg(vVoronoi[i],vVoronoi[j]);

	// Finally, write the postscript file to disk!

More access methods: Neighbors and opposite triangles

Drawing the whole triangulation is a frequent task. The automatic method Fade_2D::show(..) is provided for your convenience. It takes a pointer to a Visualizer2 object and adds the existing triangles. Subsequently additional geometric objects can be added and at the end the visualization must be finalized using the Visualizer2::writeFile() method.

The code below retrieves one (random) incident triangle pT of the vertex pVtx. Then it uses the intra-triangle-indices {0,1,2} to access the corners of pT and to write these indices as labels besides the corners. Afterwards it uses the same intra-triangle-indices in order to fetch and visualize the neighbor triangles of pT.

	Visualizer2 vis("example2b.ps");

	// Get all points
	std::vector<Point2*> vAllPoints;

	// Select one point
	Point2* pVtx(vAllPoints[0]);

	// Get one of the incident triangles of pVtx (a random one):
	Triangle2* pT(pVtx->getIncidentTriangle());

	// The corners of pT can be accessed through the so called intra-
	// triangle-indices 0,1,2. They are always oriented in counter-
	// clockwise order (CCW), let's write the intra-triangle-indices
	// besides their corners (blue):
	for(int intraTriangleIndex=0;intraTriangleIndex<3;
		Point2* pCorner=pT->getCorner(intraTriangleIndex);
		std::string text("idx="+toString(intraTriangleIndex));

	// Each triangle knows its up to three neighbor triangles and 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. In other words, pT->getOppositeTriangle(i) returns
	// a neighbor triangle of pT which is disjoint from pT->getCorner(i)
	// Let's visualize that for clearness (red):
	Label label_pT(pT->getBarycenter(),"This is pT",false);
	for(int intraTriangleIndex=0;intraTriangleIndex<3;
		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("+\
		Label label_pNeigT(barycenter,text,false);

	// Finally, write the postscript file to disk!

Intra-triangle-indices of one triangle and its neighbors.

Intra-triangle-indices of one triangle and its neighbors.

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.

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.