DISTMESH
A Simple Mesh Generator in MATLAB
DISTMESH
is a MATLAB program which generates
and manipulates unstructured meshes in 2D, 3D and general ND,
by PerOlof Persson.
The code is relatively simple, and the user is able to define
a variety of geometric shapes, and desired mesh densities.
DISTMESH can be a very quick and flexible means of computing
a set of points in a region. However, keep in mind the following
considerations:

Especially if you are have specified some fixed points which
must appear in the mesh, it is possible for DISTMESH
to return multiple instances of the same point. For finite
element applications, in particular, this can result in
catastrophe. The program TABLE_MERGE can fix this.

The nodes produced by DISTMESH are not ordered or sorted
in any way whatsoever.

Because the nodes are not ordered in any way, the triangular
elements produced by DISTMESH will typically contain
nodes with widely ranging indices. For finite element
applications, this can result in a system matrix with an
unnecessarily high bandwidth. The program
TRIANGULATION_RCM can fix this, after the fact.

The triangles produced by DISTMESH are not necessarily
oriented; they are just as likely to have positive or negative
orientation. Some finite element programs insist that all
triangles have positive orientation. The program
TRIANGULATION_ORIENT can fix this, after the fact.

When DISTMESH is trying to approximate a boundary, particularly
a long straight boundary, it is possible for several points
that really belong on the boundary to be slightly out of line.
This means that they will be used to form a triangle, of
very small area, and terrible conditioning. This can result
in perplexing problems near the boundary.

Because DISTMESH uses tolerances, it is possible for
some nodes to lie outside the boundary of the region; it is
possible for some triangles on the boundary to lie partially
outside the region; it is possible for triangles that lie
partly on the boundary, but entirely within the region, to
be deleted, leaving a triangular hole.

Once you have the mesh, you may want to know which nodes lie
on the boundary. You'll want this information, for instance, if
you need to impose boundary conditions on such nodes. You can
get a list of the boundary nodes using the program
TRIANGULATION_BOUNDARY_NODES.
Usage:
[ p, t ] = distmesh_2d ( fd, fh, h,
box, iteration_max, fixed );
where:

fd, the name of a distance function defining the region;

fh, the name of a mesh density function;

h, the nominal mesh spacing;

box, defining a box that contains the region;

iteration_max, the maximum number of iterations;

fixed, a list of points which must be included in the mesh,
or '[]', if no fixed points are given.

p, (output), a list of node coordinates;

t, (output), a list of node indices forming triangles;
Licensing:
DISTMESH is Copyright (C) 2004 PerOlof Persson.
This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2 of the License, or (at your
option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
59 Temple Place  Suite 330, Boston, MA 021111307, USA.
If you use DISTMESH in any program or publication, please
acknowledge its authors by citing the reference.
Languages:
DISTMESH is available in
a MATLAB version.
Related Data and Programs:
DIST_PLOT,
a MATLAB program which
creates a color contour plot of the
distance functions that are used by DISTMESH.
DISTMESH_3D,
a MATLAB program which
is a subset of the DISTMESH routines, exclusively for 3D problems.
MESH2D,
a MATLAB library which
can automatically create a triangular mesh for a given polygonal region,
by Darren Engwirda.
POINT_MERGE,
a MATLAB library which
considers N points in M dimensional space, and counts or indexes
the unique or "tolerably unique" items.
TABLE_IO,
a MATLAB library which
reads and writes files
using the TABLE format; these routines are used by
DISTMESH when creating some output files.
TABLE_MERGE,
a MATLAB program which
removes duplicate points from a TABLE file; it can also remove
points that are "close" to each other;
TEST_TRIANGULATION,
a MATLAB library which
defines some test regions for triangulation.
TRIANGLE,
a C program which
computes a triangulation of a geometric region,
by Jonathan Shewchuk.
TRIANGULATION_BOUNDARY_NODES,
a MATLAB program which
reads data defining a triangulation and determines which nodes lie on the boundary.
TRIANGULATION_DISPLAY_OPENGL,
a C++ program which
reads files defining a triangulation and displays an image
using Open GL.
TRIANGULATION_L2Q,
a MATLAB program which
reads data defining a linear triangulation and adds midpoint nodes to create
a quadratic triangulation.
TRIANGULATION_MASK,
a MATLAB program which
is compiled with a user routine that defines a region; it
then reads data defining a triangulation and removes all triangles
that are outside the region. This is one way to clean up an
unconstrained Delaunay triangulation of a nonconvex region.
TRIANGULATION_ORDER3,
a data directory which
discusses order 3 triangulations;
The node and triangle files output by DISTMESH are an example
of such 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 which
plots a triangulation.
TRIANGULATION_RCM,
a MATLAB program which
reads data defining a triangulation, and uses the Reverse
Cuthill McKee algorithm to reorder the nodes so as the reduce
the bandwidth of the corresponding adjacency matrix. This can
be very helpful for cases where the data is to be handled by a
frontal technique, or treated as a banded linear system.
TRIANGULATION_REFINE,
a MATLAB program which
reads data defining a triangulation and creates a refinement of the
triangulation by subdividing each triangle.
Author:
PerOlof Persson.
Reference:

http://math.mit.edu/~persson/
PerOlof Persson's web site.

PerOlof Persson and Gilbert Strang,
A Simple Mesh Generator in MATLAB,
SIAM Review,
Volume 46, Number 2, June 2004, pages 329345.
Source Code:

boundedges.m
finds the surface edges in a triangular mesh.

circumcenter.m
computes the circumcenters of the triangles that form a triangulation
of a set of nodes.

dcircle.m
returns the signed distance of one or more points to a circle.

ddiff.m
returns the signed distance of one or more points to a region
defined as the set difference of two regions.

dexpr.m
returns the signed distance of one or more points to a region
defined by a general symbolic expression.

dintersect.m
returns the signed distance to a region that is the intersection
of two regions.

distmesh_2d.m
computes a mesh of a given 2D region.

distmesh_nd.m
computes a mesh of a given ND region.

dmatrix.m
returns the signed distance to a region by interpolation of
known distance values on a Cartesian grid.

dpoly.m
returns the signed distance of one or more points to a polygon.

drectangle.m
returns the signed distance of one or more points to a rectangle.

drectangle0.m,
returns the signed distance of one or more points to a rectangle.

dsegment.cpp
(C++ file), a version of the algorithm for the signed distance
of one or more points to a set of line segments, for use with
a nonWindows version of MATLAB. This file must be compiled,
and the corresponding MEX file must be available to define the
MATLAB/C++ interface.

dsegment.dll
(binary file), a Windows DLL file, returns the signed distance
of one or more points to a set of line segments.

dsegment.m
a pure MATLAB version of DSEGMENT, which returns the signed distance
of one or more points to a set of line segments. This routine
will be significantly slower than the MEXGLX or DLL versions.

dsegment.mexglx
(binary file), used on nonWindows machines to allow MATLAB
to calculate the DSEGMENT algorithm (distance to a line segment)
by calling a compiled C++ routine (dsegment.cpp).

dsphere.m
returns the signed distance of one or more points to a sphere.

dunion.m
returns the signed distance to a region that is the union of
two regions.

file_column_count.m
counts the number of columns in a table file.

file_row_count.m
counts the number of rows in a table file.

hmatrix.m
computes the mesh size function by interpolation from values
specified on a Cartesian grid.

huniform.m
computes a uniform mesh size function.

i4mat_data_read.m
reads the data of an I4MAT file.

i4mat_header_read.m
reads the header of an I4MAT file.

i4mat_read.m
reads an I4MAT file.

i4mat_write.m
writes an I4MAT file.

meshdemo_nd.m
demonstrates the use of the program for higher dimensional problems.

post_2d.m
performs postprocessing for output from DISTMESH_2D.

protate.m
rotates a set of points by a given angle.

pshift.m
shifts a set of points by a given increment.

r8mat_data_read.m
reads the data of an R8MAT file.

r8mat_header_read.m
reads the header of an R8MAT file.

r8mat_write.m
writes an R8MAT file.

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

s_word_count.m
counts the number of "words" in a string.

simp_plot_2d.m
displays a plot of the triangles that form a mesh in 2D.

simp_plot_2d_demo.m
reads and displays the node and triangle data for each problem.

simp_plot_3d.m
displays a plot of the tetrahedrons that form a mesh in 3D.

simpqual.m
computes the simplex quality of the mesh.

simpvol.m
computes the volume of a simplex.

surftri.m
finds the surface triangles in a tetrahedral mesh.

timestamp.m
prints the current YMDHMS time as a timestamp.

triangulation_order3_plot.m
writes a PostScript file containing an image of the mesh.

uniformity.m
computes the uniformity of the mesh.
Examples and Tests:
MESHDEMO_2D runs all the 2D tests:
P01 is the circle:
P02 is the circle with a hole:
P03 is the square with a circular hole:
P04 is the hexagon with a hexagonal hole:
P05 is the horn:
P06 is the superellipse:
P07 is the bicycle seat:
P08 is the holey pie slice:
P09 is Jeff Borggaard's square with two hexagonal holes:
P10 is the unit square, with uniform density.
P11 is the Lshaped region:
P12 is the John Shadid's Hshaped region:
P13 is the Sandia fork:
P14 is Marcus Garvie's Lake Alpha, with Beta Island:
P15 is Sangbum Kim's forward step region:
P16 is Kevin Pond's elbow, a quarter of a circular annulus:
P17 is a rectangular region with a Reuleaux triangle obstacle.
P18 is a dumbbell shape, two circles connected by a rectangular channel.

p18_demo.m
runs the problem.

p18_fd.m
the signed distance function.

P18_UNIFORM uses a uniform density:

P18_NONUNIFORM uses a nonuniform density:
P19 is a triangle:
P20 is a rough draft of the first floor of ICAM's Wright House:

p20_demo.m
runs the problem.

p20_fd.m
the signed distance function.

P20_UNIFORM uses a uniform density:

P20_NONUNIFORM uses a nonuniform density:
P21 is Zhu Wang's 3x3 square with a "quarter round" bite taken out.
P22 is HansWerner van Wyk's "Big C", which allows two
portions of the region to be "physically close" although a
path from one portion to the other must take the long way around.
P23 is Mike Schneier's unit square, with nonuniform density.
P24 is the outline of a hand, with nonuniform density.
You can go up one level to
the MATLAB source codes.
Last revised on 18 January 2016.