如何在 O(n*log(n)) 时间内找到并打印 n 个给定圆的交点？

Question

我正在寻找一种O(n*logn)算法来查找和打印n给定圆的交点。每个圆都由其中心和半径指定。

O(n ² ) 算法包括检查中心之间的距离是否小于或等于（被比较的两个圆的）半径之和。但是，我正在寻找更快的！

一个类似的问题是线段的交叉。我认为即使我的问题也可以使用线扫描算法来解决，但我无法弄清楚如何在圆圈的情况下修改事件队列。

请同时注意以下角落案例。黑点表示事件点（根据用户 Sneftel 的解决方案，不会打印箭头标记的圆圈交叉点下方）

Answer 1

这是我根据 User Sneftel 算法的修改找到的正确解决方案，但该算法并不适用于所有情况。

图 1：用边界框表示每个圆。
现在要使用扫描线方法，将扫描线平行于 y 轴移动，我们需要两条线段来表示每个圆的 y 范围，如图 2 所示。

完成此操作后，问题减少为以下内容：

这里2条线段代表一个圆。
扫描线状态可以保持为任何平衡的动态数据结构，如 AVL 树、跳过列表、红黑树，插入/更新/删除/检索时间最多为 O(logn)。
本例中的比较函数将检查相邻线段对应的两个圆是否相交（而不是像原来的线扫描方法中查找线段交点那样检查线段是否相交）。这可以在 O(1) 时间内完成，因为需要恒定数量的操作。
事件点数量：4n（对于 n 个圆 => 2n 个线段 => 4n 个端点）
复杂度 = O(4nlog(4n)) = O(nlogn)