SPHERE_VORONOI
Voronoi Diagram on Unit Sphere

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

SPHERE_VORONOI 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

Licensing:

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

Languages:

SPHERE_VORONOI 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_DELAUNAY, a FORTRAN90 program which computes and plots the Delaunay triangulation of points on the unit sphere.

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_QUAD, a FORTRAN90 library which estimates the integral of a function defined on the sphere.

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_DISPLAY_OPENGL, a C++ program which displays a sphere and randomly selected generator points, and then gradually colors in points in the sphere that are closest to each generator.

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 is used by SPHERE_VORONOI to compute the Voronoi tessellation and Delaunay triangulation of the points on the sphere.

STRIPACK_VORONOI, a FORTRAN90 program which reads a set of points on the unit sphere, computes the Voronoi diagram, 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.

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

XYZF_DISPLAY, a MATLAB program which reads XYZF information defining points and faces in 3D, and displays an image using OpenGL.

XYZF_DISPLAY_OPENGL, a C++ program which reads XYZF information defining points and faces 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:

• sphere_voronoi.f90, the source code.

Examples and Tests:

GEN_00010 is a test set of 10 points:

• gen_00010.xyz, the point coordinates.
• gen_00010.png, a PNG image of the Voronoi diagram for the data.
• gen_00010.voronoi.xyz, the coordinates of the Voronoi vertices.
• gen_00010.voronoi.xyzf, the indices of the Voronoi vertices that form each face.

GEN_00100 is a test set of 100 points:

• gen_00100.xyz, the point coordinates.
• gen_00100.png, a PNG image of the Voronoi diagram for the data.
• gen_00100.voronoi.xyz, the coordinates of the Voronoi vertices.
• gen_00100.voronoi.xyzf, the indices of the Voronoi vertices that form each face.

List of Routines:

• MAIN is the main program for SPHERE_VORONOI.
• STRIPACK_INTERFACE calls STRIPACK routines.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the numeric value of a base 10 digit.
• FILE_NAME_EXT_GET determines the "extension" of a file name.
• FILE_NAME_EXT_SWAP replaces the current "extension" of a file name.
• FILE_ROW_COUNT counts the number of rows in a file.
• GET_UNIT returns a free FORTRAN unit number.
• POLY_COUNT counts the number of polygons of each size in the diagram.
• POLY_COUNT_MAX determines the highest order polygon.
• S_INDEX_LAST_C finds the LAST occurrence of a given character.
• S_TO_R8 reads an R8 from a string.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING writes the current YMDHMS date into a string.
• VR_TO_XYZF makes an XYZF file of Voronoi diagram data.
• WORD_NEXT_READ "reads" words from a string, one at a time.
• XYZ_READ reads graphics information from an XYZ file.

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