ComputationalGeometry - Maple Programming Help

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

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

 > with(ComputationalGeometry):
 > xy:=[[391,374],[240,431],[252, 340],[374, 320],[289, 214],[134, 390],[68, 186],[154, 259],[161, 107],[435, 108],[208, 148],[295, 160],[421, 212],[441, 303]];
 ${\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)
 > plots:-display(plottools:-polygon(xy,style=line));
 > t:=PolygonTriangulation(xy,method=monotone);
 ${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)
 > plots:-display(map(x->plottools:-polygon(xy[x],style=line),t));

Compatibility

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