Ads by Google
Christian Borgelt's Web Pages

Pointgon - Minimum Weight Triangulation of Polygons with Holes


pointgon.jar (78 kb) executable Java archive (149 kb) pointgon.tar.gz (104 kb) Java sources, version 3.8 (2014.10.23)


Pointgon is a program to compute the minimum weight triangulation of a (simple) polygon with holes (or pointgon for short). The four algorithms underlying this program are based on recursively cutting out triangles, one side of which is on the perimeter (a very simple idea proposed in [Grantson et al. 2005b]), on recursively splitting a given pointgon with paths through hole vertices (an idea inspired by a seminal algorithm by [Hoffmann and Okamoto 2004] and presented in this strict form in [Grantson et al. 2005a]), and on two combined approaches. The first of the combined approaches can be seen as a modification and simplification of the seminal algorithm by [Hoffmann and Okamoto 2004], the second combined approach is a simplified and straightened version of an algorithm by [Spillner 2005]. A side-by-side description of all four algorithms can be found in a technical report available below. For comparisons the program also contains a simple implementation of greedy triangulation, which, however, is a heuristic that can fail to produce the minimum weight triangulation.

The program offers a graphical user interface that visualizes pointgons and their triangulations. Pointgons may be loaded from a text file, generated randomly, triangulated, and a found triangulation may be modified by removing and adding edges. In addition, the triangulation algorithms may be invoked on the command line. See the shell scripts bench and benchall in the source package for examples.

Pointgon screenshot

More explanations about this program and the four basic underlying minimum weight triangulation algorithms (triangle-based, path-based, combined 1, and combined 2) as well as an analysis of the time complexity of these algorithms can be found in the following papers:

Basic functions of the graphical user interface include:

All other functions are accessible through the program menu.