The DelaunayTriangulation command computes a Delaunay triangulation of the set of input points. For higher dimensions, the "triangulation" is a collection of d dimension simplices, e.g. tetrahedrons for d=3.

If points is a Matrix, then each row of points is treated as a point. If it is a list of lists, then each sublist is a point.

All entries of points must evaluate to floating-point values when evalf is applied. This happens as a preprocessing step.

For d=2, if no four points lie on the same circle, then the Delaunay triangulation is unique. For higher dimensions it is also unique when a similar general position condition holds.

The Delaunay triangulation is a triangulation that maximizes the smallest angle of the triangles in the triangulation (that is, it avoids (if possible) thin triangles).  It has the property that the circum-circle (hypersphere) of any triangle (simplex) does not have any other points in its interior.

The triangles, for d=2, or simplices are returned as a list of d+1 element lists; each inner list specifies the d+1 vertices of a Delaunay triangle as integer indices into the input points list or Matrix. For example, if the first inner list is $\left[3\,10\,5\right]$, then the third, tenth, and fifth point in points form one of the Delaunay triangles.

Because the Delaunay triangulation is computed with a higher dimensional convex hull, the maximum dimension of the input is 10.

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

$\mathrm{xy}≔\left[\left[0\,0\right]\,\left[1\,0\right]\,\left[2\,0\right]\,\left[0\,1\right]\,\left[1\,1\right]\,\left[2\,1\right]\,\left[0\,2\right]\,\left[1\,2\right]\,\left[2\,2\right]\right]$

$\mathrm{xy}≔\left[\left[0\,0\right]\,\left[1\,0\right]\,\left[2\,0\right]\,\left[0\,1\right]\,\left[1\,1\right]\,\left[2\,1\right]\,\left[0\,2\right]\,\left[1\,2\right]\,\left[2\,2\right]\right]$

$t≔\mathrm{DelaunayTriangulation}\left(\mathrm{xy}\right)$

$t≔\left[\left[4\,2\,5\right]\,\left[2\,4\,1\right]\,\left[2\,6\,5\right]\,\left[6\,2\,3\right]\,\left[8\,4\,5\right]\,\left[4\,8\,7\right]\,\left[6\,8\,5\right]\,\left[8\,6\,9\right]\right]$

$\mathrm{plots}:-\mathrm{display}\left(\mathrm{map}\left(x\mapsto \mathrm{plottools}:-\mathrm{polygon}\left(\mathrm{xy}\left[x\right]\,\mathrm{style}=\mathrm{line}\right)\,t\right)\right)$

$m≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(50\,2\right)$

$m≔\begin{array}{c}\left[\begin{array}{cc}\mathrm{-38}& 76\\ 91& \mathrm{-44}\\ \mathrm{-1}& 24\\ 63& 65\\ \mathrm{-23}& 86\\ \mathrm{-63}& 20\\ \mathrm{-26}& \mathrm{-61}\\ 30& \mathrm{-48}\\ 10& 77\\ 22& 9\\ ⋮& ⋮\end{array}\right]\\ \hfill \text{50 × 2 Matrix}\end{array}$

$t≔\mathrm{DelaunayTriangulation}\left(m\right)$

$t≔\left[\left[21\,6\,47\right]\,\left[15\,6\,38\right]\,\left[36\,13\,31\right]\,\left[13\,35\,31\right]\,\left[39\,21\,40\right]\,\left[1\,48\,47\right]\,\left[6\,1\,47\right]\,\left[15\,1\,6\right]\,\left[26\,36\,31\right]\,\left[35\,37\,40\right]\,\left[37\,39\,40\right]\,\left[7\,13\,36\right]\,\left[8\,7\,36\right]\,\left[7\,8\,28\right]\,\left[13\,7\,35\right]\,\left[7\,37\,35\right]\,\left[3\,15\,38\right]\,\left[3\,28\,43\right]\,\left[28\,3\,38\right]\,\left[29\,16\,50\right]\,\left[48\,16\,45\right]\,\left[16\,29\,45\right]\,\left[16\,33\,50\right]\,\left[29\,4\,45\right]\,\left[4\,29\,50\right]\,\left[4\,17\,45\right]\,\left[22\,39\,38\right]\,\left[39\,22\,21\right]\,\left[6\,22\,38\right]\,\left[22\,6\,21\right]\,\left[9\,16\,48\right]\,\left[9\,33\,16\right]\,\left[32\,2\,12\right]\,\left[26\,32\,12\right]\,\left[2\,32\,31\right]\,\left[32\,26\,31\right]\,\left[23\,8\,36\right]\,\left[26\,23\,36\right]\,\left[23\,26\,12\right]\,\left[49\,28\,38\right]\,\left[49\,7\,28\right]\,\left[30\,1\,15\right]\,\left[3\,30\,15\right]\,\left[46\,20\,17\right]\,\left[18\,20\,46\right]\,\left[41\,18\,46\right]\,\left[18\,41\,12\right]\,\left[41\,23\,12\right]\,\left[23\,41\,8\right]\,\left[28\,41\,43\right]\,\left[8\,41\,28\right]\,\left[30\,11\,19\right]\,\left[11\,30\,3\right]\,\left[25\,33\,19\right]\,\left[11\,25\,19\right]\,\left[25\,11\,34\right]\,\left[25\,34\,46\right]\,\left[14\,25\,46\right]\,\left[25\,14\,33\right]\,\left[14\,46\,17\right]\,\left[4\,14\,17\right]\,\left[33\,14\,50\right]\,\left[14\,4\,50\right]\,\left[1\,5\,48\right]\,\left[5\,9\,48\right]\,\left[49\,27\,7\right]\,\left[37\,27\,39\right]\,\left[7\,27\,37\right]\,\left[39\,27\,38\right]\,\left[27\,49\,38\right]\,\left[24\,20\,18\right]\,\left[2\,24\,12\right]\,\left[24\,18\,12\right]\,\left[20\,24\,17\right]\,\left[17\,24\,45\right]\,\left[24\,2\,45\right]\,\left[41\,10\,43\right]\,\left[10\,41\,46\right]\,\left[10\,34\,43\right]\,\left[34\,10\,46\right]\,\left[42\,11\,3\right]\,\left[11\,42\,34\right]\,\left[42\,3\,43\right]\,\left[34\,42\,43\right]\,\left[5\,44\,9\right]\,\left[44\,30\,19\right]\,\left[30\,44\,1\right]\,\left[44\,5\,1\right]\,\left[33\,44\,19\right]\,\left[9\,44\,33\right]\right]$

$\mathrm{plots}:-\mathrm{display}\left(\mathrm{map}\left(x\mapsto \mathrm{plottools}:-\mathrm{polygon}\left(m\left[x\right]\,\mathrm{style}=\mathrm{line}\right)\,t\right)\,\mathrm{axes}=\mathrm{none}\right)$

$m≔\mathrm{RandomTools}:-\mathrm{Generate}\left(\mathrm{list}\left(\mathrm{list}\left(\mathrm{float}\left(\mathrm{range}=-95..95\right)\,3\right)\,15\right)\right)$

$m≔\left[\left[21.73755375\,8.97960333\,61.76051242\right]\,\left[27.40775176\,60.28912701\,8.33727108\right]\,\left[\mathrm{-74.22489097}\,27.09842774\,\mathrm{-83.58721340}\right]\,\left[\mathrm{-0.78447362}\,\mathrm{-5.17789092}\,\mathrm{-34.43051994}\right]\,\left[13.07930916\,15.60891286\,\mathrm{-31.91703837}\right]\,\left[\mathrm{-65.32248447}\,22.19030206\,22.85228936\right]\,\left[78.14996416\,\mathrm{-42.78547388}\,\mathrm{-56.49945055}\right]\,\left[79.84896994\,79.69509190\,\mathrm{-40.48209840}\right]\,\left[\mathrm{-93.75987033}\,\mathrm{-7.53357838}\,20.82785949\right]\,\left[74.72960972\,\mathrm{-5.51167073}\,\mathrm{-21.65563720}\right]\,\left[\mathrm{-64.79397741}\,\mathrm{-14.87680642}\,73.38815316\right]\,\left[\mathrm{-10.76246183}\,32.82672336\,\mathrm{-70.54740932}\right]\,\left[69.04845536\,\mathrm{-32.98683016}\,93.52608262\right]\,\left[79.40126029\,\mathrm{-70.60857608}\,50.11503436\right]\,\left[62.79028047\,89.28786396\,\mathrm{-76.04108382}\right]\right]$

$t≔\mathrm{DelaunayTriangulation}\left(m\right)$

$t≔\left[\left[4\,7\,14\,9\right]\,\left[7\,4\,3\,9\right]\,\left[4\,6\,3\,9\right]\,\left[15\,2\,6\,3\right]\,\left[10\,1\,4\,14\right]\,\left[7\,10\,4\,14\right]\,\left[10\,13\,1\,14\right]\,\left[2\,10\,13\,1\right]\,\left[7\,10\,14\,8\right]\,\left[10\,13\,14\,8\right]\,\left[10\,2\,13\,8\right]\,\left[15\,10\,7\,8\right]\,\left[2\,11\,6\,1\right]\,\left[13\,11\,1\,14\right]\,\left[11\,6\,4\,9\right]\,\left[11\,6\,1\,4\right]\,\left[11\,4\,14\,9\right]\,\left[1\,11\,4\,14\right]\,\left[6\,12\,4\,3\right]\,\left[2\,12\,6\,3\right]\,\left[12\,2\,15\,3\right]\,\left[12\,7\,4\,3\right]\,\left[12\,15\,7\,3\right]\,\left[5\,10\,1\,4\right]\,\left[5\,10\,2\,1\right]\,\left[6\,5\,1\,4\right]\,\left[5\,2\,6\,1\right]\,\left[12\,5\,6\,4\right]\,\left[12\,5\,2\,6\right]\,\left[10\,5\,7\,4\right]\,\left[5\,12\,7\,4\right]\,\left[10\,5\,2\,8\right]\,\left[10\,5\,15\,7\right]\,\left[5\,12\,15\,7\right]\,\left[2\,5\,15\,8\right]\,\left[5\,12\,2\,15\right]\,\left[5\,10\,15\,8\right]\right]$

$\mathrm{tetrahedron}≔A\mapsto \mathrm{plottools}:-\mathrm{polygon}\left(\left[\left[A\left[1\right]\,A\left[2\right]\,A\left[3\right]\right]\,\left[A\left[1\right]\,A\left[2\right]\,A\left[4\right]\right]\,\left[A\left[1\right]\,A\left[3\right]\,A\left[4\right]\right]\,\left[A\left[2\right]\,A\left[3\right]\,A\left[4\right]\right]\right]\,\mathrm{style}=\mathrm{line}\,\mathrm{color}=''Black''\right)\;$$\mathrm{plots}:-\mathrm{display}\left(\mathrm{plottools}:-\mathrm{point}\left(m\,\mathrm{symbolsize}=20\,\mathrm{color}=''Red''\right)\,\mathrm{map}\left(x\mapsto \mathrm{tetrahedron}\left(m\left[x\right]\right)\,t\right)\,\mathrm{axes}=\mathrm{none}\right)$

$\mathrm{tetrahedron}≔A\mapsto \mathrm{plottools}:-\mathrm{polygon}\left(\left[\left[A_1\,A_2\,A_3\right]\,\left[A_1\,A_2\,A_4\right]\,\left[A_1\,A_3\,A_4\right]\,\left[A_2\,A_3\,A_4\right]\right]\,\mathrm{style}=\mathrm{line}\,\mathrm{color}=''Black''\right)$

The ComputationalGeometry[DelaunayTriangulation] command was introduced in Maple 2018.

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

The points parameter was updated in Maple 2019.