Fitting a Polygon About a Set of Points
QUESTION: I have a set of points and I would like to calculate a polygon that completely surrounds the points. How can I do that?
ANSWER: What you want is called the "convex hull". Imagine that your points are nails sticking into a board. If you stretched a rubberband completely around your points, so that all the points were inside the perimeter of the rubberband, the nails that the rubberband touches are the points of a polygon that is called the convex hull. See the figure below.
PRO ConvexHull x=[0.36,0.35,0.39,0.42,0.60,0.41,0.48,0.73,0.46,0.42,0.42,0.42, $ 0.47,0.44,0.47,0.49,0.54,0.64,0.65] y=[0.19,0.26,0.26,0.26,0.14,0.22,0.15,0.10,0.16,0.30,0.27,0.27, $ 0.23,0.23,0.22,0.16,0.16,0.08,0.08] Window, XSize=350, YSize=350, Title='Convex Hull' Plot, x, y, color=FSC_Color("Green"), /NoData, YRange=[0.0, 0.5], $ Background=FSC_Color("Charcoal", !P.Background) Triangulate, x, y, triangles, hull Plots, [x[hull],x[hull]], [y[hull],y[hull]], Color=FSC_Color("Yellow") Plots, x, y, psym=4, Color=FSC_Color("Cyan"), Symsize=2 END
The results of the program are shown in the figure below.
Copyright © 2006 David W. Fanning
Last Updated 11 January 2006