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

Question

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

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

类似的问题是线段的交集。我认为即使是我的问题也可以使用 line sweep algorithm 来解决，但我无法弄清楚如何在圈子的情况下修改事件队列。

请注意以下极端情况。黑点表示事件点(根据 User Sneftel 的解决方案，箭头标记的圆圈交点下方将不会打印)

Answer 1

当您遇到圆圈的左极值(即 (x-r, y))时，直线扫描算法会简单地将圆圈添加到列表中，并在您遇到其右极值时将其从列表中删除。在将圈子添加到列表之前，请将其与列表中已有的圈子进行核对。所以你的事件队列基本上是所有圆圈的左右极值，按x排序。 (注意，你提前知道了所有的事件，所以它并不是真正意义上的“队列”。)

这也称为“清理和修剪”。