Up: Directory of Computational Geometry Software

Triangulation

This page covers a couple of ``full featured'' triangulation programs, but there are several other triangulation programs of various sorts scattered around these pages.

Programs for the Delaunay triangulation of a point set, either in the plane or in higher dimensions, are listed on the pages about convex hull and low-dimensional Voronoi diagrams (since the computations are equivalent!).

Programs for the triangulation or trapezoidation of a polygon or a set of line segments in the plane are on the polygon page and on the page about constrained Delaunany triangulation.

For more ``good quality'' triangulations of polygons, see the mesh generation page, or consult the mesh generation homepage.

In GIS, a triangulation of a function (known as a height field), is known as a TIN.

Triangle

 Quality two-dimensional finite element mesh generation using Ruppert's Delaunay refinement algorithm. Also produces 2D Delaunay triangulations, Voronoi diagrams, and constrained Delaunay triangulations. Produces meshes with angle and area constraints, and allows refinement of existing meshes. Uses fast adaptive exact arithmetic to ensure correctness of output. Accompanied by separate X/PostScript display program. Portable C source code for Unix workstations.

By Jonathan Shewchuk, Carnegie Mellon University.
An introduction and detailed online instructions are available from the Triangle page at CMU.

geompack

 Convex decomposition and triangulation programs for 2D polygons and 3D polyhedra. Visibility polygons for polygons. Delaunay triangulation of point sets in 2-D, 3-D and k-D, where k is small, using an incremental-plus-flipping algorithm. Fortran 77 source code, floating-point.

By Barry Joe, University of Alberta.
For more info (including references) go to the ftp site at Alberta. Documentation is in the Papers directory.

Up: Directory of Computational Geometry Software
[HOME] The Geometry Center Home Page

Comments to: nina@geom.umn.edu
Created: May 31 1995 --- Last modified: Thu Jun 1 14:31:00 1995