**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*

*The Geometry Center Home Page*
Comments to: nina@geom.umn.edu

Created: May 31 1995 ---
Last modified: Thu Jun 1 14:31:00 1995