[geos-devel] Noding linework

[Sandro Santilli]

On Thu, Jul 14, 2011 at 08:17:55PM -0700, Martin Davis wrote:
> Yes, union() is supposed to fully node linework.
> 
> This case works fine in JTS 1.11 (and JTS 1.12) - i.e. running the
> equivalent of polygonize( union( boundary(A),  B).  The output from
> the union checks out as being fully noded, and the polygonize
> produces 2 valid polygons.
> 
> So possibly this is one of those numerical issues which shows up in
> GEOS in native code, but not in JTS in Java?  This maybe one of
> those cases where GEOS and JTS need to be traced through in parallel
> (which seems really painful, but I think you've done this in the
> past, right?)

Found.

Contrary to JTS, which engages SnapRounding on first robustness failure,
GEOS first tries with a pure CommonBitsRemover approach:

Trying with original input.
Original exception: TopologyException: found non-noded intersection between LINESTRING (1.72293e+06 4.78835e+06, 1.72293e+06 4.78835e+06) and LINESTRING (1.72293e+06 4.78835e+06, 1.72293e+06 4.78834e+06) at 1.72293e+06 4.78835e+06
Trying with Common Bits Remover (CBR)

I've seen in the past already that re-adding previously removed common
bits may introduce invalidities (we discussed this in another occasion).
That's because some of the lowermost bits fall off possibly moving the
vertices to fall on a given grid. Evidentily this was the case in GEOS,
where the output from Union against the shifted geometries was fully noded
but became non-noded when re-adding common bits.

Indeed going SnapRounding directly gives a fully noded output !
But it gives failures (found non-noded intersection) in a 
couple of testcase:

 bug360.xml (http://trac.osgeo.org/geos/ticket/360) [JTS works]
 bug392.xml (http://trac.osgeo.org/geos/ticket/392) [JTS throws an exception!]

--strk;

  ()   Free GIS & Flash consultant/developer
  /\   http://strk.keybit.net/services.html