# 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.

## 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.) 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.

quick hull

##### Share on other sites
Thanks. I'll look at that. I had no idea what terms to search under.

##### Share on other sites
Quick Hull. Thanks for that. I hadn't heard of that before.

##### 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 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.

1. 1
2. 2
Rutin
21
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633742
• Total Posts
3013630
×

## Important Information

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!