8

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?

timrau
  • 22,578
  • 4
  • 51
  • 64
ffranz
  • 103
  • 1
  • 4
  • 2
    Are these polygons from `boost::geometry::polygons` http://www.boost.org/doc/libs/1_58_0/libs/geometry/doc/html/geometry/reference/concepts/concept_polygon.html of from `boost::polygon::polygon` http://www.boost.org/doc/libs/1_53_0/libs/polygon/doc/gtl_polygon_concept.htm? – alfC Jul 15 '15 at 04:12

3 Answers3

4

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;
   ...
}
Michael Simbirsky
  • 3,045
  • 1
  • 12
  • 24
  • Could you expand on this answer a little ? It's not clear (to me) how you would merge a set of polygons using property_merge ? – Paul R Mar 03 '16 at 11:58
  • Fantastic - thanks for taking the time to do this - that's really helpful! – Paul R Mar 04 '16 at 19:47
1

You might want to look at how CGAL is doing things. At least they have a function to join more than one polygon. Looking at the code, I notice a call to a function _devide_and_conquer. Which should translate to boost as well: divide the list of polygons into two, compute the union for each then the union of both. At least if the resulting polygon is still more complex than the original ones, this should give you some improvement.

If that is still not enough, you might give CGAL a try to see if there is any other magic which makes it faster than boost. If not, you might have to implement the computation yourself.

I guess I'd sort polygon edges in order of increasing x value of the left endpoint. Then you can iterate over edges of all polygons in parallel while keeping track of the outer boundaries of your union so far. Any edges which lies fully within the current bounds of the union could be omitted pretty quickly. But making the implementation robust in the face of numeric inexactness is likely a major problem if you tackle this yourself. You might want to look at robust predicates for this.

MvG
  • 57,380
  • 22
  • 148
  • 276
  • 3
    Where speed is an issue I wouldn't recommend CGAL as it's [an order of magnitude slower](http://rogue-modron.blogspot.com.au/2011/04/polygon-clipping-wrapper-benchmark.html) than other polygon clipping libraries. – Angus Johnson Apr 17 '14 at 18:12
0

It is difficult to give grounded advice without seeing how your polygons look like.

Intuition tells me that you should improve locality and merge polygons that are likely to interfere, in a bottom-up fashion.

For this, find the median abscissa of the centers of the polygons and partition them in either side of the median; for each half, repeat with the ordinate; and so on recursively. This is the same as building the kD tree of centers (http://en.wikipedia.org/wiki/Kd_tree).

When you end up with two polygons, merge them. Then, up the recursive tree, merge the polygons in pairs.