创建多个boost :: polygons的最快方法是什么？
我必须联合许多boost :: polgons，但是我的方法看起来并不是很高效（> 15分钟），尤其是对于更多数量的多边形（> 2000）。
我将所有想要合并的多边形推入多面体，然后加入多面体，
看我的代码：
BOOST_FOREACH(polygon, multipolygon)
{
boost::geometry::clear(tmp_union); //tmp_union is a multipolygon
boost::geometry::union_(result, poly, tmp_union);
result = tmp_union;
}
结果可能不包含非常多的多边形，因为大多数要结合的多边形将相交。
有没有办法让这个更高效，比如按照某种特定顺序排列多边形或者采用完全不同的方法？
谢谢
您还可以通过类property_merge http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/gtl_property_merge.htm来尝试联合的Boost.Polygon实现。
实质上，你创建一个具有普通整数属性的property_merge对象：
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;
...
}
你可能想看看CGAL是如何做的。 至少他们有一个加入多个多边形的功能。 看看代码，我注意到一个函数_devide_and_conquer的调用。 还应该转换为boost ：将多边形列表分为两部分，然后计算每个多边形的联合，然后计算两者的联合。 至少如果生成的多边形比原始多边形更复杂，这应该会给你一些改进。
如果这还不够，你可能会给CGAL一个尝试，看看是否有其他的魔法让它比加速更快。 如果不是，你可能必须自己实现计算。
我想我会按照左端点x值增加的顺序排列多边形边缘。 然后，您可以平行地遍历所有多边形的边缘，同时跟踪迄今为止的联合的外边界。 任何完全处于工会界限范围内的边缘都可以很快省略。 但是，如果你自己解决这个问题，那么在数字不精确的情况下实现强大的实现可能是一个主要问题。 你可能想看看这个强健的谓词。
没有看到你的多边形是什么样子，很难给出基础的建议。
直觉告诉我，你应该以自下而上的方式改善局部性并合并可能干扰的多边形。
为此，找出多边形中心的横坐标的中位数，并将它们分配在中值的任一侧; 对于每一半，用纵坐标重复; 等递归。 这与构建中心的kD树相同（http://en.wikipedia.org/wiki/Kd_tree）。
当你最终得到两个多边形时，合并它们。 然后，递归树，合并成对的多边形。
链接地址: http://www.djcxy.com/p/20031.html上一篇: What is the fastest way to create the union of many boost::polygons?