Exception on overlay between valid linestrings [JTS fails too]

[strk]

Two valid lines trigger a topology exception on union or difference (and probably on any other overlay operation).

Here they are:

010300002040A5000001000000050000001D020000F41831C1E399231EE6F729411C020000F41831C1B992E9C61EFB29411C020000F41831C156E1297A1CFB29411A493FC38F1831C1D8C6FEFCFEF929411D020000F41831C1E399231EE6F72941

010300002040A5000001000000040000001D020000F41831C1056DF2EC6AFA29411C020000F41831C1D1D1C8A2C7FA2941D6FA5B26EC1831C1C8F5FEAEBBFA29411D020000F41831C1056DF2EC6AFA2941

[strk]

JTS trunk revision 537 also fails:

Test Threw Exception (A difference B)     com.vividsolutions.jts.geom.TopologyException: found non-noded intersection between LINESTRING ( -1120500.0000001257 851294.299192949, -1120500.0000001257 851343.3885007716 ) and LINESTRING ( -1120500.0000001257 851343.3885007716, -1120500.0000001257 851342.2386007707 ) [ (-1120500.0000001257, 851343.3885007716, NaN) ]

[strk]

Debugging output from GEOS is interesting:

Trying with original input.
Original exception: TopologyException: found non-noded intersection between LINESTRING (-1.1205e+06 851294, -1.1205e+06 851343) and LINESTRING (-1.1205e+06 851343, -1.1205e+06 851342) at -1120500.0000001257 851343.3885007716
Trying with Common Bits Remover (CBR)
CBR: result (before common-bits addition) is INVALID: Self-intersection at or near point -1120500.0000001257 851294.29919294897 (-1120500.0000001257285 851294.29919294896536)
CBR: TopologyException: Result of overlay became invalid after re-addin common bits of operand coordinates: Self-intersection at or near point -1120500.0000001257 851294.29919294897 at -1120500.0000001257 851294.29919294897
Trying with snapping 
Computed snap tolerance: 7.8501591251697397784e-09
Computed common bits: -1120512 849920
SNAP: snapped geom 0 is INVALID: Self-intersection at or near point 11.999999874271452 1422.23860077071 (11.999999874271452427 1422.2386007707100362)
SNAP: snapped geom 0: self-unioning
SNAP: snapped geom 0 self-unioned is INVALID: Self-intersection at or near point 11.999999874271452 1422.23860077071 (11.999999874271452427 1422.2386007707100362)
SNAP: TopologyException: found non-noded intersection between LINESTRING (12 1379.82, 12 1423.39) and LINESTRING (12 1423.39, 12 1422.24) at 11.999999874271452 1423.3885007716017
EXCEPTION on case 1 test 1: TopologyException: found non-noded intersection between LINESTRING (-1.1205e+06 851294, -1.1205e+06 851343) and LINESTRING (-1.1205e+06 851343, -1.1205e+06 851342) at -1120500.0000001257 851343.3885007716

It basically tells us that the "Common bits removal" heuristic did succeed in give a result, BUT such result is invalid due to self-intersection.

When it comes to the "Snap" heuristic snapping itself creates invalid results.

[strk]

Running this test after snapping improvements:

Trying with original input.
Original exception: TopologyException: found non-noded intersection between LINESTRING (-1.1205e+06 851294, -1.1205e+06 851343) and LINESTRING (-1.1205e+06 851343, -1.1205e+06 851342) at -1120500.0000001257 851343.3885007716
Trying with Common Bits Remover (CBR)
CBR: result (after common-bits addition) is INVALID: Self-intersection at or near point -1120500.0000001257 851294.29919294897 (-1120500.0000001257285 851294.29919294896536)
CBR: result (after common-bits addition) fix_self_intersection (UnaryUnion)
CBR: result (after common-bits addition and fix_self_intersections) is INVALID: Self-intersection at or near point -1120500.0000001257 851294.29919294897 (-1120500.0000001257285 851294.29919294896536)
CBR: TopologyException: Result of overlay became invalid after re-addin common bits of operand coordinates: Self-intersection at or near point -1120500.0000001257 851294.29919294897 at -1120500.0000001257 851294.29919294897
Trying with snapping 
Computed snap tolerance: 7.8501591251697397784e-09
Computed common bits: -1120512 849920
SNAP: snapped geom 0 fix_self_intersection (UnaryUnion)
SNAP: snapped geom 1 fix_self_intersection (UnaryUnion)
SNAP: TopologyException: found non-noded intersection between LINESTRING (12 1379.82, 12 1423.39) and LINESTRING (12 1423.39, 12 1422.24) at 11.999999874271452 1423.3885007716017
EXCEPTION on case 1 test 1: TopologyException: found non-noded intersection between LINESTRING (-1.1205e+06 851294, -1.1205e+06 851343) and LINESTRING (-1.1205e+06 851343, -1.1205e+06 851342) at -1120500.0000001257 851343.3885007716

Basically this time snapping does NOT introduce any invalidity, still the exception is thrown :(

[robe]

Milestone renamed

[dbaston]

This looks to have been addressed with OverlayNG; a test case was committed at 4d3e571ed1b88697a3135c51ca14c73f4493f377/git