"Side location conflicts" in geometry parsing
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 35/100
Research direction
Reproduce the polygon failure from FootprintServiceTest.solrTest and trace JtsGeometry.java through cutUnwrappedGeomInto360 and the unwrapDateline methods. Check the noted TODO and the TopologyException stack trace; done means this South Pole/dateline polygon is converted without the side location conflict and remains valid.
Written by the indexing model from the issue text.
Description
Discovered while using solr-spatial, the following spatial polygon becomes invalid:
POLYGON ((-15.9894 -65.2345, -4.5951 -69.5654, 9.3512 -72.4781, 26.2688 -74.0308, 44.6448 -74.0661, 47.3341 -78.1059, 51.7677 -81.3178, 58.1878 -83.606, 66.9686 -85.1874, 106.2119 -87.2101, 161.1218 -86.5675, 180 -87.4608, 180 -90, -180 -90, -180 -87.4608, -120.1955 -87.5958, -99.3114 -86.8001, -85.1881 -85.4186, -76.624 -83.5204, -70.7275 -80.7504, -66.6851 -76.7469, -63.8756 -70.899, -37.2776 -69.837, -25.9748 -67.9771, -15.9894 -65.2345))
If you were to plot this on a globe, it would look like a satellite's swath that went over the South Pole, which may be causing some issues. It shape "crosses" the dateline at 180 -87.406, but we don't split it, instead we go 'down' 180 -90, then across the globe to -180 -90 and continue the shape so it's not a multipolygon but rather a single polygon.
The polygon that the spatial4j is working on becomes:
spatial4j: POLYGON ((-15.9894 -65.2345, -4.5951 -69.5654, 9.3512 -72.4781, 26.2688 -74.0308, 44.6448 -74.0661, 47.3341 -78.1059, 51.7677 -81.3178, 58.1878 -83.606, 66.9686 -85.1874, 106.2119 -87.2101, 161.1218 -86.5675, 180 -87.4608, 180 -90, 180 -90, 180 -87.4608, 239.80450000000002 -87.5958, 260.6886 -86.8001, 274.8119 -85.4186, 283.376 -83.5204, 289.2725 -80.7504, 293.31489999999997 -76.7469, 296.1244 -70.899, 322.7224 -69.837, 334.0252 -67.9771, 344.0106 -65.2345))
This happens during the 'unwrapDateline' methods. I think there is a suggestion in the code itself about this possibly being an issue:
//TODO TEST THIS! Maybe bug if doesn't cross but is in another page?
now if i manually 'fix' the polygon and add in a bunch of filler points between the -180 -90 and 180 -90 points, i can get it to work:
POLYGON((-15.9894 -65.2345, -4.5951 -69.5654, 9.3512 -72.4781, 26.2688 -74.0308, 44.6448 -74.0661, 47.3341 -78.1059, 51.7677 -81.3178, 58.1878 -83.606, 66.9686 -85.1874, 106.2119 -87.2101, 161.1218 -86.5675, 180 -87.4608, 180 -90, 120 -90, 60 -90, 0 -90, -60 -90, -120 -90, -180 -90, -180 -87.4608, -120.1955 -87.5958, -99.3114 -86.8001, -85.1881 -85.4186, -76.624 -83.5204, -70.7275 -80.7504, -66.6851 -76.7469, -63.8756 -70.899, -37.2776 -69.837, -25.9748 -67.9771, -15.9894 -65.2345))
but it's hard to modify the code generating this because we use a Ramer–Douglas–Peucker algorithm to remove unneeded points- which doesn't keep the points between the -180 -90 and 180 -90 coordinates.
Below is the full stacktrace i'm generating:
com.vividsolutions.jts.geom.TopologyException: side location conflict [ (-15.9894, -65.2345, NaN) ]
at com.vividsolutions.jts.geomgraph.EdgeEndStar.propagateSideLabels(EdgeEndStar.java:300)
at com.vividsolutions.jts.geomgraph.EdgeEndStar.computeLabelling(EdgeEndStar.java:139)
at com.vividsolutions.jts.geomgraph.DirectedEdgeStar.computeLabelling(DirectedEdgeStar.java:127)
at com.vividsolutions.jts.operation.overlay.OverlayOp.computeLabelling(OverlayOp.java:373)
at com.vividsolutions.jts.operation.overlay.OverlayOp.computeOverlay(OverlayOp.java:173)
at com.vividsolutions.jts.operation.overlay.OverlayOp.getResultGeometry(OverlayOp.java:127)
at com.vividsolutions.jts.operation.overlay.OverlayOp.overlayOp(OverlayOp.java:66)
at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.getResultGeometry(SnapIfNeededOverlayOp.java:96)
at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.overlayOp(SnapIfNeededOverlayOp.java:58)
at com.vividsolutions.jts.geom.Geometry.intersection(Geometry.java:1342)
at com.spatial4j.core.shape.jts.JtsGeometry.cutUnwrappedGeomInto360(JtsGeometry.java:468)
at com.spatial4j.core.shape.jts.JtsGeometry.(JtsGeometry.java:65)
at com.spatial4j.core.context.jts.JtsSpatialContext.makeShape(JtsSpatialContext.java:290)
at com.spatial4j.core.context.jts.JtsSpatialContext.makeShape(JtsSpatialContext.java:303)
at gov.nasa.podaac.l2ss.FootprintServiceTest.solrTest(FootprintServiceTest.java:113)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:606)
at junit.framework.TestCase.runTest(TestCase.java:164)
at junit.framework.TestCase.runBare(TestCase.java:130)
at junit.framework.TestResult$1.protect(TestResult.java:106)
at junit.framework.TestResult.runProtected(TestResult.java:124)
at junit.framework.TestResult.run(TestResult.java:109)
at junit.framework.TestCase.run(TestCase.java:120)
at org.eclipse.jdt.internal.junit.runner.junit3.JUnit3TestReference.run(JUnit3TestReference.java:131)
at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:467)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:683)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:390)
at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:197)
- Dominant language
- Java
- Stars
- 961
- Forks
- 173
- PR merge metrics
- No merged PRs in 30d
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from locationtech/spatial4j
-
question
Difficulty 5/5 Over a week Newbie friendliness 20/100
locationtech/spatial4j#233 · 1 comment ·
-
bug
Difficulty 3/5 1-2 days Newbie friendliness 35/100
locationtech/spatial4j#232 · 1 comment ·
-
Difficulty 4/5 3-5 days Newbie friendliness 25/100
locationtech/spatial4j#231 · 1 comment ·
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
locationtech/spatial4j#230 · 2 comments ·
-
bug
Difficulty 3/5 1-2 days Newbie friendliness 45/100
locationtech/spatial4j#227 · 2 comments ·
All issues in locationtech/spatial4j
Similar issues
-
test(setup): GitHub configuration tests fail when the temp path is long enough for YAML foldingOpenbug good first issue help wanted priority medium size S
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
martin-francois/symphony-trello#776 · 1 comment ·
Maintainers usually reply within 1 day
-
Console.printHexOpengood first issue kernel
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
JackFurton/who-would-build-a-kernel-in-java#33 · 2 comments ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
objectionary/eo#9182 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
objectionary/hone-maven-plugin#1293 ·
Maintainers usually reply within 1 day