Re: [boost] [GGL][Polygon][Union] Union of multi_polygon returns unexpected

Subject: Re: [boost] [GGL][Polygon][Union] Union of multi_polygon returns unexpected
From: Barend Gehrels (barend_at_[hidden])
Date: 2010-02-09 04:52:19

Hi Helal,

> Union of multi_polygon has some bugs. I must admit I could not 
> pinpoint the problem. Please let me know if I am missing something.
> These are the test cases I tried and most of them failed:
>
> Case 6: one of the list has a single polygon (FAIL)
> Case 8: Different number of polygons in the lists (FAIL)
> Case 9: 2nd list has a single polygon (FAIL)
These are now passing, I just committed the adapted sources. There was a 
failure in the assemble process which is again revised (and a bit 
simplified) now. Thanks again for the bug report.

>
> Case 11: one list has same polygon twice (FAIL)
> Case 12A: using same list twice. Its a mess. (FAIL)
> Case 12B: keeping one of the list empty. Returns empty. (FAIL)
As said, these input-multi-polygons do have self-intersections which are 
not solved (not even detected) during the overlay process.

According to OGC (Open Geospatial Consortium), these kind of input 
geometries are not valid. So spatial databases like PostGreSQL or SQL 
Server 2008 reject this input.

There is a solution of course, we are implementing a "dissolve" 
algorithm, which removes self intersections (internal borders), it can 
be used for a polygon (e.g. to convert a keyholed interior ring to a 
normal interior ring) or for a multi-polygon (to solve things like 
this). This one is not yet ready, but if yes and you call it before 
union, it will give you the expected results. It probably avoids calls 
to union in many cases, dissolve does the process of unioning a 
multi-polygon already.

An option is to call dissolve internally, from union. This however would 
halve the speed, in many cases the input is known to be valid, so this 
step is not necessary. Besides that, if you enter an input geometry A 
(multi-polygon with self-overlapping triangles) and B (empty), you will 
get back A immediatly for a union, you probably would be surprised that 
A is touched by the process.

However, yet another option is to give the union a boolean flag to 
denote to dissolve first. This is not yet decided.
Note that the dissolve is not yet in Boost.Sandbox because it is not yet 
ready, it is expected to be there one of the coming weeks.

Regards, Barend