What is the fastest way to create the union of many boost::polygons?

Question

I have to union many boost::polgons, but my approach does not seem very performant (>15 min), especially with larger numbers of polygons (>2000).

I push all the polygons i want to union into a multipolygon and then join the multipolygon, see my code:

BOOST_FOREACH(polygon, multipolygon)
{
  boost::geometry::clear(tmp_union); //tmp_union  is a multipolygon
  boost::geometry::union_(result, poly, tmp_union);
  result = tmp_union;
}

The result will presumably not contain very many polygons, because most of the polygons to union will intersect.

Is there any way to make this more performant, like sorting the polygons in some specific order or a completely different approach?

Answer 1

You can also try Boost.Polygon implementation of union by the class property_merge http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/gtl_property_merge.htm.

Essentially, you create a property_merge object with a trivial integer property:

namespace bgp = boost::polygon;
typedef int property_type;
typedef int coordinate_type;
const property_type FAKE_PROPERTY = 99;

typedef std::map<std::vector<property_type>, bpg::polygon_set_data<coordinate_type> > merge_result;
//in fact, merge_map will have 1 element only

merge_map merger;
for (polygon: my_polygons) 
   merger.insert(polygon, FAKE_PROPERTY);

merge_result mresult;
merger.merge(mresult);

//now use the only element result should have 
assert( mresult.size()<=1);
if (mresult.empty())
{
   //use empty bpg::polygon_set_data()
}
else
{
   //use 
   const bpg::polygon_set_data & result = mresult.begin()->second;
   ...
}