You are currently reviewing an older revision of this page.
This is a basic 2d convex hull.
It's still a bit buggy, but it does the job 90% of the time. I sitll haven't pinned down how to fix it up fully yet.
It takes a point cloud and returns only those points on the convex hull, they can then be used to make a polyline, or a line, or whatever you like.
It'd be great if someone else could write a divide and conquor, and a quick hull for comparison.
gct
Source
here's the origional '72 paper outlining it
and the wikipedia article
it doesn't follow the article exactly, but it's not far off. there is a bit of stuff based on the exclustion of points which is slightly fudged
The angle sort part of this code could be greatly improved by using a cross product. I'll get to it one day...