GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/DelaunayTriangulation

GraphTheory

 DelaunayTriangulation
 find the Delaunay triangulation for a given list of points

 Calling Sequence DelaunayTriangulation(points)

Parameters

 points - list of 2 element lists representing n coordinates

Description

 • This function computes a Delaunay triangulation of the input points returning a sequence of two outputs: the set of triangles and an edge adjacency Matrix.
 • The Delaunay triangulation is a triangulation that maximizes the smallest angle of the triangles in the triangulation (i.e. it avoids thin triangles).
 • The triangles are returned in a set containing the three vertices of each triangle as integer references to the input points list.
 • The adjacency matrix is an n by n symmetric Matrix that contains a $1$ in entry $i,j$ if one of the triangle edges is from ${\mathrm{points}}_{i}$ to ${\mathrm{points}}_{j}$, and $0$ otherwise.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$

For this example we first construct a point list containing all points at coordinates (i,j) for i=0..4,j=0..4, and the center points of all enclosed squares (that is, (1/2,1/2)..(7/2,7/2)).

 > $\mathrm{pts}≔\mathrm{seq}\left(\left[0,j-1\right],j=1..5\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}4\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{pts}≔\mathrm{pts},\mathrm{seq}\left(\left[i-\frac{1}{2},j-\frac{1}{2}\right],j=1..4\right),\mathrm{seq}\left(\left[i,j-1\right],j=1..5\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$
 > $\mathrm{pts}≔\left[\mathrm{pts}\right]$
 ${\mathrm{pts}}{:=}\left[\left[{0}{,}{0}\right]{,}\left[{0}{,}{1}\right]{,}\left[{0}{,}{2}\right]{,}\left[{0}{,}{3}\right]{,}\left[{0}{,}{4}\right]{,}\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{1}}{{2}}{,}\frac{{3}}{{2}}\right]{,}\left[\frac{{1}}{{2}}{,}\frac{{5}}{{2}}\right]{,}\left[\frac{{1}}{{2}}{,}\frac{{7}}{{2}}\right]{,}\left[{1}{,}{0}\right]{,}\left[{1}{,}{1}\right]{,}\left[{1}{,}{2}\right]{,}\left[{1}{,}{3}\right]{,}\left[{1}{,}{4}\right]{,}\left[\frac{{3}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{3}}{{2}}{,}\frac{{3}}{{2}}\right]{,}\left[\frac{{3}}{{2}}{,}\frac{{5}}{{2}}\right]{,}\left[\frac{{3}}{{2}}{,}\frac{{7}}{{2}}\right]{,}\left[{2}{,}{0}\right]{,}\left[{2}{,}{1}\right]{,}\left[{2}{,}{2}\right]{,}\left[{2}{,}{3}\right]{,}\left[{2}{,}{4}\right]{,}\left[\frac{{5}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{5}}{{2}}{,}\frac{{3}}{{2}}\right]{,}\left[\frac{{5}}{{2}}{,}\frac{{5}}{{2}}\right]{,}\left[\frac{{5}}{{2}}{,}\frac{{7}}{{2}}\right]{,}\left[{3}{,}{0}\right]{,}\left[{3}{,}{1}\right]{,}\left[{3}{,}{2}\right]{,}\left[{3}{,}{3}\right]{,}\left[{3}{,}{4}\right]{,}\left[\frac{{7}}{{2}}{,}\frac{{1}}{{2}}\right]{,}\left[\frac{{7}}{{2}}{,}\frac{{3}}{{2}}\right]{,}\left[\frac{{7}}{{2}}{,}\frac{{5}}{{2}}\right]{,}\left[\frac{{7}}{{2}}{,}\frac{{7}}{{2}}\right]{,}\left[{4}{,}{0}\right]{,}\left[{4}{,}{1}\right]{,}\left[{4}{,}{2}\right]{,}\left[{4}{,}{3}\right]{,}\left[{4}{,}{4}\right]\right]$ (1)

Use the DelaunayTriangulation command to get the set of triangles (tris) and the adjacency matrix (amat) for the point list pts.

 > $\mathrm{tris},\mathrm{amat}≔\mathrm{DelaunayTriangulation}\left(\mathrm{pts}\right):$

Build and display a plot of all triangles.

 > $\mathrm{plt}≔\mathrm{NULL}:$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}v\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{tris}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{plt}≔\mathrm{plt},\left[{\mathrm{pts}}_{{v}_{1}},{\mathrm{pts}}_{{v}_{2}}\right],\left[{\mathrm{pts}}_{{v}_{2}},{\mathrm{pts}}_{{v}_{3}}\right],\left[{\mathrm{pts}}_{{v}_{3}},{\mathrm{pts}}_{{v}_{1}}\right]\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$
 > $\mathrm{PLOT}\left(\mathrm{CURVES}\left(\mathrm{plt},\mathrm{COLOR}\left(\mathrm{RGB},1,0,0\right)\right),\mathrm{SCALING}\left(\mathrm{CONSTRAINED}\right),\mathrm{AXESSTYLE}\left(\mathrm{BOX}\right)\right)$

Note that in the preceding plot, many of the triangles are chosen randomly because there are two optimal choices for many of the subdivisions. A slight shift of the points will make the optimal triangulation unique:

 > $\mathrm{pts}≔\mathrm{seq}\left(\left[0,j-1\right],j=1..5\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}4\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{pts}≔\mathrm{pts},\mathrm{seq}\left(\left[i-\frac{1}{2},j-0.49999\right],j=1..4\right),\mathrm{seq}\left(\left[i,j-1\right],j=1..5\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$
 > $\mathrm{pts}≔\left[\mathrm{pts}\right]$
 ${\mathrm{pts}}{:=}\left[\left[{0}{,}{0}\right]{,}\left[{0}{,}{1}\right]{,}\left[{0}{,}{2}\right]{,}\left[{0}{,}{3}\right]{,}\left[{0}{,}{4}\right]{,}\left[\frac{{1}}{{2}}{,}{0.50001}\right]{,}\left[\frac{{1}}{{2}}{,}{1.50001}\right]{,}\left[\frac{{1}}{{2}}{,}{2.50001}\right]{,}\left[\frac{{1}}{{2}}{,}{3.50001}\right]{,}\left[{1}{,}{0}\right]{,}\left[{1}{,}{1}\right]{,}\left[{1}{,}{2}\right]{,}\left[{1}{,}{3}\right]{,}\left[{1}{,}{4}\right]{,}\left[\frac{{3}}{{2}}{,}{0.50001}\right]{,}\left[\frac{{3}}{{2}}{,}{1.50001}\right]{,}\left[\frac{{3}}{{2}}{,}{2.50001}\right]{,}\left[\frac{{3}}{{2}}{,}{3.50001}\right]{,}\left[{2}{,}{0}\right]{,}\left[{2}{,}{1}\right]{,}\left[{2}{,}{2}\right]{,}\left[{2}{,}{3}\right]{,}\left[{2}{,}{4}\right]{,}\left[\frac{{5}}{{2}}{,}{0.50001}\right]{,}\left[\frac{{5}}{{2}}{,}{1.50001}\right]{,}\left[\frac{{5}}{{2}}{,}{2.50001}\right]{,}\left[\frac{{5}}{{2}}{,}{3.50001}\right]{,}\left[{3}{,}{0}\right]{,}\left[{3}{,}{1}\right]{,}\left[{3}{,}{2}\right]{,}\left[{3}{,}{3}\right]{,}\left[{3}{,}{4}\right]{,}\left[\frac{{7}}{{2}}{,}{0.50001}\right]{,}\left[\frac{{7}}{{2}}{,}{1.50001}\right]{,}\left[\frac{{7}}{{2}}{,}{2.50001}\right]{,}\left[\frac{{7}}{{2}}{,}{3.50001}\right]{,}\left[{4}{,}{0}\right]{,}\left[{4}{,}{1}\right]{,}\left[{4}{,}{2}\right]{,}\left[{4}{,}{3}\right]{,}\left[{4}{,}{4}\right]\right]$ (2)
 > $\mathrm{tris},\mathrm{amat}≔\mathrm{DelaunayTriangulation}\left(\mathrm{pts}\right):$
 > $\mathrm{plt}≔\mathrm{NULL}:$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}v\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{tris}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{plt}≔\mathrm{plt},\left[{\mathrm{pts}}_{{v}_{1}},{\mathrm{pts}}_{{v}_{2}}\right],\left[{\mathrm{pts}}_{{v}_{2}},{\mathrm{pts}}_{{v}_{3}}\right],\left[{\mathrm{pts}}_{{v}_{3}},{\mathrm{pts}}_{{v}_{1}}\right]\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$
 > $\mathrm{PLOT}\left(\mathrm{CURVES}\left(\mathrm{plt},\mathrm{COLOR}\left(\mathrm{RGB},1,0,0\right)\right),\mathrm{SCALING}\left(\mathrm{CONSTRAINED}\right),\mathrm{AXESSTYLE}\left(\mathrm{BOX}\right)\right)$

Compatibility

 • The GraphTheory[DelaunayTriangulation] command was introduced in Maple 16.