Sign in to follow this  
Quasius

Finding the outer convex polygon from a group of 2D points

Recommended Posts

Here is the problem: I have a group of 2D points and I need to find which points form the largest-possible (outer) convex polygon. The identified points should be in-order to form the poly. For example, it should find the red points in order in the following image: (Obviously where the loop starts is arbitrary.) Photobucket I was working with a method of starting with any line segment and then trying to find which other connecting line segment formed the largest angle with it. This would eventually lead outward and around, forming the loop. The problem was that this involved lots of expensive inverse trig for finding the angles and ended up involving a lot of special cases to check for (coincident points, collinear points, etc.) Obviously the special cases can be worked out (although they are being stubborn), but this method will always involve all the inverse trig. So I was wondering if there was a known simpler solution. Thanks.

Share this post


Link to post
Share on other sites
The search terms should be "convex hull".
The question you're trying to ask is:
"I need to find the convex hull of a set of points in R2, what algorithms are there?"

I'd suggest that you look into Andrew's monotone chain algorithm.
It's easy to make it VERY robust and I found it easy to implement and never had any issues with it.

Just my 2c

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this