8

我必须联合许多 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;
}

结果可能不会包含很多多边形，因为要合并的大多数多边形都会相交。

有什么方法可以提高性能，比如按特定顺序或完全不同的方法对多边形进行排序？

4

3 回答 3

4

您还可以通过类 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;
   ...
}
于 2014-04-19T02:01:01.570 回答
1

您可能想看看CGAL是如何做事的。至少它们具有连接多个多边形的功能。查看代码，我注意到一个对函数的调用_devide_and_conquer。这也应该转化boost为：将多边形列表分成两部分，计算每个的并集，然后计算两者的并集。至少如果生成的多边形仍然比原始多边形更复杂，这应该会给您一些改进。

如果这还不够，你可以试试 CGAL 看看是否有任何其他魔法让它比 boost 更快。如果没有，您可能必须自己实现计算。

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

于 2014-04-17T14:01:07.417 回答
0

如果不了解多边形的外观，就很难给出有根据的建议。

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

为此，找到多边形中心的中值横坐标，并将它们划分在中值的任一侧；对于每一半，用纵坐标重复；以此类推。这与构建中心的 kD 树 ( http://en.wikipedia.org/wiki/Kd_tree ) 相同。

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

于 2014-04-17T15:28:34.693 回答