GEOMPACK
Delaunay triangulations

GEOMPACK is a library of C++ routines, using double precision arithmetic, which carry out certain geometric computations, including the Delaunay triangulation and Voronoi diagram of a set of points in the plane.

Related Data and Programs:

DUTCH is a FORTRAN90 library of routines for computational geometry.

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

GEOMPACK is also available in a FORTRAN90 version and a MATLAB version and a PASCAL version.

TABLE_DELAUNAY is an executable C++ program that reads a file of 2d point coordinates and computes the Delaunay triangulation.

Author:

Barry Joe,
Department of Computing Science,
University of Alberta,
Edmonton, Alberta, Canada T6G 2H1
Phone: (403) 492-5757
Email: barry@cs.ualberta.ca

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.C, the source code.
• geompack.H, the include file.
• geompack.csh, commands to compile the source code.

Examples and Tests:

• geompack_prb.C, a sample problem.
• geompack_prb.csh, commands to compile, link and run the sample problem.
• geompack_prb.out, sample problem output.
• triangulation_plot.png, a PNG image of a triangulation.

List of Routines:

• DIAEDG chooses a diagonal edge.
• DTRIS2 constructs a Delaunay triangulation of 2D vertices.
• I4_MAX returns the maximum of two integers.
• I4_MIN returns the smaller of two integers.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_SIGN returns the sign of an integer.
• I4_WRAP forces an integer to lie between given limits by wrapping.
• I4MAT_TRANSPOSE_PRINT prints an integer matrix, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of an integer matrix, transposed.
• I4VEC_HEAP_D reorders an array of integers into a descending heap.
• I4VEC_INDICATOR sets an integer vector to the indicator vector.
• I4VEC_SORT_HEAP_A ascending sorts an array of integers using heap sort.
• I4VEC_SORTED_UNIQUE finds unique elements in a sorted integer array.
• LRLINE determines where a point lies in relation to a directed line.
• PERM_CHECK checks that a vector represents a permutation.
• PERM_INV inverts a permutation "in place".
• POINTS_DELAUNAY_NAIVE_2D computes the Delaunay triangulation in 2D.
• R8_EPSILON returns the round off unit for double precision arithmetic.
• R8_MAX returns the maximum of two R8s.
• R8_MIN returns the minimum of two R8s.
• R82VEC_PART_QUICK_A reorders an R2 vector as part of a quick sort.
• R82VEC_PERMUTE permutes an R2 vector in place.
• R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R2 vector.
• R82VEC_SORT_QUICK_A ascending sorts an R2 vector using quick sort.
• R8MAT_TRANSPOSE_PRINT prints a real matrix, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of a real matrix, transposed.
• R8MAT_UNIFORM fills a double precision array with scaled pseudorandom values.
• R8VEC_EQ is true if every pair of entries in two vectors is equal.
• R8VEC_GT == ( A1 > A2 ) for real vectors.
• R8VEC_LT == ( A1 < A2 ) for real vectors.
• R8VEC_PRINT prints a double precision vector.
• R8VEC_SWAP swaps the entries of two real vectors.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• SWAPEC swaps diagonal edges until all triangles are Delaunay.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING returns the current YMDHMS date as a string.
• TRIANGLE_CIRCUMCENTER_2D computes the circumcenter of a triangle in 2D.
• TRIANGULATION_PLOT_EPS plots a triangulation of a pointset.
• TRIANGULATION_PRINT prints information defining a Delaunay triangulation.
• VBEDG determines which boundary edges are visible to a point.

You can go up one level to the C++ source codes.