TABLE_DELAUNAY
Triangulate Points in 2D

TABLE_DELAUNAY is a C++ program which computes the Delaunay triangulation of a set of points in the plane.

Specifically, TABLE_DELAUNAY reads a data file of node coordinates, computes the Delaunay triangulation of those points, and writes a triangle file listing the indices of nodes that form each triangle.

Usage:

table_delaunay prefix

• prefix_nodes.txt, the node coordinate file (input).
• prefix_elements.txt, the element file (output).

Licensing:

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

Languages:

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

Related Programs:

DELAUNAY_LMAP_2D, a FORTRAN90 program that computes the Delaunay triangulation of points in the plane under a linear mapping.

GEOMPACK, a C++ library which computes the Delaunay triangulation.

STRIPACK, a FORTRAN90 library which computes the Delaunay triangulation or Voronoi diagram of points on a sphere.

TABLE, a file format which is used for the input to this program.

TABLE_IO, a C++ library which supplies the routines used to read the TABLE file.

TABLE_TET_MESH, a FORTRAN90 program which can read a table file of 3D data, and compute a tetrahedral mesh.

TABLE_VORONOI, a C++ program which can be used to compute information about the Voronoi diagram of the points.

TRIANGULATION_DISPLAY_OPENGL, a C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_PLOT, a C++ program which may be used to visualize the triangulation.

TRIPACK, a FORTRAN90 library which computes the Delaunay triangulation of points in the plane.

Reference:

1. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0,
   LC: QA448.D38.C65.
2. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   ISBN: 0-521-79309-2,
   LC: QA377.E36.
3. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.
4. Joseph ORourke,
   Computational Geometry,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.
5. Per-Olof Persson, Gilbert Strang,
   A Simple Mesh Generator in MATLAB,
   SIAM Review,
   Volume 46, Number 2, pages 329-345, June 2004.

Source Code:

• table_delaunay.cpp, the source code.

Examples and Tests:

HEX_CVT3 puts a set of 139 nodes into the double hexagonal hole region using CVT techniques.

• hex_cvt3_nodes.txt, the nodes.
• hex_cvt3_nodes.png, a PNG image of the nodes.
• hex_cvt3_elements.txt, the triangulation created by TABLE_DELAUNAY.
• hex_cvt3_triangulation.png, a PNG image of the triangulation.

List of Routines:

• MAIN is the main program for TABLE_DELAUNAY.
• CH_CAP capitalizes a single character.
• CH_EQI is true if two characters are equal, disregarding case.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DIAEDG chooses a diagonal edge.
• DTABLE_DATA_READ reads the data from a DTABLE file.
• DTABLE_HEADER_READ reads the header from a DTABLE file.
• DTRIS2 constructs a Delaunay triangulation of 2D vertices.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_ROW_COUNT counts the number of row records in a file.
• 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_SOME prints some of an I4MAT, transposed.
• ITABLE_WRITE0 writes an ITABLE file with no header.
• I4VEC_INDICATOR_NEW sets an I4VEC to the indicator vector.
• I4VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an 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".
• R8_ABS returns the absolute value of an R8.
• 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.
• R8_NINT returns the nearest integer to an R8.
• R82VEC_PERMUTE permutes an R82VEC in place.
• R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R82VEC.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• SWAPEC swaps diagonal edges until all triangles are Delaunay.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• VBEDG determines which boundary edges are visible to a point.

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