search

pelias / polygon-lookup

Fast point-in-polygon intersection for large numbers of polygons.
72 stars 17 forks source link

check point inside containing orthogonal polygon before raycasting #49

Closed andrewharvey closed 3 years ago

andrewharvey commented 3 years ago

I'm wondering if the raycasting is contributing to slow queries, if it's a good idea that where the polygon is convex to compute the largest containing orthogonal polygon inside the polygon (http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/) during indexing.

Then when testing a point is within the polygon, you first check the rbush index, then next check a simple point inside the orthogonal polygon, and if that fails then do raycasting.

I haven't tested this so have no idea if it would improve performance, but I might give it a go if I find time, unless someone knows it's a bad idea?

andrewharvey commented 3 years ago

I'll close as polygon-lookup is already fast enough for me, what I thought was slow queries was actually my implementation issue.