This function computes a Delaunay triangulation of the region bounded by the sequence of line segments connecting the outermost 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.

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

$\mathrm{pts}≔\mathrm{seq}\left(\left[0\,j-1\right]\,j\=1..5\right)\:$

$\mathbf{for}i\mathbf{to}4\mathbf{do}\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)\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]$

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

$\mathrm{plt}≔\mathrm{NULL}\:$

$\mathbf{for}v\mathbf{in}\mathrm{tris}\mathbf{do}\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]\mathbf{end\; do}\:$

$\mathrm{plot}\left(\left[\mathrm{plt}\right]\,\mathrm{color}\=''Red''\,\mathrm{scaling}\=\mathrm{constrained}\,\mathrm{axes}\=\mathrm{box}\right)$

$\mathrm{pts}≔\mathrm{seq}\left(\left[0\,j-1\right]\,j\=1..5\right)\:$

$\mathbf{for}i\mathbf{to}4\mathbf{do}\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)\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]$

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

$\mathrm{plt}≔\mathrm{NULL}\:$

$\mathbf{for}v\mathbf{in}\mathrm{tris}\mathbf{do}\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]\mathbf{end\; do}\:$

$\mathrm{plot}\left(\left[\mathrm{plt}\right]\,\mathrm{color}\=''Red''\,\mathrm{scaling}\=\mathrm{constrained}\,\mathrm{axes}\=\mathrm{box}\right)$

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

For more information on Maple 16 changes, see Updates in Maple 16.