georust
GeometryGraph and PreparedGeometry multi-threaded (Send)
Make GeometryGraph and PreparedGeometry Send so that it can be used by multiple threads.
Based on and depends on: https://github.com/georust/geo/pull/1197
#1197 has been merged - could you do a rebase or merge to minimize the diff?
I have rebased, but I haven't had time to work any further on this yet (feel free to make changes if you have time).
Some of the test fails seem like numeric precision errors, they are also present on main. There is one failing test left (debug assert), which I don't know why is failing.
3 failed: algorithm::interior_point::test::polygon_cell_test ▐
thread 'algorithm::interior_point::test::polygon_cell_test' panicked at geo/src/algorit▐
hm/relate/geomgraph/edge_end_bundle_star.rs:112:21: ▐
side_location conflict with coordinate: Coord { x: 2.0, y: 1.0 }, right_location: Insid▐
e, current_location: Outside ▐
The lifetime in prepared geometry is tedious to work with. Could that be replaced by a Cow or maybe a owned version of the geometrygraph?
The lifetime in prepared geometry is tedious to work with. Could that be replaced by a Cow or maybe a owned version of the geometrygraph?
Just realized that is exactly how it is now...
This seems to be working now.
It appears that a new geometrygraph + intersection matrix is created for every point I want to check against the preparedgeometry.
It appears that a new geometrygraph + intersection matrix is created for every point I want to check against the preparedgeometry.
Can you expand on this and / or illustrate it with a minimal test case?
My use case is roaring-landmask, here's a PR where I am running against these changes: https://github.com/gauteh/roaring-landmask/pull/28, in https://github.com/gauteh/roaring-landmask/blob/georust-prepared/src/shapes.rs#L129 I check if a point is in any of the polygons using is_covers:
self.geom.relate(&p).is_covers()
this creates a geometrygraph of the point p and tests it against the PreparedGeometry. I believe geos has a PreparedPolygon/PreparedMultiPolygon with specializations for checking various relates towards a point.
In roaring-landmask this may be tested with e.g.: cargo test --features nightly --release -j 1 many -- --nocapture
It appears that a new geometrygraph + intersection matrix is created for every point I want to check against the preparedgeometry.
That's right. The difference with PreparedGeometry is that the Polygon's geometry graph isn't created from scratch every time.
The point's graph will be created from scratch, since it's a different point every time, but it should also be a pretty trivial graph.
I check if a point is in any of the polygons using is_covers:
Note that in the case of points and polygons, polygon.relate(points).is_covers() is the same as polygon.instersects(point).
The GeometryGraph is a very general tool, built to handle all the de-9im relations for all geometry types. If you are only interested in "point intersects polygon" checks, there is likely a faster approach involving less machinery - maybe ray casting, but I don't think we have an implementation of that yet.
It appears that a new geometrygraph + intersection matrix is created for every point I want to check against the preparedgeometry.
That's right. The difference with
PreparedGeometryis that the Polygon's geometry graph isn't created from scratch every time.The point's graph will be created from scratch, since it's a different point every time, but it should also be a pretty trivial graph.
Indeed, the tree has no members.
I check if a point is in any of the polygons using is_covers:
Note that in the case of points and polygons,
polygon.relate(points).is_covers()is the same aspolygon.instersects(point).
Is there any performance difference? Or exactly the same?
The GeometryGraph is a very general tool, built to handle all the de-9im relations for all geometry types. If you are only interested in "point intersects polygon" checks, there is likely a faster approach involving less machinery - maybe ray casting, but I don't think we have an implementation of that yet.
So it appears, and that makes sense (to start with). I think that this PR is mostly functional now. I had to make a few slightly messy changes to satisfy borrowing rules, without doing a much greater re-structuring. There is some cleanup to be done, but it should be a useful feature (and actually a pretty cool plus over geos, where it is not safe to share the PreparedGeometry) to other applications. Sadly, I don't think it will make much difference to my issue (https://github.com/georust/geo/issues/1184).
@michaelkirk I've rebased and tidied this up and appeased young master Clipperton – I only have one query regarding the "satisfy rust's borrowing rules section" but otherwise this hasn't added any obvious complexity to our GeomGraph machinery (though it's difficult to imagine how that would be possible…), and the Send bound will probably come in useful at some point. WDYT?
@gauteh I'm going to convert this to a draft until the comments and merge conflicts are addressed
Development seems to have stalled on this, so I'm going to close this pull request. @gauteh If you get around to resuming work on this, please reopen!