SXYZ_DELAUNAY
Delaunay Triangulation on Unit Sphere

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

SXYZ_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.

Usage:

sxyz_delaunay file.xyz

Licensing:

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

Related Data and Programs:

EPS, a data directory which contains examples of EPS files, the Encapsulated PostScript file format for 2D graphics;

IVREAD is a FORTRAN90 program which converts graphics information between various 3D formats.

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

SPHERE_DESIGN_RULE is 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.

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

STRIPACK_INTERACTIVE is a 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 program which computes and plots the Voronoi diagram of points on the unit sphere.

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

XYZ_IO is 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 is a MATLAB program which reads XYZL information defining points and lines in 3D, and displays an image in a MATLAB graphics window.

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

Reference:

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

Source Code:

• sxyz_delaunay.f90, the source code.
• sxyz_delaunay.csh, commands to compile and load 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 Delaunay triangulation.
• gen_00010.xyzl, the XYZL file listing the indices of points to connect to form the Delaunay triangulation.

GEN_00100 is a test set of 100 points:

• gen_00100.xyz, the point coordinates.
• gen_00100.png, a PNG image of the Delaunay triangulation.
• gen_00100.xyzl, the XYZL file listing the indices of points to connect to form the Delaunay triangulation.

List of Routines:

• MAIN is the main program for SXY_DELAUNAY.
• 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.
• 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.
• TR_TO_XYZL makes an XYZL file of Delaunay triangulation 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.