mar*_*nev 6 algorithm computational-geometry data-structures
我有一个矩形区域，其中有半径相等的圆。我想找到哪些圆与其他圆重叠（输出是重叠圆的 2 元素集的列表）。
我知道如何检查两个圆是否重叠（它们的中心之间的距离小于直径）。我可以对每对圆圈执行此检查，但我想知道是否有更好的算法（比 更快O(n^2)）。
编辑
圆圈的数量通常在100个左右，并且不会经常发生重叠。
以下是一些背景信息：矩形是游戏中的战场。单位的移动是小步完成的，我正在尝试检测单位之间的碰撞。
小智 2
鉴于问题陈述的新解释，我会推荐一种不同的方法。
在战场上覆盖一个方形网格，网格步长等于一个圆的直径。每个圆圈最多可以重叠四个单元格。在每个单元格中，保留重叠圆圈的列表（并在每次移动时更新它）。
检测潜在的碰撞现在每个圆需要大约四个单元/圆测试，即接近线性时间。