Menu
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
847
Use the Points To Line tool to create lines from points, followed by the Feature To Polygon tool to create polygons within line feature boundaries. Click Analysis > Tools to open the Geoprocessing pane in ArcGIS Pro. Search for the Points To Line (Data Management) tool and click it.
Draw a horizontal line to the right of each point and extend it to infinity. Count the number of times the line intersects with polygon edges. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.
One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray, starting from the point and going in any fixed direction, intersects the edges of the polygon. If the point is on the outside of the polygon the ray will intersect its edge an even number of times.
A convex polygon is a simple polygon (with no self intersections) such that any line segment between two points inside of the polygon lies completely inside of it. The point will be inside a convex polygon if and only if it lies on the same side of the support line of each of the segments.
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).
164
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! :)
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
