Subject: Re: [boost] [GGL][Polygon][Union] Union of multi_polygon returns unexpected
From: Barend Gehrels (barend_at_[hidden])
Date: 2010-02-06 09:04:19
> 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.
Yes, there was indeed a problem. Thanks again for your report. However,
I could not reproduce some of your tests marked as failed.
> 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)
They indeed fail, all for the same reason
> Case 11: one list has same polygon twice (FAIL)
IMO it passes (see below)
> Case 12A: using same list twice. Its a mess. (FAIL)
IMO passes perfectly.
> Case 12B: keeping one of the list empty. Returns empty. (FAIL)
IMO it passes and it does not return empty. It is in comments in your
code, so I cannot see what was going wrong when it was not commented.
We have to define what is failing and what is passing. The overlay
algorithms using multi-polygons currently do not remove internal
boundaries. So, in case 12B, you have one multi-polygon of several
overlapping polygons, and one empty. You get back the input (in my
test). This is my adapted version of your code:
union_inserter<polygon_2d>(ps1, ps2, std::back_inserter(ps3)); //B
dump_wkt("case12b.wkt", ps1, ps2, ps3);
(will explain dump_wkt below).
(Note that I made a change here last week, it might indeed be that it
failed earlier, didn't check).
Case 11 passes the same polygon twice, and it is not overlapping with
the other polygon, so you get it back like you entered it, combining the
two geometries and listing that same polygon twice.
I had a look at case 6,8,9 because they should not fail. It is solved
and I will update boost.sandbox soon, I will notify the list if that is
I will come back to the union of two multi-polygons which do have self
intersections in another email, it will either be implemented or there
will be a possibility to solve it differently.
I added a "dump_wkt" which produces well-known text (WKT). Those are
strings which I can easily use in my unit tests. In case you find more
errors, maybe you can include the WKT's and I will probably not need the
template <typename G1, typename G2, typename G3>
inline void dump_wkt(std::string const& s, G1 const& a, G2 const& b, G3
out << s << std::endl;
out << area(a) << " " << area(b) << " -> " << area(c);
out << std::endl;
out << wkt(a) << std::endl;
out << wkt(b) << std::endl;
out << wkt(c) << std::endl;
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk