TRIANGULATION_DELAUNAY_DISCREPANCY
Local Delaunay Discrepancy of a Triangulation

TRIANGULATION_DELAUNAY_DISCREPANCY is a C++ program which computes the local Delaunay discrepancy of a triangulation.

A (maximal) triangulation is Delaunay if and only if it is locally Delaunay.

A triangulation is Delaunay if the minimum angle over all triangles in the triangulation is maximized. That is, there is no other triangulation of the points which has a larger minimum angle.

A triangulation is locally Delaunay if, for every pair of triangles that share an edge, the minimum angle in the two triangles is larger than the minimum angle in the two triangles formed by removing the common edge and joining the two opposing vertices.

This function examines the question of whether a given triangulation is locally Delaunay. It does this by looking at every pair of neighboring triangles and comparing the minimum angle attained for the current triangle pair and the alternative triangle pair.

Let A(i,j) be the minimum angle formed by triangles T(i) and T(j), which are two triangles in the triangulation which share a common edge. Let B(I,J) be the minimum angle formed by triangles S(i) and S(j), where S(i) and S(j) are formed by removing the common edge of T(i) and T(j), and joining the opposing vertices.

Then the triangulation is Delaunay if B(i,j) <= A(i,j) for every pair of neighbors T(i) and T(j).

If A(i,j) < B(i,j) for at least one pair of neighbors, the triangulation is not a Delaunay triangulation.

This program returns VALUE = min ( A(i,j) - B(i,j) ) over all triangle neighbors. VALUE is scaled to be in degrees, for comprehensibility. If VALUE is negative, then at least one pair of triangles violates the Delaunay condition, and so the entire triangulation is not a Delaunay triangulation. If VALUE is nonnegative, then the triangulation is a Delaunay triangulation.

It is useful to return VALUE, rather than a simple True/False value, because there can be cases where the Delaunay condition is only "slightly" violated. A simple example is a triangulation formed by starting with a mesh of squares and dividing each square into two triangles by choosing one of the diagonals of the square. The Delaunay discrepancy for this mesh, if computed exactly, is 0, but roundoff could easily result in discrepancies that were very slightly negative.

If VALUE is positive, and not very small in magnitude, then every pair of triangles in the triangulation satisfies the local Delaunay condition, and so the triangulation is a Delaunay triangulation.

If VALUE is negative, and not very small in magnitude, then at least one pair of triangles violates the Delaunay condition, and to a significant degree. The triangulation is not a Delaunay triangulation.

If the magnitude of VALUE is very close to zero, then the triangulation is numerically ambiguous. At least one pair of triangles violates or almost violates the condition, but no triangle violates the condition to a great extent. The user must judge whether the violation is significant or not.

Usage:

triangulation_delaunay_discrepancy prefix

• prefix_nodes.txt, the node coordinates;
• prefix_elements.txt, the element definitions.

Licensing:

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

Languages:

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

Related Data and Programs:

TABLE_DELAUNAY, a C++ program which triangulates a set of nodes whose coordinates are stored in a file.

TRIANGLE, a C program which computes a triangulation of a geometric region.

TRIANGULATION, a C++ library which carries out various operations on order 3 ("linear") or order 6 ("quadratic") triangulations.

TRIANGULATION_BOUNDARY_NODES, a C++ program which reads data defining a triangulation, determines which nodes lie on the boundary, and writes their coordinates to a file.

TRIANGULATION_CORNER, a C++ program which patches triangulations so that no triangle has two sides on the boundary.

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

TRIANGULATION_HISTOGRAM, a C++ program which computes histograms of data over a triangulation.

TRIANGULATION_L2Q, a C++ program which reads data defining a 3-node triangulation and generates midside nodes and writes out the corresponding 6-node triangulation.

TRIANGULATION_MASK, a C++ program which takes an existing triangulation and deletes triangles and their corresponding nodes as requested by the user.

TRIANGULATION_NODE_TO_ELEMENT, a C++ program which reads files describing a set of nodes, their triangulation, and the value of one or more quantities at each node, and outputs a file that averages the quantities for each element. This operation in effect creates an "order1" finite element model of the data.

TRIANGULATION_ORDER3, a directory which contains a description and examples of order 3 triangulations.

TRIANGULATION_ORDER6, a directory which contains a description and examples of order 6 triangulations.

TRIANGULATION_ORIENT, a C++ program which reads data defining a triangulation, makes sure that every triangle has positive orientation, and if not, writes a corrected triangle file.

TRIANGULATION_PLOT, a C++ program which reads data defining a triangulation and creates a PostScript image of the nodes and triangles.

TRIANGULATION_Q2L, a C++ program which reads data defining a 6-node triangulation, and subdivides each triangle into 4 3-node triangles, writing the resulting triangulation to a file.

TRIANGULATION_QUAD, a C++ program which estimates the integral of a function over a triangulated region.

TRIANGULATION_QUALITY, a C++ program which reads data defining a triangulation and computes a number of quality measures.

TRIANGULATION_RCM, a C++ program which reads data defining a triangulation, determines an ordering of the nodes that will reduce the bandwidth of the adjacency matrix, and writes the new triangulation information to a file.

TRIANGULATION_REFINE, a C++ program which reads data defining a triangulation, replaces each triangle by four congruent smaller ones, and writes the new triangulation information to a file.

TRIANGULATION_TRIANGLE_NEIGHBORS, a C++ program which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, September 1991, pages 345-405.
2. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0,
   LC: QA448.D38.C65.
3. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, Number 5, 1991, pages 325-331.
4. Joseph ORourke,
   Computational Geometry,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.

Source Code:

• triangulation_delaunay_discrepancy.cpp, the source code.

Examples and Tests:

TEN3 is a triangulation of 10 nodes. It is a Delaunay triangulation.

• ten3_nodes.txt, the nodes.
• ten3_elements.txt, commands to compile and run the sample program.
• ten3.png, an image of the triangulation.
• ten3_output.txt, output from the program.

TED3 is a triangulation of 10 nodes. It is NOT a Delaunay triangulation.

• ted3_nodes.txt, the nodes.
• ted3_elements.txt, commands to compile and run the sample program.
• ted3.png, an image of the triangulation.
• ted3_output.txt, output from the program.

List of Routines:

• MAIN is the main program for TRIANGULATION_DELAUNAY_DISCREPANCY.
• ARC_COSINE computes the arc cosine function, with argument truncation.
• 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.
• FILE_COLUMN_COUNT counts the columns in the first line of a file.
• FILE_EXIST reports whether a file exists.
• 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_WRAP forces an I4 to lie between given limits by wrapping.
• I4COL_COMPARE compares columns I and J of an I4COL.
• I4COL_SORT_A ascending sorts the columns of an I4COL.
• I4COL_SWAP swaps two columns of an I4COL.
• I4MAT_DATA_READ reads data from an I4MAT file.
• I4MAT_HEADER_READ reads the header from an I4MAT file.
• I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of an I4MAT, transposed.
• R8_HUGE returns a "huge" R8.
• R8_MIN returns the minimum of two R8's.
• R8MAT_DATA_READ reads the data from an R8MAT file.
• R8MAT_HEADER_READ reads the header from an R8MAT file.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• R8VEC_MAX returns the value of the maximum element in an R8VEC.
• R8VEC_MIN returns the value of the minimum element in an R8VEC.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• S_TO_I4 reads an I4 from a string.
• S_TO_I4VEC reads an I4VEC from a string.
• 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.
• SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRIANGLE_ANGLES_2D_NEW computes the angles of a triangle in 2D.
• TRIANGULATION_DELAUNAY_DISCREPANCY_COMPUTE reports if a triangulation is Delaunay.
• TRIANGULATION_ORDER3_NEIGHBOR_TRIANGLES determines triangle neighbors.

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