Expanding a n-vertices polygon with a new data set to a n-vertices polygon

views:

337

answers:

+2 Q:

Expanding a n-vertices polygon with a new data set to a n-vertices polygon

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.

+2 A:

Beta 2009-09-10 00:06:16

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 2009-09-10 07:38:19

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 2009-09-10 07:40:27

+1 A:

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 log*n)* convex hull algorithms exist for two dimensions. Qhull is a nice C implementation.

ire_and_curses 2009-09-10 13:20:15

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 2009-09-10 14:20:56

@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 2009-09-10 15:16:42

@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 2009-09-15 12:07:44

ansaurus

tags:

views:

answers:

Expanding a n-vertices polygon with a new data set to a n-vertices polygon

related questions