Correctness issues with Contains #513

michaelkirk · 2020-09-21T16:30:49Z

There are some correctness issues with our Contains implementation - discussed in #511

We should fix them.

I can find time to fix these this week, unless @rmanoka was already planning to do the work (I'm happy either way, so long as it gets fixed).

rmanoka · 2020-09-21T17:30:30Z

@michaelkirk Please go ahead! I suggest that we turn this into a tracking issue for completing both the Intersects and Contains traits (as these two are interrelated and use each other in the impls.). Here are my thoughts on what we should have eventually. We currently have 12 geometry types. Ideally, we should have an Intersects and Contains implementation for all the combinations.

Some of these (especially in the case of Intersects trait) can be solved via a blanket implementation based on another implementation:

Point<T>: Intersects<G> from Coordinate<T>: Intersects<G>
MultiPoint<T>: Intersects<G> from Point<T>: Intersects<G>
MultiLineString from LineString
MultiPolygon from Polygon

We could check off (or add comments on what is done / left) as and when we ensure correctness of specific pairs of geometries. Please let me know if you wish to discuss any specific combination.

michaelkirk · 2020-09-21T18:26:02Z

Sounds good!

michaelkirk · 2020-09-23T21:45:50Z

Seems like JTS's approach (and thus probably GOES/PostGIS/GDAL's) is to actually generate an explicit dimensional matrix to compare to the DE-9IM definition for the general case, with some short-circuit optimizations where possible.

Sounds like a lot of work, but maybe the way to go. I'm going to do some more research.

Geometry#contains:
https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/geom/Geometry.java#L877

calculate intersection matrix:
https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/operation/relate/RelateComputer.java#L73

michaelkirk · 2020-09-23T23:19:30Z

After looking into more, I think we should explicitly calculate an explicit DE-9IM style intersection matrix.

As well as fixing contains, this would give us default implementations for all the other DE-9IM relations "for free".

you can see the JTS implementation:
https://github.com/locationtech/jts/tree/5c78e723cc4a9dcd8cbbc74615305690203293df/modules/core/src/main/java/org/locationtech/jts/operation/relate

It's ~1k lines of code/comments by itself:

[15:36:39] ~/src/georust/jts/modules/core/src/main/java/org/locationtech/jts/operation/relate (master)
$ wc -l *
     150 EdgeEndBuilder.java
     192 EdgeEndBundle.java
      69 EdgeEndBundleStar.java
     389 RelateComputer.java
      52 RelateNode.java
      33 RelateNodeFactory.java
     135 RelateNodeGraph.java
     115 RelateOp.java
      52 package.html
    1187 total

And of course it depends on lots of other things, maybe most notably JTS's own geomgraph module, which seems to coordinate the bulk of the topological calculations. We'd have to build a corollary for this - unless someone knows of an existing crate with this functionality - I couldn't find anything.

$ find . -name \*.java | xargs wc -l
     154 ./Node.java
     201 ./Label.java
     151 ./EdgeIntersectionList.java
      87 ./EdgeIntersection.java
      84 ./EdgeNodingValidator.java
     338 ./EdgeEndStar.java
     114 ./EdgeList.java
     185 ./TopologyLocation.java
     137 ./Depth.java
     231 ./EdgeRing.java
     387 ./DirectedEdgeStar.java
     120 ./NodeMap.java
      84 ./GraphComponent.java
      40 ./Position.java
     144 ./index/SimpleSweepLineIntersector.java
     117 ./index/MonotoneChainIndexer.java
     206 ./index/SegmentIntersector.java
      57 ./index/EdgeSetIntersector.java
      91 ./index/SweepLineEvent.java
      34 ./index/MonotoneChain.java
      82 ./index/SimpleEdgeSetIntersector.java
     142 ./index/MonotoneChainEdge.java
     151 ./index/SimpleMCSweepLineIntersector.java
      53 ./index/SweepLineSegment.java
     219 ./DirectedEdge.java
     238 ./PlanarGraph.java
     139 ./Quadrant.java
     475 ./GeometryGraph.java
      29 ./NodeFactory.java
     129 ./EdgeEnd.java
     270 ./Edge.java
    4889 total

Line count is admittedly a crude metric, I didn't strip out comments and we can probably make some simplifying assumptions, e.g. maybe we can skip having pluggable boundaryDeterminationRules, but I'm trying to impress that it's a large undertaking, and I wanted to get some input about the approach before investing a lot of time/code into it.

As well as getting a wider array of (theoretically correct) implementations for some of the relation booleans, JTS (et al) also use the geomgraph stuff as a dependency of building buffers and some other operations, so it might pay some future dividends.

What do you think @georust/core - is there interest in merging several-thousand lines to do explicit DE-9IM calculations?

urschrei · 2020-09-23T23:40:52Z

What do you think @georust/core - is there interest in merging several-thousand lines to do explicit DE-9IM calculations?

Yes very much so – I think having a full DE-9IM implementation is incredibly valuable for geo as a project. It's not an insurmountable amount of work, but as you say, it's not a 200-line PR, either.

Let's create a tracking issue and discuss ideas for what concretely needs to be done, and who is available/interested in helping?

rmanoka · 2020-09-24T14:37:11Z

I'm in favour of adding the functionality to compute the full matrix. Also agree with @urschrei in creating a tracking issue, and incrementally adding this functionality.

That said, we should still aim to keep the existing traits as efficient as we can (but also fully correct ofc), and not compute the whole matrix before answering the Intersects or Contains traits. May be provide traits for each entry of the matrix, and for calculating boundary of a geometry. Then the current traits can use those, but exit early if it is not needed to compute all the entries.

How about working on a couple of RFCs to brainstorm the design of the traits / planning the implementation?

On a related note, could we enable GitHub pages on a gh-pages branch for this repo? The long list of check boxes above could be nicely made into a table, but GitHub doesn't like css (for security reasons) in it's markdown. I also would also like to see / add some proofs of correctness of our implementations which we can maintain there as pandoc documents (it has excellent math support via LaTeX in it's markdown).

urschrei · 2020-09-24T15:39:07Z

How about working on a couple of RFCs to brainstorm the design of the traits / planning the implementation?

Great idea. I've also enabled "projects" for this repo – may be useful.

On a related note, could we enable GitHub pages on a gh-pages branch for this repo?

Yep.

I also would also like to see / add some proofs of correctness of our implementations which we can maintain there as pandoc documents (it has excellent math support via LaTeX in it's markdown).

💓

rmanoka · 2020-10-02T19:00:50Z

I've put together a basic table for the Intersects trait here. The aim would be to fill in the values there as and when we verify our existing impls and add new ones. Thoughts?

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 <[email protected]> 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 <[email protected]> Co-authored-by: bors[bot] <26634292+bors[bot]@users.noreply.github.com>

michaelkirk · 2022-06-28T18:03:28Z

This was fixed via the Relate trait as part of https://github.com/georust/geo/pull/639/files#diff-08d17193a69d2a7a1cd99190027773b1297a80d626840cc464d85939bbf4dae7L382

michaelkirk mentioned this issue Oct 1, 2020

DE-9IM Proposal #515

Closed

michaelkirk mentioned this issue Nov 10, 2020

Add implementation: impl<T> Contains<T, Geometry<T>> for Geometry<T> #535

Closed

michaelkirk mentioned this issue Mar 12, 2021

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

Merged

2 tasks

michaelkirk closed this as completed Jun 28, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Correctness issues with Contains #513

Correctness issues with Contains #513

michaelkirk commented Sep 21, 2020 •

edited

Loading

rmanoka commented Sep 21, 2020

michaelkirk commented Sep 21, 2020

michaelkirk commented Sep 23, 2020 •

edited

Loading

michaelkirk commented Sep 23, 2020 •

edited

Loading

urschrei commented Sep 23, 2020

rmanoka commented Sep 24, 2020

urschrei commented Sep 24, 2020

rmanoka commented Oct 2, 2020

michaelkirk commented Jun 28, 2022

Correctness issues with Contains #513

Correctness issues with Contains #513

Comments

michaelkirk commented Sep 21, 2020 • edited Loading

rmanoka commented Sep 21, 2020

michaelkirk commented Sep 21, 2020

michaelkirk commented Sep 23, 2020 • edited Loading

michaelkirk commented Sep 23, 2020 • edited Loading

urschrei commented Sep 23, 2020

rmanoka commented Sep 24, 2020

urschrei commented Sep 24, 2020

rmanoka commented Oct 2, 2020

michaelkirk commented Jun 28, 2022

michaelkirk commented Sep 21, 2020 •

edited

Loading

michaelkirk commented Sep 23, 2020 •

edited

Loading

michaelkirk commented Sep 23, 2020 •

edited

Loading