-1

I'm working on R on the following problem.

I have a set of polygons defined by their vertices (x and y coordinates).

I also have a set of points (with given x and y coordinate), and I need an efficient algorithm which would assign each point to each polygon with some probability.

One algorithm, for example, could be testing the distances of the test point from the centroid of each polygon - and the smaller the distance, the higher the probability of that point being in the polygon.

Any other ideas / enhancements to the above idea would be appreciated.

wrahool
  • 1,101
  • 4
  • 18
  • 42
  • possible duplicate: [Distance of point feature to nearest polygon in R](http://stackoverflow.com/q/16448402/1036500) – Ben Jul 23 '13 at 06:14
  • Along the lines of your idea, you could look at making the probability inversely proportional to the distance to the closest vertex of each polygon. Moreover you could project the point onto the polygon and measure that distance. You could expand your question with what you are using this for, why is the algorithm you gave not sufficient? – pippin1289 Jul 23 '13 at 06:14
  • I'm looking for something that would give more accurate results than the algorithm that I've used. – wrahool Jul 23 '13 at 06:21
  • In that case, I think projecting the point to its nearest point on the polygon and measuring that distance would be the most accurate – pippin1289 Jul 23 '13 at 06:22
  • How would you suggest projecting the point to a polygon? – wrahool Jul 23 '13 at 06:40
  • I'm not sure about efficiency, but in terms or accuracy, there is the `point.in.polygon` function within the `sp` package. – Marc in the box Jul 23 '13 at 09:51

1 Answers1

1

I would not only order the polygons by probability related on the distance. I would as a first (pre process) step calculate a minimal circle around each polygon and store the center and radius. With this you can eliminate very efficient polygons from your further testing, for which the point is outside the surrounding circle of the polygon.

MrSmith42
  • 9,961
  • 6
  • 38
  • 49