GEOMPACK
Delaunay triangulation

GEOMPACK is a PASCAL library (written for the DELPHI compiler) which computes the Delaunay triangulation of a set of points in the plane.

Related Data and Programs:

GEOMETRY is a FORTRAN90 library of routines for geometric calculations in 2, 3 and N dimensional space.

GEOMPACK is also available in a C++ version and a FORTRAN90 version and a MATLAB version.

GEOMPACK2 is a more extensive FORTRAN90 library, from which GEOMPACK was extracted.

GEOMPACK3 is a FORTRAN90 library for 3D geometric problems.

TRIANGULATION_DISPLAY_OPEN_GL is an executable C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_TRIANGLE_NEIGHBORS is an executable FORTRAN90 program that reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Author:

Barry Joe,
Department of Computing Science,
University of Alberta,
Edmonton, Alberta, Canada.

Program Port to Delphi Pascal Compiler:

Malte Persike,
Institute of Psychology,
Department of Psychological Methods,
D-55099 Mainz, Germany,
email: malte@t-online.de.

Notes Specific to the Delphi Pascal Version:

The Delphi code is a port of the C++ version of GEOMPACK (10 November 2006). Several significant modifications have been made to the code in order to provide a smooth transition to Delphi.

1. Data types
   • Doubles have been converted to Reals.
   • Array variables have been converted to dynamic arrays.
2. Error handling
   • All error handling is done through exceptions. No error codes are returned from any functions.
   • Functions with an error status return value have been converted to procedures.
3. Superseded functions
   • I4_MAX, I4_MIN, R8_MAX, and R8_MIN have been substituted by the built in functions Min() and Max().
   • S_LEN_TRIM has been substituted by Length(Trim()).
4. Required external units
   • Only built-in Delphi units are needed to compile GEOMPACK. These are (a) Math, (b) SysUtils, and (c) Windows.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991,
   ../../pdf/aurenhammer.pdf
2. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.

Source Code:

• geompack.pas, the core computational functions.
• geomprnt.pas, functions that print data to the console.
• arrtypes.pas, declarations of dynamic array types.
• geompack.csh, commands to compile the source code.

Examples and Tests:

• geompack_prb.pas, a sample calling program.
• geompack_prb.csh, commands to compile and run the sample program.
• geompack_prb_output.txt, the output from a run of the sample program.

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