What you're computing called the
convex hull of the set of points in 2D, and there's a widely used algorithm known as
Graham Scan after its author, R L Graham, who published it in 1972. It's perhaps worth noting that you can look for the convex hull of a set of points in 3D, and also that
Graham Scan is not easily adapted to that variant of the problem.
The Princeton Computer Science department have quite a
nice visual demonstration of how the algoirthm works that I just found through Google. These are the main steps (adapted from their page, again, as they provide a good succinct overview of the algorithm):
- Find an 'extreme' point, such as the point with largest y coordinate. This will be the pivot and is guaranteed to be on the hull.
- Sort the points in order of increasing angle about the pivot. We end up with a star-shaped polygon (one in which one special point, in this case the pivot, can "see" the whole polygon).
- Build the hull, by marching around the star-shaped poly, adding edges when we make a left turn, and back-tracking when we make a right turn.
Take a look at their
demos to give you more of an idea what they mean. I suspect that for now you might want to treat this as an interesting diversion but not one that you want to implement in your game, since you have something that works - but if I'm wrong then you should post back and we might be able to help you implement it!
A point to note is that I believe implementations of Graham scan should avoid actually computing the actual angle between the pivot and each of the other points when sorting them in step 2, because that is a time consuming operation (like your rotating line probably is!) and there are more optimised approaches to doing that sort.
Well - hope that's of interest and not too vague...!
Richard
Edited by Richard, 03 September 2011 - 10:22 AM.
