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)\:$

$$\begin{gathered} \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}\mathbf{do}\: \end{gathered}$$

$\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}\:$

$$\begin{gathered} \mathbf{for}v\mathbf{in}\mathrm{tris}\mathbf{do} \\ \mathrm{plt}≔\mathrm{plt},\left[\mathrm{pts}\left[v\left[1\right]\right]\,\mathrm{pts}\left[v\left[2\right]\right]\right],\left[\mathrm{pts}\left[v\left[2\right]\right]\,\mathrm{pts}\left[v\left[3\right]\right]\right],\left[\mathrm{pts}\left[v\left[3\right]\right]\,\mathrm{pts}\left[v\left[1\right]\right]\right] \\ \mathbf{end}\mathbf{do}\: \end{gathered}$$

$\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)\:$

$$\begin{gathered} \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}\mathbf{do}\: \end{gathered}$$

$\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}\:$

$$\begin{gathered} \mathbf{for}v\mathbf{in}\mathrm{tris}\mathbf{do} \\ \mathrm{plt}≔\mathrm{plt},\left[\mathrm{pts}\left[v\left[1\right]\right]\,\mathrm{pts}\left[v\left[2\right]\right]\right],\left[\mathrm{pts}\left[v\left[2\right]\right]\,\mathrm{pts}\left[v\left[3\right]\right]\right],\left[\mathrm{pts}\left[v\left[3\right]\right]\,\mathrm{pts}\left[v\left[1\right]\right]\right] \\ \mathbf{end}\mathbf{do}\: \end{gathered}$$

$\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.