Opened 10 years ago

Last modified 11 months ago

#522 new defect

Exception on overlay between valid linestrings [JTS fails too]

Reported by: strk Owned by: geos-devel@…
Priority: major Milestone: Upstream
Component: Default Version: 3.3.2
Severity: Unassigned Keywords: jtsfail
Cc:

Description

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

Here they are:

010300002040A5000001000000050000001D020000F41831C1E399231EE6F729411C020000F41831C1B992E9C61EFB29411C020000F41831C156E1297A1CFB29411A493FC38F1831C1D8C6FEFCFEF929411D020000F41831C1E399231EE6F72941

010300002040A5000001000000040000001D020000F41831C1056DF2EC6AFA29411C020000F41831C1D1D1C8A2C7FA2941D6FA5B26EC1831C1C8F5FEAEBBFA29411D020000F41831C1056DF2EC6AFA2941

Attachments (1)

bug522.xml (652 bytes) - added by strk 10 years ago.

Download all attachments as: .zip

Change History (8)

Changed 10 years ago by strk

Attachment: bug522.xml added

comment:1 Changed 10 years ago by strk

Keywords: jtsfail added
Summary: Exception on overlay between valid linestringsException on overlay between valid linestrings [JTS fails too]

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) ]

comment:2 Changed 10 years ago by 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.

comment:3 Changed 10 years ago by strk

Milestone: 3.3.33.3.4

comment:4 Changed 9 years ago by strk

Milestone: 3.3.4GEOS Future

comment:5 Changed 8 years ago by 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 :(

comment:6 Changed 3 years ago by robe

Milestone: GEOS FutureGEOS Fund Me

Milestone renamed

comment:7 Changed 11 months ago by pramsey

Milestone: GEOS Fund MeUpstream
Note: See TracTickets for help on using tickets.