创建许多boost ::多边形的联合的最快方法是什么？

Question

我必须联合许多boost :: polygons，但我的方法似乎不是很高效（> 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;
}

结果可能不包含很多多边形，因为要连接的大多数多边形将相交。

有没有办法让这个更高效，比如按特定顺序排序多边形或完全不同的方法？

Answer 1

您还可以通过类property_merge http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/gtl_property_merge.htm尝试Boost.Polygon实现union。

实质上，您使用一个简单的整数属性创建一个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;
   ...
}

Answer 2

您可能想看看CGAL是如何做事的。至少他们有a function加入多个多边形。看一下代码，我注意到函数_devide_and_conquer的调用。哪个也应该转换为boost：将多边形列表分成两个，计算每个的并集，然后计算两者的并集。至少如果得到的多边形仍然比原始多边形更复杂，这应该会给你一些改进。

如果仍然不够，你可以尝试CGAL，看看是否有任何其他魔法让它比提升更快。如果没有，您可能必须自己实施计算。

我想我会按照增加左端点的x值的顺序对多边形边缘进行排序。然后，您可以并行迭代所有多边形的边，同时跟踪到目前为止联合的外边界。完全位于联合的当前边界内的任何边缘都可以很快省略。但是，如果你自己解决这个问题，那么在数字不精确的情况下使实现变得强大可能是一个主要问题。你可能想看看robust predicates。

Answer 3

如果不了解多边形的外观，很难提供基础建议。

Intuition告诉我，你应该以自下而上的方式改善局部性并合并可能干扰的多边形。

为此，找到多边形中心的中位横坐标，并将它们划分为中位数的两侧;每半个，用纵坐标重复;等等递归。这与构建中心的kD树（http://en.wikipedia.org/wiki/Kd_tree）相同。

当你最终得到两个多边形时，合并它们。然后，在递归树上，成对合并多边形。