Incorporate rust-geo-booleanop algorithms directly into geo?

[frewsxcv]

https://github.com/21re/rust-geo-booleanop

Related: #80, #81

Reach out to the maintainer? Add as a dependency? Offer to take over the crate? Copy and paste and update our license files?

[Nevsden]

Is it stable enough? I’ve read it still lacks correctness for boolean op on some test cases.

[Nevsden]

Maybe the geo-clipper crate could be considered instead. The C++ port of the AngusJ clipper library written originally in Pascal is a 1:1 port and seems to be quite stable since many years. It also has a nice inward/outward offsetting function on polygons, which I already tried.

[dabreegster]

Maybe the geo-clipper crate could be considered instead

One advantage of rust-geo-booleanop is that it's just Rust, not bindings to C++, so it also compiles to wasm. Or do you think porting clipper to rust is reasonable?

[frewsxcv]

Is it stable enough? I’ve read it still lacks correctness for boolean op on some test cases.

Thank you for calling this out as this is something we should definitely consider. If you recall where you saw a discussion on correctness, would love to link to that from this issue.

[urschrei]

Yes, correctness in some cases is definitely still an issue, and I wouldn't advocate moving functionality into geo until we have a clear sense of where the failing cases are and whether existing efforts (robust etc) can help to resolve them (to be clear: I don't think this is a concern if the georust org were to adopt the crate). I would also prefer not to use geo-clipper.

[urschrei]

This seems to be the main issue around stability: 21re/rust-geo-booleanop#17

[Nevsden]

Yes, correctness in some cases is definitely still an issue, and I wouldn't advocate moving functionality into geo until we have a clear sense of where the failing cases are and whether existing efforts (robust etc) can help to resolve them (to be clear: I don't think this is a concern if the georust org were to adopt the crate). I would also prefer not to use geo-clipper.

But if I remember correctly, the problem is deeply rooted with the data representation of the line sweep algorithm, which could get quite nasty to fix. The crate uses a tree to represent event that are linked to incoming and outgoing end points of a line segment, which are swept over with a line sweeping algorithm. The problem seems to be that the sorting of these events is not stable enough resulting in missing sweep events which ultimately result in a panic or broken result.

Assuming, georust were to adopt the crate, I think if we could fix that issue, we would greatly forward development of the crate.

[urschrei]

But if I remember correctly, the problem is deeply rooted with the data representation of the line sweep algorithm

Yes I believe so. But I know that @bluenote10 had proposed an alternative (splay tree based?) data structure and made some progress towards integrating it, and that @daef had done some work too.

[bluenote10]

Yes and I still think this should all be fixable, but certainly requires some work. Due to a shift of priorities I didn't had time to finish it, but the ideas should be documented in the linked issue.

[Nevsden]

Just to mention another repo, which may be usable in the next few months:
CavalierContours is a C++ implementation for boolean ops (and offsetting) of closed polylines.
The author mentions he is currently developing an implementation purely in rust here.

[anlumo]

Please don't integrate C or C++ libraries. I'm using geo in a wasm application, and you can't use those libraries together with Rust's wasm32-unknown-unknown target.

[urschrei]

It is vanishingly unlikely that we'll integrate any c++ libraries into geo – people are free to propose the addition of wrapper crates for these and can include primitives that easily conform to geo-types, or take the plunge and directly use them.

[rmanoka]

I recently coded up boolean-ops based on the Martinez-Rueda-Freito algorithm here. I don't think the impl is 100% accurate to fp errors but seems to pass all the reference test-cases available in rust-geo-booleanop, incl. some where the latter panics.

The performance is worse though: about 2x slower in the worst-case. However, the impl. is modular, and we hope to eventually get it to be accurate and fast. We also use the Kernel traits, so we might eventually be able to get it working with integers, like geo-clipping. If there's interest, we could merge the impl. here.

[frewsxcv]

That sounds great to me! My vote is to merge the impl here. Having any accurate implementation (no matter how slow) is better than having none.

[urschrei]

That sounds great to me! My vote is to merge the impl here. Having any accurate implementation (no matter how slow) is better than having none.

💯 this!

[michaelkirk]

That sounds great @rmanoka!

[frewsxcv]

Boolean operations were added in #835. Thanks @rmanoka!