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
where prefix is the common prefix for the node and triangle files,

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:

Marc deBerg, Marc Krevald, Mark Overmars,
Otfried Schwarzkopf,
Computational Geometry,
Springer, 2000,
ISBN: 3540656200,
LC: QA448.D38.C65.

Herbert Edelsbrunner,
Geometry and Topology for Mesh Generation,
Cambridge, 2001,
ISBN: 0521793092,
LC: QA377.E36.

Barry Joe,
GEOMPACK  a software package for the generation of meshes
using geometric algorithms,
Advances in Engineering Software,
Volume 13, pages 325331, 1991.

Joseph ORourke,
Computational Geometry,
Second Edition,
Cambridge, 1998,
ISBN: 0521649765,
LC: QA448.D38.

PerOlof Persson, Gilbert Strang,
A Simple Mesh Generator in MATLAB,
SIAM Review,
Volume 46, Number 2, pages 329345, June 2004.
Source Code:
Examples and Tests:
HEX_CVT3 puts a set of 139 nodes into the double hexagonal
hole region using CVT techniques.
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.
Last revised on 01 October 2009.