TopologyException unioning valid linestrings [JTS fails too]

[jsewell]

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;

[jsewell]

Can't upload the geoms (too large)

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

anonymous/anonymous

[strk]

Packet is not available anymore, could you reupload ?

[strk]

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

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

[strk]

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

[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

[strk]

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

[strk]

first reduction

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

[strk]

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.

[strk]

second reduction. JTS 1.12 fails with this too.

[strk]

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

[strk]

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

[strk]

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

[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.

[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.

[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.

[strk]

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

[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.

[strk]

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

[strk]

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

[strk]

for the record, r3514 forward-ports this to trunk

[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.