TABLE_DELAUNAY
Triangulate Points in 2D

TABLE_DELAUNAY is an executable C++ program, using double precision arithmetic, which computes the Delaunay triangulation of a set of points in the plane.

Specifically, TABLE_DELAUNAY reads a data file in real TABLE file format, containing the point coordinates, computes the Delaunay triangulation, writes out another file (in integer TABLE file format) containing the indices of the points that form each triangle, and also creates an Encapsulated PostScript file containing an image of the triangulation.

Usage:

table_delaunay points.txt

reads the node information in points.txt, creates a triangulation file in points.delaunay.txt, and a PostScript image of the triangulation in points.delaunay.eps.

Related Programs:

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

GEOMPACK is a C++ library written by Barry Joe, containing the routines used for computing the Delaunay triangulation.

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

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

TABLE_BARPLOT_PPMA is an executable FORTRAN90 program which reads a table file and creates a PPMA bargraph of the data.

TABLE_BORDER is an executable FORTRAN90 program which can be used to add a border (of zero values) to a table file.

TABLE_COLUMNS is an executable FORTRAN90 program which can extract specific columns of data from a table file.

TABLE_DELAUNAY is also available in a FORTRAN90 version.

TABLE_DIAPHONY is an executable FORTRAN90 program which computes the diaphony of a set of points stored in a table file.

TABLE_HISTOGRAM is an executable FORTRAN90 program which can make a histogram of a set of points stored in a table file.

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

TABLE_LATINIZE is a FORTRAN90 program that reads a file of points and creates a "latinized" version by adjusting the data.

TABLE_MERGE is a FORTRAN90 program that reads a file of points, and removes duplicates, and points that are close to each other.

TABLE_ORTHONORMALIZE is a FORTRAN90 program that reads a file of points and orthonormalizes the columns.

TABLE_QUALITY is a C++ program that reads a file of points and computes the quality of dispersion.

TABLE_READ is a MATLAB script that can read in a TABLE file.

TABLE_RECORD_MATCH is an executable FORTRAN90 program that can be used to find close records in a table file.

TABLE_SCALE is an executable FORTRAN90 program that can be used to multiply the entries of a table file by a scale vector.

TABLE_SHIFT is an executable FORTRAN90 program that can be used to shift the entries of a table file by a shift vector.

TABLE_STATS is an executable FORTRAN90 program that can read a table file and compute certain statistics.

TABLE_TET_MESH is an executable FORTRAN90 program that can read a table file of 3D data, and compute a tetrahedral mesh.

TABLE_TOP is an executable FORTRAN90 program that can read a table file of M-dimensional data and make a table of plots of all pairs of coordinates.

TABLE_UNBORDER is an executable FORTRAN90 program that can be used to remove the border from a table file.

TABLE_UNIFORM_NOISE is an executable FORTRAN90 program that can be used to add a uniform noise term to the data in a table file.

TABLE_VORONOI is an executable FORTRAN90 program than can be used to compute information about the Voronoi diagram of the points.

TRIANGULATION_DISPLAY_OPEN_GL is an executable C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_L2Q is an executable C++ program which can be used to convert the triangulation from three-node triangles to six-node triangles.

TRIANGULATION_PLOT is an executable C++ program which may be used to visualize the triangulation.

TRIANGULATION_REFINE is an executable C++ program which refines a triangulation.

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

Reference:

1. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   QA377.E36,
   ISBN 0-521-79309-2.
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.
3. 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.C, the source code.
• table_delaunay.csh, commands to compile, link and load the source code.

Examples and Tests:

• hex_cvt_nodes.csh, commands to run the sample problem.
• hex_cvt_nodes.out, output from the sample problem.
• hex_cvt_nodes.txt, a (real) TABLE file describing a set of 139 points in the unit square. The points lie on the boundary or in the interior of a region that has two hexagonal holes.
• hex_cvt_nodes.png, a PNG image of the nodes.
• hex_cvt_nodes.delaunay.txt, the (integer) TABLE file, created by TABLE_DELAUNAY, describing the Delaunay triangulation of the points. There are 240 triangles. Each line lists the indices of three nodes that make up a triangle.
• hex_cvt_nodes.delaunay.png, a PNG image of the triangulated data.

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 real TABLE file.
• DTABLE_HEADER_READ reads the header from a real TABLE 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_NAME_EXT_GET determines the "extension" of a file name.
• FILE_NAME_EXT_SWAP replaces the current "extension" of a file name.
• FILE_ROW_COUNT counts the number of row records in a file.
• I4_MAX returns the maximum of two integers.
• I4_MIN returns the smaller of two integers.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_SIGN returns the sign of an integer.
• I4_WRAP forces an integer to lie between given limits by wrapping.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of an integer matrix, transposed.
• ITABLE_DATA_WRITE writes data to an integer TABLE file.
• ITABLE_HEADER_WRITE writes the header of an integer TABLE file.
• ITABLE_TRIANGULATION_WRITE writes an integer triangulation table to a file.
• I4VEC_INDICATOR sets an integer vector to the indicator vector.
• I4VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an integer vector.
• LRLINE determines where a point lies in relation to a directed line.
• PERM_INV inverts a permutation "in place".
• R8_EPSILON returns the round off unit for double precision arithmetic.
• R8_HUGE returns a "huge" double precision value.
• R8_MAX returns the maximum of two real values.
• R8_MIN returns the minimum of two real values.
• R8_NINT returns the nearest integer to a double precision value.
• R82VEC_PERMUTE permutes an R2 vector in place.
• R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R2 vector.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• S_INDEX_LAST_C returns a pointer to the last occurrence of a given character.
• 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.
• TIMESTRING returns the current YMDHMS date as a string.
• TRIANGULATION_ORDER3_PLOT_EPS plots a triangulation of a set of nodes.
• VBEDG determines which boundary edges are visible to a point.

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