SPHERE_DELAUNAY
Delaunay Triangulation on Unit Sphere


SPHERE_DELAUNAY is a FORTRAN90 program which computes the Delaunay triangulation of points on the unit sphere.

SPHERE_DELAUNAY takes as input an XYZ file, containing coordinates of points on the unit sphere in 3D. It passes this data to Renka's STRIPACK library which computes the Delaunay triangulation. The program then takes one "snapshot" of the triangulation, which is written to an EPS image file, and stores the line information that defines the Delaunay triangulation as an XYZL file.

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.

Usage:

sphere_delaunay file.xyz
reads the XYZ file file.xyz containing the point coordinates, creates an EPS file file.eps containing a 2D projection of the Delaunay triangulation, and creates an XYZL file file.xyzl which can be used, in conjunction with file.xyz to display the 3D triangulation.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

SPHERE_DELAUNAY is available in a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

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

SPHERE_DESIGN_RULE, a FORTRAN90 library 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_INTEGRALS, a FORTRAN90 library which defines test functions for integration over the surface of the unit sphere in 3D.

SPHERE_QUAD, a FORTRAN90 library which approximates an integral over the surface of the unit sphere by applying a triangulation to the surface;

SPHERE_STEREOGRAPH, a FORTRAN90 library 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 program which computes and plots the Voronoi diagram of points on the unit sphere.

SPHERE_XYZ_DISPLAY_OPENGL, a C++ program which reads XYZ information defining points in 3D, and displays a unit sphere and the points, using OpenGL.

STRIPACK, a FORTRAN90 library which computes the Delaunay triangulation of the points on the unit sphere.

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

XYZ, a data directory which contains examples of XYZ files, a simple 3D graphics point format;

XYZ_IO, a FORTRAN90 library which reads and writes XYZ files.

XYZL, a data directory which contains examples of XYZL files, a simple 3D graphics point and line format;

XYZL_DISPLAY, a MATLAB program which reads XYZL information defining points and lines in 3D, and displays an image in a MATLAB graphics window.

XYZL_DISPLAY_OPENGL, a C++ program which reads XYZL information defining points and lines in 3D, and displays an image using OpenGL.

Reference:

  1. 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.
  2. 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, 1997.
  3. Edward Saff, Arno Kuijlaars,
    Distributing Many Points on a Sphere,
    The Mathematical Intelligencer,
    Volume 19, Number 1, 1997, pages 5-11.

Source Code:

Examples and Tests:

GEN_00010 is a test set of 10 points:

GEN_00100 is a test set of 100 points:

List of Routines:

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


Last revised on 19 December 2008.