Delaunay Triangulation in Java:

 

Triangulation is a popular way to represent surfaces (e.g. terrains).

There are many triangulation packages, yet some of them uses naive algorithms (with running time as high as O(n^3)). Other triangulation packages were written with runtime “in mind” but they are hard to use and are very platform independent (e.g. CGAL triangulation).

 

During 2001-2004 I wrote a prototype for a GIS expert system for locating large scale wireless networks (see, http://www.yosh.ac.il/dom/bbm/publications/PHD.pdf ch7). Naturally, such a system needs to support irregular terrains (TINs). During that time I was unable to find a triangulation package, with the following two main properties:

 

  1. Simplicity: this package supposes to be as simple as it gets and to allow programmer with almost NO background in computational geometry to use 2.5D triangulation in a simple, safe, efficient way.
  2. Performance: should be able to construct triangulations of size 10^5 vertices, in few seconds, moreover point location should be efficient without using too much memory.

 

With these two guidelines in mind I decided to write the triangulation package in Java.

Only the Delaunay Triangulation was implemented – being the most popular triangulation to present terrains. To do that I took the best “public” code I could find in the web (Klasse für Kreise code from 1996-1997), and rewrote it:

 

The (DT) package contains only 3 public classes:

Point in 3D: with some basic geometric methods.

Triangle in 3D: representing both a triangle in triangulation and a 3D plane.

Delaunay Triangulation in 2.5D: The main class (with some inner classes) and IO capabilities (save / load to / from text file).

 

Who use it?:

The DT package is still a prototype and has never been deeply tested, yet about 50 students have used it to implement various projects in Computational Geometry courses (graduated). Moreover the DT package was used in the following experiments: 

Visibility preserving terrain simplification - An experimental study

Approximating the Visible Region of a Point on a Terrain

Approximating Radio Maps - An experimental study

Geometric Facility Location Optimization

 

Get it:

The current version requires java 1.5 (uses generics for the iterators).

 

Note: this package is NOT a freeware but I’ll be glad to share the source with any nonprofit organization, for that or for any other comments (say bugs, questions…)

Email me: benmoshe@cs.bgu.ac.il