Finding the outer convex polygon from a group of 2D points
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.)
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.
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement