GEOMPACK
Delaunay triangulation

GEOMPACK is a FORTRAN90 library, using double precision arithmetic, which computes the Delaunay triangulation of a set of points in the plane.

Related Data and Programs:

DUTCH is a FORTRAN90 library which carries out tasks in computational geometry.

GEOMETRY is a FORTRAN90 library which performs geometric calculations in 2, 3 and N dimensional space.

GEOMPACK is also available in a C++ version and a MATLAB version and a PASCAL 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 a C++ program which reads files defining a triangulation and displays an image using OpenGL.

TRIANGULATION_TRIANGLE_NEIGHBORS is a FORTRAN90 program which 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 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.f90, the source code.
• geompack.csh, commands to compile the source code.

Examples and Tests:

• geompack_prb.f90, 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.
• 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.
• GET_UNIT returns a free FORTRAN unit number.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_SWAP swaps two integer values.
• I4_WRAP forces an integer to lie between given limits by wrapping.
• I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
• I4VEC_HEAP_D reorders an I4VEC into an descending heap.
• I4VEC_SORT_HEAP_A ascending sorts an I4VEC using heap sort.
• I4VEC_SORTED_UNIQUE finds the unique elements in a sorted I4VEC.
• LRLINE determines if a point is left of, right or, or on a directed line.
• PERM_CHECK checks that a vector represents a permutation.
• PERM_INV inverts a permutation "in place".
• POINTS_DELAUNAY_NAIVE_2D is a naive Delaunay triangulation scheme.
• R82VEC_PART_QUICK_A reorders an R82VEC as part of a quick sort.
• R82VEC_PERMUTE permutes an R82VEC in place.
• R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R82VEC.
• R82VEC_SORT_QUICK_A ascending sorts an R82VEC using quick sort.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• R8MAT_UNIFORM fills an R8MAT with scaled pseudorandom numbers.
• R8VEC_EQ is true if two R8VEC's are equal.
• R8VEC_GT == ( A1 > A2 ) for R8VEC's.
• R8VEC_LT == ( A1 < A2 ) for R8VEC's.
• 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.
• TIMESTRING writes the current YMDHMS date into a string.
• TRIANGLE_CIRCUMCENTER_2D computes the circumcenter of a triangle in 2D.
• TRIANGULATION_ORDER3_PLOT plots a 3-node triangulation of a set of nodes.
• TRIANGULATION_ORDER3_PRINT prints out information defining a Delaunay triangulation.
• VBEDG determines which boundary edges are visible to a point.

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