Given a set of polygons and a series of points, fi

Question

This is a question similar to the one here, but I figure that it would be helpful if I can recast it in a more general terms.

I have a set of polygons, these polygons can touch one another, overlap and can take on any shape. My question is, given a list of points, how to devise an efficient algorithm that find which polygons are the points located?

One of the interesting restriction of the location of the points is that, all the points are located at the edges of the polygons, if this helps.

I understand that r-trees can help, but given that I am doing a series of points, is there a more efficient algorithm instead of computing for each point one by one?

Answer 1

I think you are bumping up against intuition about the problem (which is a quasi-analog perception) versus a computational approach which is of necessity O(n).

Given a plane, a degenerate polygon (a line), and an arbitrary set of points on the plane, do the points intersect the line or fall "above" or "below" it? I cannot think of an approach that is smaller than O(n) even for this degenerate case.

Either, each point would have to be checked for its relation to the line, or you'd have to partition the points into some tree-like structure which would require at least O(n) operations but very likely more.

If I were better at computational geometry, I might be able to say with authority that you've just restated Klee's measure problem but as it is I just have to suggest it.

Answer 2

If points can only fall on the edges, then you can find the polygons in O(n) by just examining the edges.

If it were otherwise, you'd have to triangulate the polygons in O(n log n) to test against the triangles in O(n).

You could also divide the space by the line extended from each segment, noting which side is inside/outside of the corresponding polygon. A point is inside a polygon if it falls on an edge or if it's on the inside part of every edge of the polygon. It's O(n) on the number of edges in the worst case, but tends to O(m) on the number of polygons on the average case.

An R-tree would help in both cases, but only if you have several points to test. Otherwise, constructing the R-tree would be more expensive than searching through the list of triangles.

Answer 3

The key search term here is point location. Under that name, there are many algorithms in the computational geometry literature for various cases, from special to general. For example, this link lists various software packages, including my own. (A somewhat out-of-date list now.)

There is a significant tradeoff between speed and program complexity (and therefore implementation effort). The easiest-to-program method is to check each point against each polygon, using standard point-in-polygon code. But this could be slow depending on how many polygons you have. More difficult is to build a point-location data structure by sweeping the plane and finding all the edge-edge intersection points. See the this Wikipedia article to see some of your options.