sphere_voronoi

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

The code 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 Voronoi diagram. The program then takes one "snapshot" of the diagram, which is written to an EPS image file, and stores the vertex and line information defines the Voronoi triangulation as XYZ and XYZF files.

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_voronoi file.xyz
reads the XYZ file file.xyz containing the point coordinates, creates an EPS file file.eps containing a 2D projection of the Voronoi diagram, and creates an XYZ file file.voronoi.xyz and an XYZF file file.xyzf which can be used, in conjunction with file_voronoi.xyz to display the 3D Voronoi diagram.

Licensing:

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

Languages:

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

Related Data and Programs:

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

SPHERE_DELAUNAY, a FORTRAN90 code which computes and plots the Delaunay triangulation of points on the unit 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_test

STRIPACK, a FORTRAN90 code which is used by SPHERE_VORONOI to compute the Voronoi tessellation and Delaunay triangulation of the points on the sphere.

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:

Last revised on 30 August 2020.