Opened 10 years ago

Closed 9 years ago

Last modified 9 years ago

#392 closed defect (fixed)

TopologyException unioning valid linestrings [JTS fails too]

Reported by: jsewell Owned by: strk
Priority: major Milestone:
Component: Core Version: master
Severity: Unassigned Keywords: Union topologyexception
Cc:

Description

When performing a Union (with an empty linestring or as an aggregate) on linestring geometries with many similar lines PostGIS reports a GEOS error as follows:

"NOTICE: TopologyException?: found non-noded intersection between LINESTRING (xxx xxx) and LINESTRING (xxx xxx) at xxx xxx ERROR: GEOS union() threw an error!"

The attached WKB data can be used to create the error in the following ways (when the two geoms are imported into lw).

CREATE TABLE lwu AS

SELECT

st_union(st_collect(the_geom), ST_SetSRID('LINESTRINGEMPTY', 4283))

AS the_geom FROM lw;

CREATE TABLE lwu AS

SELECT

st_union(the_geom)

AS the_geom FROM lw;

Attachments (2)

bug392.xml.gz (154.2 KB) - added by strk 10 years ago.
first reduction
bug392simp2.txt.gz (12.5 KB) - added by strk 10 years ago.
second reduction. JTS 1.12 fails with this too.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 10 years ago by jsewell

Can't upload the geoms (too large)

Geoms.zip can be found at ftp://ftp.lisasoft.com/UPLOADS/geom.zip

anonymous/anonymous

comment:2 Changed 10 years ago by strk

Packet is not available anymore, could you reupload ?

comment:3 Changed 10 years ago by strk

Found, it was 'geoms' not 'geom':

ftp://ftp.lisasoft.com/UPLOADS/geoms.zip

comment:4 Changed 10 years ago by strk

Version: 3.2.0svn-trunk

Test with:

 POSTGIS="2.0.0SVN" GEOS="3.3.0-CAPI-1.7.0" PROJ="Rel. 4.7.1, 23 September 2009" LIBXML="2.7.6" USE_STATS

The first union (LINESTRING EMPTY, collection of the two input geoms) is a no-op, ie: return the non-empty input untouched.

=# select st_npoints(st_union(st_collect(g), st_setsrid('LINESTRING EMPTY', 4283))) from bug392;
 st_npoints 
------------
     201483

=# select sum(st_npoints(g)) from bug392 ;
  sum   
--------
 201483

The second query does indeed attempt to perform an actual union, failing with:

=# select st_summary(st_union(g)) from bug392;   
ERROR:  GEOSUnion: TopologyException: found non-noded intersection between LINESTRING (146.593 -37.2263, 146.593 -37.2263) and LINESTRING (146.593 -37.2263, 146.593 -37.2263) at 146.593 -37.2263

Unary union doesn't help either:

=# select st_summary(st_unaryunion(st_collect(g))) from bug392;
ERROR:  GEOSUnion: TopologyException: found non-noded intersection between LINESTRING (146.593 -37.2263, 146.593 -37.2263) and LINESTRING (146.593 -37.2263, 146.593 -37.2263) at 146.593 -37.2263

comment:5 Changed 10 years ago by strk

XML test (~3Mb compressed): http://strk.keybit.net/tmp/bug392.xml.gz

Fails with current JTS trunk too:

=====  Test Runner  -  JTS Topology Suite (Version 1.12.0 alpha)  =====
Reading test file /usr/src/geos/geos/tests/xmltester/tests/bug392.xml
Running tests...

Case bug392.xml - #1 (7): http://trac.osgeo.org/geos/ticket/392
TopologyException: found non-noded intersection between LINESTRING (146.593 -37.2263, 146.593 -37.2263) and LINESTRING (146.593 -37.2263, 146.593 -37.2263) at 146.593 -37.2263
Test Failed (A union B)


1 cases with 3 tests  --  2 passed, 1 failed, 0 threw exceptions

*******  ERRORS ENCOUNTERED IN RUN  ********

Elapsed time: 14.364 seconds

comment:6 Changed 10 years ago by strk

Summary: GEOS 3.2.2 Union bug (linestrings)TopologyException unioning valid linestrings [JTS fails too]

comment:7 Changed 10 years ago by strk

Status: newassigned
Summary: TopologyException unioning valid linestrings [JTS fails too]TopologyException unioning valid linestrings [JTS succeeds]

I was wrong, JTS is not failing (I confused description printing with actual exception). Will try to reduce the testcase.

Changed 10 years ago by strk

Attachment: bug392.xml.gz added

first reduction

comment:8 Changed 10 years ago by strk

I've attached a reduced version of the test. This time with the expected result taken from JTS. It's a multilinestring with 6 elements (but still about 6k points)

comment:9 Changed 10 years ago by strk

Summary: TopologyException unioning valid linestrings [JTS succeeds]TopologyException unioning valid linestrings [JTS fails too]

Further reducing the test got to a point where also JTS fails:

1 cases with 2 tests  --  1 passed, 0 failed, 1 threw exceptions

The success if in the IsValid? test, while the UnaryUnion? throws the exception. I'll attach the HEXWKB of the offending multilinestring.

Changed 10 years ago by strk

Attachment: bug392simp2.txt.gz added

second reduction. JTS 1.12 fails with this too.

comment:10 Changed 10 years ago by strk

May be of interest that doing the unaryunion of the collection of the unaryunions of each component linestring fixes it.

comment:11 Changed 10 years ago by strk

Running the test with a fixed PrecisionModel? (scale 1e-80) seems to be still good :!

comment:12 Changed 10 years ago by strk

A precisionModel with scale = 1e300 also fixes (bigger scale should mean smaller grid, if I got it right)

comment:13 Changed 10 years ago by strk

The reason why running unaryunion on each of the multiline component strings works is that the common-bits remover shifts more bits when dealing with a more localized space. At least this is true for the latest reduction.

comment:14 Changed 10 years ago by strk

As a confirmation of the previous statement, running a non-unary union from postgis makes the result come out due to a narrower extent taken in consideration on each turn. A possible solution might be providing special threatment for lines like it's done for polygons with CascadedPolygonUnion?. Such implementation would perform the union between nearby components first, hopefully snapping enough.

comment:15 Changed 10 years ago by strk

A draft implementation confirms that all cases are fixed by using the same "cascaded" approach reserved to polygons. This is of course with the unary union, where geos can have control about the order in which unions are performed.

comment:16 Changed 10 years ago by strk

Resolution: fixed
Status: assignedclosed

Fixed by r3296

We have a CascadedUnion? class now, used by UnaryUnionOp? for linestrings. Theoretically, CascadedPolygonUnion? could be removed as CascadedUnion? doesn't do anything different but accepts more types. I won't do this for now as I'd like to see the moves of JTS first.

PostGIS would now have more reasons to hook on unary union from the union aggregate in a general way (rather than restricting to polygon).

comment:17 Changed 10 years ago by strk

For the record, since the original submission clearly shows the use case being postgis, this postgis ticket would fix the second call described in the original submission: http://trac.osgeo.org/postgis/ticket/922

That is, st_union(geom) should automatically make use of the improved robustness code.

comment:18 Changed 9 years ago by strk

Resolution: fixed
Status: closedreopened

The fix broke noding of self-intersecting lines, see #482

comment:19 Changed 9 years ago by strk

Resolution: fixed
Status: reopenedclosed

r3513 fixes this w/out breaking noding of self-intersecting lines (#482). This is the case failing in JTS...

comment:20 Changed 9 years ago by strk

for the record, r3514 forward-ports this to trunk

comment:21 in reply to:  20 Changed 9 years ago by jsewell

Changed to unaryunion and I've broken it again with a similar case.

GEOSUnion: TopologyException?: found non-noded intersection between LINESTRING (0.501356 0.115067, 0.501403 0.115079) and LINESTRING (0.501361 0.115068, 0.501356 0.115067) at 0.501356 0.115067

I'll try and get a cut down version of the massive dataset it fails with today, when I've done that I'll reopen the case.

Thanks for all the help strk!

James.

Note: See TracTickets for help on using tickets.