what shall I do If I get a topology exception in union op?

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

what shall I do If I get a topology exception in union op?

Stefan Steiniger
Hei Martin and others,

I get the exception below while intersecting two layers of polygons (in
OpenJUMP >Tools>two Layers>intersect polygon layers).
Is there a way to proceed despite the exception?
Could it be that the problem is within one layer of polygons? i.e.
overlapping polygons in one layer?

The coordinates are also not useful [1] - not sure what coordinate
system they are in???

stefan

[1]
bbox(677104.8683854531,228446.29622920923,687118.4247461993,237423.31161814026)


com.vividsolutions.jts.geom.TopologyException: found non-noded
intersection between LINESTRING ( 5453.300000000047 32281.0,
5454.177554877591 32280.11017162766 ) and LINESTRING ( 5454.177554877578
32280.110171627675, 5452.379085899257 32281.844875321825 ) [
(5454.177554877563, 32280.11017162769, NaN) ]
        at
com.vividsolutions.jts.noding.FastNodingValidator.checkValid(FastNodingValidator.java:109)
        at
com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:94)
        at
com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:59)
        at
com.vividsolutions.jts.operation.overlay.OverlayOp.computeOverlay(OverlayOp.java:170)
        at
com.vividsolutions.jts.operation.overlay.OverlayOp.getResultGeometry(OverlayOp.java:127)
        at
com.vividsolutions.jts.operation.overlay.OverlayOp.overlayOp(OverlayOp.java:66)
        at
com.vividsolutions.jts.operation.overlay.snap.SnapOverlayOp.getResultGeometry(SnapOverlayOp.java:67)
        at
com.vividsolutions.jts.operation.overlay.snap.SnapOverlayOp.overlayOp(SnapOverlayOp.java:24)
        at
com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.getResultGeometry(SnapIfNeededOverlayOp.java:76)
        at
com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.overlayOp(SnapIfNeededOverlayOp.java:25)
        at com.vividsolutions.jts.geom.Geometry.union(Geometry.java:1173)
        at
org.openjump.core.geomutils.algorithm.IntersectGeometries.nodeLines(IntersectGeometries.java:471)
        at
org.openjump.core.ui.plugin.tools.IntersectPolygonLayersPlugIn.runIntersectionNew(IntersectPolygonLayersPlugIn.java:179)
        at
org.openjump.core.ui.plugin.tools.IntersectPolygonLayersPlugIn.run(IntersectPolygonLayersPlugIn.java:112)
        at
com.vividsolutions.jump.workbench.ui.task.TaskMonitorManager$TaskWrapper.run(TaskMonitorManager.java:149)
        at java.lang.Thread.run(Thread.java:619)
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: what shall I do If I get a topology exception in union op?

Martin Davis
This is likely due to lines in the input which are almost, but not quite
coincident.  This would be caused by two polygons which have similar,
but not identical, line(s) along a portion of their boundaries.  These
might be in a single layer, or they might be in different input layers.

Unfortunately in general these are not easy to recover from.  One thing
you can try is to reduce the precision of your input geometries.

I think the ultimate technical solution to this is to snap-round the
datasets individually and together.  Unfortunately I don't have code or
an API for doing this at this point.

The coordinates in the error message are not useful - they are in a
translated coordinate system used internally.

I'd be interested to see the input dataset, if you can provide it.

Martin

Stefan Steiniger wrote:

> Hei Martin and others,
>
> I get the exception below while intersecting two layers of polygons
> (in OpenJUMP >Tools>two Layers>intersect polygon layers).
> Is there a way to proceed despite the exception?
> Could it be that the problem is within one layer of polygons? i.e.
> overlapping polygons in one layer?
>
> The coordinates are also not useful [1] - not sure what coordinate
> system they are in???
>
> stefan
>
> [1]
> bbox(677104.8683854531,228446.29622920923,687118.4247461993,237423.31161814026)
>
>
>
> com.vividsolutions.jts.geom.TopologyException: found non-noded
> intersection between LINESTRING ( 5453.300000000047 32281.0,
> 5454.177554877591 32280.11017162766 ) and LINESTRING (
> 5454.177554877578 32280.110171627675, 5452.379085899257
> 32281.844875321825 ) [ (5454.177554877563, 32280.11017162769, NaN) ]
>     at
> com.vividsolutions.jts.noding.FastNodingValidator.checkValid(FastNodingValidator.java:109)
>
>     at
> com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:94)
>
>     at
> com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:59)
>
>     at
> com.vividsolutions.jts.operation.overlay.OverlayOp.computeOverlay(OverlayOp.java:170)
>
>     at
> com.vividsolutions.jts.operation.overlay.OverlayOp.getResultGeometry(OverlayOp.java:127)
>
>     at
> com.vividsolutions.jts.operation.overlay.OverlayOp.overlayOp(OverlayOp.java:66)
>
>     at
> com.vividsolutions.jts.operation.overlay.snap.SnapOverlayOp.getResultGeometry(SnapOverlayOp.java:67)
>
>     at
> com.vividsolutions.jts.operation.overlay.snap.SnapOverlayOp.overlayOp(SnapOverlayOp.java:24)
>
>     at
> com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.getResultGeometry(SnapIfNeededOverlayOp.java:76)
>
>     at
> com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.overlayOp(SnapIfNeededOverlayOp.java:25)
>
>     at com.vividsolutions.jts.geom.Geometry.union(Geometry.java:1173)
>     at
> org.openjump.core.geomutils.algorithm.IntersectGeometries.nodeLines(IntersectGeometries.java:471)
>
>     at
> org.openjump.core.ui.plugin.tools.IntersectPolygonLayersPlugIn.runIntersectionNew(IntersectPolygonLayersPlugIn.java:179)
>
>     at
> org.openjump.core.ui.plugin.tools.IntersectPolygonLayersPlugIn.run(IntersectPolygonLayersPlugIn.java:112)
>
>     at
> com.vividsolutions.jump.workbench.ui.task.TaskMonitorManager$TaskWrapper.run(TaskMonitorManager.java:149)
>
>     at java.lang.Thread.run(Thread.java:619)
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: what shall I do If I get a topology exception in union op?

Stefan Steiniger
In reply to this post by Stefan Steiniger
Hei Martin,

thank you for your answer. So it seems there is no "debugging" procedure
and instead you suggest a data simplification.

I will send you the dataset in a personal email. I have actually now
taken a different approach by splitting the datasets and using the
Symmetric Difference Function in ArcGIS.

stefan
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: what shall I do If I get a topology exception in union op?

Martin Davis
No, unfortunately there's no debugging procedure.  This situation is due
to a known limitation in the current overlay algorithm design.   So it
doesn't need debugging - it needs some brilliant new thinking!

Thanks for the dataset....  Good that you found a workaround.

Martin

Stefan Steiniger wrote:

> Hei Martin,
>
> thank you for your answer. So it seems there is no "debugging"
> procedure and instead you suggest a data simplification.
>
> I will send you the dataset in a personal email. I have actually now
> taken a different approach by splitting the datasets and using the
> Symmetric Difference Function in ArcGIS.
>
> stefan
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: what shall I do If I get a topology exception in union op?

mbedward
2009/3/18 Martin Davis <[hidden email]>:
> So it doesn't need debugging - it needs some brilliant new thinking!

Sounds like what I think about most of my code...

Out of interest Martin, do you use anything like the approach described here...

Edelsbrunner & Mucke (1990) Simulation of simplicity: a technique to
cope with degenerate cases in geometric algorithms.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.5997

I've been trying to understand it.

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: what shall I do If I get a topology exception in union op?

Martin Davis
No, I don't use this technique.  It looks pretty complicated!  And I
have never seen any implementation examples on the web (which is the
case for 90% of the papers out there, of course).

For predicates I use the technique of exact determinant sign evaluation
by Devillers et al.  For robustness of line arrangment computation I use
a snap-rounding approach (see Hobby and others).

M

Michael Bedward wrote:

> 2009/3/18 Martin Davis <[hidden email]>:
>  
>> So it doesn't need debugging - it needs some brilliant new thinking!
>>    
>
> Sounds like what I think about most of my code...
>
> Out of interest Martin, do you use anything like the approach described here...
>
> Edelsbrunner & Mucke (1990) Simulation of simplicity: a technique to
> cope with degenerate cases in geometric algorithms.
>
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.5997
>
> I've been trying to understand it.
>
> Michael
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: what shall I do If I get a topology exception in union op?

mbedward
2009/3/19 Martin Davis <[hidden email]>:
> No, I don't use this technique.  It looks pretty complicated!

That's reassuring.  Ironic given the title :-)

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...