Tinfour

High-Performance 2D Delaunay Triangulation and Related Utilities Written in Java

Notice

The Tinfour compiled binary files (Jar files) are available at
Sonatype’s Maven Central Repository
or the Maven Central Repository

We are migrating some of our documentation to a separate project.
Visit TinfourDocs to check it out.

Delaunay Triangulation

The Delaunay Triangulation defines an optimal form for organizing unstructured or semi-random
sample points into a triangular mesh. That optimality makes the Delaunay Triangulation
a useful tool for interpolation, grid construction, and surface analysis.

Tinfour

Tinfour is a software library written in Java that provides tools for constructing
and applying Triangulated Irregular Networks (TINs) that conform to the Delaunay
criterion. Because it is intended to process large data sets,
the implementation gives a great deal of attention to performance and
memory use. On a conventional laptop, Tinfour is capable of processing sample
points at a rate of better than one million points per second.

The Tinfour source code includes extensive documentation. This project also includes
an informal paper that describes the uses, algorithms, and implementation
of the software with enough detail to support potential developers
who may wish to contribute code or employ Tinfour in their own work. For more details, see
Data Elements and Algorithms for the Tinfour Libary.
If you would like to discuss the Tinfour project or tell us about your own work, feel free to visit The Tinfour Discussion Page.

The Tinfour Viewer

When someone first sees a project like Tinfour, they might reasonably ask
that most thorny of questions “What is it good for?” To answer that question,
this library includes a simple demonstration application called Tinfour Viewer
that allows the user to exercise the major functions of the Tinfour library.
Using Tinfour Viewer, the user can explore data sets ranging in size from just a few points
up to the millions.

Here’s a screenshot from the Tinfour Viewer showing a collection of Lidar elevation data
collected over a section of Interstate highway in the U.S. Northeast.

The Tinfour Viewer application is intended to show how the Tinfour library could be integrated
into a full-featured GIS application or other analysis tool. It’s a simple
implementation with a minimum of features.
Instructions for setting up and running the Tinfour Viewer application
are provided at the wiki page Tinfour Execution from the Command Line.
Our wiki page attempts to simplify the process of running Tinfour demostration applications as much as possible. It also
explains some of the nuances of the launch procedures and provides the details
you will need to set up a command window and run the command-line variations
for all the various Tinfour applications.

To run the Tinfour software, you must have Java installed
on your system. If you do not have Java installed on your computer, you may
download an installer for free from
Oracle Corporation, Java Downloads.

Sources of Data

Lidar is a system for collecting surface elevation using laser measuring devices
mounted on low flying aircraft. It’s pretty amazing technology.
There are excellent sources of Lidar data to be had for free, you might start at
Free LiDAR Data Sources
or the USGS 3D Elevation Program.
The Commonwealth of Pennsylvania was one of the first states to collect and post
a comprehensive survey of lidar data, and they did the job right… Their site includes
not just lidar data, but the supporting breakline files (Shapefiles), multi-spectral imagery,
and project metadata (including Dewberry reports). Visit this excellent resource at
PAMAP Lidar Elevation Data.

If you just want to download a single Lidar file and view it, we recommend PAMAP Tile 4100133PAS
which can be found at ftp://pamap.pasda.psu.edu/pamap_lidar/cycle1/LAS/South/2006/40000000/41001330PAS.zip.
At 36.7 megabytes, the PAMAP file isn’t dainty. But it does contain interesting land features and sufficient
detail to exercise the major functions of the viewer.

A short demo

Recently, we found an earlier Delaunay triangulation project by “The Mad Creator” (Bill Dwyer)
that provided a four-line demo. It was such a elegant way of introducing the package,
that we decided to include one of our own.

public static void main(String []args) throws Exception {
    IncrementalTin tin = new IncrementalTin(1.0);
    List<Vertex>vertexList = TestVertices.makeRandomVertices(100, 0);
    tin.add(vertexList, null);
    TinRenderingUtility.drawTin(tin, 500, 500, new File("tin.png"));
}

Does Tinfour require external project dependencies?

The core Tinfour module has no external dependencies. All it requires
is the standard Java API. Thus, you can integrate the core classes
into your own applications without adding unnecessary object code to
your software.

The associated, extended-functionality modules do depend on object code from external projects.
These include modules that can read data from Geographic Information System (GIS) sources
(Shapefiles and airborne Lidar LAS files) and those that perform advanced mathematical
and statistical analysis. These modules and dependencies are described in the Tinfour wiki page
Tinfour Builds and Dependencies.

What version of Java is required for Tinfour?

Tinfour is compiled under Java 11 or higher.

Configuring Tinfour in an IDE

In terms of its software and package organization, Tinfour has a relatively simple structure, so opening
it in an Integrated Development Environment (IDE) is straight forward.
The major Java IDEs (Netbeans, Eclipse, and IntelliJ) all support direct access to Maven projects.
If you have one of these IDE’s you can simply load the Tinfour project and run with it. All work fine.
More hints and background information on configuring Tinfour for use in an IDE are included in the Tinfour wiki page
Tinfour Builds and Dependencies.

Current Work

Development work on the Constrained Conforming Delaunay Triangulation is now complete.

Development work for the next release of Tinfour will focus on the introduction of Delaunay Refinement.
Delaunay Refinement is a technique for improving the quality of the triangles
formed by a Delaunay Triangulation through the introduction of synthetic vertices
at well-chosen positions. Refinement techniques are particularly useful in areas near
the boundaries of constraints or near the permimeter of a triangulation. These
areas are often prone to the formation of “skinny” triangles (triangles with two small
angles and one very large angle).

Currently, we are investigating the use of Ruppert’s Algorithm as a refinement technique, though other
refinement techniques do exist (such as Chew’s Second Delaunay Refinement Algorithm).

For more detail about the Tinfour project development plans, see the
Tinfour Project Status and Roadmap page.

Our Companion Project

Visit the Gridfour Software Project to learn more about our companion
software project dedicated to creating open-source software tools for raster (grid) data sets.

Conclusion

Finally, the whole point of working on a project like Tinfour is to see
it employed to do something useful. To that end, I welcome ideas, requests, and
recommendations for analysis tools and applications that would
benefit the open source and scientific communities. Got something
to say? You can contact the Tinfour project at [email protected]