Geometry Boost List: Re: [geometry] Fwd: Some updates [union of multi_polygon]

Subject: Re: [geometry] Fwd: Some updates [union of multi_polygon]
From: Menelaos Karavelas (menelaos.karavelas_at_[hidden])
Date: 2014-08-05 04:27:51

Hi Carl.

On 05/08/2014 08:09 πμ, Carl Wellington wrote:
> I'm the originator of this question that Andrew posted to this list. First, I
> apologize for the rant about boost documentation. That was written in a
> moment of frustration to my co-worker Andrew and wasn’t really intended to
> be included in a request for help to a mailing list. Second, thank you for

Documentation is definitely one of the hardest parts.
As Adam said, suggestions and/or contributions are more than welcome.

> all the helpful responses (especially given the tone of my documentation
> rant). The responses provided were very helpful and are exactly the kind of
> thing that I would love to see more of in boost documentation. Having a
> concrete example is extremely helpful and then I can go back to the concept
> definition and understand how to generalize things, but without an example
> it can be hard to get started. To be specific, I would love to have seen the
> responses in this thread on the model::multi_polygon page of the
> documentation - that would have saved me hours.

We will see what we can about those. You have definitely given us some 
very helpful hints on what to focus on.
In any case, please feel free to post questions to the geometry mailing 
list.

> Anyway, back to my problem at hand. I believe I understand what is causing
> my problem but I do not understand why it is a problem since it seems to me
> like it should be a valid use case. If I take a union of two polygons and
> place the result in a multi_polygon, that succeeds. However, if I take a
> multi_polygon and then repeatedly union the polygons into that multi_polygon
> it fails.
>
> Below is an adaptation of the code example for union
> (http://www.boost.org/doc/libs/1%5f55%5f0/libs/geometry/doc/html/geometry/reference/models/model_multi_polygon.html)
> that demonstrates my problem:
>
> -----------------------
>
> // Display some info about a multi_polygon
> void check(const multi_polygon& mp)
> {
>     std::cout << "  Size: " << mp.size() << std::endl;
>     for(int i = 0; i < mp.size(); ++i)
>     {
>        std::cout << "    Num points: " << boost::geometry::num_points(mp[i])
> << std::endl;
>     }
>     std::cout << "  Intersects: " << boost::geometry::intersects(mp) <<
> std::endl;
> }
>
>
> int main()
> {
>     polygon green, blue;
>
>     // Using polygons from example - details are unimportant, any overlapping
> polygons would do
>     boost::geometry::read_wkt(
>        "POLYGON((2 1.3,2.4 1.7,2.8 1.8,3.4 1.2,3.7 1.6,3.4 2,4.1 3,5.3
> 2.6,5.4 1.2,4.9 0.8,2.9 0.7,2 1.3)"
>        "(4.0 2.0, 4.2 1.4, 4.8 1.9, 4.4 2.2, 4.0 2.0))", green);
>
>     boost::geometry::read_wkt(
>        "POLYGON((4.0 -0.5 , 3.5 1.0 , 2.0 1.5 , 3.5 2.0 , 4.0 3.5 , 4.5 2.0 ,
> 6.0 1.5 , 4.5 1.0 , 4.0 -0.5))", blue);
>
>     // Try 1 [WORKS]: Take union of two polygons and put result into
> multi_polygon
>     multi_polygon output1;
>     boost::geometry::union_(green, blue, output1);
>     std::cout << "output1 = union(green,blue)" << std::endl;
>     check(output1);
>
>     std::cout << std::endl;
>      
>     // Try 2 [FAILS]: Build up multi_polygon by repeatedly unioning in each
> polygon
>     multi_polygon output2;
>     boost::geometry::union_(output2, green, output2);
>     std::cout << "output2 = union(output2,green)" << std::endl;
>     check(output2);
>      
>     boost::geometry::union_(output2, blue, output2);
>     std::cout << "output2 = union(output2,blue)" << std::endl;
>     check(output2);
>
>     return 1;
> }
>
> -----------------------
>
> Result (Using Boost 1.55):
>
> output1 = union(green,blue)
>    Size: 1
>      Num points: 27
>    Intersects: 0
>
> output2 = union(output2,green)
>    Size: 1
>      Num points: 17
>    Intersects: 0
> output2 = union(output2,blue)
>    Size: 2
>      Num points: 17
>      Num points: 27
>    Intersects: 1
>
> -----------------------
>
> It appears that when I repeatedly union the polygons in one at a time, then
> it does not do what I expect. I would expect the above two cases to be
> equivalent, but when I add polygons one at a time, then the resulting
> multi-polygon has multiple parts and keeps the first polygon in addition to
> the union. Therefore it self-intersects and cannot be used for further
> calls.

Here is what is happening: the third parameter of the the union_ 
function should better be thought of /*not*/ as a multipolygon, but 
rather as a container of polygons. What union_ does is that it computes 
the union of the two geometries that you pass as the first two 
arguments, and then outputs (appends to be exact) the resulting 
polygon(s) in the polygon container. So the keyword here is 
/*outputs/*//*appends*/. The contents of the third argument to union_are 
*/not/*/*cleared*/, which means that when you write:
     bg::union_(output2, blue, output2)
the output2 and blue polygons are unioned, and then the resulting 
polygon(s) (only one in this case) is appended to output2. This is why 
you see the green polygon in output2 after this union operation. See 
also my attached program that uses yet another multipolygon for the 
union of output2 and blue.

> So, is this behavior expected? If so, is there an alternative formulation I

Yes it is expected in the sense that the contents of the third argument 
to union are not cleared.

> can use to build up a union of many polygons?

Yes, of course, but you will need more than one output multipolygon.
I have not coded it, and I am pretty sure it is not the most efficient 
way of doing it, but something like the following should work.
I am writing it here more in the sense of a proof-of-concept rather than 
as the best/suggested way to do it.

--------------------
std::vector<polygon> polygons; // just to indicate that I have many 
polygons.
// initialize the vector polygons

multi_polygon output, tmp;

for (std::size_t i = 0; i < polygons.size(); ++i)
{
     bg::clear(output);
     bg::union_(tmp, polygons[i], output);
     tmp = output;
}

// output contains the union of all your polygons
--------------------

If you use BG's multi_polygon, this is essentially the same an an 
std::vector. So you can replace the assignment "tmp = output" by a swap 
operation, which should be more efficient.

An even more sophisticated approach would be to build a tournament tree 
for the polygons you want to union, and my feeling would be that it 
would be faster than adding each polygon to the current union of the 
previous ones, but to be sure abut this I would need to implement it and 
do performance tests on it; so at this points this is just one more idea.

> Thanks again for the help,

You are welcome.

Best,

- m.

> Carl
>
>
>
> --
> View this message in context: http://boost-geometry.203548.n3.nabble.com/Fwd-Some-updates-tp4026145p4026149.html
> Sent from the Boost Geometry mailing list archive at Nabble.com.
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry