Given a set of points in the plane, find a (not necessarily convex) polygon of minimal area containing them
Zach Conn
Given a set of points in the plane, I want to find the smallest polygon containing all the points. More precisely, the vertices of this polygon must be a subset of the original set of points.
The easiest approach would be to find the convex hull, which can be computed in O(N log(N)) time using Graham's scanning algorithm, but I would ideally like to drop the requirement that the polygon be convex. Are there any standard approaches to this? I imagine this problem is a fair bit harder because it seems to me there is not guaranteed to be a unique solution.
Penguino
Do you need the absolutely smallest area solution or just a 'fairly good' solution. If the latter then one possible algorithm would be: 1) calculate the convex hull of all your points - all these points must be vertexes of your final solution. 2) calculate the convex hull of the remaining points - repeat this process until you have no points left. You will end up with n non-intersecting convex hulls. 3) Determine (possibly by greedy algorithm), where to join these hulls to form a single contiguous path between all the points by adding pairs of lines between neighboring points in neighboring hulls and removing lines in the hulls.
This might not be the minimal area but should be a fairly good solution.
Added comment: Greedy removal from the outermost hull to the next inner one should be by removing the largest area region separating the two. Greedy removal from the second hull to the next inner one should be by 'removing' (which is actually retaining) the smallest area separating the hulls...and so on inwards swapping between largest and smallest areas...
Picture added to explain better than my 100 words. 
Collected from the Internet
Please contact [email protected] to delete if infringement.
edited at
- Prev: Item description and sums missing in paypal express checkout approval page
- Next: SQL INSERT with multiple rows of values using Jython and zxJDBC
Related
Related Related
- 1
Find the area of a bounding polygon that encloses a set of points
- 2
Given a set of coordinate points, remove inner points (or find the outer ring of points) to form polygon
- 3
Find and draw regression plane to a set of points
- 4
Find and draw regression plane to a set of points
- 5
find the maximum convex area
- 6
Connect points to plane/Draw Polygon
- 7
Polygon area to points
- 8
Convex hull or two convex hulls of the given set of points with the lowest possible perimeter
- 9
Prove that the farthest point among a set of points(in 2-d plane) should lie on the convex hull
- 10
Finding largest subset of points forming a convex polygon
- 11
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line
- 12
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line
- 13
Insert a set of vertex within a convex polygon
- 14
How to generate a set of random points within a given (x,y) coordinates in an x-y plane?
- 15
projecting points onto a plane given by a normal and a point
- 16
Separation of plane by line given two points
- 17
Create polygon area based on center of points
- 18
Calculate area of polygon given (x,y) coordinates
- 19
Area of grid polygon given length of edges
- 20
How to find the coordinate points of polygon?
- 21
C++/JAVA: Efficiently find a set in the collection containing given value
- 22
Find smallest substring containing a given set of letters in a larger string
- 23
Given a set of intervals, how to find the maximum number of intersections among them,
- 24
How to find the smallest ellipse covering a given fraction of a set of points in R?
- 25
PostGIS: How to find N closest sets of points to a given set?
- 26
Extract interior points of polygon given the exterior coordinates
- 27
When given groups of numbers, how can I find the minimal set of groups to represent all the numbers?
- 28
How to find a minimal set of keys?
- 29
Region inside a convex polygon
Comments