TRIPACK
Constrained Delaunay Triangulation


TRIPACK is a FORTRAN90 library which computes the Delaunay triangulation of a set of points in the plane, by Robert Renka.

TRIPACK has the unusual option of allowing the user to specify constraint curves to be included in the triangulation.

TRIPACK is primarily a FORTRAN90 "translation" of the original FORTRAN77 program written by Robert Renka, and published in the ACM Transactions on Mathematical Software.

TRIPACK is ACM TOMS algorithm 751. The text of the original FORTRAN77 program is available online through ACM: http://www.acm.org/pubs/calgo or NETLIB: http://www.netlib.org/toms/index.html.

Specifically, the directory http://www.netlib.org/toms/751 contains the original, true, correct version of ACM TOMS Algorithm 751.

Languages:

TRIPACK is available in a FORTRAN90 version.

Related Data and Programs:

DELAUNAY_LMAP_2D, a FORTRAN90 program which computes the Delaunay triangulation of points in the plane subject to a linear mapping.

GEOMPACK, a FORTRAN90 library which can compute Delaunay triangulations Voronoi diagrams and other information, written by Barry Joe.

STRIPACK, a FORTRAN90 library which computes the Delaunay triangulation or Voronoi diagram of points on a sphere.

TABLE_DELAUNAY, a FORTRAN90 program which reads a file of point coordinates in the TABLE format and writes out the Delaunay triangulation.

TRIANGULATION, a FORTRAN90 library which performs various operations on order 3 ("linear") or order 6 ("quadratic") triangulations.

TRIANGULATION_PLOT, a FORTRAN90 program which makes a PostScript image of a triangulation of points.

TRIANGULATION_TRIANGLE_NEIGHBORS, a FORTRAN90 program which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Author:

Robert Renka

Reference:

  1. Franz Aurenhammer,
    Voronoi diagrams - a study of a fundamental geometric data structure,
    ACM Computing Surveys,
    Volume 23, pages 345-405, September 1991.
  2. Robert Renka,
    Algorithm 751: TRIPACK, A Constrained Two-Dimensional Delaunay Triangulation Package,
    ACM Transactions on Mathematical Software,
    Volume 22, Number 1, 1996.
  3. Brian Wichmann, David Hill,
    An Efficient and Portable Pseudo-random Number Generator,
    Applied Statistics,
    Volume 31, Number 2, 1982, pages 188-190.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the FORTRAN90 source codes.


Last revised on 15 December 2005.