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

Martin Davis mtnclimb at telus.net
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

More information about the geos-devel mailing list