Boost logo

Geometry :

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

Geometry list run by mateusz at loskot.net