PolygonTriangulation - Maple Help

ComputationalGeometry

 PolygonTriangulation
 triangulate a simple polygon

 Calling Sequence PolygonTriangulation(polygon) PolygonTriangulation(polygon,option)

Parameters

 polygon - a list of two element lists or an n by 2 Matrix representing a simple polygon in either clockwise or counterclockwise order option - (optional) keyword option of the form method=name

Description

 • The PolygonTriangulation command computes a triangulation of a simple polygon.
 • The method option specifies the triangulation algorithm used. method can be either earclipping or monotone. The default method is earclipping.
 • The monotone method is faster for large polygons, but the earclipping method is more likely to produce better quality triangulations.
 • The triangles are returned as a list of three element lists; each inner list specifies the three vertices of a triangle as integer references into the input polygon list or Matrix.
 • Except for the first vertex and the last vertex, the polygon should not contain duplicate vertices.

Examples

 > $\mathrm{with}\left(\mathrm{ComputationalGeometry}\right):$
 > $\mathrm{xy}≔\left[\left[391,374\right],\left[240,431\right],\left[252,340\right],\left[374,320\right],\left[289,214\right],\left[134,390\right],\left[68,186\right],\left[154,259\right],\left[161,107\right],\left[435,108\right],\left[208,148\right],\left[295,160\right],\left[421,212\right],\left[441,303\right]\right]$
 ${\mathrm{xy}}{≔}\left[\left[{391}{,}{374}\right]{,}\left[{240}{,}{431}\right]{,}\left[{252}{,}{340}\right]{,}\left[{374}{,}{320}\right]{,}\left[{289}{,}{214}\right]{,}\left[{134}{,}{390}\right]{,}\left[{68}{,}{186}\right]{,}\left[{154}{,}{259}\right]{,}\left[{161}{,}{107}\right]{,}\left[{435}{,}{108}\right]{,}\left[{208}{,}{148}\right]{,}\left[{295}{,}{160}\right]{,}\left[{421}{,}{212}\right]{,}\left[{441}{,}{303}\right]\right]$ (1)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{plottools}:-\mathrm{polygon}\left(\mathrm{xy},\mathrm{style}=\mathrm{line}\right)\right)$
 > $t≔\mathrm{PolygonTriangulation}\left(\mathrm{xy},\mathrm{method}=\mathrm{monotone}\right)$
 ${t}{≔}\left[\left[{3}{,}{1}{,}{2}\right]{,}\left[{4}{,}{3}{,}{1}\right]{,}\left[{14}{,}{4}{,}{1}\right]{,}\left[{5}{,}{14}{,}{4}\right]{,}\left[{13}{,}{5}{,}{14}\right]{,}\left[{5}{,}{8}{,}{6}\right]{,}\left[{12}{,}{13}{,}{5}\right]{,}\left[{12}{,}{5}{,}{8}\right]{,}\left[{11}{,}{12}{,}{8}\right]{,}\left[{9}{,}{10}{,}{11}\right]{,}\left[{9}{,}{11}{,}{8}\right]{,}\left[{7}{,}{8}{,}{6}\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)$

Compatibility

 • The ComputationalGeometry[PolygonTriangulation] command was introduced in Maple 2018.
 • For more information on Maple 2018 changes, see Updates in Maple 2018.