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 :
And the Solution (Sorry for the quick scketeches):
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!