Opened 8 months ago

Closed 7 months ago

#1051 closed defect (fixed)

overlayng::EdgeMerger::merge(): Assertion `baseEdge->size() == edge->size()' failed.

Reported by: strk Owned by: geos-devel@…
Priority: blocker Milestone: 3.9.0
Component: Default Version: master
Severity: Unassigned Keywords:
Cc:

Description

OverlayNG difference crashes with a failed assertion when fed valid data in input. The input data can be found in https://github.com/qgis/QGIS/issues/39029

Old generation results in TopologyException?. New generation crashes:

postgres: ../../../../../src/operation/overlayng/EdgeMerger.cpp:57: std::vector<geos::operation::overlayng::Edge*> geos::operation::overlayng::EdgeMerger::merge(): Assertion `baseEdge->size() == edge->size()' failed.

Attachments (3)

TestOverlayNG-geos-1051.xml (127.3 KB) - added by strk 8 months ago.
XML testcase
TestOverlay-geos-1051-simp.xml (17.7 KB) - added by strk 7 months ago.
First simplification of testcase (1/10 simplification)
TestOverlay-geos-1051-simp2.xml (648 bytes) - added by strk 7 months ago.
Further simplified testcase (only 6 vertices each polygon)

Download all attachments as: .zip

Change History (39)

Changed 8 months ago by strk

Attachment: TestOverlayNG-geos-1051.xml added

XML testcase

comment:1 Changed 8 months ago by strk

I've attached an XML testcase to reproduce the problem. Simple OverlayNG still throws an exception, but OverlayRobust? catches the exception to attempt another run (after snapping, I guess) and triggers the crash.

Martin: how do I trigger OverlayNGRobust in JTS from the XML ? I found GEOS only uses OverlayNGRobust with the "overlayareatest" XML operation, but JTS doesn't look like doing that

comment:2 Changed 8 months ago by strk

The crash happens when OverlayNGRobust tries overlaySnapping(tol 1.79499e-06)

comment:3 Changed 8 months ago by strk

I tried <op name="differencesr" arg1="A" arg2="B" arg3="1.79499e-06"> but it returns a POLYGON EMPTY, which doesn't make much sense to me (both in JTS and GEOS)

comment:4 in reply to:  3 Changed 8 months ago by mdavis

Replying to strk:

I tried <op name="differencesr" arg1="A" arg2="B" arg3="1.79499e-06"> but it returns a POLYGON EMPTY, which doesn't make much sense to me (both in JTS and GEOS)

Yes, because that is using SnapRounding?, which is not what needs to be tested.

But the result seems fine to me. The A polygon contains the B polygon (more or less, apart from some jitter that snap-rounding eliminates).

Last edited 8 months ago by mdavis (previous) (diff)

comment:5 in reply to:  1 Changed 8 months ago by mdavis

Replying to strk:

I've attached an XML testcase to reproduce the problem. Simple OverlayNG still throws an exception, but OverlayRobust? catches the exception to attempt another run (after snapping, I guess) and triggers the crash.

Martin: how do I trigger OverlayNGRobust in JTS from the XML ? I found GEOS only uses OverlayNGRobust with the "overlayareatest" XML operation, but JTS doesn't look like doing that

Use the TestRunner? option -geomfunc org.locationtech.jtstest.function.OverlayNGRobustFunctions org.locationtech.jts.operation.overlayng.OverlayNGRobust.

Note that the overlayAreaTest operation is boolean-valued, so the XML test file will be have to changed to have true as the expected output.

You can also run the test in the TestBuilder? (load the XML test file, then on the Functions > Scalar tab run OverlayNGRobust.overlayAreaTest.

The test works for me in JTS.

Last edited 8 months ago by mdavis (previous) (diff)

comment:6 Changed 8 months ago by mdavis

This is a good test - we can add it to the robust/overlay test corpus.

comment:7 Changed 8 months ago by mdavis

A quick hack/fix would be to change the EdgeMerger? assertion into a TopologyException?. Then the OverlayNGRobust logic I think would drop through to use Snap-Rounding, which should work.

It would be nice to fix the noding code, however - if that's possible.

comment:8 Changed 8 months ago by strk

Martin I'm unable to use the -geomfunc option, can you give full commandline ? I'm getting:

java.lang.ClassNotFoundException: org.locationtech.jtstest.function.OverlayNGRobustFunctions org.locationtech.jts.operation.overlayng.OverlayNGRobust

comment:9 Changed 8 months ago by strk

The TopologyException? trick works, without getting to Snap-Rounding but simply using a bigger snap tolerance:

loating point overlay FAILURE: TopologyException: found non-noded intersection between LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) and LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) at 655065.0840699079 1794820.6249905184
Trying overlaySnapping(tol 1.79499e-06).
overlaySnapping(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
overlaySnapBoth(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
Trying overlaySnapping(tol 1.79499e-05).
Floating point overlay FAILURE: TopologyException: found non-noded intersection between LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) and LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) at 655065.0840699079 1794820.6249905184
Trying overlaySnapping(tol 1.79499e-06).
overlaySnapping(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
overlaySnapBoth(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
Trying overlaySnapping(tol 1.79499e-05).
Floating point overlay FAILURE: TopologyException: found non-noded intersection between LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) and LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) at 655065.0840699079 1794820.6249905184
Trying overlaySnapping(tol 1.79499e-06).
overlaySnapping(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
overlaySnapBoth(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
Trying overlaySnapping(tol 1.79499e-05).
Floating point overlay FAILURE: TopologyException: found non-noded intersection between LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) and LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) at 655065.0840699079 1794820.6249905184
Trying overlaySnapping(tol 1.79499e-06).
overlaySnapping(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
overlaySnapBoth(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
Trying overlaySnapping(tol 1.79499e-05).
Floating point overlay FAILURE: TopologyException: found non-noded intersection between LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) and LINESTRING (655065 1.79482e+06, 655065 1.79482e+06) at 655065.0840699079 1794820.6249905184
Trying overlaySnapping(tol 1.79499e-06).
overlaySnapping(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
overlaySnapBoth(tol 1.79499e-06) FAILURE: TopologyException: Merge of edges of different sizes - probable noding error.
Trying overlaySnapping(tol 1.79499e-05).
../../tests/xmltester/tests/robust/overlay/TestOverlayNG-geos-1051.xml: case1: test1: overlayareatest(A, B): ok. (0 ms)

comment:10 Changed 8 months ago by Sandro Santilli <strk@…>

Resolution: fixed
Status: newclosed

In abb9662/git:

Throw TopologyException? on noding error after snapping

Fixes #1051

NOTE: JTS passes the test without change, so we should really fix

the noding code...

comment:11 Changed 8 months ago by mdavis

After building JTS with mvn clean install, the command for running the test is:

bin/testrunner.sh
-geomfunc org.locationtech.jtstest.function.OverlayNGRobustFunctions   org.locationtech.jts.operation.overlayng.OverlayNGRobust
-files <file-dir>/TestOverlayNG-geos-1051.xml

Note that the Functions classes are in the app module, so if running in an environment such as Eclipse, the run needs to include that module.

comment:12 Changed 8 months ago by strk

Here's what happens to me:

$ bin/testrunner.sh -geomfunc \
> org.locationtech.jtstest.function.OverlayNGRobustFunctions \
> org.locationtech.jts.operation.overlayng.OverlayNGRobust \
> -files TestOverlayNG-geos-1051.xml
=====  Test Runner  -  JTS Topology Suite (Version 1.18.0 SNAPSHOT) =====
Adding Geometry Functions from: org.locationtech.jtstest.function.OverlayNGRobustFunctions
java.lang.ClassNotFoundException: org.locationtech.jtstest.function.OverlayNGRobustFunctions
        at java.base/jdk.internal.loader.BuiltinClassLoader.loadClass(BuiltinClassLoader.java:581)
        at java.base/jdk.internal.loader.ClassLoaders$AppClassLoader.loadClass(ClassLoaders.java:178)
        at java.base/java.lang.ClassLoader.loadClass(ClassLoader.java:522)
        at org.locationtech.jtstest.geomop.GeometryFunctionRegistry.add(GeometryFunctionRegistry.java:77)
        at org.locationtech.jtstest.testrunner.JTSTestRunnerCmd.readOptions(JTSTestRunnerCmd.java:227)
        at org.locationtech.jtstest.testrunner.JTSTestRunnerCmd.main(JTSTestRunnerCmd.java:205)

comment:13 Changed 8 months ago by strk

Sorry, after mvn clean install things work fine!

comment:14 Changed 8 months ago by mdavis

Hmm, I'm actually suprised to hear that, since I realized that testrunner.sh runs a jar file that doesn't include the app module classes.

Here's a command line that works for me. In the JTS root dir (chsnge XML file pathname as needed):

java -cp modules/app/target/JTSTestBuilder.jar \
org.locationtech.jtstest.testrunner.JTSTestRunnerCmd \
-geomfunc org.locationtech.jtstest.function.OverlayNGRobustFunctions  \
org.locationtech.jts.operation.overlayng.OverlayNGRobust \
-files TestOverlayNG-geos-1051.xml
Last edited 8 months ago by mdavis (previous) (diff)

comment:15 Changed 8 months ago by mdavis

One way to try and bisect the cause of this problem is to choose some info to dump out during noding, and compare to JTS. Could start with the points that are snapped. Also the final set of edge before merging would be interesting to compare (since that is apparently the source of the error).

comment:16 Changed 7 months ago by strk

Martin: I'm trying at first to reduce the test for easier comparison. Should I be able to detect the difference by using the SnappingNoderTest? class ? How would I run a single test in that class, with JTS test runner ?

In GEOS, the inputs in this class result in:

     message: `TopologyException: found non-noded intersection between LINESTRING (655016 1.79494e+06, 655016 1.79494e+06) and LINESTRING (655016 1.79494e+06, 655016 1.79494e+06) at 655016.27295748401 1794940.0344945551`

Both with 1.79499E-6 and 1 tolerance

comment:17 Changed 7 months ago by strk

It does not help that for Java these inputs trigger "constant string too long"

comment:18 Changed 7 months ago by strk

For the record: SnappingNoderTest? can be run in JTS as such:

java -cp \
./modules/core/target/jts-core-1.18.0-SNAPSHOT.jar:./modules/core/target/jts-core-1.18.0-SNAPSHOT-tests.jar:/home/strk/.m2/repository/junit/junit/4.12/junit-4.12.jar \
org.locationtech.jts.noding.snap.SnappingNoderTest

Will still need a way to avoid the long literal

comment:19 Changed 7 months ago by strk

Reading the WKT from a file allows me to run the test, but the result of the test is a MULTILINESTRING EMPTY, dunno why:

      FileInputStream fstream = new FileInputStream("/tmp/x");
      BufferedReader br = new BufferedReader(new InputStreamReader(fstream));
      String wkt1 = br.readLine();
      String wkt2 = br.readLine(); 
      String expected = "POINT EMPTY"; /* known to NOT be what we really want */
      double tol = 1.79499E-6;
      System.err.println("Using WKT1: " + wkt1);
      System.err.println("Using WKT2: " + wkt2);
      System.err.println("Using tolerance: " + tol);
      checkRounding(wkt1, wkt2, tol, expected);

Which results in:

FAIL - Expected = POINT EMPTY actual = MULTILINESTRING EMPTY
F
Time: 0.095
There was 1 failure:
1) testOverlappingLinesWithNearVertex(org.locationtech.jts.noding.snap.SnappingNoderTest)junit.framework.AssertionFailedError
        at test.jts.GeometryTestCase.checkEqual(GeometryTestCase.java:61)
        at org.locationtech.jts.noding.snap.SnappingNoderTest.checkRounding(SnappingNoderTest.java:53)
        at org.locationtech.jts.noding.snap.SnappingNoderTest.testOverlappingLinesWithNearVertex(SnappingNoderTest.java:31)
        at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
        at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at org.locationtech.jts.noding.snap.SnappingNoderTest.main(SnappingNoderTest.java:14)

FAILURES!!!
Tests run: 1,  Failures: 1,  Errors: 0

comment:20 Changed 7 months ago by strk

Martin: how about an XML operation doing just SnappingNoder? ?

comment:21 Changed 7 months ago by mdavis

This is what the jtsop utility is for. You can put WKT or WKB in files, and run any function that is provided in the TestBuilder? (which is many), or else run your own (by add a class file containing static methods).

So if you have the following files:

snapping-test-a.wkt:
LINESTRING (100 200, 200 100.1, 300 100)

snapping-test-b.wkt:
LINESTRING (100 200, 200 100.1, 300 100)

the SnappingNoder? can be run using:

<JTS_HOME>/bin/jtsop.sh -a snapping-test-a.wkt -b snapping-test-b.wkt -f wkt Noding.snappingNoder 1

(Note that the Noding.snappingNoder function actually allows a null second input, but at the moment the jtsop command doesn't recognize this).

Changed 7 months ago by strk

First simplification of testcase (1/10 simplification)

comment:22 Changed 7 months ago by strk

With TestOverlay?-geos-1051-simp.xml​ both GEOS and JTS SnappingNoder? end up with 636 noded segmentstrings. Hard to tell how they differ between one-other as the output is slightly different in terms of significant digits.

To get you an Idea I'll paste the first 10 noded segstrings for each.

GEOS:

Trying overlaySnapping(tol 1.79499e-06).
NODED:  LINESTRING(654948.38532997924 1794977.1058540251, 654995.48203391524 1794988.7717037243)
NODED:  LINESTRING(654995.48203391524 1794988.7717037243, 654997.17955858458 1794989.1921804454)
NODED:  LINESTRING(654997.17955858458 1794989.1921804454, 655000.36381421797 1794989.9809203045, 655006.34643579996 1794983.8258888787)
NODED:  LINESTRING(655006.34643579996 1794983.8258888787, 655051.77446297742 1794937.088696653, 655102.56059972045 1794927.5021000544)
NODED:  LINESTRING(655102.56059972045 1794927.5021000544, 655108.42102836783 1794926.3958618378, 655110.0720664172 1794923.1048861023)
NODED:  LINESTRING(655110.0720664172 1794923.1048861023, 655110.12012789119 1794923.0090862843)
NODED:  LINESTRING(655110.12012789119 1794923.0090862843, 655111.03361745446 1794921.1882487882, 655105.8944992529 1794809.0953964447, 655103.6628449125 1794805.4566734952)
NODED:  LINESTRING(655103.6628449125 1794805.4566734952, 655070.41920929297 1794806.064489258, 655062.62551842164 1794798.488781017, 655061.46045440866 1794798.8496030809, 655063.81619753118 1794810.6547597279)
NODED:  LINESTRING(655063.81619753118 1794810.6547597279, 655064.15367999999 1794812.3459600001, 655064.1887750614 1794812.591778927, 655042.95566738653 1794904.1646406003, 655029.10396397568 1794921.2111610321, 655029.01317000005 1794921.3055899998, 655028.61825000006 1794921.71276, 655028.22155999998 1794922.1181999999, 655027.82310000004 1794922.5219099999, 655027.69848218339 1794922.6470757592, 655027.63206300582 1794922.7137853792, 655027.62398069503 1794922.721903034)
NODED:  LINESTRING(655027.62398069503 1794922.721903034, 655027.62397786777 1794922.7219058727)

JTS:

try overlaySnapping with tolerance 1.7949899809203045E-6
NODED: LINESTRING (654948.3853299792 1794977.105854025, 654995.4820339152 1794988.7717037243)
NODED: LINESTRING (654995.4820339152 1794988.7717037243, 654997.1795585846 1794989.1921804454)
NODED: LINESTRING (654997.1795585846 1794989.1921804454, 655000.363814218 1794989.9809203045, 655006.3464358 1794983.8258888787)
NODED: LINESTRING (655006.3464358 1794983.8258888787, 655051.7744629774 1794937.088696653, 655102.5605997205 1794927.5021000544)
NODED: LINESTRING (655102.5605997205 1794927.5021000544, 655108.4210283678 1794926.3958618378, 655110.0720664172 1794923.1048861023)
NODED: LINESTRING (655110.0720664172 1794923.1048861023, 655110.1201278912 1794923.0090862843)
NODED: LINESTRING (655110.1201278912 1794923.0090862843, 655111.0336174545 1794921.1882487882, 655105.8944992529 1794809.0953964447, 655103.6628449125 1794805.4566734952)
NODED: LINESTRING (655103.6628449125 1794805.4566734952, 655070.419209293 1794806.064489258, 655062.6255184216 1794798.488781017, 655061.4604544087 1794798.849603081, 655063.8161975312 1794810.654759728)
NODED: LINESTRING (655063.8161975312 1794810.654759728, 655064.15368 1794812.34596, 655064.1887750614 1794812.591778927, 655042.9556673865 1794904.1646406003, 655029.1039639757 1794921.211161032, 655029.01317 1794921.3055899998, 655028.61825 1794921.71276, 655028.22156 1794922.1182, 655027.8231 1794922.52191, 655027.6984821834 1794922.6470757592, 655027.6320630058 1794922.7137853792, 655027.623980695 1794922.721903034)
NODED: LINESTRING (655027.623980695 1794922.721903034, 655027.6239778678 1794922.7219058727)

comment:23 Changed 7 months ago by strk

Snap tolerance is the same up to 17 significant digits: 1.7949899809203045E-6 (verified in GEOS)

Changed 7 months ago by strk

Further simplified testcase (only 6 vertices each polygon)

comment:24 Changed 7 months ago by strk

The second simplified testcase has only 6 vertices in each polygon, which should help comparing JTS and GEOS.

comment:25 Changed 7 months ago by strk

Now that I see only 20 noded segments strings I can spot that ONE segmentstring has 3 vertices instead of 2 in the GEOS case. I'll write them all here:

GEOS:

NODED: LINESTRING(654948.38532997924 1794977.1058540251, 655015.54770534404 1794940.3747519043)
NODED: LINESTRING(655015.54770534404 1794940.3747519043, 655016.29615051334 1794939.965427252)
NODED: LINESTRING(655016.29615051334 1794939.965427252, 655016.3812220972 1794939.9189016039, 655016.20226531825 1794940.1099718122)
NODED: LINESTRING(655016.20226531825 1794940.1099718122, 655016.20226000005 1794940.10998)
NODED: LINESTRING(655016.20226000005 1794940.10998, 655016.20225819293 1794940.1099794197)
NODED: LINESTRING(655016.20225819293 1794940.1099794197, 655016.20126093226 1794940.1110076148)
NODED: LINESTRING(655016.20126093226 1794940.1110076148, 655014.92640687118 1794941.4254068714, 655014.83171824354 1794941.5196832407)
NODED: LINESTRING(655014.83171824354 1794941.5196832407, 655014.82956023223 1794941.5218318563)
NODED: LINESTRING(655014.82956023223 1794941.5218318563, 655014.74088346737 1794941.6101225375)
NODED: LINESTRING(655014.74088346737 1794941.6101225375, 654948.38532997924 1794977.1058540251)
NODED: LINESTRING(655103.66284549481 1794805.4566744049, 655016.29615051334 1794939.965427252)
NODED: LINESTRING(655016.29615051334 1794939.965427252, 655016.20226531825 1794940.1099718122)
XXXXX: LINESTRING(655016.20226531825 1794940.1099718122, 655016.20226000005 1794940.10998, 655016.20225819293 1794940.1099794197)
NODED: LINESTRING(655016.20225819293 1794940.1099794197, 655016.20226000005 1794940.10998)
NODED: LINESTRING(655016.20226000005 1794940.10998,      655016.20126093226 1794940.1110076148)
NODED: LINESTRING(655016.20126093226 1794940.1110076148, 655014.83171824354 1794941.5196832407)
NODED: LINESTRING(655014.83171824354 1794941.5196832407, 655014.82956023223 1794941.5218318563)
NODED: LINESTRING(655014.82956023223 1794941.5218318563, 655014.74088346737 1794941.6101225375)
NODED: LINESTRING(655014.74088346737 1794941.6101225375, 655015.54770534404 1794940.3747519043)
NODED: LINESTRING(655015.54770534404 1794940.3747519043, 655103.66284549481 1794805.4566744049)

JTS:

NODED: LINESTRING(654948.3853299792  1794977.105854025,  655015.547705344   1794940.3747519043)
NODED: LINESTRING(655015.547705344   1794940.3747519043, 655016.2961505133  1794939.965427252)
NODED: LINESTRING(655016.2961505133  1794939.965427252, 655016.3812220972 1794939.918901604,  655016.2022653183  1794940.1099718122)
NODED: LINESTRING(655016.2022653183  1794940.1099718122, 655016.20226       1794940.10998)
NODED: LINESTRING(655016.20226       1794940.10998, 655016.2022581929  1794940.1099794197)
NODED: LINESTRING(655016.2022581929  1794940.1099794197, 655016.2012609323  1794940.1110076148)
NODED: LINESTRING(655016.2012609323  1794940.1110076148, 655014.9264068712  1794941.4254068714, 655014.8317182435 1794941.5196832407)
NODED: LINESTRING(655014.8317182435  1794941.5196832407, 655014.8295602322  1794941.5218318563)
NODED: LINESTRING(655014.8295602322  1794941.5218318563, 655014.7408834674  1794941.6101225375)
NODED: LINESTRING(655014.7408834674  1794941.6101225375, 654948.3853299792  1794977.105854025)
NODED: LINESTRING(655103.6628454948  1794805.456674405,  655016.2961505133  1794939.965427252)
NODED: LINESTRING(655016.2961505133  1794939.965427252, 655016.2022653183  1794940.1099718122)
NODED: LINESTRING(655016.2022653183  1794940.1099718122, 655016.20226       1794940.10998)
NODED: LINESTRING(655016.20226       1794940.10998,      655016.2022581929  1794940.1099794197)
NODED: LINESTRING(655016.2022581929  1794940.1099794197, 655016.2012609323  1794940.1110076148)
NODED: LINESTRING(655016.2012609323  1794940.1110076148, 655014.8317182435  1794941.5196832407)
NODED: LINESTRING(655014.8317182435  1794941.5196832407, 655014.8295602322  1794941.5218318563)
NODED: LINESTRING(655014.8295602322  1794941.5218318563, 655014.7408834674  1794941.6101225375)
NODED: LINESTRING(655014.7408834674  1794941.6101225375, 655015.547705344   1794940.3747519043)
NODED: LINESTRING(655015.547705344   1794940.3747519043, 655103.6628454948  1794805.456674405)

See the one marked with XXXXX in the GEOS output

comment:26 Changed 7 months ago by mdavis

The problem turns out to be that GEOS is not sorting the SegmentNodes in a SegmentNodeList quite correctly. This is shown by dumping the segment nodes for the B geometry:

GEOS:

0: Seg 0 - 655103.66284549481 1794805.4566744049 (Segment Start vertex)
1: Seg 0 - 655016.29615051334 1794939.965427252
2: Seg 0 - 655016.20226531825 1794940.1099718122
3: Seg 1 - 655016.20225819293 1794940.1099794197 <-- *** incorrectly sorted ***
4: Seg 1 - 655016.20226000005 1794940.10998 (Segment Start vertex)

JTS:

0: Seg 0 - 655103.66284549481 1794805.4566744049 (Segment Start vertex)
1: Seg 0 - 655016.29615051334 1794939.965427252
2: Seg 0 - 655016.20226531825 1794940.1099718122
3: Seg 1 - 655016.20226 1794940.10998 (Segment Start vertex)
4: Seg 1 - 655016.20225819293 1794940.1099794197

Note that the order of the last two nodes is different, AND that in GEOS in segment 1 the segment start point is incorrectly sorted after the next node in the segment.

The reason for this is because the SegmentNodeComparator algorithm is slightly non-commutative as it stands in GEOS. This is due to the assumption that the nodes being compared are very close to the segment they are assigned to, so that their relative octant is the same as or adjacent to the segment octant. This assumption doesn't hold in some situations when using a snapping tolerance. I.e. a node near a segment endpoint may actually lie far enough from the segment that it does not lie in the same or an adjacent octant).

JTS fixed this in March 2019 in PR 399, with this code (released in JTS 1.17). I verified that this fix solves this test case.

Last edited 7 months ago by mdavis (previous) (diff)

comment:27 Changed 7 months ago by mdavis

Well spotted, Sandro! This is a sneaky little bug for sure.

Now, the question is whether to change the EdgeMerger? error back to an assertion, rather than a TopologyException. My vote is to revert this change, since otherwise it may mask any further issues with the noding code.

comment:28 Changed 7 months ago by mdavis

Resolution: fixed
Status: closedreopened

comment:29 Changed 7 months ago by strk

Great hunter! Reverting to Assert sounds dangerous from a production point of view (nobody wants their database cluster brougth down by a bug). But we should have an AssertionFailedException? handy, to avoid TopologyException? catching

comment:30 in reply to:  29 Changed 7 months ago by mdavis

Replying to strk:

Great hunter! Reverting to Assert sounds dangerous from a production point of view (nobody wants their database cluster brougth down by a bug). But we should have an AssertionFailedException? handy, to avoid TopologyException? catching

Very good point. Is there an AssertionFailedException in GEOS?

comment:31 Changed 7 months ago by Sandro Santilli <strk@…>

In e215772/git:

Port JTS fix for very close nodes on same segment.

References #1051 fixing its root cause.

This commit partially reverts abb96620c275 to avoid hiding
eventual other missing ports from JTS.

comment:32 Changed 7 months ago by strk

Yes, and we now use that exception. I'm leaving this ticket open waiting for your new fix test to land in JTS and port here (or please close the ticket if you don't think you'll create such test)

comment:33 Changed 7 months ago by mdavis

Some new JTS tests testing SegmentNode? ordering using this data are in JTS PR 610.

comment:34 Changed 7 months ago by Sandro Santilli <strk@…>

comment:35 Changed 7 months ago by Sandro Santilli <strk@…>

In 3507276/git:

Another test for 1051, at another level

References #1051

comment:36 Changed 7 months ago by strk

Resolution: fixed
Status: reopenedclosed

All tests ported, thanks !

Note: See TracTickets for help on using tickets.