TABLE_DELAUNAY\
Triangulate Points in 2D {#table_delaunay-triangulate-points-in-2d align=”center”}
========================
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: {#usage align=”center”}
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: {#licensing align=”center”}
The computer code and data files described and made available on this
web page are distributed under the GNU LGPL
license.
Languages: {#languages align=”center”}
TABLE_DELAUNAY is available in a C++
version and a
FORTRAN90 version and
a MATLAB version.
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: {#reference align=”center”}
- Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,\
Computational Geometry,\
Springer, 2000,\
ISBN: 3-540-65620-0,\
LC: QA448.D38.C65.
- Herbert Edelsbrunner,\
Geometry and Topology for Mesh Generation,\
Cambridge, 2001,\
ISBN: 0-521-79309-2,\
LC: QA377.E36.
- Barry Joe,\
GEOMPACK - a software package for the generation of meshes using
geometric algorithms,\
Advances in Engineering Software,\
Volume 13, pages 325-331, 1991.
- Joseph ORourke,\
Computational Geometry,\
Second Edition,\
Cambridge, 1998,\
ISBN: 0521649765,\
LC: QA448.D38.
- Per-Olof Persson, Gilbert Strang,\
A Simple Mesh Generator in MATLAB,\
SIAM Review,\
Volume 46, Number 2, pages 329-345, June 2004.
Source Code: {#source-code align=”center”}
Examples and Tests: {#examples-and-tests align=”center”}
HEX_CVT3 puts a set of 139 nodes into the double hexagonal hole
region using CVT techniques.
List of Routines: {#list-of-routines align=”center”}
- 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.