DelaunayTriangulation - Maple Help

ComputationalGeometry

 DelaunayTriangulation
 compute Delaunay triangulation of a set of points

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

Examples

 > $\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]$ (1)
 > $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]$ (2)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{map}\left(x↦\mathrm{plottools}:-\mathrm{polygon}\left(\mathrm{xy}\left[x\right],\mathrm{style}=\mathrm{line}\right),t\right)\right)$

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

 > $m≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(50,2\right)$
 ${m}{≔}\begin{array}{c}\left[\begin{array}{cc}{-38}& {76}\\ {91}& {-44}\\ {-1}& {24}\\ {63}& {65}\\ {-23}& {86}\\ {-63}& {20}\\ {-26}& {-61}\\ {30}& {-48}\\ {10}& {77}\\ {22}& {9}\\ {⋮}& {⋮}\end{array}\right]\\ \hfill {\text{50 × 2 Matrix}}\end{array}$ (3)
 > $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]$ (4)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{map}\left(x↦\mathrm{plottools}:-\mathrm{polygon}\left(m\left[x\right],\mathrm{style}=\mathrm{line}\right),t\right),\mathrm{axes}=\mathrm{none}\right)$

A 3-D example

 > $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[{-74.22489097}{,}{27.09842774}{,}{-83.58721340}\right]{,}\left[{-0.78447362}{,}{-5.17789092}{,}{-34.43051994}\right]{,}\left[{13.07930916}{,}{15.60891286}{,}{-31.91703837}\right]{,}\left[{-65.32248447}{,}{22.19030206}{,}{22.85228936}\right]{,}\left[{78.14996416}{,}{-42.78547388}{,}{-56.49945055}\right]{,}\left[{79.84896994}{,}{79.69509190}{,}{-40.48209840}\right]{,}\left[{-93.75987033}{,}{-7.53357838}{,}{20.82785949}\right]{,}\left[{74.72960972}{,}{-5.51167073}{,}{-21.65563720}\right]{,}\left[{-64.79397741}{,}{-14.87680642}{,}{73.38815316}\right]{,}\left[{-10.76246183}{,}{32.82672336}{,}{-70.54740932}\right]{,}\left[{69.04845536}{,}{-32.98683016}{,}{93.52608262}\right]{,}\left[{79.40126029}{,}{-70.60857608}{,}{50.11503436}\right]{,}\left[{62.79028047}{,}{89.28786396}{,}{-76.04108382}\right]\right]$ (5)
 > $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]$ (6)

plots need the polygon faces of the tetrahedrons in t

 > $\mathrm{tetrahedron}≔A↦\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↦\mathrm{tetrahedron}\left(m\left[x\right]\right),t\right),\mathrm{axes}=\mathrm{none}\right)$
 ${\mathrm{tetrahedron}}{≔}{A}{↦}{\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)$

Compatibility

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