PointInPolygon#choose_good_ray is too slow

[PikachuEXE]

I have modified PointInPolygon#point_location to use random_ray directly instead Then it becomes very fast for me

And the result is acceptable too (observed on a map with markers and polygons)

So I wonder if it's possible to add an option to pass when calculating

I might make a PR later

[DanielVartanov]

Hey there!

That's great, could you prepare some sample benchmarks please? Also, you're saying that "result is acceptable too", does it mean that observable return values of the method were somehow changed? Sorry, the phrase confused me.

[PikachuEXE]

Oh sorry about confusing phrase.

When I run with choose_good_ray, it keeps running for > 20s and I have to terminate it. But when I use random_ray, it only takes < 0.5s.

Let me find some example points and create a benchmark script.

[PikachuEXE]

Gist created: https://gist.github.com/PikachuEXE/71c6d0961e6bdc31846f

[DanielVartanov]

Hi,

I read your gist, thanks a lot for it. The main reason why we have to run #choose_good_ray is because whenever a tracing ray includes a vertex of your polygon, the method gives incorrect result. If your polygon is large and has lots of vertices, you have a high risk of getting incorrect result if you don't run #choose_good_ray.

If you really need to increase performance of this method, you should choose other ways. For instance, #good_ray? checks the following:

edges.none? { |edge| edge.parallel_to?(ray) }

But in fact if the tracing ray is parallel to some edge, it is fine. The problem is when the tracing ray includes an edge completely.

Thanks, Daniel

[PikachuEXE]

If I only remove

edges.none? { |edge| edge.parallel_to?(ray) }

from good_ray? then it is fast enough also But adding the above code will make the calculation VERY long