Implement `Stitch` trait

[RobWalt]

This is an implementation of a trait which offers functionality to stitch up geometry parts that were split at some point of time. It's an alternative to boolean operations which doesn't panic and returns user friendly errors instead.

This is mostly used within the new SpadeBoolops trait which needs to stitch together some parts of a triangulation. Hence, this trait is mostly used on triangles but isn't constraint on those and was implemented here for a more general scenario. Here are some rough visuals of what the operation does

---

• [x] I agree to follow the project's code of conduct.
• [x] I added an entry to CHANGES.md if knowledge of this change could be valuable to users.

---

TODOs

• [x] add docs for main trait
• [x] Add simple benchmarks
• [x] try to optimize performance

[RobWalt]

This PR is in a reviewable state now. Please feel free to take a look. It's important for the SpadeBoolops PR.

[frewsxcv]

how does this compare to the boolean operation "union"?

[RobWalt]

how does this compare to the boolean operation "union"?

Compared to the BooleanOps trait this is probably not as performant. One of the checks which reassociates holes needs to construct Polygons from LineString-rings just for containment checks. This and some other allocations probably make it less performant.

On the other hand, this is just another safe (non-panic) alternative to BooleanOps which provides robustness in all cases if the invariants of the algo are fulfilled at it's start. While writing this I wonder though if BooleanOps would be safe operation under exactly the same invariants though. I probably need to do some more testing on it and we might be able to scratch this algo. Nevertheless, even if that were the case, I couldn't prove that it wouldn't hit one of the BooleanOps panics.

Thanks for asking those kinds of questions!

[RobWalt]

Sorry this sat here so long @RobWalt!

All of the performance related commentary is "take it or leave it". I'd be happy to follow up on that later. I'm primarily interested in the correctness aspect, and have asked a few questions that I'd like to understand better.

Thanks for your efforts in reviewing this. I'd also like to improve performance here since it's a bottleneck in the SpadeBoolops so I'll take another shot in optimizing here. I'll try to add some benchmarks first so we can meassure improvements.

[RobWalt]

Thanks for the thorough review @michaelkirk. In the end we got a

27% + 88% + 8% which roughly equates 92% total

performance improvement.

[frewsxcv]

@michaelkirk Do you have any outstanding reservations before merging this?

[michaelkirk]

Yes, I'd like to take another look now that it's been reformulated in terms of triangles. I'll try to do that in the next couple days.

[piaoger]

@RobWalt I tried your is-geo-boolops-still-broken tool, stitch/spade-boolops PRs. I am using them in my in-house tool and polygon boolean works really good. What make these great PRs suspended, need more tests or codeview?

[RobWalt]

Currently, this PR here boils down to this comment here https://github.com/georust/geo/pull/1087#discussion_r1447981666 . Once that is resolved, we should be able to merge this PR and continue with the Boolops PR. Given that someone (you) actually uses the new feature I might be motivated enough to tackle it! Thanks for the feedback by the way!

[piaoger]

Currently, this PR here boils down to this comment here #1087 (comment) . Once that is resolved, we should be able to merge this PR and continue with the Boolops PR. Given that someone (you) actually uses the new feature I might be motivated enough to tackle it! Thanks for the feedback by the way!

A robust geometry boolean library is always welcome and I find SpadeBoolops is quit good :)

[urschrei]

How do we feel about merging (once the changelog conflict is resolved)?

[RobWalt]

How do we feel about merging (once the changelog conflict is resolved)?

I'm feeling good about it now 👍🏼

[RobWalt]

Dunno, CI fails for weird reasons. spade seems to leak a private type somehow on an older rust version CI test. I can't reproduce that locally on rust 1.80. The relevant command is

cargo check --all-targets --no-default-features

[urschrei]

I don't think we're committed to supporting v1.70, so we should probably bump our test version.

[urschrei]

OK we'll try again when #1201 merges

[urschrei]

Dunno, CI fails for weird reasons. spade seems to leak a private type somehow on an older rust version CI test. I can't reproduce that locally on rust 1.80. The relevant command is

cargo check --all-targets --no-default-features

A rebase against main should fix it.

[RobWalt]

Dunno, CI fails for weird reasons. spade seems to leak a private type somehow on an older rust version CI test. I can't reproduce that locally on rust 1.80. The relevant command is cargo check --all-targets --no-default-features

A rebase against main should fix it.

It finally went through 👍🏼

[urschrei]

Last call, would like to merge this tomorrow.

[RobWalt]

Last call, would like to merge this tomorrow.

@urschrei bump 🥺👉👈