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.
The convex hull can be calulated with the TRIANGULATE command. Here is an example program that illustrates the technique. It requires the FSC_Color program from the Coyote Library to run.
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[0]]], [y[hull],y[hull[0]]], 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