Round up Intersects implementations #516

rmanoka · 2020-10-03T18:10:24Z

This PR completes the Intersects implementation for all pairs of current geo-types (discounting possible bugs)!

Add OGC-SA descriptions to geo-types docs
Verify existing implementations
Add implementations for containers: Geometry, GeometryCollection

See here for table describing the implementation status / map.

Interestingly, we didn't need geom-graph for this trait (presumably because this trait doesn't distinguish between interior and boundary). I also removed any usage of Contains trait in this trait for easier verification of correctness.

+ semantics of geo-types + validity of geo-types

+ simplify symmetric impl. macro + add macro intersects with rhs=pt impl from rhs=coord + verify for coord (hence point, multipoint) + verify for line (hence linestring, multilinestring) + verify for polygon (hence multipolygon, triangle) + add remaining for rect

+ add blanket impl for Geometry, Geom.Coll.

michaelkirk

One correctness concern around the triangle semantics comment, everything else was just style nits which you can feel free to ignore.

michaelkirk · 2020-10-06T01:33:23Z

geo-types/src/coordinate.rs

+/// This type does not represent any geospatial primitive,
+/// but is used in their definitions. The only requirement
+/// is that the coordinates it contains are valid numbers
+/// (for eg. not `f64::NAN`).


By "requirements" are you speaking to our concept of "validity"?

i.e. our geometric primitives have different rules for validity, but the validity rules all pre-suppose that their coordinates are not NAN?

I left this intentionally vague, as I also wasn't sure of the exact requirements. For instance, inf - inf is nan, so any operation that computes diffs (would end up producing nan coordinates if starting with inf).

michaelkirk · 2020-10-06T01:34:12Z

geo-types/src/lib.rs

+//!
+//! # Semantics
+//!
+//! The geospatial types provided here aim to adhere to the


Do we dare make this claim just yet?

Well, we just "aim to"; nothing wrong in aiming high!

geo-types/src/multi_line_string.rs

geo-types/src/multi_point.rs

michaelkirk · 2020-10-06T01:41:34Z

geo-types/src/point.rs

+///
+/// The _interior_ of the point is itself (a singleton set),
+/// and its _boundary_ is empty. A point is _valid_ if and
+/// only if the `Coordinate` is valid.


Do we mean only that the Coordinate cannot have an x or y value of NAN? Or do we mean more here?

I'm referring to validity requirement of Coordinate (which is vague too :) )

geo-types/src/polygon.rs

geo-types/src/triangle.rs

michaelkirk · 2020-10-06T01:49:28Z

geo/src/algorithm/intersects/rect.rs

+
+// Same logic as Polygon<T>: Intersects<Line<T>>, but avoid
+// an allocation.
+impl<T> Intersects<Line<T>> for Rect<T>


Are we missing a symmetric_intersects_impl!(Rect<T>, <Line>)?

michaelkirk · 2020-10-06T02:01:57Z

geo/src/algorithm/intersects/point.rs

 where
    T: CoordinateType,
+    Coordinate<T>: Intersects<G>,


michaelkirk

Thanks for kicking this off @rmanoka!

Co-authored-by: Michael Kirk <michael.code@endoftheworl.de>

+ missed Line-Rect intersection + added Geom-Geom test to verify impl of all combination

rmanoka · 2020-10-06T06:12:20Z

Seem to be getting a few CI failures due to some error in compiling proj: https://github.com/rmanoka/geo/runs/1213075197 . Any idea why?

--- stderr
pkg-config unable to find existing libproj installation: Failed to run `"pkg-config" "--libs" "--cflags" "proj" "proj >= 7.1.0"`: No such file or directory (os error 2)
building libproj from source
thread 'main' panicked at '
failed to execute command: No such file or directory (os error 2)
is `cmake` not installed?

build script failed, must exit now', /github/home/.cargo/registry/src/github.com-1ecc6299db9ec823/cmake-0.1.44/src/lib.rs:885:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

Error: Process completed with exit code 101.

michaelkirk · 2020-10-06T16:48:45Z

Seem to be getting a few CI failures due to some error in compiling proj: https://github.com/rmanoka/geo/runs/1213075197 . Any idea why?

We've made a fair number of changes to proj compilation and the underlying ci docker images... I suspect I broke something. I'll take a look!

michaelkirk · 2020-10-06T22:08:15Z

Seem to be getting a few CI failures due to some error in compiling proj: https://github.com/rmanoka/geo/runs/1213075197 . Any idea why?

We've made a fair number of changes to proj compilation and the underlying ci docker images... I suspect I broke something. I'll take a look!

Ok, I've fixed CI in #517

michaelkirk · 2020-10-07T05:00:28Z

bors try This should be good to merge now - but I’m not sure if you were wanting to make any further changes, so I’ll leave it to you to merge @rmanoka

…

On Oct 5, 2020, at 23:12, rmanoka ***@***.***> wrote: Seem to be getting a few CI failures due to some error in compiling proj: https://github.com/rmanoka/geo/runs/1213075197 . Any idea why? --- stderr pkg-config unable to find existing libproj installation: Failed to run `"pkg-config" "--libs" "--cflags" "proj" "proj >= 7.1.0"`: No such file or directory (os error 2) building libproj from source thread 'main' panicked at ' failed to execute command: No such file or directory (os error 2) is `cmake` not installed? build script failed, must exit now', /github/home/.cargo/registry/src/github.com-1ecc6299db9ec823/cmake-0.1.44/src/lib.rs:885:5 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace. Error: Process completed with exit code 101. — You are receiving this because your review was requested. Reply to this email directly, view it on GitHub, or unsubscribe.

bors · 2020-10-07T05:09:41Z

try

Build succeeded:

rmanoka · 2020-10-07T06:03:54Z

@michaelkirk Thanks for fixing the CI! I'm merging this now

bors r+

bors · 2020-10-07T06:13:48Z

Build succeeded:

639: Introduce the geomgraph module for DE-9IM Relate trait r=michaelkirk a=michaelkirk - [x] I agree to follow the project's [code of conduct](https://github.com/georust/geo/blob/master/CODE_OF_CONDUCT.md). - [x] I added an entry to `CHANGES.md` if knowledge of this change could be valuable to users. --- Fixes #513, #515 (I'm sorry it's so large) ~~I'm going to leave it as a draft (edit: 🤦 I failed to actually open the PR as a draft) while I wait to merge #636 and #638 and then do some rebasing, but I don't anticipate doing other large changes before review.~~ *update: ready for review!* Here's some of the earlier work in pursuit of this: #514 #516 #523 #524 #538 #552 #561 #611 #628 #629 #636 Primarily, this introduces the geomgraph module for a DE-9IM `Relate` trait. geomgraph implements a topology graph largely inspired by JTS's module of the same name: https://github.com/locationtech/jts/tree/jts-1.18.1/modules/core/src/main/java/org/locationtech/jts/geomgraph You can see some of the reference code if you omit the "REMOVE JTS COMMENTS" commit. In some places the implementation is quite close to the JTS source. The overall "flow" is pretty similar to that of JTS, but in the small, there were some divergences. It's not easy (or desirable) to literally translate a Java codebase making heavy use of inheritance and pointers to rust. Additionally, I chose to take advantage of `Option` and rust's enums with associated data to make some case analysis more explicit. There is a corresponding PR in our [jts-test-runner](georust/jts-test-runner#6) crate which includes the bulk of the tests for the new Relate trait. ## Algorithm Overview This functionality is accessed on geometries, via the `Relate` trait, e.g. `line.relate(point)` which returns a DE-9IM [`IntersectionMatrix`](https://en.wikipedia.org/wiki/DE-9IM#Matrix_model). The `Relate` trait is driven by the `RelateOperation`. The `RelateOperation` builds a `GeometryGraph` for each of the two geometries being related. A `GeometryGraph` is a systematic way to organize the "interesting" parts of a geometry's structure - e.g. where its vertices, lines, and areas lie relative to one another. Once the `RelateOperation` has built the two `GeometryGraph`s, it uses them to efficiently compare the two Geometries's structures, outputting the `IntesectionMatrix`. Co-authored-by: Michael Kirk <michael.code@endoftheworl.de> Co-authored-by: bors[bot] <26634292+bors[bot]@users.noreply.github.com>

639: Introduce the geomgraph module for DE-9IM Relate trait r=frewsxcv,rmanoka a=michaelkirk - [x] I agree to follow the project's [code of conduct](https://github.com/georust/geo/blob/master/CODE_OF_CONDUCT.md). - [x] I added an entry to `CHANGES.md` if knowledge of this change could be valuable to users. --- Fixes #513, #515 (I'm sorry it's so large) ~~I'm going to leave it as a draft (edit: 🤦 I failed to actually open the PR as a draft) while I wait to merge #636 and #638 and then do some rebasing, but I don't anticipate doing other large changes before review.~~ *update: ready for review!* Here's some of the earlier work in pursuit of this: #514 #516 #523 #524 #538 #552 #561 #611 #628 #629 #636 Primarily, this introduces the geomgraph module for a DE-9IM `Relate` trait. geomgraph implements a topology graph largely inspired by JTS's module of the same name: https://github.com/locationtech/jts/tree/jts-1.18.1/modules/core/src/main/java/org/locationtech/jts/geomgraph You can see some of the reference code if you omit the "REMOVE JTS COMMENTS" commit. In some places the implementation is quite close to the JTS source. The overall "flow" is pretty similar to that of JTS, but in the small, there were some divergences. It's not easy (or desirable) to literally translate a Java codebase making heavy use of inheritance and pointers to rust. Additionally, I chose to take advantage of `Option` and rust's enums with associated data to make some case analysis more explicit. There is a corresponding PR in our [jts-test-runner](georust/jts-test-runner#6) crate which includes the bulk of the tests for the new Relate trait. ## Algorithm Overview This functionality is accessed on geometries, via the `Relate` trait, e.g. `line.relate(point)` which returns a DE-9IM [`IntersectionMatrix`](https://en.wikipedia.org/wiki/DE-9IM#Matrix_model). The `Relate` trait is driven by the `RelateOperation`. The `RelateOperation` builds a `GeometryGraph` for each of the two geometries being related. A `GeometryGraph` is a systematic way to organize the "interesting" parts of a geometry's structure - e.g. where its vertices, lines, and areas lie relative to one another. Once the `RelateOperation` has built the two `GeometryGraph`s, it uses them to efficiently compare the two Geometries's structures, outputting the `IntesectionMatrix`. Co-authored-by: Michael Kirk <michael.code@endoftheworl.de> Co-authored-by: bors[bot] <26634292+bors[bot]@users.noreply.github.com>

Confirm to OGC-SFA standards

5413ddc

+ semantics of geo-types + validity of geo-types

rmanoka mentioned this pull request Oct 3, 2020

DE-9IM Proposal #515

Closed

rmanoka added 2 commits October 5, 2020 23:05

Clean-up Intersects

5f877c4

+ simplify symmetric impl. macro + add macro intersects with rhs=pt impl from rhs=coord + verify for coord (hence point, multipoint) + verify for line (hence linestring, multilinestring) + verify for polygon (hence multipolygon, triangle) + add remaining for rect

Complete rest of Intersects

f7b6527

+ add blanket impl for Geometry, Geom.Coll.

rmanoka force-pushed the feat/verify-intersects branch from a2596d9 to f7b6527 Compare October 5, 2020 17:51

rmanoka changed the title ~~Feat/verify intersects~~ Round up Intersects implementations Oct 5, 2020

rmanoka marked this pull request as ready for review October 5, 2020 18:06

rmanoka requested a review from michaelkirk October 5, 2020 18:06

michaelkirk reviewed Oct 6, 2020

View reviewed changes

michaelkirk approved these changes Oct 6, 2020

View reviewed changes

rmanoka and others added 2 commits October 6, 2020 11:00

Apply suggestions from code review

ee5314f

Co-authored-by: Michael Kirk <michael.code@endoftheworl.de>

Add missing impls

11ac854

+ missed Line-Rect intersection + added Geom-Geom test to verify impl of all combination

bors bot added a commit that referenced this pull request Oct 7, 2020

Try #516:

2b7e425

bors bot merged commit 6cb6979 into georust:master Oct 7, 2020

michaelkirk mentioned this pull request Mar 12, 2021

Introduce the geomgraph module for DE-9IM Relate trait #639

Merged

2 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Round up Intersects implementations #516

Round up Intersects implementations #516

rmanoka commented Oct 3, 2020 •

edited

Loading

michaelkirk left a comment

michaelkirk Oct 6, 2020

rmanoka Oct 6, 2020

michaelkirk Oct 6, 2020

rmanoka Oct 6, 2020

michaelkirk Oct 6, 2020

rmanoka Oct 6, 2020

michaelkirk Oct 6, 2020

michaelkirk Oct 6, 2020

michaelkirk left a comment

rmanoka commented Oct 6, 2020

michaelkirk commented Oct 6, 2020

michaelkirk commented Oct 6, 2020

michaelkirk commented Oct 7, 2020 via email

bors bot commented Oct 7, 2020

rmanoka commented Oct 7, 2020

bors bot commented Oct 7, 2020

Round up Intersects implementations #516

Round up Intersects implementations #516

Conversation

rmanoka commented Oct 3, 2020 • edited Loading

michaelkirk left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

michaelkirk left a comment

Choose a reason for hiding this comment

rmanoka commented Oct 6, 2020

michaelkirk commented Oct 6, 2020

michaelkirk commented Oct 6, 2020

michaelkirk commented Oct 7, 2020 via email

bors bot commented Oct 7, 2020

try

rmanoka commented Oct 7, 2020

bors bot commented Oct 7, 2020

rmanoka commented Oct 3, 2020 •

edited

Loading