TOMS772
STRIPACK, Delaunay Triangulation on a Sphere

TOMS772 is a FORTRAN77 library which implements ACM TOMS Algorithm 772, called STRIPACK, which is a library of routines for computational geometry on the unit sphere in 3D, by Robert Renka.

I have a modified FORTRAN90 version available in STRIPACK but it's nice to have this original source code close by.

STRIPACK can compute the Delaunay triangulation or the Voronoi diagram of a set of points on the unit sphere.

STRIPACK can make a PostScript plot of the Delaunay triangulation or the Voronoi diagram from a given point of view.

STRIPACK is a generalization of Robert Renka's code TRIPACK, which computes Delaunay triangulations and Voronoi diagrams for a set of points in the plane.

STRIPACK is ACM TOMS Algorithm 772. The text of the original FORTRAN77 version is available online through ACM: http://www.acm.org/pubs/calgo or NETLIB: http://www.netlib.org/toms/index.html.

Languages:

TOMS772 is available in a FORTRAN77 version.

Related Data and Programs:

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

GEOMPACK, a FORTRAN90 library which contains Barry Joe's geometry package which includes Delaunay triangulation routines.

SPHERE_CVT, a FORTRAN90 library which creates a mesh of well-separated points on a unit sphere using Centroidal Voronoi Tessellations.

SPHERE_DELAUNAY, a MATLAB program which computes the Delaunay triangulation of points on a sphere.

SPHERE_VORONOI, a MATLAB program which computes the Voronoi diagram of points on a sphere.

SPHERE_QUAD, a FORTRAN90 library which estimates the integral of a function defined on the sphere.

STRIPACK, a FORTRAN90 library which carries out computational geometry on the sphere.

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

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

TRIPACK, a FORTRAN90 library which computes the Delaunay triangulation of points in the plane.

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. Jacob Goodman, Joseph ORourke, editors,
   Handbook of Discrete and Computational Geometry,
   Second Edition,
   CRC/Chapman and Hall, 2004,
   ISBN: 1-58488-301-4,
   LC: QA167.H36.
3. Robert Renka,
   Algorithm 772: STRIPACK: Delaunay Triangulation and Voronoi Diagram on the Surface of a Sphere,
   ACM Transactions on Mathematical Software,
   Volume 23, Number 3, September 1997, pages 416-434.

Source Code:

• toms772.f, the source code;
• toms772.sh, commands to compile the source code;

Examples and Tests:

• toms772_prb.f, a sample calling program;
• toms772_prb.sh, commands to compile, link and run the test program;
• toms772_prb_output.txt, the output file;
• toms772_prb_tri.png, a PNG image of the Delaunay triangulation.
• toms772_prb_vor.png, a PNG image of the Voronoi diagram.

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