algorithm - Given a set of polygons and a series of points, find the which polygons are the points located

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

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.