One of the best things that happens to an open-source project is when a user contributes an idea that extends the software beyond its original concept. The TriangleCollector class is one of those contibutions. It was provided by a user who needed a convenient way to process the collection of triangles that comprises a Delaunay Triangulation. Since then, the TriangleCollector has become one of my favorite features in the Tinfour library. Not only does it provide a much needed capability to the library, but it is also elegant, efficient, and easy to use.

In this tutorial, I will introduce the TriangleCollector and offer a few suggestions on how to take advantage of its features.

The design of the Tinfour software library is strongly influenced by the need to process large data sets. Some of the geophysical data sets Tinfour supports can include multiple millions of sample points. To process such large collections of vertices, the Tinfour software needs to be both fast and conservative in its use of memory. Thus, the data objects created by Tinfour tend to be quite lean in their design.

This requirement to be sparing in use of memory leads to some counter-intuitive design choices. In particular, even though the basis of a Delaunay Triangulation is the triangle, the Tinfour structures do not incorporate any explict triangle objects into its design. The fundamental objects in a Tinfour Triangulated Irregular Network (TIN) are the vertex and the edge.

While this design approach leads to an efficient software implementation, the result isn't especially convenient for an application that needs to process the triangular elements that comprise the TIN. For example, in the Lake Volume Example, a series of triangular sections were used to compute the volume and surface area of a Lake Victoria (in Africa) based on bathymetry (depth-sounding) data. Since these triangular structures didn't explicitly exist in the Tinfour structure, they had to be computed "on the fly". The TriangleCollector provided a handy way of doing that.

Now let's look at a simple example of how to use the TriangleCollector.

The first step in using the TriangleCollector is to define a "triangle consumer". So we will start this example by describing what a consumer does.

In Java version 1.8, Oracle introduced the idea of a Java "Consumer". The Java Consumer interface provides an alternate way to implement a loop in an application. In a consumer loop, an implementation of the Consumer interface receives objects via the accept method. Control of the loop itself is handed over to an external code module. This approach is somewhat inside-out from the usual way of thinking of the flow-of-control through a block of code. Instead of writing code for a loop to invoke some logic, a developer writes some logic to be invoked by an external loop.

This description sounds rather more abstract than I prefer. The actual process is much easier to understand when you look at some code. First, let's look at the consumer itself.

import java.util.function.Consumer;
import org.tinfour.common.SimpleTriangle;

class TriangleConsumer implements Consumer<SimpleTriangle> {

	int nTriangles;
	double sumArea;

	@Override
	public void accept(SimpleTriangle t) {
	  nTriangles++;
	  sumArea += t.getArea();
	}
}

As you can see, there really isn't that much to it. The consumer implements the "accept" method that is specified by the Java Consumer interface. The accept method simply receives a object of type "SimpleTriangle" and does whatever processing is required for a particular application. In this case, it simply counts how many times it is called and computes a running sum of the area of each triangle in the associated TIN.

Earlier, I said that the Tinfour TIN classes do not include explicit instances of triangle objects. That's completely true. In this case, the instances of SimpleTriangle are constructed on-the-fly by Tinfour's internal processing. The consumer shown above will loop through each triangle in the Delaunay Triangulation.

Now let's look at the application code that invokes the consumer.

IncrementalTin tin = new IncrementalTin(1.0);
List<Vertex> vertexList = TestVertices.makeRandomVertices(100, 0);
tin.add(vertexList, null);

TriangleConsumer consumer = new TriangleConsumer();
TriangleCollector.visitSimpleTriangles(tin, consumer);

System.out.format("Number of triangles  %4d%n", consumer.nTriangles);
System.out.format("Total area:          %7.2f%n", consumer.sumArea);

For the example, I created a set of 100 vertices at random and used them to populate an instance of the IncrementalTin (which embodies a DelaunayTriangulation). I then constructed an instance of the TriangleConsumer class introduced above and passed it into the TriangleCollector.

The "visitSimpleTriangles" method loops through each triangle in the Tinfour TIN, constructs a SimpleTriangle object to pass into the TriangleConsumer's "accept" method, and then returns control to the main application code. At that point, the example prints the results:

    Number of triangles   186
    Total area:             0.92

The mathematician Boris Nikolaevich Delaunay, for whom the Delaunay Triangulation is named, demonstrated that for a Delaunay Triangulation containing sufficiently large number of vertices, N, the number of triangles in the triangulation is roughly 2N. 100 vertices isn't a particularly large number, but we can see here that the number of triangles does approach 2N. Just out of curiosity, I also tried running the example above with a larger number of vertices: 100000.

    Number of triangles  199968
    Total area:             1.00

As you can see, the ratio of vertices to triangles does indeed become closer to a factor of two as the number of vertices grows.

One thing that you don't see in the example code above is the complexity of the code needed to loop through the set of triangles that comprise the TIN. At the beginning of this wiki article, I described the TriangleCollector implementation as "elegant". Its ability to encapsulate complexity and present a developer with a simple Application Programmer Interface (API) is just what I was referring to when I used that term.

You can find further, more ambitious use of the TriangleCollector in some of the other code examples in the Tinfour project. Again, the Lake Volume Example demonstrates a real-world application of the collector. Beyond that, the collector is useful for graphics and rendering applications, surface analysis, and a host of other spatial analysis applications.