Polygon enclosing a set of points

Question

I have a set S of points (2D : defined by x and y) and I want to find P, the smallest (meaning : with the smallest number of points) polygon enclosing all the points of the set, P being an ordered subset of S.

Are there any known algorithms to compute this? (my lack of culture in this domain is astonishing...)

Thanks for your help

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! :)

Solution 3

You probably mean you want the smallest area, which is the convex hull.

If you really do want the fewest points, you can just make a triangle with super-large vertex positions so that all your points are enclosed.

Solution 4

Here's a good resource on convex hull algorithms: The Convex Hull of a 2D Point Set or Polygon (by Dan Sunday)

View more solutions