Polygon enclosing a set of points

Solution 1:

There are many algorithms for this problem. It is called "minimum bounding box". You will find solutions too searching for "convex hull", especially here.

One way is to find the leftmost point and then repeat to search for a point where all other points are to the right of the line p(n-1)p(n).

Solution 2:

Here is a simple solution...

Begin with any three points to form a triangle. Add each additional point to the polygon with the following operation:

Divide the edges into two continuous paths, where in one path the line of each edge separates the point to be added from the rest of the polygon (let's call this the "separating path") and in the other path, the line of each edge has the point on the same side as the polygon.

(Note: as long as your shape remains convex, which it must, these two paths will be continuous and form the entire shape)

If the separating path has no edges, the point is inside the polygon and should be ignored, otherwise, remove the separating path from the polygon. Replace it with two segments, connecting each endpoint of the separating path to the new point.

Ta-da! :)