compute Delaunay triangulation of a set of points
a list of d element lists or an n by d Matrix representing n coordinates in d-dimensional space
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 3,10,5, 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.
xy ≔ 0,0,1,0,2,0,0,1,1,1,2,1,0,2,1,2,2,2
t ≔ DelaunayTriangulation⁡xy
Note that the Delaunay triangulation is not unique in the above example.
m ≔ LinearAlgebra:-RandomMatrix⁡50,2
t ≔ DelaunayTriangulation⁡m
A 3-D example
m ≔ RandomTools:-Generate⁡list⁡list⁡float⁡range=−95..95,3,15
plots need the polygon faces of the tetrahedrons in t
tetrahedron ≔ A→plottools:-polygon⁡A1,A2,A3,A1,A2,A4,A1,A3,A4,A2,A3,A4,style=line,color=Black;plots:-display⁡plottools:-point⁡m,symbolsize=20,color=Red,map⁡x→tetrahedron⁡mx,t,axes=none
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.
Download Help Document