Three Easy Iterators: Edges, Vertices, and Triangles

Introduction

A Delaunay triangulation consists of three basic elements: edges, vertices, and triangles. When an application uses the Tinfour software library to create a Delaunay triangulation, Tinfour provides three simple iterators for looping through each of these kinds of elements.

The Tinfour iterators are easy to use and efficient to operate. In this article I will look at each type of iterator and offer some hints on using them effectively. To begin, let's take a look at the code snippet below. Recall that the abbreviation TIN, for Triangulated Irregular Network, is often used to refer to Delaunay triangulations. The Tinfour IncrementalTin class in this example produces TINs from a set of unstructured input vertices supplied by an application.

	import java.util.List;
	import org.tinfour.common.IQuadEdge;
	import org.tinfour.common.SimpleTriangle;
	import org.tinfour.common.Vertex;
	import org.tinfour.standard.IncrementalTin;

	List<Vertex> inputList = // list of vertices supplied by application

	IncrementalTin tin = new IncrementalTin(1.0);
	tin.add(inputList, null);

	int nEdges = 0;
	for (IQuadEdge edge : tin.edges()) {
	  nEdges++;
	}

	int nVertices = 0;
	for (Vertex vertex : tin.vertices()) {
	  nVertices++;
	}

	int nTriangles = 0;
	for (SimpleTriangle triangle : tin.triangles()) {
	  nTriangles++;
	}

As you can see, the example code uses the iterators to count how many of each type of object is found in the tin. We will review each of them in turn.

The Edge Iterator

Many developers assume that Tinfour uses the triangle as its the fundamental data structure for building a Delaunay triangulation. This is not an unreasonable assumption. After all, the mathematical definition for a Delaunay is based on triangles. But for software purposes, it turns out that edge-based data structures are simpler than triangles and have advantages in terms of memory and computational processing. So the fundamental data structure used in a Tinfour triangulation is the edge.

Edge techniques are so useful when dealing with Tinfour triangulations that there is a whole wiki article devoted to them at Tutorial Using Edge Based Techniques, Part I. But for our purposes, let's stick to a simple example that uses the edge iterator as a way of computing the average distance between vertices in the input-vertex list.

	int nSum=0;
	double sSum=0;
	for (IQuadEdge edge : tin.edges()) {
	  nSum++;
	  sSum += edge.getLength();
	}
	System.out.print("(Average distance between vertices: " + (sSum / nSum));

Some of the edge objects used internally by the Tinfour API have special properties that make them unsuitable for geometry-based computations such as the distance calculation shown above. Fortunately, the edges iterator handles these so-called "ghost" edges internally and does not expose them to application code.

The Vertex Iterator

The code example at the start of this article used a set of input vertices supplied by an application. For now, we don't have to worry about how that list of vertices got populated. We just assume that it did. However, at some point, we might want to get a list of vertices back from the IncrementalTin instance. The following example shows one way to do that:

	List<Vertex>outputList = new ArrayList<>();
	for(Vertex vertex: tin.vertices()){
	  outputList.add(vertex);
	}

To conserve memory, Tinfour does not maintain an actual list of vertices inside its IncrementalTin instance. Instead, the iterator obtains a set of vertices using edge-traversal techniques. The details of this operation are hidden inside the iterator. But there are two important things to keep in mind about this approach

1. The order of the vertices in the output list will usually not be the same as the order of vertices in the input.
2. The output list may include synthetic vertices and may hide some of the vertices from the original input.

When an input vertex set includes clusters of vertices that are too close together, it sometimes stores them in synthetic vertices called the "VertexMergerGroup". When that happens, the grouped objects will be presented by the iterator rather than the source vertices. If you want, the VertexMergerGroup does provide an API that lets you obtain the original inputs.

	for(Vertex vertex: tin.vertices()){
	   if(vertex instanceof VertexMergerGroup){
		VertexMergerGroup g = (VertexMergerGroup)vertex;
		for(Vertex v: g.getVertices()){
		  outputList.add(v);
		}
	   }else{
	        outputList.add(vertex);
	   }
	}

The Triangle Iterator

The Tinfour treatment of a Delaunay triangulation does not actually include any instances of Java objects that directly represent triangles. When an application uses the triangles iterator to obtain triangles, they are constructed dynamically by the API. A new object of type SimpleTriangle is constructed with each loop of the iterator and passed to the calling application. Here's an example using the triangle iterator to compute the overall area of the Delaunay triangulation:

	double aSum = 0;
	for(SimpleTriangle triangle: tin.triangles()){
	  aSum+=triangle.getArea();
	}
	System.out.println("The overall area covered by the triangulation is "+aSum);

SimpleTriangles depend on the IncrementalTin instance and become invalid if the associated triangulation is modified through the addition or removal of vertices. They also require about 36 bytes of storage. Since a sufficiently large Delaunay triangulation produces roughly twice as many triangles as the number of input vertices, there may be a significant memory cost to preserving a set of simple triangles in a Java collection object such as an ArrayList or HashMap.

Conclusion

One of the overall goals of the Tinfour project was to create an API that was straightforward and intuitive to use. The three easy iterators are a particularly successful example of of that goal. I hope you find that using them streamlines your coding and expedites you application's processing.