TRIANGULATION
Triangulation of 2D data
TRIANGULATION,
a MATLAB 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 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 FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
CVT_TRIANGULATION,
a FORTRAN90 program which
uses routines from the TEST_TRIANGULATION library
to create a CVTbased triangularization.
DISTMESH,
a MATLAB program which
takes the definition of
a 2D region, and fills it up with a set of nodes, and triangulates
those nodes to make a triangulation of the region. The region may
be nonconvex and may include holes; the user may request a specific
density for the nodes, and may require certain points to be in the
set of nodes.
MESH_BANDWIDTH,
a MATLAB program which
returns the geometric bandwidth associated with a mesh of
elements of any order and in a space of arbitrary dimension.
MESH_TO_XML,
a MATLAB 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.
MESH2D,
a MATLAB library which
can automatically create a triangular mesh for a given polygonal region,
by Darren Engwirda.
TABLE_DELAUNAY,
a MATLAB program which
triangulates a set of nodes whose coordinates are
stored in a file.
TEST_TRIANGULATION,
a MATLAB library which
can set up a number of triangulation test problems.
TRIANGLE,
a C program which
computes a triangulation of a geometric region,
by Jonathan Shewchuk.
triangulation_test
TRIANGULATION_BOUNDARY_EDGES,
a MATLAB program which
reads data defining a triangulation, determines which edges
lie on the boundary, organizes them into connected components,
and writes this information to a file.
TRIANGULATION_BOUNDARY_NODES,
a MATLAB program which
reads data defining a triangulation, determines which nodes
lie on the boundary, and writes their coordinates to a file.
TRIANGULATION_CORNER,
a MATLAB program which
patches triangulations so that no triangle has two sides on the boundary.
TRIANGULATION_DELAUNAY_DISCREPANCY,
a MATLAB program which
measures the amount by which a triangulation fails the local Delaunay test;
TRIANGULATION_DISPLAY,
a MATLAB program which
displays the nodes and elements of a triangulation on the MATLAB graphics screen;
TRIANGULATION_DISPLAY_OPENGL,
a C++ program which
reads files defining a triangulation and displays an image using Open GL.
TRIANGULATION_HISTOGRAM,
a MATLAB program which
computes histograms of data over a triangulation.
TRIANGULATION_L2Q,
a MATLAB program which
reads data defining a 3node triangulation and generates
midside nodes and writes out the corresponding 6node triangulation.
TRIANGULATION_MASK,
a MATLAB program which
takes an existing triangulation and deletes triangles and
their corresponding nodes as requested by the user.
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 MATLAB 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 MATLAB program
that reads data defining a triangulation and creates a
PostScript image of the nodes and triangles.
TRIANGULATION_Q2L,
a MATLAB 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 MATLAB program which
estimates the integral of a function over a triangulated region.
TRIANGULATION_QUALITY,
a MATLAB program which
reads data defining a triangulation and computes a number
of quality measures.
TRIANGULATION_RCM,
a MATLAB 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 MATLAB 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_TO_GMSH,
a MATLAB program which
reads a file of node coordinates and a file of elements defined by
node indices, and creates a corresponding Gmsh mesh file.
TRIANGULATION_TRIANGLE_NEIGHBORS,
a MATLAB program which
reads data defining a triangulation, determines the neighboring
triangles of each triangle, and writes that information to a file.
TSEARCH,
a MATLAB library which
compares several replacements for MATLAB's obsolete tsearch() function,
which searched a Delaunay triangulation to find the triangle
that encloses a given point.
Reference:

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, Number 5, 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:

alpha_measure.m,
measures the triangulated point set quality measure ALPHA.

angle_rad_2d.m,
returns the angle swept out by two rays in 2D;

area_measure.m,
measures the triangulated point set area ratio quality measure.

bandwidth.m,
determines the bandwidth associated with the finite element mesh;

delaunay_swap_test.m,
chooses a diagonal edge;

diaedg.m,
chooses a diagonal edge;

get_seed.m,
chooses an arbitrary seed for the random number generator;

i4_modp.m,
returns the nonnegative remainder of I4 division;

i4_sign.m,
returns the sign of an I4;

i4_swap.m,
swaps two I4's;

i4_wrap.m,
forces an I4 to lie in a given range;

i4col_compare.m,
compares two columns of an I4COL;

i4col_sort_a.m,
ascending sorts the columns of an I4COL;

i4col_sorted_unique_count.m,
counts the unique columns in a sorted I4COL;

i4col_swap.m,
swaps two columns of an I4COL;

i4i4_sort_a.m,
ascending sorts a pair of I4's;

i4mat_transpose_print.m,
prints an I4MAT, transposed;

i4mat_transpose_print_some.m,
prints some of an I4MAT, transposed;

i4vec_heap_d.m,
reorders an I4VEC into a descending heap;

i4vec_indicator.m,
sets an I4VEC to the indicator vector;

i4vec_print.m,
prints an I4VEC;

i4vec_sort_heap_a.m,
ascending sorts an I4VEC using heap sort;

i4vec_sorted_unique.m,
returns the unique elements in a sorted I4VEC;

i4vec2_compare.m,
compares pairs of elements in an I4VEC2;

i4vec_sorta.m,
ascending sorts an I4VEC2;

i4vec2_sorted_unique.m,
returns the unique elements in a sorted I4VEC2;

lrline.m,
determines if a point is left or right of a directed line;

lvec_print.m,
prints an LVEC.

mesh_base_one.m
adjusts a mesh to use 1based indexing.

mesh_base_zero.m
adjusts a mesh to use 0based indexing.

node_merge.m,
detects nodes that should be merged.

ns_adj_col_set.m,
sets up the column vector associated with the sparse compressed
column storage of the variable adjacencies in a TaylorHood
order 3/order 6 triangulation for Navier Stokes velocity and pressure.

ns_adj_count.m,
counts the variable adjacencies in a TaylorHood order 3/order 6
triangulation for Navier Stokes velocity and pressure.

ns_adj_insert.m,
inserts an adjacency into a compressed column adjacency matrix.

ns_adj_row_set.m,
sets the Navier Stokes sparse compressed column row indices.

perm_check.m,
checks that a permutation of 1:N is valid;

perm_check2.m,
checks that a permutation of BASE:BASE+N1 is valid;

perm_inverse.m,
computes the inverse of a permutation;

points_delaunay_naive_2d.m,
a "naive" algorithm for computing the Delaunay triangulation
of a set of points in 2D;

points_hull_2d.m,
computes the convex hull of a set of points in 2D;

points_point_near_naive_nd.m,
finds the nearest of a set of points to a point in ND;

q_measure.m,
measures the triangulated point set quality measure Q.

quad_convex_random.m,
returns a random convex quadrilateral in the unit square.

r4_uniform_01.m,
returns a random R4 in [0,1];

r8_acos.m,
computes the inverse cosine;

r8_huge.m,
returns a huge R8;

r8_uniform_01.m,
returns a random R8 in [0,1];

r82vec_permute.m,
permutes an R82VEC in place;

r82vec_sort_heap_index_a.m,
does an indexed heap ascending sort of an R82VEC;

r8mat_print.m,
prints an R8MAT;

r8mat_print_some.m,
prints some of an R8MAT;

r8mat_transpose_print.m,
prints the transpose of an R8MAT;

r8mat_transpose_print_some.m,
prints some of the transpose of an R8MAT;

r8mat_uniform_01.m,
returns a unit pseudorandom R8MAT.

r8tris2.m,
computes the Delaunay triangulation of a set of points in 2D;

r8vec_bracket.m,
searches a sorted R8VEC for brackets of a value;

s_len_trim.m,
returns the length of a string to the last nonblank;

sort_heap_external.m,
externally sorts a list of values into ascending order;

swapec.m,
swaps diagonal edges until all triangles are Delaunay;

timestamp.m,
prints the current YMDHMS date as a timestamp;

triangle_angles_2d.m,
returns the angles of a triangle in 2D;

triangle_area_2d.m,
returns the area of a triangle in 2D;

triangle_circumcenter_2d.m,
returns the circumcenter of a triangle in 2D;

triangle_reference_sample.m,
randomly samples a point from the reference triangle;

triangle_sample.m,
randomly samples a point from a triangle;

triangulation_area.m
returns the area of a triangulation.

triangulation_areas.m
returns the triangle areas in a triangulation.

triangulation_delaunay_discrepancy_compute.m
reports if a triangulation is Delaunay.

triangulation_neighhbor_elements.m,
determines element neighbors in a triangulation;

triangulation_node_order.m,
determines the order of the nodes in a triangulation;

triangulation_order3_adj_count.m,
counts adjacencies in an order 3 triangulation;

triangulation_order3_adj_set.m,
records adjacencies in an order 3 triangulation;

triangulation_order3_adj_set2.m,
records adjacencies in an order 3 triangulation;

triangulation_order3_adjacency.m,
sets the full adjacency matrix for an order 3 triangulation.

triangulation_order3_boundary_edge_count.m,
determines the number of boundary edges in an order 3 triangulation;

triangulation_order3_boundary_edge_count_euler.m,
uses Euler's formula to determine the number of boundary edges
in an order 3 triangulation;

triangulation_order3_boundary_node.m,
determines the boundary nodes in an order 3 triangulation;

triangulation_order3_check.m,
carries out some simple checks on an order 3 triangulation;

triangulation_order3_edge_check.m,
checks the edges of an order 3 triangulation;

triangulation_order3_example1.m,
returns an example order 3 triangulation;

triangulation_order3_example1_size.m,
returns the sizes of arrays in an example order 3 triangulation;

triangulation_order3_example2.m,
returns an example order 3 triangulation;

triangulation_order3_example2_size.m,
returns the sizes of arrays in an example order 3 triangulation;

triangulation_order3_neighhbor.m,
determines a neighbor of a given triangle in an order 3 triangulation;

triangulation_order3_neighhbor_nodes.m,
determines the neighbors of nodes in an order 3 triangulation;

triangulation_order3_neighhbor_nodes_print.m,
prints information about an order 3 triangulation neighbor nodes;

triangulation_order3_plot.m,
creates a EPS image of an order 3 triangulation;

triangulation_order3_print.m,
prints information about an order 3 triangulation;

triangulation_order3_quad.m,
approximates the integral of a function over
an order 3 triangulation.

triangulation_order3_refine_compute.m,
computes a refinement of an order3 mesh

triangulation_order3_refine_size.m,
sizes a refinement of an order3 mesh;

triangulation_order3_sample.m,
returns random points in an order 3 triangulation;

triangulation_order4_plot.m,
creates a EPS image of an order 4 triangulation;

triangulation_order6_adj_count.m,
counts adjacencies in an order 6 triangulation;

triangulation_order6_adj_set.m,
records adjacencies in an order 6 triangulation;

triangulation_order6_boundary_edge_count.m,
determines the number of boundary edges in an order 6 triangulation;

triangulation_order6_boundary_edge_count_euler.m,
uses Euler's formula to determine the number of boundary edges
in an order 6 triangulation;

triangulation_order6_boundary_node.m,
determines the boundary nodes in an order 6 triangulation;

triangulation_order6_example1.m,
returns an example order 6 triangulation;

triangulation_order6_example1_size.m,
returns the sizes of arrays in an example order 6 triangulation;

triangulation_order6_example2.m,
returns an example order 6 triangulation;

triangulation_order6_example2_size.m,
returns the sizes of arrays in an example order 6 triangulation;

triangulation_order6_neighhbor.m,
determines a neighbor of a given triangle in an order 6 triangulation;

triangulation_order6_plot.m,
creates a EPS image of an order 6 triangulation;

triangulation_order6_print.m,
prints information about an order 6 triangulation;

triangulation_order6_refine_compute.m,
computes a refinement of an order6 mesh

triangulation_order6_refine_size.m,
sizes a refinement of an order6 mesh;

triangulation_order6_to_order3.m,
converts an order 6 triangulation to an order 3 triangulation;

triangulation_order6_vertex_count.m,
counts the number of vertex and midside nodes in an
order 6 triangulation;

triangulation_search_delaunay.m,
finds the triangle containing a point, using a Delaunay search;

triangulation_search_naive.m,
finds the triangle containing a point, using a naive search;

vbedg.m,
determines which boundary edges are visible to a point;

voronoi_polygon_area.m,
computes the area of a Voronoi polygon.

voronoi_polygon_centroid.m,
computes the centroid of a Voronoi polygon.

voronoi_polygon_vertices.m,
computes the vertices of a Voronoi polygon.
Last revised 09 April 2019.