Is the performance of boolean operation algorithms good enough?

[garma83]

I've seen a mention of maybe replacing the boolean operation algorithms for example here:
#620

What is the general state of the boolean operation algorithms from a performance perspective in this crate?

Reason is I ran a (somewhat simple) comparison test between this crate and npm's Turf crate. The intersect algorithm on polygons of Turf seems to be magnitudes faster even though it is written in typescript. I had a look at the source, and one reason I saw is the turf algorithm does a bounding box comparison before the actual intersect.

I would have no problem doing this myself, but it leads me to the question: Are you guys happy with the current algorithms? What can I expect in the future?

Add-on question: Is it possible to retrieve the resulting intersection when doing the intersection between two polygons?

[rmanoka]

@erikpols We're happy to improve the performance of our impls. The bbox. heuristic has been discussed in #649 before; we could discuss it there. Reg. retreiving the intersection: it is not available here, but refer #620 for other options.

PRs / interest in impl. either of these is very welcome; please revive the issue, and we can plan it out.

[garma83]

ok ty. Those links are super helpful to me, I wasn't aware of geo-clipper and it makes all the difference. I understand its a c++ implementation but for me that's ok.

But just FYI it was a 15-30x difference

[rmanoka]

@erikpols Could you share a minimal repo. of your bench-marking code? Would be very helpful when we address the bbox. issue.

[urschrei]

@rmanoka The easiest thing would be to benchmark and test geo-crossings for this, right? Turf uses Martinez-Rueda (IIRC), but Bentley-Ottmann should be comparable in terms of speed.

[rmanoka]

Yeah, we have some benchmarks in geo-crossings that show r-star heuristics is the best "edge-intersector" used by the Intersects and Relate impls. If we can get some good dataset to benchmark against, we can have a before-after comparison and try adding it.

[michaelkirk]

I prototyped an integration of rtree into geo here to see what kind of performance wins we might get:
https://github.com/georust/geo/tree/mkirk/rstar-edge-set-intersector

A good benchmark suite to compare against would be great. Lacking good benchmarks, here are some mediocre ones from benches/relate.rs :

relate overlapping 50-point polygons:

  time: [28.870 us 28.905 us 28.946 us]
change: [-12.304% -12.144% -11.999%] (p = 0.00 < 0.05)
        Performance has improved.

disjoint polygons

  time: [100.13 us 100.53 us 100.96 us]                              
change: [-6.0273% -5.8229% -5.6196%] (p = 0.00 < 0.05)
        Performance has improved.

relate norway (8854 points) with a rotated norway:

  time: [8.1432 ms 8.1851 ms 8.2257 ms]                                   
change: [-98.925% -98.918% -98.912%] (p = 0.00 < 0.05)
        Performance has improved.

relate norway (8854 points) with an offset (but still overlapping) norway:

  time: [7.9076 ms 7.9426 ms 7.9762 ms]                            
change: [-98.943% -98.938% -98.933%] (p = 0.00 < 0.05)
        Performance has improved.

jts test suite:

Interestingly, benching against the entire JTS test suite takes a pretty big hit. I haven't dug into why yet. It does have an outsized emphasis on pathological geometries, so maybe that's responsible.

  time: [1.0527 ms 1.0564 ms 1.0603 ms]                                   
change: [+25.389% +25.851% +26.302%] (p = 0.00 < 0.05)
        Performance has regressed.

[urschrei]

Interesting that you're seeing at most a ~99 % speedup (which to be clear is great), vs a purported 15x to 30x speedup from a JS M-R implementation. @erikpols it would be great to get a look at your test suite if at all possible…

[michaelkirk]

Yeah, the 99% reduction (100x speedup) is pretty wild. I'd love it if someone can scrutinize it, or at least run the benches themselves against main to see if they get a similar speedup.

[garma83]

Hi guys,

Interesting that you're seeing at most a ~99 % speedup (which to be clear is great), vs a purported 15x to 30x speedup from a JS M-R implementation. @erikpols it would be great to get a look at your test suite if at all possible…

I prepared a repo with a minimal example of both approaches. you can find it here:
https://github.com/erikpols/vellum-public/blob/master/geo-performance-rust/src/main.rs

the data consists of a set of cadastre plots that is intersected with a set of regulatory zones. The data is retrieved as FeatureCollections, and then first converted to vectors of Polygons, which are then input for both algorithms.

results for geo
data retrieved after: 2280
converted plots after: 2287
zones converted after: 2299
nr plots 316 nr zones 91
Intersection tests: 28756 Intersections: 974 Non-intersections: 27782
Intersection test done after: 137589

results for geo_clipping
data retrieved after: 1988
converted plots after: 1995
zones converted after: 2007
nr plots 316 nr zones 91
Intersection tests: 28756 Intersections: 948 Non-intersections: 27808
Intersection test done after: 3211

Interestingly enough the results are not the same. Im guessing this has to do with the multiply parameter that clipper needs (clipper works with integers so all data needs to be multiplied by a parameter first)

[michaelkirk]

I've clarified the benchmark a little bit to show the output of geo-clipper vs geo here: https://github.com/erikpols/vellum-public/compare/master...michaelkirk:mkirk/clarify-bench?expand=1

$ cargo run --release    
   Compiling geo-performance-rust v0.1.0 (/Users/mkirk/src/georust/vellum-public/geo-performance-rust)
    Finished release [optimized] target(s) in 1.08s
     Running `target/release/geo-performance-rust`
data retrieved after: 8798
converted plots after: 8798
zones converted after: 8799
nr plots 316 nr zones 91
## geo-clipper
Intersection tests: 28756 Intersections: 948 Non-intersections: 27808
geo-clipper intersection test duration: 474   <----
## geo
Intersection tests: 28756 Intersections: 974 Non-intersections: 27782
geo intersection test duration: 2780   <----

So initially, I'm seeing that geo is 5x-6x slower.

I've improved the situation a bit by doing a bbox check to short-circuit the intersection computation here:
https://github.com/erikpols/vellum-public/compare/master...michaelkirk:mkirk/geo-perf?expand=1

$ cargo run --release                          
   Compiling geo v0.20.1 (https://github.com/georust/geo?branch=mkirk/intersection-perf#915a0670)
   Compiling geo-performance-rust v0.1.0 (/Users/mkirk/src/georust/vellum-public/geo-performance-rust)
    Finished release [optimized] target(s) in 1.87s
     Running `target/release/geo-performance-rust`
data retrieved after: 8557
converted plots after: 8558
zones converted after: 8559
nr plots 316 nr zones 91
## geo-clipper
Intersection tests: 28756 Intersections: 948 Non-intersections: 27808
geo-clipper intersection test duration: 475   <----
## geo
Intersection tests: 28756 Intersections: 974 Non-intersections: 27782
geo intersection test duration: 935    <----

With that, we're better, but still about 2x as slow as the clipper implementation.

It's worth pointing out that geo vs. geo-clipper implementations in your example are doing two pretty different things:

• geo-clipper: is constructing the actual intersection (multi)polygon between two shapes, and measuring its area.
• geo: is only checking wether an intersection exists (even if it's a zero area intersection, like touching parcels)

This might explain the discrepancy in the results (Intersections: 948 vs Intersections: 974). I'm a bit surprised though - if anything, I'd expect construction (like geo-clipper is doing) to be a more complicated operation than only checking for the existence of an intersection (like geo is doing).

One question, that I haven't dug into yet, is if geo-clipper is using robust operations like we do in geo (which also might explain the discrepancy in results and perf)

In any case, it sounds like ultimately you're looking to generate the actual shape of the intersection, not just check for the existence, right? AFAIK geo-booleanops is the only option for that in pure rust.

I've shown that integration here: https://github.com/erikpols/vellum-public/compare/master...michaelkirk:mkirk/geo-booleanop?expand=1

It's similarly 2x slower than geo-clipper.

$ cargo run --release           
   Compiling geo-performance-rust v0.1.0 (/Users/mkirk/src/georust/vellum-public/geo-performance-rust)
    Finished release [optimized] target(s) in 1.14s
     Running `/Users/mkirk/src/georust/vellum-public/geo-performance-rust/target/release/geo-performance-rust`
data retrieved after: 9211
converted plots after: 9211
zones converted after: 9212
nr plots 316 nr zones 91
## geo-clipper
Intersection tests: 28756 Intersections: 948 Non-intersections: 27808
geo-clipper intersection test duration: 502   <----
## geo
Intersection tests: 28756 Intersections: 974 Non-intersections: 27782
geo intersection test duration: 1084    <----

[michaelkirk]

Oh also, I've turned this dataset into a benchmark for the geo repo in #828. Thanks for the test cases! Hopefully we'll continue to find ways to speed it up.

[garma83]

No problem happy to help;

BTW im made a bit of a classical error; I wondered why I got 30-40x, and you 5-6x. But I ran the tests in debug mode. No big implications though. Fixed below.

I included the bbox tests as well in the repo, and also for the geo-clipper approach for good measures. Interestingly enough, including the bbox test with clipper also leads to an improvement. This might be explained by the fact that doing the bbox in advance saves having to do the conversion to integers for those polygons, which is what geo-clipping does. However, the downside of course is that the bbox comparison is now done twice.

data retrieved after: 1745
converted plots after: 1747
zones converted after: 1749
nr plots 316 nr zones 91
## geo-clipper started at: 0
Intersection tests: 28756 Intersections: 948 Non-intersections: 27808
geo-clipper intersection test duration: 686
## geo-clipper started at: 0
Intersection tests: 28756 Intersections: 948 Non-intersections: 27808
geo-clipper bbox intersection test duration: 273
## geo
Intersection tests: 28756 Intersections: 974 Non-intersections: 27782
geo intersection test duration: 3603
## geo
Intersection tests: 28756 Intersections: 974 Non-intersections: 27782
geo bbox intersection test duration: 1331

Correct, I also need the actual intersection itself, so that is a benefit of clipper for me.

Knowing the dataset, the different intersection results don't surprise me. Some of that data has shared lines between the zones and the plots. So small discrepancies in the input data (like the multiplier I mentioned introduces) will result in small differences in intersection result. To fully negate this for the test, it might be possible to multiply the datasets beforehand and convert them to integers, and only then feeding them to both. That should lead to equal results.

I'm getting the idea that clipper is some kind of standard library/ approach that seems to be ported to several languages 'as is'. Might be an idea to do that as well? The typescript version is fairly easy to read.

[urschrei]

All other things being equal, (which is tricky, see below) integer operations will be faster than floating point on x86_64 (and probably on aarch64) in many cases, although this is an extremely general statement; pipeline length, cache, and compiler optimisations are big confounding factors here, and that's just the tip of the iceberg. At the very least we should be comparing perf on the same machine.

[garma83]

Indeed; but I wonder whether the multiplication (tot avoid that too much details are lost when using lon/lat coordinates) as well as the casting to integers offset the benefits enough. Apparently it does but it surprises me

[michaelkirk]

@erikpols, in case you missed it, as of geo-0.21, we have boolean operations (construction an Intersection, Union, Xor, or Difference) built directly into geo:

https://docs.rs/geo/latest/geo/algorithm/bool_ops/trait.BooleanOps.html

The approach is slightly different from geo-boolean-ops - it's currently slower, but does handle some edge cases better.
#620 (comment)

I've updated my fork of your benchmark to test it here: https://github.com/erikpols/vellum-public-geo-performance-rust/compare/master...michaelkirk:mkirk/geo-booleanop?expand=1

[rmanoka]

We have a bool ops. implementation, and its performance is in the ball-park of the bool predicates implementation (Relate); so this issue is safe to close? Will close in a couple of days unless anything yet to be addressed.