triangulation
triangulation,
an Octave code 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 Taylor-Hood 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 MIT license
Languages:
triangulation is available in
a C version and
a C++ version and
a Fortran90 version and
a MATLAB version and
an Octave version.
Related Data and Programs:
triangulation_test
distmesh,
an Octave code 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,
an Octave code which
returns the geometric bandwidth associated with a mesh of
elements of any order and in a space of arbitrary dimension.
mesh2d,
an Octave code which
can automatically create a triangular mesh for a given polygonal region,
by Darren Engwirda.
test_triangulation,
an Octave code which
can set up a number of triangulation test problems.
triangulation_boundary_edges,
an Octave code 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,
an Octave code which
reads data defining a triangulation, determines which nodes
lie on the boundary, and writes their coordinates to a file.
triangulation_corner,
an Octave code which
patches triangulations so that no triangle has two sides on the boundary.
triangulation_delaunay_discrepancy,
an Octave code which
measures the amount by which a triangulation fails the local delaunay test;
triangulation_display,
an Octave code which
displays the nodes and elements of a triangulation on the MATLAB graphics screen;
triangulation_histogram,
an Octave code which
computes histograms of data over a triangulation.
triangulation_l2q,
an Octave code which
reads data defining a 3-node triangulation and generates
midside nodes and writes out the corresponding 6-node triangulation.
triangulation_mask,
an Octave code 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,
an Octave code which
reads data defining a triangulation, makes sure that
every triangle has positive orientation, and if not, writes a
corrected triangle file.
triangulation_plot,
an Octave code
that reads data defining a triangulation and creates a
postscript image of the nodes and triangles.
triangulation_q2l,
an Octave code 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,
an Octave code which
estimates the integral of a function over a triangulated region.
triangulation_quality,
an Octave code which
reads data defining a triangulation and computes a number
of quality measures.
triangulation_rcm,
an Octave code 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,
an Octave code 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,
an Octave code 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,
an Octave code which
reads data defining a triangulation, determines the neighboring
triangles of each triangle, and writes that information to a file.
Reference:
-
Franz Aurenhammer,
Voronoi diagrams -
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, September 1991, pages 345-405.
-
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: 3-540-65620-0.
-
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.
-
Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
Academic Press, 1978,
ISBN: 0-12-519260-6,
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: 0-471-98635-6,
LC: QA278.2.O36.
-
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, June 2004, pages 329-345.
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;
-
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 1-based indexing.
-
mesh_base_zero.m
adjusts a mesh to use 0-based 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 Taylor-Hood
order 3/order 6 triangulation for Navier Stokes velocity and pressure.
-
ns_adj_count.m,
counts the variable adjacencies in a Taylor-Hood 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+N-1 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_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;
-
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 04 July 2023.