ComputationalGeometry - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Geometry : Computational Geometry : ComputationalGeometry/DelaunayTriangulation

ComputationalGeometry

  

DelaunayTriangulation

  

compute Delaunay triangulation of a set of points

 

Calling Sequence

Parameters

Description

Examples

Compatibility

Calling Sequence

DelaunayTriangulation(points)

Parameters

points

-

a list of d element lists or an n by d Matrix representing n coordinates in d-dimensional space

Description

• 

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.

Examples

withComputationalGeometry:

xy0,0,1,0,2,0,0,1,1,1,2,1,0,2,1,2,2,2

xy0,0,1,0,2,0,0,1,1,1,2,1,0,2,1,2,2,2

(1)

tDelaunayTriangulationxy

t4,2,5,2,4,1,2,6,5,6,2,3,8,4,5,4,8,7,6,8,5,8,6,9

(2)

plots:-displaymapxplottools:−polygonxyx,style=line,t

Note that the Delaunay triangulation is not unique in the above example.

mLinearAlgebra:-RandomMatrix50,2

(3)

tDelaunayTriangulationm

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

(4)

plots:-displaymapxplottools:−polygonmx,style=line,t,axes=none

A 3-D example

mRandomTools:-Generatelistlistfloatrange=95..95,3,15

m21.73755375,8.97960333,61.76051242,27.40775176,60.28912701,8.33727108,−74.22489097,27.09842774,−83.58721340,−0.78447362,−5.17789092,−34.43051994,13.07930916,15.60891286,−31.91703837,−65.32248447,22.19030206,22.85228936,78.14996416,−42.78547388,−56.49945055,79.84896994,79.69509190,−40.48209840,−93.75987033,−7.53357838,20.82785949,74.72960972,−5.51167073,−21.65563720,−64.79397741,−14.87680642,73.38815316,−10.76246183,32.82672336,−70.54740932,69.04845536,−32.98683016,93.52608262,79.40126029,−70.60857608,50.11503436,62.79028047,89.28786396,−76.04108382

(5)

tDelaunayTriangulationm

t4,7,14,9,7,4,3,9,4,6,3,9,15,2,6,3,10,1,4,14,7,10,4,14,10,13,1,14,2,10,13,1,7,10,14,8,10,13,14,8,10,2,13,8,15,10,7,8,2,11,6,1,13,11,1,14,11,6,4,9,11,6,1,4,11,4,14,9,1,11,4,14,6,12,4,3,2,12,6,3,12,2,15,3,12,7,4,3,12,15,7,3,5,10,1,4,5,10,2,1,6,5,1,4,5,2,6,1,12,5,6,4,12,5,2,6,10,5,7,4,5,12,7,4,10,5,2,8,10,5,15,7,5,12,15,7,2,5,15,8,5,12,2,15,5,10,15,8

(6)

plots need the polygon faces of the tetrahedrons in t

tetrahedronAplottools:−polygonA1,A2,A3,A1,A2,A4,A1,A3,A4,A2,A3,A4,style=line,color=Black;plots:-displayplottools:-pointm,symbolsize=20,color=Red,mapxtetrahedronmx,t,axes=none

tetrahedronAplottools:−polygonA1,A2,A3,A1,A2,A4,A1,A3,A4,A2,A3,A4,style=line,color=Black

Compatibility

• 

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.

See Also

ComputationalGeometry

GraphTheory[DelaunayTriangulation]