SimpleClosedPath - Maple Help

ComputationalGeometry

 SimpleClosedPath
 determine an order of points so they form a simple closed path

 Calling Sequence SimpleClosedPath( P ) SimpleClosedPath( P, a )

Parameters

 P - 2-D array of point coordinates (in the same form as the array in PointOrientation for highest efficiency), or a listlist of point coordinates a - (optional) the index of the point from which to start the curve. The point with minimal y-coordinate is used by default. The output is not guaranteed to be simple unless the anchor is on the convex hull.

Description

 • The SimpleClosedPath command returns a list of indices of the points in P so that they form a non-self-intersecting polygon in counterclockwise orientation.
 • The algorithm starts with an anchor point a and sorts the remaining points by the angle of the segment they form with a. The angle is not computed explicitly, but rather PointOrientation is used to determine the order implicitly.

Examples

 > $\mathrm{with}\left(\mathrm{ComputationalGeometry}\right):$
 > $P≔\left[\left[0.17,0.13\right],\left[0.39,0.74\right],\left[0.76,0.68\right],\left[0.93,0.85\right],\left[0.036,0.66\right],\left[0.96,0.79\right],\left[0.92,0.42\right],\left[0.14,0.80\right],\left[0.48,0.96\right],\left[0.97,0.16\right],\left[0.96,0.96\right],\left[0.55,0.28\right],\left[0.098,0.63\right],\left[0.91,0.13\right],\left[0.91,0.82\right]\right]$
 ${P}{≔}\left[\left[{0.17}{,}{0.13}\right]{,}\left[{0.39}{,}{0.74}\right]{,}\left[{0.76}{,}{0.68}\right]{,}\left[{0.93}{,}{0.85}\right]{,}\left[{0.036}{,}{0.66}\right]{,}\left[{0.96}{,}{0.79}\right]{,}\left[{0.92}{,}{0.42}\right]{,}\left[{0.14}{,}{0.80}\right]{,}\left[{0.48}{,}{0.96}\right]{,}\left[{0.97}{,}{0.16}\right]{,}\left[{0.96}{,}{0.96}\right]{,}\left[{0.55}{,}{0.28}\right]{,}\left[{0.098}{,}{0.63}\right]{,}\left[{0.91}{,}{0.13}\right]{,}\left[{0.91}{,}{0.82}\right]\right]$ (1)

P is not a simple polygon in the order given

 > $\mathrm{plots}:-\mathrm{polygonplot}\left(P,\mathrm{style}=\mathrm{line}\right)$
 > $\mathrm{path}≔\mathrm{SimpleClosedPath}\left(P\right)$
 ${\mathrm{path}}{≔}\left[{1}{,}{14}{,}{10}{,}{7}{,}{12}{,}{6}{,}{3}{,}{15}{,}{4}{,}{11}{,}{9}{,}{2}{,}{8}{,}{13}{,}{5}\right]$ (2)

The output of SimpleClosedPath is a simple polygon.

 > $\mathrm{plots}:-\mathrm{polygonplot}\left(\left[\mathrm{seq}\left({P}_{i},i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{path}\right)\right],\mathrm{style}=\mathrm{line}\right)$

There are many possible orders; the convex hull gives some but not all of them.

 > $\mathrm{ch}≔\mathrm{ConvexHull}\left(P\right)$
 ${\mathrm{ch}}{≔}\left[{10}{,}{11}{,}{9}{,}{8}{,}{5}{,}{1}{,}{14}\right]$ (3)
 > $M≔\mathrm{plots}:-\mathrm{display}\left(\mathrm{Matrix}\left(2,4,\left[\mathrm{seq}\left(\mathrm{plots}:-\mathrm{polygonplot}\left(\left[\mathrm{seq}\left({P}_{i},i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{SimpleClosedPath}\left(P,c\right)\right)\right],'\mathrm{color}'=c,'\mathrm{scaling}'='\mathrm{constrained}','\mathrm{title}'=\mathrm{cat}\left("anchor=",c\right)\right),c\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}∈\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{ch}\right),'\mathrm{PLOT}\left(\mathrm{AXESSTYLE}\left(\mathrm{NONE}\right)\right)'\right]\right)\right)$

Compatibility

 • The ComputationalGeometry[SimpleClosedPath] command was introduced in Maple 2023.