7

MI Shamos 在他 1978 年的论文中首先提出了在平面上找到“N”个圆盘/圆的交点/并集的问题：

Shamos，密歇根州“计算几何”博士 论文，耶鲁大学，纽黑文，CT 1978。

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

1988 年，Franz Aurenhammer 提出了一种更有效的 O(n log n) 时间和 O(n) 空间算法，用于使用幂图（Voronoi 图的推广）进行圆相交/并集：Aurenhammer, F. 使用幂的改进的圆盘和球算法图表。算法杂志 9 (1985)，第 151-161 页。

早在 1983 年，Paul G. Spirakis 还提出了一个 O(n^2) 时间确定性算法和一个 O(n) 概率算法：Spirakis, PG Very Fast Algorithms for the Union of Many Circles。Rep. 98，计算部。科学，Courant 研究所，纽约大学，1983 年。

我一直在寻找上述算法的任何实现，专注于计算几何包，但我还没有找到任何东西。由于两者似乎都不重要，如果有人能指出我正确的方向，那就太好了！

也许建设性立体几何 (CSG) 包将具有用于重叠圆形基元的表面积特征？

4

2 回答 2

6

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

CGAL 库有一个实现球并集的包。这比您感兴趣的维度高一维，并且它不处理交叉点。所以可能没有雪茄。

如果您在 2 维中工作，则问题相当于在 3 维中找到凸包。您可以使用 CGAL 或其他软件包中的凸包材料。

如果您正在寻找您提到的特定算法的实现，我无法帮助您。但是，如果您只想找到允许您轻松计算并集和交集的幂图，那么使用 3D 凸包算法自行推出可能比您想象的要容易。

对不起，半生不熟的答案，但我们不妨从某个地方开始，看看你有多大的灵活性。

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

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

于 2010-05-18T03:48:10.617 回答
1

CGAL 中没有 2D 功率图实现。上面建议的链接 (http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html) 用于加法加权 Voronoi 图，它使用 euclid + 权重，而不是 euclid^2 +重量（如功率图所做的那样）。

于 2011-08-08T15:20:33.233 回答