__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:

: 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.__Simplicity__: 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.__Performance__

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).

- DT Java API (lots of spelling mistakes):
- DT jar file
- JVM “executable” which uses the DT package (input files: t1-1000.tsin, t1-5000.tsin)

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