The Tinfour software package includes a number of built-in utilities for processing collections of unstructured data. But sooner or later, you may find that your own applications have unique requirements and that you need to write custom implementations. To get you started in that effort, this tutorial introduces techniques for accessing the data elements constructed by the Tinfour package when it builds a Triangulated Irregular Network (TIN).

In particular, this tutorial focuses on edge iterators and edge-indexing schemes. Edge iterators allow a Java application to loop through the collection of edges that define a TIN. Edge indexing provides a way for applications to keep track of which edges it processes.

And, finally, if you would like more information about any of the ideas or software elements described in this tutorial, you may find more detail in the document Data Elements and Algorithms for the Tinfour Libary. Also, the Tinfour API documentation is available at Tinfour API.

The picture below show a TIN that was constructed from a small set of vertices using the Tinfour software. The positions of the vertices are arbitrary. The labels that attach to the vertices are arbitrary as well. They are intended to illustrate the ideas in this discussion, but do not represent any actual data. In fact, the reason for the choice of city names as labels was to avoid confusing them with mathematical variables or software elements. The use of city names, something which is clearly outside the scope of the Tinfour implementation, also emphasizes the idea that Tinfour treats vertices as belonging strictly to the domain of the application code. Tinfour does not adjust or otherwise modify the content of the vertex objects.

On the other hand, the creation and management of edge structures belongs squarely within the domain of the Tinfour software. Edges are constructed based on a set of formally defined rules (most notably, the Delaunay criterion) and software considerations. The triangulation created by Tinfour is a consequence of the geometry of the input points (the Cartesian X and Y coordinates of the vertices). But, once established, the edges should not be modified by the application code.

In Tinfour, edges are represented using a pair of tightly coupled Java objects, one for each direction of traversal. So if an edge connects Vertex A to Vertex B, it will consist of an object linking A to B and a dual object that links B to A. In the diagram, the arrows show the direction of traversal. If you would like, you can view a Tinfour edge object as actually being one side of the true edge that connects two vertices. For that perspective, the dual is just the opposite side of the edge object.

If you follow the direction of the arrows in the diagram above, you can see that the triangles are all specified so that the interior "sides" of the edges are traversed in a counterclockwise order. By design, Tinfour always constructs edges so that the resulting triangles are placed to the left side of the edge. The counterclockwise ordering is a natural consequence of this specification.

The numbers shown in the diagram are the "edge index" values associated with each of these edge components. A Tinfour edge always has two edge-index values, one for each direction of traversal (one for each side of the edge). The index values are assigned in sequence when the edge object is constructed. The lower of the two index values is always an even number. The higher value of the pair is always assigned an index one greater than its dual.

The index values are a key component of the Tinfour memory management scheme and are designed so that they can also be utilized by applications that use the Tinfour package. The are assigned as edges are built. And, as long as the application doesn't do something to change the structure of the TIN (such as adding or removing vertices), they will not change. Thus the edge indices are stable and can be used safely by the application.

Because the index values uniquely identify each edge component, they can be useful for any application code that needs to navigate the network keep track of which edges it has traversed or otherwise processed. We'll look at the use of the edge index in more detail in the examples below.

Before beginning the examples, though, I need to say something about the way edges are accessed by Tinfour-based applications. In Tinfour, edges are represented using IQuadEdge, a Java interface which is implemented by all of the Tinfour edge-related classes. Tinfour edge elements are based on the "quad edge" structure that was popularized by Guibas and Stolfi in 1985. The quad edge structure is used in many computational geometry implementations in addition to Tinfour. The IQuadEdge interface defines several methods that are inspired by the quad-edge definition as well as providing elements that are unique to Tinfour. The ones of primary concern for this discussion are given in the table below.

In the Java programming language, an Iterator is an interface that permits a software module to loop through the content of a collection of data objects. Tinfour implements two main edge-related iterators:

1. The edge iterator permits software to loop through the entire collection of edges one-at-a-time.
2. The "pinwheel" iterator permits software to loop through all edges that connect to a specific vertex.

Let's look at an example code snippet showing the use of the edge iterator. We start with a list of vertices that are pre-populated by the application code, use the IncrementalTin class to build a TIN object, and then loop through the edges that were constructed to represent that TIN. The edge iterator can be accessed using Java's "enhanced loop" construct by making a call to tin.edges().

	List<Vertex> vertexList; // pre-populated with arbitary vertices
	IncrementalTin tin = new IncrementalTin();
	tin.add(vertexList, null);

	int nEdges = 0;
	for(IQuadEdge edge: tin.edges()) {  // main edge iterator loop
		System.out.format("Edge %4d %n", edge.getIndex()); 
		nEdges++;
	}
	System.out.println("The number of edges in the TIN is "+nEdges);

The code above works just fine, but it only tells half the story. If you were to run it, the result would be a list of even numbers. Recall that a Tinfour edge is actually a pair of objects. As used in the code above, the loop only exposes one of the objects in the pair. So only the indices for the even-numbered side of the edges are output. If you wished to print the indices for both sides of the edge, you could do so by accessing the dual

	for(IQuadEdge edge: tin.edges()) {  // main edge iterator loop
		IQuadEdge dual = edge.getDual();
		System.out.format("Edge %4d %4d %n", edge.getIndex(), dual.getIndex()); 
	}

The examples above use the IQuadEdge that was introduced above. Each side of the edge-object-pair consists of an object that implements IQuadEdge. These implementations are symmetrical and transitive. So, if you get the dual of an edge, then the dual of the dual is the original edge.

Sometimes, an application needs to be able to compare one vertex to all the other vertices that connect to it. For example, if an application were using Tinfour to process temperature data from a set of weather stations, the user might want to know which readings represented local maximums. For that purpose, the pinwheel iterator would provide a convenient way for the loop through the neighbors of each vertex.

In the diagram above, the labeled arrows shows both the index and direction of traversal for the "sides" of the edges that made up the mesh. Now imagine a case where an application needs to loop through all the edges that link to the vertex labeled "Boston". If it had some mechanism for finding just one of the edges (perhaps by using an edge iterator), it could loop through all the others using the pinwheel iterator.

In the diagram, edge zero links Vertex Boston to Vertex Prague. The IQuadEdge interface defines a method called "pinwheel()" that constructs an instance of a pinwheel iterator. That iterator lets a Java application loop through each adjacent vertex in a wheel-like pattern.

The figure shown below shows just the subsection of the larger triangulated mesh that would be relevant to a pinwheel iterator for Vertex Boston, starting at edge zero. Most of the directional arrows from the diagram above have been removed from the figure. It shows only those arrows that correspond to the IQuadEdge objects produced by the pinwheel iterator. The circular loop shows the direction of traversal. Thus, if we take the perspective of viewing the operation as following a wheel-like patterm then Boston is the hub. And each connecting edge can be viewed as spokes.

Referring to the figure above, the pinwheel iterator would produce edges as follows:

1. Edge 0 from Boston to Prague
2. Edge 5 from Boston to Vancouver
3. Edge 6 from Boston to Columbus
4. Edge 15 from Boston to Rio de Janeiro

Now let's return to our example of an application that searches for local maximum values. It we stored data for temperature values as the z coordinate of a set of vertices in a collection of weather observations, the following loop would detect local maxima:

for (IQuadEdge edge : tin.edges()) {
  Vertex hub = edge.getA(); // the initial vertex of edge e
  boolean localMaximum = true; // start optimistic
  for (IQuadEdge p : edge.pinwheel()) {
    // the initial vertex of edge p will be the hub vertex
    // the second vertex will be the neighbor.
    // it may be null, so test for that first
    Vertex neighbor = p.getB();
    if (neighbor == null || neighbor.getZ() >= hub.getZ()) {
         // the hub is not a local maximum.  
         // set the flag to false and break the loop.
         localMaximum = false;
         break;  // break the pinwheel loop
    }
  }
  if(localMaximum){
    System.out.println("Local Maximum "+hub.getZ());
  }
}

Note that the code implements logic to check to see if the neighbor vertex is null. Null neighbors can happen when the hub vertex lies on the perimeter of the TIN. Tinfour uses special "ghost" edges to maintain the logical consistency of the construction. The main edge iterator filters these out, but the pinwheel iterator exposes them. When a neighbor is null, it signals the code that the hub vertex is on the perimeter. And since perimeter vertices are not surrounded by neighbors on all sides, they don't really qualify as local maximums.

Now that we've covered edge iterators and the Tinfour edge-indexing scheme, we're ready for a fully realized example. The IncrementalTin class implements a method called getVertices() that extracts the vertices from the TIN. Let's see how that method could be written.

First, we'll start with a fragment that produces a wrong result:

ArrayList<Vertex> vertexList = new ArrayList<>();
for(IQuadEdge edge: tin.edges()){
  vertexList.add(edge.getA());
  vertexList.add(edge.getB());
}

The resulting list will certainly contain all the vertices in the TIN. Unfortunately, many of them will appear in the list more than once. In the code above, there is no mechanism for screening out duplicates. As a brute-force solution, we could do so by using the contains() method for the Java ArrayList() to check to see if list contains a vertex before adding it:

for (IQuadEdge edge : tin.edges()) {
  if (!vertexList.contains(edge.getA())) {
    vertexList.add(edge.getA());
  }
  if (!vertexList.contains(edge.getB())) {
    vertexList.add(edge.getB());
  }
}

The problem with this approach is that the ArrayList contains() method searches a list in a linear fashion. For a TIN containing N vertices, the number of operations to perform these repeated linear searches is proportional to N-squared. So as the vertex count becomes large, the operation count required for the contains() method becomes very large. Consequently, the overall run time for the loop will increase until it exceeds the limits of available processing time or, at least, the limits of our patience.

The following code sample avoids that overhead by using a boolean array to keep track of which edges are "visited", and only adding the vertices for edges the first time they are encountered. It accomplishes that by using the edge index as the index into the visited array.

int maxEdgeIndex = tin.getMaximumEdgeAllocationIndex();
boolean[] visited = new boolean[maxEdgeIndex + 1];
for (IQuadEdge edge : tin.edges()) {
  if (!visited[edge.getIndex()]) {
    Vertex hub = edge.getA();
    vertexList.add(hub);
    for (IQuadEdge p : edge.pinwheel()) {
      visited[p.getIndex()] = true;
    }
  }
}

The getMaximumEdgeAllocationIndex() gets a value that is at least as large as the maximum index for all edges in the TIN. So the visited array will be large enough to hold any edge index that the code encounters. Using the array, each time a vertex is added to the list, all the edges that connect to it are marked as visited. Thus the vertex will only be added once.

Of course, the example above requires one last refinement. Referring to the diagram of the TIN that was given at the beginning of this tutorial, note that all the edges that start with Vertex Columbus have odd-numbered indices. Since the edge iterator only produces even-index edges, the example code will fail to process Vertex Columbus. So, to ensure that all vertices are added to the list, we add processing for the dual edge to the main loop:

int maxEdgeIndex = tin.getMaximumEdgeAllocationIndex();
boolean[] visited = new boolean[maxEdgeIndex + 1];
for (IQuadEdge edge : tin.edges()) {
  if (!visited[edge.getIndex()]) {
	Vertex hub = edge.getA();
	vertexList.add(hub);
	for (IQuadEdge p : edge.pinwheel()) {
	  visited[p.getIndex()] = true;
	}
  }
  
  IQuadEdge dual = edge.getDual();
  if (!visited[dual.getIndex()]) {
	Vertex hub = dual.getA();
	vertexList.add(hub);
	for (IQuadEdge p : dual.pinwheel()) {
	  visited[p.getIndex()] = true;
	}
  }
}

At first glance, the example of extracting vertices from a TIN may seem a bit contrived. After all, if the application code knows which vertices it stored in the TIN, why would it need to go through all that work to get them back out? The answer is that Tinfour implements special handling for cases where two or more input vertices are located at the same position. If, for example, your input vertex set included two vertices with identical (or nearly identical) x/y coordinates, Tinfour would combine them into a single synthetic vertex represented using a Tinfour class known as the VertexMergerGroup. The VertexMergerGroup is a container class that stores the input vertices that triggered its creation. The coincident vertices from the input set would not be stored directly in the TIN, but would be encapsulated in the VertexMergerGroup which would be referenced by the appropriate edge objects. So if your data included redundant or conflicting input vertices, you would find that the output vertex list from the loop above includes some merged group implementations but not your original vertices (at least not directly).

How many operations does it take to collect vertices using the alternate approach? A proof in graph theory shows that as the number of vertices in a Delaunay Triangulation approaches infinity (or, at least, approaches a comfortably large number), the average number of edges connecting to a vertex approaches six. Since the loop performs one pinwheel per vertex recognized, the number of pinwheels for a TIN containing N vertices is just N. How many times is the visited array accessed? Each pinwheel operation will produce an average of six edges and thus will set a value in the visited array six times. The outer edge iterator produces all edges in the TIN. On average, a Delaunay triangulation of sufficient size includes three times as many edges as vertices.
In each pass through the loop the code checks a value of the visited array once for each edge and once for each dual. Thus the average total operation count is

The techniques introduced in this tutorial will simplify the implementation of many applications that perform surveys across the collection of vertices and edges embedded in a TIN. The edge iterator allows the construction of loops that process the set of all edges in the TIN. The pinwheel iterator provides a simple way of performing operations that compare a vertex with its immediate neighbors.

I am still working on Part II of this tutorial. When it's ready, we will work through an example of a real-world data processing problem that detects anomalous values in a set of Earth-surface meteorological reports. Armed with the insights from this article and its sequel, you should find it much easier to apply Tinfour to your own applications.

Guibas, L., Stolfi, J (1985). "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams", ACM Transactions on Graphics, Vol. 4, No. 2, April 1985, p 74-123.