Jump to content
  • Advertisement
Sign in to follow this  
Quasius

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

This topic is 3874 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
There are also all numbers of rotating-caliper algorithms, one of which creates convex hulls. Caliper algorithms can do some pretty neat tricks with clouds of points, actually.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!