GEOMPACK
Delaunay triangulations

GEOMPACK is a C++ library which carries out certain geometric computations, including the Delaunay triangulation and Voronoi diagram of a set of points in the plane, by Barry Joe.

Licensing:

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

Languages:

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

Related Data and Programs:

DUTCH, a FORTRAN90 library for computational geometry.

GEOMETRY, a C++ library which carries out geometric calculations in 2, 3 and N dimensional space.

TABLE_DELAUNAY, a C++ program which reads a file of 2d point coordinates and computes the Delaunay triangulation.

Author:

Original FORTRAN77 version by Barry Joe; C++ version by John Burkardt.

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.
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.cpp, the source code.
• geompack.hpp, the include file.
• geompack.sh, commands to compile the source code.

Examples and Tests:

• geompack_test.cpp, a sample problem.
• geompack_test.sh, commands to compile, link and run the sample problem.
• geompack_test.txt, the output file.
• triangulation_plot.png, a PNG image of a triangulation.

List of Routines:

• ALPHA_MEASURE determines the triangulated pointset quality measure ALPHA.
• ANGLE_RAD_2D returns the angle in radians swept out between two rays in 2D.
• DIAEDG chooses a diagonal edge.
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the minimum of two I4's.
• I4_MODP returns the nonnegative remainder of I4 division.
• I4_SIGN returns the sign of an I4.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of an I4MAT, transposed.
• I4VEC_HEAP_D reorders an I4VEC into a descending heap.
• I4VEC_INDICATOR_NEW sets an I4VEC to the indicator vector.
• I4VEC_MIN returns the value of the minimum element in an I4VEC.
• I4VEC_SORT_HEAP_A ascending sorts an I4VEC using heap sort.
• I4VEC_SORTED_UNIQUE finds unique elements in a sorted I4VEC.
• LRLINE determines where a point lies in relation to a directed line.
• PERM_CHECK checks that a vector represents a permutation.
• PERM_INVERSE inverts a permutation "in place".
• POINTS_DELAUNAY_NAIVE_2D computes the Delaunay triangulation in 2D.
• POINTS_HULL_2D computes the convex hull of a set of nodes in 2D.
• QUAD_CONVEX_RANDOM returns a random convex quadrilateral.
• R8_ABS returns the absolute value of an R8.
• R8_ACOS computes the arc cosine function, with argument truncation.
• R8_EPSILON returns the R8 roundoff unit.
• R8_HUGE returns a "huge" R8.
• R8_MAX returns the maximum of two R8's.
• R8_MIN returns the minimum of two R8's.
• 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 an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• R8MAT_UNIFORM_01 returns a unit pseudorandom R8MAT.
• R8MAT_UNIFORM_01_NEW returns a unit pseudorandom R8MAT.
• R8TRIS2 constructs a Delaunay triangulation of 2D vertices.
• 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 an R8VEC.
• R8VEC_SWAP swaps the entries of two R8VEC's.
• SWAPEC swaps diagonal edges until all triangles are Delaunay.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• 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.