[geos-devel] Non Noded intersection bugs when performing Geometry overlay

Mon Feb 27 11:39:41 EST 2012

Hi, James.

This is definitely a GEOS issue.

What you're seeing, of course, is the usual issue of robustness problems 
- likely due to "nearly coincident" linework during the second union.  
This is where I'd expect to see problems, since if your input data is a 
properly noded coverage, then the first union is simply dissolving 
common line segments.

The only short-term recommendations is the usual one to reduce the 
precision of the input geometry as much as possible (using I think 
ST_SnapToGrid).  This may still not solve the problem, however.  The 
ultimate solution is perform snap-rounding over the entire input set.  I 
don't think ST_Snap is doing this - AFAIK it's doing some 
heuristic-based snapping only.

 From the long series of ticket replies, it seems like C handling of 
floating point might be causing some problems too, since GEOS seems to 
be somewhat less robust than JTS in these various cases (although JTS 
itself is not 100% robust either).

It would help if you can post the data, or a subset of it which exhibits 
the problem.  The problem area should be in the close neighbourhood of 
the lines reported in the exception.

On 2/26/2012 10:25 PM, James Sewell wrote:
>
> Hello All,
>
> I'm never sure which list to fire these GEOS problems from PostGIS 
> issues to, so I'll try them both this time.
>
> I'm using the following:
>
> PostgreSQL 9.1.2 on i686-pc-linux-gnu, compiled by gcc (GCC) 4.1.2 
> 20080704 (Red Hat 4.1.2-44), 32-bit
>
> POSTGIS="2.0.0alpha7SVN" GEOS="3.3.2-CAPI-1.7.2" PROJ="Rel. 4.7.1, 23 
> September 2009" LIBXML="2.6.26" USE_STATS
>
> I have been closely following the updates to GEOS / PostGIS at the end 
> of last year with regards to overlay routines. Since the advent of 
> ST_UnaryUnion and the updates in the BinaryOp code as of r3552 I have 
> been trying to get our overlay code working again. We currently do the 
> following:
>
> ·Break left layer and right layer into smaller regions (both are 
> multipolygons)
>
> ·For each region
>
> oUse ST_Snap to snap the left layer (which in this case is less 
> accurate) to a collection of the right layer at 10E-8
>
> oDump the left and the right layers to linework and collect them to 
> two geoms
>
> oPerform a ST_UnaryUnion on each layer, then collect them together
>
> oPerform a ST_UnaryUnion on the collection (I found using this two 
> tiered Union approach sometimes resolved nodding errors, obviously at 
> the cost of speed though). If I get a non-noded intersection problem 
> it is here 100% of the time.
>
> oPolygonize the output
>
> oPerform overlay map to pull through gids from original left and right 
> layers
>
> At one point I did translate to the origin before any Union 
> operations, but this broke down as the linework got more complex 
> (which unfortunately happens every month as new polygons are added).
>
> At the moment the problem I face is the same as my old problem (when 
> using ST_Union, see http://trac.osgeo.org/geos/ticket/392). When 
> performing the second ST_UnaryUnion of the collected left and right 
> lineworks (which are valid) I get the following:
>
> GEOSUnion: TopologyException: found non-noded intersection between 
> LINESTRING (149.169 -37.739, 149.169 -37.7391) and LINESTRING (149.169 
> -37.7391, 149.169 -37.739) at 149.16916209449002 -37.739087184984776
>
> This year I've been familiarising myself with the code and reading 
> through all the old posts I can find which apply to this.
>
> I just wanted to throw this list post out there to see what others had 
> to say about this issue. It seems to have been round for a while now, 
> and from what I can tell it's not an easy fix.
>
> Yum install
>
> Is it likely to be a precision issue? I am currently upgrading my GCC 
> version so I can try this http://trac.osgeo.org/geos/ticket/504, does 
> anyone have any thoughts on if that might help?
>
> Or is the issue more likely to be as described here? 
> http://trac.osgeo.org/geos/ticket/459
>
> Sorry for the long post, just hoping to get some discussion going. I 
> will try to post a fresh testcase which causes the error tomorrow.
>
> Cheers,
>
> James Sewell
> Solutions Architect
> LISAsoft
>
> ------------------------------------------------------------------------
>
> *Ph: *+61 3 8680 3250 *Fax: *+61 3 8680 3299
> Level 9, 601 Bourke St, Melbourne Vic 3000
>
> ------------------------------------------------------------------------
>
> http://www.lisasoft.com <http://www.lisasoft.com/>
>
>
> ------------------------------------------------------------------------
> The contents of this email are confidential and may be subject to 
> legal or professional privilege and copyright. No representation is 
> made that this email is free of viruses or other defects. If you have 
> received this communication in error, you may not copy or distribute 
> any part of it or otherwise disclose its contents to anyone. Please 
> advise the sender of your incorrect receipt of this correspondence.
>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>
>
> No virus found in this message.
> Checked by AVG - www.avg.com <http://www.avg.com>
> Version: 2012.0.1913 / Virus Database: 2114/4833 - Release Date: 02/26/12
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20120227/d3960b86/attachment.html