3
$\begingroup$

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!

1 Answers 1

5

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

  • 0
    Thank you, I was actually looking for a concave hull but this pointed me in the right direction!!!!!2011-03-01