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@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/geometry