2

There is a simple polygon P1 with n vertices, n is small, let say 8. This polygon shall represent a perimeter of some set of 2D points.

Next, we have another polygon, lets call it P2, also with max number of vertices n. P2 is close to P1, so it makes sense to draw a new polygon, P3, which will describe the area of P1 and P2 together.

I am looking for the algorithm to select the points of the new polygon P3. I would like to describe (still, with n points!) the shape of P1 + P2 as good as possible: the number of the points used for creating the polygon which are still inside the new polygon P3 shall be maximized, but the area of P3 is as small as possible.

The process of expanding the polygon will be in my application called repeatedly.

Ron Warholic
  • 9,994
  • 31
  • 47
Joanna
  • 23
  • 4
  • 1
    This question is unclear. Must the interior of P3 contain the interiors of P1 and P2? Must all the vertices of P3 be vertices of P1 or P2? Can P1 and P2 overlap? – Beta Sep 08 '09 at 16:03
  • Sorry. Yes, the interior of P1 and P2 shall be described by P3. Yes, P1 and P2 are overlapping or at least are near by lying areas. To build P3 we can use any of the vertices of P1 and P2, but no more then set "n" (the size of the description shall stay constant). So the problem is to choose from 2 sets of n points 1 set of n points, ordered (so, we can draw a polygon, check if some other point belong to it...), so the new n points best suite the sum of the two origin shapes together. – Joanna Sep 09 '09 at 08:00
  • Simpler problem statement: we have polygon P with n wrtices, there is a new vertex V_new. We want to include it in P. Which of the n vertices of P shall be evicted from P? – Joanna Sep 09 '09 at 08:21

2 Answers2

2

If I am reading this problem correctly, it is impossible. Consider a "semicircle", defined by N points along the curve and none on the the straight edge. Let P1 and P2 be two such semicircles, with their straight edges facing each other like this: (| |). Clearly the only polygon that will contain them both consists of all 2N points.

The simpler problem (introduce a new vertex and choose an old one to evict) is impossible too: consider a triangle, and a new point near the middle of an edge.

If we abandon the requirement that none of the interior may be lost, then the problem can be solved, but not perfectly. I suggest you try a few of these to see which suites you best.

  • Simply combine P1 and P2 into a single 2N polygon, then eliminate every other vertex (d.h. keep vertices 2, 4, 6...). Crude, but perhaps good enough.
  • Combine the two nearest neighbors into one. Repeat until you have only N left.
  • Eliminate the "straightest" vertices until only N remain.
  • Start with the 2N polygon, then measure each vertex's contribution to the area by taking the cross-product of its two edges. If positive, this vertex is convex and "protects" much of the interior. If negative, this is a concave vertex that "excludes" much of the exterior. Now eliminate the least valuable vertices. Note that this is not a perfect method, since eliminating two neighbors can do more damage than the scores indicate.
Beta
  • 96,650
  • 16
  • 149
  • 150
  • Thanks. You got the problem right. I know, that a new polygon with N vertices will not be perfect (will not include all points from P1 and P2). I could choose between taking too much area or not enough. I just want to keep the imprecision as small as possible. I like your ideas and I will consider them. Important is, that it is a new problem, not solved already. Otherwise, I would take the existing solution. – Joanna Sep 10 '09 at 07:38
  • The nice thing about my problem is, that the set of points for which I create the polygons are distributed somehow regular. We can see theses points as vertices of a sparse graph, where the lenght of edges is limited. In fact, they represent the wireless telecommunication network. The exchange of information happens also only between the neighbors in the graph. When I have results on the (coverage) efficiency of different policies, I will report it here. – Joanna Sep 10 '09 at 07:40
1

It sounds like you are trying to find a set of polygons with an acceptable density of points. Have you considered constructing a series of convex hulls? Grow your set outwards, constructing the new convex hull each time you add a point. Find the density of the new hull. If unacceptable, remove the point and select a different one. Stop when you reach a target area or total number of points.

This can also be applied in reverse. You can use your initial polygons P1 and P2 to seed the convex hull, and then consider throwing away a single point and calculating the new density. The most useful point to remove is the one that maximises the increase in density. Repeat until satisfied.

Simple O(n logn) convex hull algorithms exist for two dimensions. Qhull is a nice C implementation.

ire_and_curses
  • 68,372
  • 23
  • 116
  • 141
  • My shapes must not be convex, e.g., it can look like a kidney. But, the idea of throwing points away is feasible, as I will have max of 2n points only. The goal is to maximize the precision P and recall R at the same time for the classifying if some point on a plane belongs to the area P1+P2, by using the new polygon P3 as a classifier. I don't understand your remark about density. Thanks for the anwsering. – Joanna Sep 10 '09 at 14:20
  • 1
    @Joanna: By density, I simply mean the number of points per unit area of space. I take your point about kidney shapes. There are a number of related questions that may be helpful to you. See e.g. http://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull – ire_and_curses Sep 10 '09 at 15:16
  • @ire_: The concave hull algorithm from the cited link is what I need. Perfect would give as an result a fixed number of points, or I will have to trim the result every iteration. Good day, thanks! – Joanna Sep 15 '09 at 12:07