perf: speed up Relate trait with an R-Tree backed EdgeSetIntersector

[michaelkirk]

Extracted from our conversation here: #641 (comment)

background:

The Relate trait (introduced in #639) topologically relates two geometries based on DE-9IM semantics, — whether A contains B, A is within B, A overlaps B, etc.

Part of the computation is finding all the intersections between the set of all segments in the geometries, which happens via the EdgeSetIntersector trait.

We currently only have a naive O(n^2) implementation which intersects every segment with every other.

The Bentley-Ottman class of sweep line algorithms can be much faster than our naive approach. We don't currently have a BO implementation, but @rmanoka et al have discussed before (some previous discussion #515 (comment))

JTS/GEOS currently rely on a "Monotonic Chain Sweeper" for this functionality, which I understand to be an augmented Bentley-Ottman algorithm (though I could be mistaken).

Another option, proposed here, would be an r-tree backed approach, which, apparently can perform reasonably well in practice for both sparsely and densely intersecting sets.

And, since we already have access to the rstar crate, might prove simpler to implement.

Part of this work should be some benchmarks on a useful array of cases to have some kind of baseline for assessing this work.

Note that other work, like perhaps a future Buffering feature could also benefit from this.

[rmanoka]

@michaelkirk I've created a geo-crossings crate that implements the Bentley-Ottman algorithm. I'm using it internally in a special-case of polygon-clipping algorithms; however, the main iterator interface should essentially be a drop-in replacement for the brute-force comparison.

I haven't published the crate; You could check the crate docs to see if this is usable for the Edge-Intersector use-case. You can also see the book that tries to explain the inner workings in some detail.

My hope is to transfer the code into this repo if it is usable. I think the BO algorithm may be of independent use (eg. polygon clipping, etc. use it as a sub-routine).

[michaelkirk]

This looks excellent @rmanoka, thanks for doing this.

Let me know if there's something I can help with.

[rmanoka]

I added a few benchmarks in the geo-crossings. Indeed the r-star heuristic is faster than the Bentley-Ottman in most common cases, and almost as good as the brute-force algorithm even if the O(n^2) pairs of lines intersect. I also agree the r-star heuristic is the best way to speed-up the EdgeSetIntersector.

[michaelkirk]

Nice benchmarks! I ran them as a sanity check and saw the same results.