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.

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

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

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

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

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