Boost logo

Geometry :

Subject: [ggl] Difference / xor for multi polygons
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-03-07 18:57:51

Barend Gehrels wrote:

 Sorry, both input polygons are indeed not valid. Neither holes, neither parts of a multi-polygon may touch each other at more than one point. Sorry about that, these are the OGC-rules and reported as such by both MS SQL Server Spatial and PostGIS. But there is reasoning behind this rules - these polygons can be rewritten easily forming two polygons or one polygon with two holes.

Boost Geometry has functionality to do this, the dissolve function, and I just tested it with this input polygons, and it runs well. It gives (left/right, not at same scale):
The problem with "dissolve" is that it is not guaranteed to work (therefore in an extension now). With polygons forming a multi-polygon, it should always work (just calling union and that should work). Multiple holes are in fact a similar situation, but those cases are not thoroughly tested yet. However, for this kind of input, I expect it to work (and otherwise I'm interested in the WKT-s).

What are the prospects for enhancing the polygon clipping algorithm itself to handle such cases correctly? I'll leave aside handling of self intersection/self overlap, but handling self abutment of polygons seems like a reasonable expectation from the user's perspective. If dissolve can be made guaranteed to work then it can be run on each input to handle these cases. Alternately the precondition can be checked and an exception thrown. Silently returning the wrong result for self abutting or self intersecting input polygons is not very desirable, from a user perspective. Perhaps you can throw self intersecting polygon or self abutting polygon exception and perhaps also the coordinates of the first detected instance of the precondition violation so that the user is not caught unaware. CGAL throws a generic precondition violation for any problem, but it isn't at all clear what all of the precondition requirements are, which one was violated or where the violation is in the input. I'd like to see better
error handling than that, since I found CGAL very frustrating. Keep in mind that error handling is part of the interface. The user may wish to catch the exception and cleanup their data then retry.

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at