Geometry Boost List: [ggl] Difference / xor for multi polygons

Subject: [ggl] Difference / xor for multi polygons
From: Barend Gehrels (barend)
Date: 2011-03-07 16:44:07

Hi Javier,

On 7-3-2011 20:37, Javier Gonzalez wrote:
> Here's another one though:
> Difference of:
>
>  POLYGON((560 -400, 600 -400, 600 -440, 560 -440, 560 -400)), 
> POLYGON((480 -400, 520 -400, 520 -440, 480 -440, 480 -400)), 
> POLYGON((600 -320, 640 -320, 640 -360, 600 -360, 600 -320)), 
> POLYGON((520 -400, 560 -400, 560 -440, 520 -440, 520 -400))
> (4 rectangular holes, 3 close to each other, one separate)
>
> with
> POLYGON((0 0, 2000 0, 2000 -2000, 0 -2000, 0 0), (560 -400, 560 -440, 
> 600 -440, 600 -400, 560 -400), (480 -400, 480 -440, 520 -440, 520 
> -400, 480 -400), (600 -320, 600 -360, 640 -360, 640 -320, 600 -320), 
> (520 -400, 520 -440, 560 -440, 560 -400, 520 -400))
> (a big rectangle with those same 4 rectangles as holes)
>

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):

Blue-black outlined is the input, red outlined is the output. So seems 
correct.

The difference then works. I pasted my code here:
http://codepad.org/ArAgjZKQ

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).

Regards, Barend

-- 
Barend Gehrels
http://about.me/barendgehrels
-------------- next part --------------
Skipped content of type multipart/related