What is the fastest way to create the union of many boost::polygons?
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?
Thank you
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;
...
}
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.
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.
链接地址: http://www.djcxy.com/p/20032.html