#392 closed defect (fixed)
TopologyException unioning valid linestrings [JTS fails too]
Reported by: | jsewell | Owned by: | strk |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | Core | Version: | main |
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)
Change History (23)
comment:1 by , 13 years ago
comment:4 by , 13 years ago
Version: | 3.2.0 → svn-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 by , 13 years ago
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 by , 13 years ago
Summary: | GEOS 3.2.2 Union bug (linestrings) → TopologyException unioning valid linestrings [JTS fails too] |
---|
comment:7 by , 13 years ago
Status: | new → assigned |
---|---|
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.
comment:8 by , 13 years ago
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 by , 13 years ago
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.
by , 13 years ago
Attachment: | bug392simp2.txt.gz added |
---|
second reduction. JTS 1.12 fails with this too.
comment:10 by , 13 years ago
May be of interest that doing the unaryunion of the collection of the unaryunions of each component linestring fixes it.
comment:11 by , 13 years ago
Running the test with a fixed PrecisionModel (scale 1e-80) seems to be still good :!
comment:12 by , 13 years ago
A precisionModel with scale = 1e300 also fixes (bigger scale should mean smaller grid, if I got it right)
comment:13 by , 13 years ago
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 by , 13 years ago
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 by , 13 years ago
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 by , 13 years ago
Resolution: | → fixed |
---|---|
Status: | assigned → closed |
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 by , 13 years ago
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 by , 12 years ago
Resolution: | fixed |
---|---|
Status: | closed → reopened |
The fix broke noding of self-intersecting lines, see #482
comment:19 by , 12 years ago
Resolution: | → fixed |
---|---|
Status: | reopened → closed |
comment:21 by , 12 years ago
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.
Can't upload the geoms (too large)
Geoms.zip can be found at ftp://ftp.lisasoft.com/UPLOADS/geom.zip
anonymous/anonymous