Given a set of 2D points (x,y) (cloud of points), find the points that, when connected, will contain all other points

Question

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!

Answer 1

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