PointInPolygon#choose_good_ray is too slow #5

PikachuEXE opened this Issue Aug 13, 2013 · 5 comments


None yet
2 participants

PikachuEXE commented Aug 13, 2013

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 commented Aug 13, 2013

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 commented Aug 13, 2013

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.


DanielVartanov commented Aug 16, 2013


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.



PikachuEXE commented Aug 16, 2013

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

@PikachuEXE PikachuEXE changed the title from PointInPolygon#choose_good_ray is too low to PointInPolygon#choose_good_ray is too slow May 27, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment