Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at