Pointgon 3.5

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 (an 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.<br /><br />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.

Requirements:	No special requirements
Platforms:	Mac, Mac OSX
Keyword:	Algorithm,  Algorithms,  Approaches,  Combined,  Found,  Grantson,  Hoffmann,  Minimum,  Okamoto,  Pointgon,  Pointgons,  Program,  Recursively,  Seminal,  Simple,  Triangulation,  Visualizes,  Weight
Users rating:	0/10