It might be the case (in the case of intersecting two polygons) that the operation will return a polygon or a linestring or a point or nothing, the return type will need to reflect this. Maybe something like this?

trait Intersection<...> {
    fn intersection(&self, other) -> Option<IntersectionResult> {
        ...
    }
}

// not a fan of "Result" here since it sounds similar to std::result::Result
enum IntersectionResult {   
    Polygon(Polygon),
    LineString(LineString),
    Point(Point),
}

Note that this is different from the Intersects trait which simply returns a bool indicating if two geometries intersect at any point

As part of https://github.com/dabreegster/abstreet/issues/198, I've been working on adding an implementation of the Concave Hull algorithm primarily inspired by https://github.com/mapbox/concaveman. This implementation doesn't completely copy concaveman but it does ape the notion of using R trees in order to avoid a linear search through the points although my use of R trees relies on a circular envelope rather than the rectangular envelope that concaveman seems to use.

• [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.

This pull request addresses issue #544 The ClosestPoint method was implemented for the remaining members of the Geometry enum ie., Triangle, Rect and GeometryCollection and then implemented for the enum itself.

Explicitly declare rstar_0_8 and rstar_0_9 to make it clearer which version is being used. For backward compatibility, the rstar is now a feature that enables rstar_0_8

• [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.

per https://github.com/georust/geo/issues/513 I've written up a proposal about an addition I'd like to make to geo - introducing a DE-9IM module, and using it to help drive and correct some of our relation traits: e.g. Contains, Intersects. It would also make it much easier to add future traits like Disjoint, Touches, Crosses, etc.

Read the full proposal here: https://gist.github.com/michaelkirk/3ac4afe651fe24ad229dec0b56ec8f9d

(a gist allows easier editing than updating issue text in situ).

Please take a look! I spent some time adding context, in hope that it would be accessible to you even if you don't know what DE-9IM is.

The idea is that after getting a little feedback on the proposal, I'll add some specific issues to this tracking issue.

• [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.
  • I will do this if we decide we want this
• [x] Add entry to table of contents in lib.rs

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

Related: https://github.com/georust/geo/issues/80, https://github.com/georust/geo/issues/81

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

The Point struct has both x/y and lat/lon getter methods. This can be confusing when both are used in the same method.

Additionally i think using lat/lon is very dangerous in general. My experience is that many people think x = lat and y = lon ...

I've seen a mention of maybe replacing the boolean operation algorithms for example here: https://github.com/georust/geo/issues/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?

If we agree to merge this, the wkt repo should be archived, and all issues should be moved to this repo. I believe it would be good to merge it here because:

• geo-test-fixtures requires wkt, and wkt requires geo-types - creating a circular dependency between two repos, making development more complicated and error-prone
• this is a commonly used geo feature
• this is a pure Rust lib

This merges the entire history of the wkt repository from

https://github.com/georust/wkt/tree/dbd80f22099fc11ad69a1d072c3516f9a1ca4376

as a /wkt directory, and adds the CI and adds path links from Crates.toml files:

• wkt/Cargo.toml - link to /geo-types
• geo-test-fixtures/Cargo.toml - link to /wkt

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

• [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.

PR to import the boolean-ops code from geo-crossings. The impl. is not a 100% accurate to fixed-precision errors, but seems to handle the degenerate cases encountered in rust-geo-booleanop. When comparing the difference in outputs between the two algos, both algos panic in a few cases. The hope is to eventually improve some of the internal data-structures to be a 100% robust.

The performance, is about 1.25-1.5x worse when using the splay-tree, and about 1.5-2x if using vanilla btree. However, splay-tree seems to trigger an extra panic (not on the test cases, but while comparing outputs between the two impls), so I'm inclined to stick with vanilla BTree. Eventually, I hope we can figure out a intrusive impl. of BTree (eg. btree_slab) that is both performant, and fixes the fp accuracy issues.

• [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.

Essentially implementing ClosestPoint trait for spherical geometry. I named the new trait HaversineClosestPoint.

There is a slight (intentional) difference in behavior in the case when a segment (arc)'s length is very close to zero, the spherical algorithm will return Closest::SinglePoint instead of Closest::Indeterminate. I think even if the segment has degenerated to a point, there is still a closest point.

• [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.

Fixes: https://github.com/georust/geo/issues/575

Changed:

• SimplifyVW -> SimplifyVw
• SimplifyVWPreserve -> SimplifyVwPreserve
• simplifyvw -> simplify_vw

Unchanged:

• SimplifyVwIdx

When processing OSM data, sometimes we have bad geometry, and using the library for interior_point causes a panic. Normally, feeding bad geometry to a geometry library should return an error, not a panic, as this is a standard thing to expect.

I have to recover from the panic with panic::catch_unwind, which is not ideal.

https://github.com/georust/geo/blob/3b0d5738f54bd8964f7d1f573bd63dc114587dc4/geo/src/algorithm/sweep/active.rs#L54

[2022-12-04T19:14:40.661064000Z geo::algorithm::sweep::active] could not compare segments:
        Active(Segment{ LPt((444882789.06824327, 332473624.5), (444882817.0, 332473624.5))
        of Line { start: Coordinate { x: 444881047.0, y: 332473624.5 }, end: Coordinate { x: 444882817.0, y: 332473624.5 } }
         [NON/NON] })
        Active(Segment{ LPt((444882200.0, 332474331.0), (444882789.06824327, 332473624.5))
        of Line { start: Coordinate { x: 444882817.0, y: 332473591.0 }, end: Coordinate { x: 444882200.0, y: 332474331.0 } }
        [1st] [NON/NON] })
thread '<unnamed>' panicked at 'unable to compare active segments!', /Users/n/.cargo/registry/src/github.com-1ecc6299db9ec823/geo-0.23.0/src/algorithm/sweep/active.rs:54:13

https://github.com/georust/geo/issues/940#issuecomment-1332274260

https://stackoverflow.com/questions/57052434/can-i-guess-the-appropriate-epsilon-for-rdp-ramer-douglas-peucker