Welcome to the Tinfour Project Documentation

What Tinfour Does

The focus of Tinfour is the Delaunay triangulation. The Delaunay triangulation defines an optimal structure for organizing unstructured or semi-random sample points into a triangular mesh. That optimality makes the Delaunay triangulation useful for interpolation, grid construction, and surface analysis.

Project Notes

To help you use Tinfour, we have posted four kinds of documentation:

• The Ideas – Articles that introduce the concepts and techniques used in the Tinfour software. These pages cover general topics related to the Delaunay triangulation, graph theory, and geospatial analysis.
• The Wiki – Tutorials, code examples, useful tricks, and step-by-step instructions for using Tinfour in your own projects.
• The Internals – A PDF providing notes on the internal design and algorithms of the Tinfour API. If you wish to add new features to Tinfour, or write your own Delaunay triangulation software, you will find this document useful.
• The API – Our source code includes extensive documentation. You can access the Javadoc for each Tinfour module at the following links:
  • Core – The core implementation of our Delaunay triangulation, interpolation, and other support classes (no external dependencies)
  • GIS – While Tinfour is not a Geographic Information System (GIS), it does provide a small set of tools for accessing GIS-related data sources, including LiDAR elevation and ESRI shapefiles.
  • Demo – Demonstration implementations that show how to use the Tinfour APIs
  • SVM – The Simple Volumetric Model (SVM), a hydrographic analysis utility for estimating the volume and capacity of lakes and reservoirs using the Delaunay triangulation
  • Analysis – The Analysis module includes our experimental Geographically Weighted Regression implementation and other mathematics and statistics applications.

You can find source code and project information on GitHub at:

• The Tinfour Repository – A free, open-source collection of high-performance Delaunay triangulation software written in Java.

The Ideas

The articles listed below describe the ideas that form the basis of the Tinfour software.

The Delaunay Triangulations

• An introduction to the Delaunay triangulation  – The Delaunay triangulation is a kind of Triangulated Irregular Network (TIN) with many desirable properties. This article provides information about what makes the Delaunay so useful.
• What is the constrained Delaunay triangulation and why would you care?  – This article describes how the Delaunay can be extended to handle discontinuities and regional subdivisions in data sets.

Natural Neighbor Interpolation

Natural Neighbor Interpolation is a technique for reconstructing a smooth and visually pleasing surface from a set of scattered sample points.

• An introduction to Natural Neighbor Interpolation  – This article provides a lightweight introduction to the ideas and mathematics behind Natural Neighbor Interpolation. It also discusses some of the strengths and weaknesses of the technique.
• A fast and accurate algorithm for Natural Neighbor Interpolation  – The Tinfour software suite includes a robust implementation of the Natural Neighbor technique that can process over a million interpolations per second on a commodity laptop. This article describes the Tinfour algorithm and introduces an often overlooked test procedure that can be used to verify that a Natural Neighbor implementation is correct.

Volume and Capacity Analysis for Lakes and Reservoirs

The Constrained Delaunay Triangulation (CDT) can be used as an efficient tool for computing the volume and capacity of lakes and reservoirs. This series of articles describes the Tinfour technique and how it is used in an application called the Simple Volumetric Model (SVM).

• Using the Delaunay to compute lake volume, Part 1: Concepts  – This article describes how the Constrained Delaunay triangulation was used to compute the volume of Lake Victoria in Africa. The analysis used two collections of depth soundings and a digitized shoreline.
• Using the Delaunay to compute lake volume, Part 2: Implementation  – This article provides implementation notes and detailed results for the Tinfour lake computations. Sample code is available in the Tinfour Software Project repository on GitHub.
• Using the Delaunay to create a model for variable reservoir volume and surface area  – The volume of water in a reservoir can vary based on season and public demand. The Simple Volumetric Model (SVM) provides a tool for computing water volume and capacity based on water level. Results are provided for the Alan Henry Reservoir in Texas, USA.
• Using the Simple Volumetric Model (SVM)  – This article provides details on using the Simple Volumetric Model. Results are provided for the Lake of the Arbuckles in Oklahoma, USA.

• The Articles
• An introduction to the Delaunay Triangulation
• What is the Constrained Delaunay Triangulation and why would you care?
• An introduction to Natural Neighbor Interpolation (NNI)
• A brief introduction to Delaunay refinement
• A fast and accurate algorithm for Natural Neighbor Interpolation (NNI)
• Using the Delaunay to compute lake volume, Part 1: Concepts
• Using the Delaunay to compute lake volume, Part 2: Implementation
• Using the Delaunay to create a model for variable reservoir volume and surface area
• Using the Simple Volumetric Model (SVM)
• Implementation details for a 2D alpha shape utility,
  Part 1: Concepts
• Implementation details for a 2D alpha shape utility,
  Part 2: Implementation
• Using the Delaunay triangulation to detect anomalies in unstructured data
• Using the Delaunay triangulation to estimate spacing between neighboring samples in unstructured data
• Data elements and algorithms for the Tinfour software library (PDF)