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

Question

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

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

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

谢谢

Answer 1

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

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

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