Add support for dateline wrapping for circle to geometry conversion #194

StijnCaerts · 2020-10-05T11:16:37Z

Added support for dateline wrapping when converting a circle to a geometry. I implemented it like this;

support geometries that start at negative pages in JtsGeometry::cutUnwrappedGeomInto360()
put the geometry of the circle in a JtsGeometry if the circle crosses the dateline

Signed-off-by: Stijn Caerts <stijncaerts@gmail.com>

dsmiley

Nice contribution!

dsmiley · 2020-10-06T02:12:34Z

src/main/java/org/locationtech/spatial4j/shape/jts/JtsGeometry.java

      double minX = -180 + page * 360;
      if (geomEnv.getMaxX() <= minX)
        break;
      Geometry rect = geom.getFactory().toGeometry(new Envelope(minX, minX + 360, -90, 90));
      assert rect.isValid() : "rect";
-      Geometry pageGeom = rect.intersection(geom);//JTS is doing some hard work
+      Geometry pageGeom = rect.intersection(geom).copy();//JTS is doing some hard work


Shifting the intersection also alters the original geometry. Using the example from JtsSpatialContextTest, here is an overview of the value of geom in the cutUnwrappedGeomInto360 loop:

Page 0

geom: POLYGON ((181 -90, 179 -90, 179 90, 181 90, 181 -90))

pageGeom: POLYGON ((179 90, 180 90, 180 -90, 179 -90, 179 90))

Intersection isn't shifted because it is already in the -180 to 180 area.

Page 1

geom: POLYGON ((181 -90, 179 -90, 179 90, 181 90, 181 -90))

pageGeom: POLYGON ((180 -90, 180 90, 181 90, 181 -90, 180 -90))

Now the intersection is shifted -360 degrees

Page 2

geom: POLYGON ((181 -90, 179 -90, 179 90, 181 90, -179 -90))

No intersection is calculated because the geometry doesn't span across this page. But notice that the original geometry has changed by shifting the intersection in the previous iteration.

But when we start on a negative page, we already shift in the first iteration and then the geometry is messed up for the following iterations. This hasn't been noticed in the tests because all tested geometries only have 2 pages (0 and 1). If it is possible to have more than 2 pages, you would see the same problem there.

Shifting the intersection also alters the original geometry.

Woah; I thought the intersection produced an entirely new geometry!

I'm glad you are looking into this. If it's not asking too much, perhaps a new test might perturb these problems.

dsmiley · 2020-10-06T04:02:08Z

src/main/java/org/locationtech/spatial4j/shape/jts/JtsGeometry.java

@@ -573,17 +573,16 @@ private static Geometry cutUnwrappedGeomInto360(Geometry geom) {
      return geom;
    assert geom.isValid() : "geom";

-    //TODO opt: support geom's that start at negative pages --
-    // ... will avoid need to previously shift in unwrapDateline(geom).


Do you think you can address this second line of the comment you deleted? if you look in unwrapDateline(LineString), there will be a final shifting going on that I think the improvement you added here obsoletes. Granted I wrote that 8 years ago so I'm a little unclear now looking back at it!

I will take a look at it!

dsmiley · 2020-10-14T12:12:07Z

HI Stijn. I'm looking to do a Spatial4j release soon and I'm not sure what to do related to this issue right now. I could merge as-is -- it's an improvement. Or maybe you feel it's insufficient. If Spatial4j is released without this... it would honestly be a long time before another release occurred based on the track record here.

StijnCaerts · 2020-10-14T13:03:23Z

Hi David, I think it is better then to include the changes as-is in the release. I was still looking into removing the shift in unwrapDateline(LineString), but it wasn't as straightforward as I hoped. Removing the final shift causes the Fiji test case to fail as the geometry is not deemed valid in cutUnwrappedGeomInto360(Geometry) (assertion fails).
I haven't been able yet to figure out what the problem is exactly, but I can take a look at it again today or tomorrow. So I propose to merge as-is if we can't solve this soon.

codecov-io · 2020-10-14T18:28:18Z

Codecov Report

Merging #194 into master will increase coverage by 0.12%.
The diff coverage is 100.00%.

@@             Coverage Diff              @@
##             master     #194      +/-   ##
============================================
+ Coverage     75.85%   75.98%   +0.12%     
- Complexity     1108     1112       +4     
============================================
  Files            57       57              
  Lines          3822     3826       +4     
  Branches        774      775       +1     
============================================
+ Hits           2899     2907       +8     
+ Misses          644      642       -2     
+ Partials        279      277       -2

Impacted Files	Coverage Δ	Complexity Δ
.../locationtech/spatial4j/shape/jts/JtsGeometry.java	`78.09% <100.00%> (+0.59%)`	`82.00 <0.00> (+2.00)`
...ationtech/spatial4j/shape/jts/JtsShapeFactory.java	`92.61% <100.00%> (+1.02%)`	`58.00 <0.00> (+1.00)`
...iontech/spatial4j/shape/impl/ShapeFactoryImpl.java	`82.41% <0.00%> (+1.09%)`	`40.00% <0.00%> (+1.00%)`

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 23b14c9...454c925. Read the comment docs.

StijnCaerts · 2020-10-14T19:27:17Z

I think I might have a clue why the Fiji test fails when the final shift is removed in unwrapDateline(LineString). The WKT contains overlapping polygons: the polygon over the island of Taveuni to the left of the antimeridian contains values that are not in the [-180; 180] range (eg. 180.00000033527613). This causes the two polygons over the island to overlap. However, the JtsSpatialContextFactory used in this test is not configured to allow multiple overlapping polygons. I guess this problem went unnoticed by shifting around with the geometry...

So are these values incorrect in the included WKT or are they there intentionally?

dsmiley · 2020-10-26T02:48:10Z

Stijn, can you please submit an Eclipse Contributor License Agreement: https://projects.eclipse.org/user/sign/cla
It's a one-time thing.

Signed-off-by: Stijn Caerts <stijncaerts@gmail.com>

StijnCaerts · 2020-10-27T08:28:21Z

I submitted the Eclipse Contributor License Agreement and added a sign-off to one of the commits.

add support for dateline wrapping for circle to geometry conversion

3d687be

Signed-off-by: Stijn Caerts <stijncaerts@gmail.com>

dsmiley reviewed Oct 6, 2020

View reviewed changes

StijnCaerts and others added 3 commits October 27, 2020 09:22

Added test case: polygon crossing the dateline twice

2aaa1f7

Signed-off-by: Stijn Caerts <stijncaerts@gmail.com>

Only copy pageGeom when needed

d7dc78b

CHANGES.md

ca3b490

StijnCaerts force-pushed the circleDatelineWrap branch from 454c925 to ca3b490 Compare October 27, 2020 08:24

dsmiley merged commit ee39723 into locationtech:master Oct 28, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add support for dateline wrapping for circle to geometry conversion #194

Add support for dateline wrapping for circle to geometry conversion #194

StijnCaerts commented Oct 5, 2020

dsmiley left a comment

dsmiley Oct 6, 2020

StijnCaerts Oct 6, 2020

dsmiley Oct 7, 2020

dsmiley Oct 6, 2020

StijnCaerts Oct 6, 2020

dsmiley commented Oct 14, 2020

StijnCaerts commented Oct 14, 2020

codecov-io commented Oct 14, 2020 •

edited

StijnCaerts commented Oct 14, 2020

dsmiley commented Oct 26, 2020

StijnCaerts commented Oct 27, 2020

Add support for dateline wrapping for circle to geometry conversion #194

Add support for dateline wrapping for circle to geometry conversion #194

Conversation

StijnCaerts commented Oct 5, 2020

dsmiley left a comment

Choose a reason for hiding this comment

dsmiley Oct 6, 2020

Choose a reason for hiding this comment

StijnCaerts Oct 6, 2020

Choose a reason for hiding this comment

dsmiley Oct 7, 2020

Choose a reason for hiding this comment

dsmiley Oct 6, 2020

Choose a reason for hiding this comment

StijnCaerts Oct 6, 2020

Choose a reason for hiding this comment

dsmiley commented Oct 14, 2020

StijnCaerts commented Oct 14, 2020

codecov-io commented Oct 14, 2020 • edited

Codecov Report

StijnCaerts commented Oct 14, 2020

dsmiley commented Oct 26, 2020

StijnCaerts commented Oct 27, 2020

codecov-io commented Oct 14, 2020 •

edited