Pointgon - Minimum Weight Triangulation of Polygons with Holes

Download

Description

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.

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.

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:

• Fixed Parameter Algorithms for the Minimum Weight Triangulation Problem
  Magdalene G. Borgelt, Christian Borgelt, and Christos Levcopoulos
  Int. Journal of Computational Geometry and Applications 18(3):185--220.
  World Scientific, Hackensack, NJ, USA 2008
• Fixed Parameter Algorithms for the Minimum Weight Triangulation Problem
  Magdalene Grantson, Christian Borgelt, and Christos Levcopoulos.
  Technical Report LU-CS-TR:2005-238, ISSN 1650-1276 Report 158, Lund University, Lund, Sweden 2006.
  tr_238_orig.pdf (455 kb) tr_238_orig.ps.gz (281 kb) (original version, 33 pages; February 13, 2006)
  tr_238.pdf (460 kb) tr_238.ps.gz (283 kb) (extended version, 34 pages; February 20, 2006)
• A Fixed Parameter Algorithm for Minimum Weight Triangulation: Analysis and Experiments
  Magdalene Grantson, Christian Borgelt, and Christos Levcopoulos.
  Technical Report LU-CS-TR:2005-234, ISSN 1650-1276 Report 154, Lund University, Lund, Sweden 2005.
  tr_234.pdf (273 kb) tr_234.ps.gz (192 kb) cover_234.pdf (264 kb) (12 pages; April 20, 2005)
• Minimum Weight Triangulation by Cutting Out Triangles
  Magdalene Grantson, Christian Borgelt, and Christos Levcopoulos.
  Proc. 16th Annual Int. Symposium on Algorithms and Computation (ISAAC'05, Sanya, China), LNCS 3827:984-994.
  Springer-Verlag, Heidelberg, Germany 2005.
  isaac_05.pdf (239 kb) isaac_05.ps.gz (185 kb) (10 pages)
  An earlier version of this paper was published as:
  Technical Report LU-CS-TR:2005-235, ISSN 1650-1276 Report 155, Lund University, Lund, Sweden 2005 (July 4, 2005).
  cover_235.pdf (264 kb)

Basic functions of the graphical user interface include:

• Zoom into the pointgon
  Press and hold the middle or right mouse button (different zoom factors), then move the mouse vertically.
• Move the pointgon
  If the pointgon does not fit into the window (scrollbars are shown), it can be moved by pressing and holding the left mouse button and then moving the mouse.
• Remove an edge of a triangulation
  Press and hold either the shift or the control key, then press the right mouse button close to the edge you want to remove.
• Add an edge to a triangulation
  Press and hold either the shift or the control key, then press the left mouse button first close to the source vertex and then close to the destination vertex. A selection of the source can be discarded by pressing the middle mouse button.

All other functions are accessible through the program menu.