Unfold an n-vertex polygon with a new dataset into an n-vertex polygon
There is a simple polygon P1 with n vertices, n is small, say 8. This polygon must represent the perimeter of some set of two-dimensional points.
Then we have another polygon, let's call it P2, also with the maximum number of vertices n. P2 is close to P1, so it makes sense to draw a new polygon P3 that will describe the area P1 and P2 together.
I am looking for an algorithm to select the points of the new P3 polygon. I would like to describe (still, with n points!) The shape of P1 + P2 as best as possible: the number of points used to create the polygon that are still inside the new polygon P3 should be maximized, but the area of P3 is as small as possible.
The process of expanding the polygon will be repeated in my application.
source to share
If I am reading this problem correctly it is not possible. Consider a "semicircle" defined by N points along the curve and none on the straight line. Let P1 and P2 be two such semicircles, whose straight faces are facing each other as follows: (| |). It is clear that the only polygon that will contain them consists of all 2N points.
A simpler problem (to enter a new vertex and select the old one for eviction) is also impossible: consider a triangle and a new point near the middle of the edge.
If we drop the requirement that no interior can be lost, then the problem can be solved, but not quite. I suggest you try a few of them to find out which suites are best for you.
- Just combine P1 and P2 into one 2N polygon, then eliminate all other vertices (dh keep vertices 2, 4, 6 ...). Rough, but maybe good enough.
- Combine two closest neighbors into one. Repeat until only N. is left.
- Eliminate the "straightest" vertices until only N. is left.
- Start at polygon 2N, then measure each contribution of the vertices to the area by taking the cross product of its two edges. If so, this top is convex and "protects" most of the interior. If negative, it is a concave vertex that "excludes" most of the outside. Now let's eliminate the least valuable vertices. Note that this is not an ideal method, as eliminating two neighbors can do more damage than the score indicates.
source to share
It looks like you are trying to find many polygons with acceptable point density. Have you considered building a series of convex hulls ? Grow your set outward, creating a new convex hull each time you add a point. Find the density of the new enclosure. If this is unacceptable, delete the point and select another. Stop when you reach the target area or total points.
This can also be applied in reverse. You can use your starting polygons P1 and P2 to plant a convex hull, then consider dropping one point and calculating a new density. The most beneficial point to remove is the one that maximizes the increase in density. Repeat until you are satisfied.
Simple O (n logn) convex hull algorithms exist for two dimensions. Qhull is a good C implementation.
source to share