Determine the position of a Coordinate relative to a geometry. #538

michaelkirk · 2020-11-12T21:36:40Z

Examples

use geo::{polygon, Coordinate};
use geo::coordinate_position::{CoordinatePosition, CoordPos};
let square_poly = polygon![(x: 0.0, y: 0.0), (x: 2.0, y: 0.0), (x: 2.0, y: 2.0), (x: 0.0, y: 2.0), (x: 0.0, y: 0.0)];
let inside_coord = Coordinate { x: 1.0, y: 1.0 };
assert_eq!(square_poly.coordinate_position(&inside_coord), CoordPos::Inside);
let boundary_coord = Coordinate { x: 0.0, y: 1.0 };
assert_eq!(square_poly.coordinate_position(&boundary_coord), CoordPos::OnBoundary);
let outside_coord = Coordinate { x: 5.0, y: 5.0 };
assert_eq!(square_poly.coordinate_position(&outside_coord), CoordPos::Outside);

Some work extracted from the geomgraph effort.

michaelkirk · 2020-11-12T21:37:21Z

geo-types/src/coordinate.rs

-impl<T: CoordinateType> Zero for Coordinate<T> {
-    fn zero() -> Self {
+impl<T: CoordinateType> Coordinate<T> {
+    pub fn zero() -> Self {


...tangential quality of life improvement.

michaelkirk · 2020-11-12T21:38:58Z

geo/src/algorithm/coordinate_position.rs

+
+/// Calculate the position of a `Coordinate` relative to a
+/// closed `LineString`.
+pub fn coord_pos_relative_to_ring<T>(coord: Coordinate<T>, linestring: &LineString<T>) -> CoordPos


This method was moved from utils unmodified.

In an effort to keep utils from becoming a big junk drawer, this seemed like a more specific home for it.

michaelkirk · 2020-11-12T21:41:38Z

geo/src/algorithm/coordinate_position.rs

+
+/// The position of a `Coordinate` relative to a `Geometry`
+#[derive(PartialEq, Clone, Debug)]
+pub enum CoordPos {


moved this from utils where it was previously only used as a return from "coord_pos_relative_to_ring".

@rmanoka (et al) - do you see any issue with re-using this enum?

At first I introduced a new "Interior/Exterior/Boundary" enum, but it seemed redundant.

Sounds fine to me

rmanoka · 2020-11-16T12:07:31Z

geo/src/algorithm/coordinate_position.rs

+/// let outside_coord = Coordinate { x: 5.0, y: 5.0 };
+/// assert_eq!(square_poly.coordinate_position(&outside_coord), CoordPos::Outside);
+/// ```
+pub trait CoordinatePosition<T>


@michaelkirk Do you prefer the CoordinatePosition<T> in favor of CoordinatePosition with a associate type Scalar: CoordinateType ? My personal pref. is the latter; optional comment.

I believe I've done this here: a60dc27 - can you take a look @rmanoka?

Despite reading a couple articles on this, I only kind of theoretically understand why this distinction is good, and still don't have a very intuitive grasp for when to apply it.

Is your rule of thumb to prefer associated types and only use full-blown generic type params when associated types are insufficient?

I'll plan to merge this in a couple days if I don't hear otherwise.

@michaelkirk Sorry for the late response; the changes look great! My pref. is mostly similar to Iterator vs AddAsign traits in std. I go for an associated type unless the same type could implement the trait with two possible param. Here, we're implementing the trait CoordinatePosition with only T = Ty for Line<Ty>, so prefer it to be associated than make the trait CoordinatePosition<T>.

May be in the future, our scalar types could have additional sophistication that tells us when T1 can be converted to T2 without loss in precision, and we can make some of our traits like CoordinatePosition, ForEach into generics.

frewsxcv

looks great, thanks!

geo/src/algorithm/coordinate_position.rs

michaelkirk · 2020-11-23T16:13:34Z

bors r=frewsxcv

bors · 2020-11-23T16:13:49Z

Merge conflict.

More often than not, I'm using the `zero` method as a convenient way to get "some" coord, rather than needing a strictly as a mathematical 'zero' value. Having to import num_traits::zero everywhere defeats that purpose.

coord_pos_relative_to_ring was moved unmodified into the new coorindate_position module

michaelkirk · 2020-11-23T16:20:41Z

bors retrt

michaelkirk · 2020-11-23T16:20:47Z

bors retry

bors · 2020-11-23T16:41:10Z

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>

michaelkirk commented Nov 12, 2020

View reviewed changes

rmanoka reviewed Nov 16, 2020

View reviewed changes

frewsxcv approved these changes Nov 16, 2020

View reviewed changes

geo/src/algorithm/coordinate_position.rs Outdated Show resolved Hide resolved

geo/src/algorithm/coordinate_position.rs Outdated Show resolved Hide resolved

geo/src/algorithm/coordinate_position.rs Outdated Show resolved Hide resolved

michaelkirk added 2 commits November 23, 2020 08:15

define 'zero' directly on coordinate

f24c363

More often than not, I'm using the `zero` method as a convenient way to get "some" coord, rather than needing a strictly as a mathematical 'zero' value. Having to import num_traits::zero everywhere defeats that purpose.

coordinate position trait

89f62f0

coord_pos_relative_to_ring was moved unmodified into the new coorindate_position module

michaelkirk force-pushed the mkirk/coordinate-position branch from a60dc27 to 89f62f0 Compare November 23, 2020 16:16

bors bot merged commit d759812 into master Nov 23, 2020

michaelkirk deleted the mkirk/coordinate-position branch December 2, 2020 19:41

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

Determine the position of a Coordinate relative to a geometry. #538

Determine the position of a Coordinate relative to a geometry. #538

michaelkirk commented Nov 12, 2020

michaelkirk Nov 12, 2020

michaelkirk Nov 12, 2020

michaelkirk Nov 12, 2020 •

edited

Loading

rmanoka Nov 16, 2020

rmanoka Nov 16, 2020

michaelkirk Nov 17, 2020

michaelkirk Nov 19, 2020

rmanoka Nov 23, 2020

frewsxcv left a comment

michaelkirk commented Nov 23, 2020

bors bot commented Nov 23, 2020

michaelkirk commented Nov 23, 2020

michaelkirk commented Nov 23, 2020

bors bot commented Nov 23, 2020

Determine the position of a Coordinate relative to a geometry. #538

Determine the position of a Coordinate relative to a geometry. #538

Conversation

michaelkirk commented Nov 12, 2020

Examples

michaelkirk Nov 12, 2020

Choose a reason for hiding this comment

michaelkirk Nov 12, 2020

Choose a reason for hiding this comment

michaelkirk Nov 12, 2020 • edited Loading

Choose a reason for hiding this comment

rmanoka Nov 16, 2020

Choose a reason for hiding this comment

rmanoka Nov 16, 2020

Choose a reason for hiding this comment

michaelkirk Nov 17, 2020

Choose a reason for hiding this comment

michaelkirk Nov 19, 2020

Choose a reason for hiding this comment

rmanoka Nov 23, 2020

Choose a reason for hiding this comment

frewsxcv left a comment

Choose a reason for hiding this comment

michaelkirk commented Nov 23, 2020

bors bot commented Nov 23, 2020

michaelkirk commented Nov 23, 2020

michaelkirk commented Nov 23, 2020

bors bot commented Nov 23, 2020

michaelkirk Nov 12, 2020 •

edited

Loading