36

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

Igor Brejc
  • 18,714
  • 13
  • 76
  • 95
Laurent K
  • 3,503
  • 3
  • 30
  • 36

4 Answers4

36

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).

Ralph M. Rickenbach
  • 12,893
  • 5
  • 29
  • 49
  • 1
    Thank you, this was exactly what I was looking for. By typing "jarvis march java" or "quick hull java" on google, I did even find java implentations. – Laurent K May 06 '09 at 11:40
  • 2
    "minimum bounding box" is… a box. Not a generic polygon. The other links might be good. – o0'. Jul 24 '15 at 19:37
  • Not sure what "minimum bounding box" has to do with it, considering that P is required to be a subset of S. – AnT stands with Russia Mar 29 '17 at 06:04
6

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

Evan Rogers
  • 768
  • 4
  • 11
4

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.

SPWorley
  • 11,550
  • 9
  • 43
  • 63
  • 8
    The points P in your huge triangle would not be a subset of S, which is one of the requirements. – Daniel Daranas May 06 '09 at 10:31
  • @DanielDaranas How can obtain the vertices of this super large triangle? – Dinesh Mar 16 '14 at 18:37
  • The convex hull isn't the smallest polygon containing every point.There are non-convex polygons (e.g. stars) which can contain every point and still be smaller than the convex hull. They would have a longer perimeter than the convex hull, but a smaller area. – Eric Duminil Mar 30 '21 at 10:27
4

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

Igor Brejc
  • 18,714
  • 13
  • 76
  • 95