联合许多凸多边形的快速算法或库

Question

我需要对许多凸多边形（高达数万个）应用布尔或运算（a.k.a联合），每个多边形的顶点少于100个。我尝试了Boost.Geometry（boost :: geometry :: union_（）函数），它需要大约200ms来联合1500多边形。

我已经实现了一个简单的优化：

1. 多边形分成两组，
2. 递归工会两组分为两个多边形集合，
3. 联盟最后两个多边形集合。

这种优化比将多边形逐个联合起来要快10倍左右。

我需要一个算法或C/C++库来在大约10ms内完成这些操作。

有什么建议吗？

==== ====编辑

我已经取代Boost.Geometry与快船（http://www.angusj.com/delphi/clipper.php），它满足我的要求。 Clipper可以在一个操作中合并多个多边形（Boost.Geometry一次只能合并两个），这可能是它比Boost.Geometry快得多的原因。

Answer 1

您可以尝试扫描线算法，该算法将一次处理所有多边形。

从上到下将所有边从上到下排列，并按照顶点的纵坐标从上到下排列它们。

维护一个活动列表，即横过当前顶点水平的所有边的列表。对于该线的位置，可以确定与活动边的所有交点。保持活动边沿水平排列，以交叉点的横坐标为基准。

当您从一个顶点移动到另一个顶点时，某些边缘会进入该列表，而其他边缘则会离开它。另外，在排序过程中，某些边可以交换，这表明它们相交。

交叉点成对，跟踪多边形内的线段。沿着水平线合并所有分段是一个简单的一维问题。

将所有这些成分放在一起，通过将合并输出从扫描线的一个位置链接到下一个位置，您将形成对应于最终联合的图形。它不一定是连接的。

应该有可能将整个过程实现为单个过程，并避免在不需要的边缘进行分段。

并仔细考虑活动列表处理是如何组织的，算法应该在时间O（NLog（N）+ NK）中运行，其中K是侧面交点的数量。