algorithm - 用于计算 'N' 圆的交集/并集的 Sharir 或 Aurenhammer 确定性算法的实现

Question

在平面上求“N”个圆盘/圆的交集/并集的问题最早是由 M. I. Shamos 在他 1978 年的论文中提出的:

Shamos, M. I.“计算几何”博士论文，耶鲁大学，康涅狄格州纽黑文，1978 年。

从那时起，在 1985 年，Micha Sharir 提出了一种 O(n log2n) 时间和 O(n) 空间确定性算法来解决圆盘相交/并集问题(基于修改后的 Voronoi 图):Sharir, M. Intersection and closest-一组平面圆盘的配对问题。暹罗.J 计算。 14 (1985)，第 448-468 页。

1988 年，Franz Aurenhammer 提出了一种更高效的 O(n log n) 时间和 O(n) 空间算法，用于使用幂图(Voronoi 图的推广)的圆相交/并集:Aurenhammer, F. Improved algorithms for discs and使用功率图的球。算法杂志 9(1985 年)，第 151-161 页。

早在 1983 年，Paul G. Spirakis 还提出了 O(n^2) 时间确定性算法和 O(n) 概率算法:Spirakis, P.G.多圆联合区域的非常快速的算法。众议员 98，部门计算。 Sci., Courant Institute, New York University, 1983.

---

我一直在寻找上述算法的任何实现，重点是计算几何包，但我还没有找到任何东西。由于这两者在实践中都显得微不足道，如果有人能为我指明正确的方向，那就太好了!

也许构造性实体几何 (CSG) 包具有用于重叠圆形图元的表面积特征？

Answer 1

我花了一些时间研究计算一组球的并集的算法 - 正如您提到的，它是通过使用广义 Voronoi 图完成的。

CGAL 库有 a package that implements a union of balls .这比您感兴趣的维度高一维，并且不处理交叉点。所以可能没有雪茄。

如果您在 2 维中工作，则该问题等同于在 3 维中寻找凸包。您可以使用 CGAL 或其他包中的凸包。

如果您正在寻找您提到的特定算法的实现，我帮不了您。但是，如果您只是想找到可以轻松计算并集和交集的幂图，使用 3D 凸包算法自己动手可能比您想象的要容易。

对于半生不熟的答案，我们深表歉意，但我们不妨从某个地方开始，看看您有多少灵 active 。

编辑:还有一个用于二维功率图的 CGAL 包:http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html .

另外，@RGrey 找到了一个 CGAL 库，用于计算广义多边形的 2D bool 值，包括位于 http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html 的圆.