stripack


stripack, a FORTRAN90 code which carries out some computational geometry tasks on the unit sphere in 3D, by Robert Renka.

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

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

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

The code is a FORTRAN90 "translation" of the original FORTRAN77 code written by Robert Renka and published in the ACM Transactions on Mathematical Software.

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

According to Steven Fortune, it is possible to compute the Delaunay triangulation of points on a sphere by computing their convex hull. If the sphere is the unit sphere at the origin, the facet normals are the Voronoi vertices.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

stripack is available in a FORTRAN90 version.

Related Data and Programs:

GEOMETRY, a FORTRAN90 code which computes various geometric quantities, including grids on spheres.

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

SPHERE_DELAUNAY, a FORTRAN90 code which computes the Delaunay triangulation of points on a sphere.

SPHERE_DESIGN_RULE, a FORTRAN90 code which returns point sets on the surface of the unit sphere, known as "designs", which can be useful for estimating integrals on the surface, among other uses.

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

SPHERE_STEREOGRAPH, a FORTRAN90 code which computes the stereographic mapping between points on the unit sphere and points on the plane Z = 1; a generalized mapping is also available.

SPHERE_VORONOI, a FORTRAN90 code which computes and plots the Voronoi diagram of points on the unit sphere.

stripack_test

STRIPACK_DELAUNAY, a FORTRAN90 code which reads a set of points on the unit sphere, computes the Delaunay triangulation, and writes it to a file.

STRIPACK_VORONOI, a FORTRAN90 code which reads a set of points on the unit sphere, computes the Voronoi diagram, and writes it to a file.

TRIANGULATION_PLOT, a FORTRAN90 code which may be used to make a PostScript image of a triangulation of points.

TRIPACK, a FORTRAN90 code 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. Thomas Ericson, Victor Zinoviev,
    Codes on Euclidean Spheres,
    Elsevier, 2001,
    ISBN: 0444503293,
    LC: QA166.7E75
  3. Gerald Folland,
    How to Integrate a Polynomial Over a Sphere,
    American Mathematical Monthly,
    Volume 108, Number 5, May 2001, pages 446-448.
  4. 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.
  5. AD McLaren,
    Optimal Numerical Integration on a Sphere,
    Mathematics of Computation,
    Volume 17, Number 84, October 1963, pages 361-383.
  6. 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.
  7. Edward Saff, Arno Kuijlaars,
    Distributing Many Points on a Sphere,
    The Mathematical Intelligencer,
    Volume 19, Number 1, 1997, pages 5-11.
  8. Brian Wichmann, David Hill,
    An Efficient and Portable Pseudo-random Number Generator,
    Applied Statistics,
    Volume 31, Number 2, 1982, pages 188-190.

Source Code:


Last revised on 31 August 2020.