On 05/08/2014 08:09 πμ, Carl Wellington
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
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
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
Below is an adaptation of the code example for union
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::cout << " Intersects: " << boost::geometry::intersects(mp) <<
polygon green, blue;
// Using polygons from example - details are unimportant, any overlapping
polygons would do
"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);
"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
boost::geometry::union_(green, blue, output1);
std::cout << "output1 = union(green,blue)" << std::endl;
std::cout << std::endl;
// Try 2 [FAILS]: Build up multi_polygon by repeatedly unioning in each
boost::geometry::union_(output2, green, output2);
std::cout << "output2 = union(output2,green)" << std::endl;
boost::geometry::union_(output2, blue, output2);
std::cout << "output2 = union(output2,blue)" << std::endl;
Result (Using Boost 1.55):
output1 = union(green,blue)
Num points: 27
output2 = union(output2,green)
Num points: 17
output2 = union(output2,blue)
Num points: 17
Num points: 27
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
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
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::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.
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