search

georust / geo

Geospatial primitives and algorithms for Rust
https://crates.io/crates/geo
Other
1.51k stars 195 forks source link

Performance fix for point in polygon #1004

Closed b4l closed 1 year ago

b4l commented 1 year ago
michaelkirk commented 1 year ago

Some testing around edge cases, like if the ray is passing through an internal or external vertex would be nice, but I'm biased towards merging it even without that.

Actually! It looks like we already this: see point_in_polygon_with_ray_passing_through_a_vertex_test and neighbors.

urschrei commented 1 year ago

Some testing around edge cases, like if the ray is passing through an internal or external vertex would be nice, but I'm biased towards merging it even without that.

Actually! It looks like we already this: see point_in_polygon_with_ray_passing_through_a_vertex_test and neighbors.

I love past, diligent [whoever contrived that test]

michaelkirk commented 1 year ago

Doing a little git archeology... @bjornharrtell is responsible for most of the current implementation, introduced in https://github.com/georust/geo/pull/972.

Maybe @bjornharrtell would like to review?

And the good tests were from @amatissart as part of https://github.com/georust/geo/pull/526

bjornharrtell commented 1 year ago

Nice work 🙂

bjornharrtell commented 1 year ago

Had a second check and nice catch about the orientation checks. I don't remember why I ended up using those as they were not in the original code that I ported...

b4l commented 1 year ago

Thanks for the reviews!

Honestly the tests were what gave me confidence to open the pr in the first place.

I think the only open issue is whether to put back in the proceeding bounding rect intersection test. No preference here.

michaelkirk commented 1 year ago

I think the only open issue is whether to put back in the proceeding bounding rect intersection test. No preference here.

My best guess is to leave it out, since it seemed to only slow things down in all of our benchmarks.

How'd you feel about including this bench though? I think it's an interesting case if we revisit this code in the future: https://github.com/georust/geo/commit/efac869b7b7430bb27bb91922bacdf4bcfaa1e21

b4l commented 1 year ago

How'd you feel about including this bench though? I think it's an interesting case if we revisit this code in the future: efac869

Sure, if it helps. Performance wise your nice comb would be even better including a version with the point inside the bounds.

michaelkirk commented 1 year ago

Sure, if it helps. Performance wise your nice comb would be even better including a version with the point inside the bounds.

Sure, I'll throw one together right now, standby.

michaelkirk commented 1 year ago

Ok done! https://github.com/georust/geo/compare/coord-pos...mkirk/coord-pos?expand=1

If it looks good to you, merge it into this branch, and then we can merge the whole shebang into main.

michaelkirk commented 1 year ago

btw, here's the bench diff for that new case:

point horizontal to comb teeth aka bart's haircut
                        time:   [16.153 ns 16.169 ns 16.189 ns]
                        change: [+156.71% +157.26% +157.85%] (p = 0.00 < 0.05)
                        Performance has regressed.

I think that's fine given the pathological nature of the input.

b4l commented 1 year ago

@michaelkirk thanks! I hope I did this right with the merge.

bors[bot] commented 1 year ago

Build succeeded: