Polygon enclosing a set of points

algorithm language-agnostic geometry polygon
Laurent K picture Laurent K · May 6, 2009 · Viewed 32.4k times · Source

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

Answer

Ralph M. Rickenbach picture Ralph M. Rickenbach · May 6, 2009

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

Related questions

Equation for testing if a point is inside a circle

If you have a circle with center (center_x, center_y) and radius radius, how do you test if a given point with coordinates (x, y) is inside the circle?

Read More
How to find two most distant points?

This is a question that I was asked on a job interview some time ago. And I still can't figure out sensible answer. Question is: you are given set of points (x,y). Find 2 most distant points. Distant from each …

Read More
How to check if line segment intersects a rectangle?

If you have 2 points, (x1, y1) and (x2, y2), which represent two opposite corners of a rectangle, and 2 other points, (x3,y3) and (x4,y4), which represent 2 endpoints of a line segment, how can you check if the line segment …

Read More