STRIPACK
Delaunay Triangulation on a Sphere

STRIPACK is a FORTRAN90 library, using double precision arithmetic, for computational geometry on the unit sphere in 3D.

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 a FORTRAN90 "translation" of the original FORTRAN77 code written by Robert Renka and published in the ACM Transactions on Mathematical Software.

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.

Related Data and Programs:

BIVAR is a FORTRAN90 library which computes a function F(X,Y) that interpolates scattered data by using a Delaunay triangulation.

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

DESIGN is a FORTRAN90 library which returns point sets on the sphere that constitute "designs".

GEOMETRY is a library of FORTRAN90 routines which compute various geometric quantities, including grids on spheres.

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

SCVT is a FORTRAN90 library which can find a set of well separated points on a sphere using Centroidal Voronoi Tessellations.

STRI_QUAD is a FORTRAN90 library which estimates the integral of a function defined on the sphere.

STRIPACK_INTERACTIVE is an executable FORTRAN90 program which reads a set of points on the unit sphere, computes the Delaunay triangulation, and writes it to a file.

SXYZ_VORONOI is a FORTRAN90 library which computes and plots Delaunay triangulations and Voronoi diagrams of points on the sphere.

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

TOMS772 is the original FORTRAN77 text of the STRIPACK program.

TRIANGULATION_PLOT is a FORTRAN90 program which may be used to make a PostScript image of a triangulation of points.

TRIPACK is 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. 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. AD McLaren,
   Optimal Numerical Integration on a Sphere,
   Mathematics of Computation,
   Volume 17, Number 84, October 1963, pages 361-383.
5. 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.
6. Edward Saff, Arno Kuijlaars,
   Distributing Many Points on a Sphere,
   The Mathematical Intelligencer,
   Volume 19, Number 1, 1997, pages 5-11.
7. Brian Wichmann, David Hill,
   An Efficient and Portable Pseudo-random Number Generator,
   Applied Statistics,
   Volume 31, Number 2, 1982, pages 188-190.

Source Code:

• stripack.f90, the source code.
• stripack.csh, commands to compile the source code.

Examples and Tests:

STRIPACK_PRB is a sample problem. Test files you may copy include:

• stripack_prb.f90, a sample problem.
• stripack_prb.csh, commands to compile, link and run the sample problem.
• stripack_prb.out, sample problem output.
• stripack_prb_del.png, a PNG image of the Delaunay triangulation.
• stripack_prb_vor.png, a PNG image of the Voronoi diagram.

STRIPACK_PRB2 is a second sample problem. Test files you may copy include:

• stripack_prb2.f90, a sample problem.
• stripack_prb2.csh, commands to compile, link and run the sample problem.
• stripack_prb2.out, sample problem output.

List of Routines:

• ADDNOD adds a node to a triangulation.
• ARC_COSINE computes the arc cosine function, with argument truncation.
• AREAS computes the area of a spherical triangle on the unit sphere.
• BDYADD adds a boundary node to a triangulation.
• BNODES returns the boundary nodes of a triangulation.
• CIRCUM returns the circumcenter of a spherical triangle.
• COVSPH connects an exterior node to boundary nodes, covering the sphere.
• CRLIST returns triangle circumcenters and other information.
• DELARC deletes a boundary arc from a triangulation.
• DELNB deletes a neighbor from the adjacency list.
• DELNOD deletes a node from a triangulation.
• EDGE swaps arcs to force two nodes to be adjacent.
• GETNP gets the next nearest node to a given node.
• I4_SWAP swaps two integer values.
• INSERT inserts K as a neighbor of N1.
• INSIDE determines if a point is inside a polygonal region.
• INTADD adds an interior node to a triangulation.
• INTSRC finds the intersection of two great circles.
• JRAND returns a random integer between 1 and N.
• LEFT determines whether a node is to the left of a plane through the origin.
• LSTPTR returns the index of NB in the adjacency list.
• NBCNT returns the number of neighbors of a node.
• NEARND returns the nearest node to a given point.
• OPTIM optimizes the quadrilateral portion of a triangulation.
• R83VEC_NORMALIZE normalizes each R83 in an R83VEC to have unit norm.
• SCOORD converts from Cartesian to spherical coordinates.
• STORE forces its argument to be stored.
• SWAP replaces the diagonal arc of a quadrilateral with the other diagonal.
• SWPTST decides whether to replace a diagonal arc by the other.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRANS transforms spherical coordinates to Cartesian coordinates.
• TRFIND locates a point relative to a triangulation.
• TRLIST converts a triangulation data structure to a triangle list.
• TRLPRT prints a triangle list.
• TRMESH creates a Delaunay triangulation on the unit sphere.
• TRPLOT makes a PostScript image of a triangulation on a unit sphere.
• TRPRNT prints the triangulation adjacency lists.
• VORONOI_POLY_COUNT counts the polygons of each size in the Voronoi diagram.
• VRPLOT makes a PostScript image of a Voronoi diagram on the unit sphere.

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