TRIANGULATION
Triangulation of 2D data
TRIANGULATION
is a C++ library which
computes a triangulation of
a set of points in 2D, and carries out various other related
operations on triangulations of order 3 or 6.
The mesh is the collection of triangles. Each triangle
is termed an "element". The points used to define the shape of the
triangle (the corners, and sometimes a few more points) are called
the "nodes".
Routines are available to:

evaluate "quality measures" for the mesh;

create a "node neighbor array" for each node;

create an "element neighbor array" for each element;

estimate the integral of a function over the region covered by the mesh;

plot the nodes and elements of a mesh;

determine the parts of the mesh that lie on the boundary;

sample points at random from the region covered by the mesh;

search a mesh to determine which element contains a point.
Since triangulations are often used to define a finite element
mesh, which in turn defines a sparse matrix, there are routines
available which can define the sparse compressed column arrays
needed for a sparse matrix associated with a mesh of order 3
or 6. The special case of the TaylorHood mixed element is also
handled, which is essentially an order 6 grid counted twice
and an order 3 grid that only uses the vertices of the order 6 grid.
Licensing:
The computer code and data files described and made available on this web page
are distributed under
the GNU LGPL license.
Languages:
TRIANGULATION is available in
a C version and
a C++ version and
a FORTRAN77 version and
a FORTRAN90 version and
a MATLAB version.
Related Programs:
MESH_TO_XML,
a C++ program which
reads information defining a 1D, 2D or 3D mesh, namely
a file of node coordinates and a file of elements defined by
node indices, and creates a corresponding XML file for input
to DOLFIN or FENICS.
TABLE_DELAUNAY,
a C++ program which
reads a file of 2d point coordinates and computes the Delaunay triangulation.
TRIANGLE,
a C program which
computes a triangulation of a geometric region.
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_DELAUNAY_DISCREPANCY,
a C++ program which
measures the amount by which a triangulation fails the local Delaunay test;
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 3node triangulation and generates
midside nodes and writes out the corresponding 6node 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 6node triangulation, and subdivides
each triangle into 4 3node 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.
References:

Franz Aurenhammer,
Voronoi diagrams 
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, September 1991, pages 345405.

Paul Bratley, Bennett Fox, Linus Schrage,
A Guide to Simulation,
Second Edition,
Springer, 1987,
ISBN: 0387964673.

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

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

Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
Academic Press, 1978,
ISBN: 0125192606,
LC: QA164.N54.

Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu,
Spatial Tessellations:
Concepts and Applications of Voronoi Diagrams,
Second Edition,
Wiley, 2000,
ISBN: 0471986356,
LC: QA278.2.O36.

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, June 2004, pages 329345.
Source Code:
Examples and Tests:
List of Routines:

ALPHA_MEASURE determines the triangulated pointset quality measure ALPHA.

ANGLE_RAD_2D returns the angle in radians swept out between two rays in 2D.

ARC_COSINE computes the arc cosine function, with argument truncation.

AREA_MEASURE determines the area ratio quality measure.

BANDWIDTH determines the bandwidth associated with the finite element mesh.

DELAUNAY_SWAP_TEST performs the Delaunay swap test.

DIAEDG chooses a diagonal edge.

GET_SEED returns a random seed for the random number generator.

I4_MAX returns the maximum of two I4's.

I4_MIN returns the smaller of two I4's.

I4_MODP returns the nonnegative remainder of I4 division.

I4_POWER returns the value of I^J.

I4_SIGN returns the sign of an I4.

I4_SWAP switches two I4's.

I4_UNIFORM returns a scaled pseudorandom I4.

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 an I4COL.

I4COL_SORTED_UNIQUE_COUNT counts unique elements in an I4COL.

I4COL_SWAP swaps two columns of an I4COL.

I4I4_SORT_A ascending sorts a pair of I4's.

I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.

I4MAT_TRANSPOSE_PRINT_SOME prints some of an I4MAT, transposed.

I4VEC_HEAP_D reorders an I4VEC into a descending heap.

I4VEC_INDICATOR_NEW sets an I4VEC to the indicator vector.

I4VEC_MIN returns the value of the minimum element in an I4VEC.

I4VEC_PRINT prints an I4VEC.

I4VEC_REVERSE reverses the elements of an I4VEC.

I4VEC_SORT_HEAP_A ascending sorts an I4VEC using heap sort.

I4VEC_SORTED_UNIQUE finds unique elements in a sorted I4VEC.

I4VEC2_COMPARE compares pairs of integers stored in two vectors.

I4VEC2_SORT_A ascending sorts a vector of pairs of integers.

I4VEC2_SORTED_UNIQUE keeps the unique elements in a array of pairs of integers.

LRLINE determines where a point lies in relation to a directed line.

LVEC_PRINT prints a logical vector.

NODE_MERGE detects nodes that should be merged.

NS_ADJ_COL_SET sets the COL array in a Navier Stokes triangulation.

NS_ADJ_COUNT counts adjacencies in a Navier Stokes triangulation.

NS_ADJ_INSERT inserts an adjacency into a compressed column adjacency matrix.

NS_ADJ_ROW_SET sets the Navier Stokes sparse compressed column row indices.

PERM_CHECK checks that a vector represents a permutation.

PERM_INVERSE inverts a permutation "in place".

POINTS_DELAUNAY_NAIVE_2D computes the Delaunay triangulation in 2D.

POINTS_HULL_2D computes the convex hull of a set of nodes in 2D.

POINTS_POINT_NEAR_NAIVE_ND finds the nearest point to a given point in ND.

Q_MEASURE determines the triangulated pointset quality measure Q.

QUAD_CONVEX_RANDOM returns a random convex quadrilateral.

R4_ABS returns the absolute value of an R4.

R4_NINT returns the nearest integer to an R4.

R8_ABS returns the absolute value of an R8.

R8_EPSILON returns the roundoff unit for R8 arithmetic.

R8_HUGE returns the largest legal 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.

R8_UNIFORM_01 returns a unit pseudorandom R8.

R82VEC_PERMUTE permutes an R82VEC in place.

R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R82VEC.

R8MAT_PRINT prints an R8MAT, with an optional title.

R8MAT_PRINT_SOME prints some of an R8MAT.

R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.

R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.

R8MAT_UNIFORM_01 returns a unit pseudorandom R8MAT.

R8TRIS2 constructs a Delaunay triangulation of 2D vertices.

R8VEC_BRACKET searches a sorted array for successive brackets of a value.

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.

SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.

SWAPEC swaps diagonal edges until all triangles are Delaunay.

TIMESTAMP prints the current YMDHMS date as a time stamp.

TRIANGLE_ANGLES_2D computes the angles of a triangle in 2D.

TRIANGLE_AREA_2D computes the area of a triangle in 2D.

TRIANGLE_CIRCUMCENTER_2D computes the circumcenter of a triangle in 2D.

TRIANGLE_ORDER3_PHYSICAL_TO_REFERENCE maps physical points to reference points.

TRIANGLE_ORDER3_REFERENCE_TO_PHYSICAL maps reference points to physical points.

TRIANGLE_ORDER6_PHYSICAL_TO_REFERENCE maps a physical point to a reference point.

TRIANGLE_ORDER6_REFERENCE_TO_PHYSICAL maps reference points to physical points.

TRIANGLE_REFERENCE_SAMPLE returns random points in the reference triangle.

TRIANGLE_SAMPLE returns random points in a triangle.

TRIANGULATION_DELAUNAY_DISCREPANCY reports if a triangulation is Delaunay.

TRIANGULATION_ORDER3_NEIGHBOR_TRIANGLES determines triangle neighbors.

TRIANGULATION_NODE_ORDER determines the order of nodes in a triangulation.

TRIANGULATION_ORDER3_ADJ_COUNT counts adjacencies in a triangulation.

TRIANGULATION_ORDER3_ADJ_SET sets adjacencies in a triangulation.

TRIANGULATION_ORDER3_ADJ_SET2 sets adjacencies in a triangulation.

TRIANGULATION_ORDER3_BOUNDARY_EDGE_COUNT counts the boundary edges.

TRIANGULATION_ORDER3_BOUNDARY_EDGE_COUNT_EULER counts boundary edges.

TRIANGULATION_ORDER3_BOUNDARY_NODE indicates nodes on the boundary.

TRIANGULATION_ORDER3_CHECK makes some simple checks on a triangulation.

TRIANGULATION_ORDER3_EDGE_CHECK checks the edges of a triangulation.

TRIANGULATION_ORDER3_EXAMPLE1 sets up a sample triangulation.

TRIANGULATION_ORDER3_EXAMPLE1_SIZE sets sizes for a sample triangulation.

TRIANGULATION_ORDER3_EXAMPLE2 sets up a sample triangulation.

TRIANGULATION_ORDER3_EXAMPLE2_SIZE sets sizes for a sample triangulation.

TRIANGULATION_ORDER3_NEIGHBOR determines a neighbor of a given triangle.

TRIANGULATION_ORDER3_NEIGHBOR_NODES determines node neighbors.

TRIANGULATION_ORDER3_NEIGHBOR_NODES_PRINT prints a node neighbor array.

TRIANGULATION_ORDER3_PLOT plots a triangulation of a set of nodes.

TRIANGULATION_ORDER3_PRINT prints information defining a triangulation.

TRIANGULATION_ORDER3_QUAD approximates an integral over a triangulation.

TRIANGULATION_ORDER3_REFINE_COMPUTE computes a refined order 3 triangulation.

TRIANGULATION_ORDER3_REFINE_SIZE sizes a refined order 3 triangulation.

TRIANGULATION_ORDER3_SAMPLE returns random points in a triangulation.

TRIANGULATION_ORDER4_PLOT plots a 4node triangulation.

TRIANGULATION_ORDER6_ADJ_COUNT counts adjacencies in a triangulation.

TRIANGULATION_ORDER6_ADJ_SET sets adjacencies in a triangulation.

TRIANGULATION_ORDER6_BOUNDARY_EDGE_COUNT counts the boundary edges.

TRIANGULATION_ORDER6_BOUNDARY_EDGE_COUNT_EULER counts boundary edges.

TRIANGULATION_ORDER6_BOUNDARY_NODE indicates nodes on the boundary.

TRIANGULATION_ORDER6_EXAMPLE1 sets up a sample triangulation.

TRIANGULATION_ORDER6_EXAMPLE1_SIZE sets sizes for a sample triangulation.

TRIANGULATION_ORDER6_EXAMPLE2 sets up a sample triangulation.

TRIANGULATION_ORDER6_EXAMPLE2_SIZE sets sizes for a sample triangulation.

TRIANGULATION_ORDER6_NEIGHBOR determines a neighbor of a given triangle.

TRIANGULATION_ORDER6_PLOT plots a 6node triangulation of a set of nodes.

TRIANGULATION_ORDER6_PRINT prints information defining a triangulation.

TRIANGULATION_ORDER6_REFINE_COMPUTE computes a refined order 6 triangulation.

TRIANGULATION_ORDER6_REFINE_SIZE sizes a refined order 6 triangulation.

TRIANGULATION_ORDER6_TO_ORDER3 linearizes a quadratic triangulation.

TRIANGULATION_ORDER6_VERTEX_COUNT counts vertex nodes in a triangulation.

TRIANGULATION_SEARCH_DELAUNAY searches a triangulation for a point.

TRIANGULATION_SEARCH_NAIVE naively searches a triangulation for a point.

VBEDG determines which boundary edges are visible to a point.

VORONOI_POLYGON_AREA computes the area of a Voronoi polygon.

VORONOI_POLYGON_CENTROID_2D computes the centroid of a Voronoi polygon.

VORONOI_POLYGON_VERTICES_2D computes the vertices of a Voronoi polygon.
You can go up one level to
the C++ source codes.
Last revised 11 September 2009.