Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a set of 2D points I have to find the points that when connected will form a polygon that contains all the points in the set.

A quick example: imagine you have a set S={(1,1),(2,1),(1,2),(2,2),(4,4)}.

The solution would be SolS={(1,1),(2,1),(1,2),(4,4)} as those points (when connected) form a polygon that cointains all the points in the set ((2,2) is cointained inside the polygon).

Here is a diagram describing the problem : enter image description here

And the Solution (Sorry for the quick scketeches): enter image description here

Now, this obviously need to be extended to deal with n 2D points.

I have been cracking my head trying to work out an algorithm but I just cant find it.

Thank you so much for your help!

share|improve this question

1 Answer 1

up vote 5 down vote accepted

The word for what you are describing is the convex hull of the points. Wikipedia has a list of algorithms for computing them.

share|improve this answer
    
Thank you so much! –  Zebs Mar 1 '11 at 7:20
    
@Zebs: No problem! –  Zev Chonoles Mar 1 '11 at 7:23
    
Thank you, I was actually looking for a concave hull but this pointed me in the right direction!!!!! –  Zebs Mar 1 '11 at 7:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.