algorithm - 查找重叠的圆圈

Question

我有一个矩形区域，其中有半径相等的圆。我想找出哪些圆圈与其他圆圈重叠(输出是重叠圆圈的 2 元素集列表)。

我知道如何检查两个圆是否重叠(圆心之间的距离小于直径)。我可以对每一对圆执行此检查，但我想知道是否有更好的算法(比 O(n^2) 更快)。

编辑

圆圈的数量通常在 100 个左右，重叠的情况不会经常发生。

这里是一些上下文:矩形是游戏中的战场。单位的移动是小步完成的，我正在尝试检测单位之间的碰撞。

Answer 1

鉴于对问题陈述的新解释，我会推荐一种不同的方法。

在战场上覆盖一个正方形网格，网格步长等于一个圆的直径。每个圆圈最多可以重叠四个单元格。在每个单元格中，保留重叠圆圈的列表(并在每次移动时更新它)。

检测潜在的碰撞现在需要每个圆进行大约四次单元/圆测试，即接近线性时间。