查找重叠的圆圈
Find overlapping circles
我有一个矩形区域，里面有半径相等的圆。我想找出哪些圆圈与其他圆圈重叠（输出是重叠圆圈的 2 元素集列表）。
我知道如何检查两个圆是否重叠（圆心之间的距离小于直径）。我可以对每一对圆圈执行此检查，但我想知道是否有更好的算法（比 O(n^2) 更快）。
编辑
圈数通常在100个左右，重叠的情况不会经常发生。
这里是一些上下文：
矩形是游戏中的战场。单位的移动是小步完成的，我正在尝试检测单位之间的碰撞。
对于一个简单的解决方案，将中心插入二维树中，并围绕每个中心执行圆形范围查询，查询半径为 2R。在良好的条件下，这可以是 O(N Log(N)).
或者，只需对X上的中心进行排序，然后依次尝试所有圆：通过二分法搜索，定位横坐标Xc并扫描到Xc-2R和Xc+2R，然后检查二维距离。
二分搜索的成本将为 O(N Log(N))。如果圆圈均匀分布在 S 边的正方形中，则宽度为 4R 的条带包含 4RN/S 个圆圈，因此总比较成本为 4RN²/S。如果 S 很大，这是一个很好的表现（认为对于正方形中 N 个紧密排列的圆圈，S~2R√N，因此 2N√N 次比较）。
直接答案：一般来说，你不可能比 O(n^2) 更好，因为圆圈可能全部重叠，所以你必须生成 n^2 个答案。
如果你更具体，你可能会得到更好的答案。例如，如果您真正想做的是在 2D 模拟中找到边界球体，您可以从以下事实中获益：实体仅在帧之间移动那么远，如果圆圈稀疏，则与它们紧密堆积时不同，等等.所以让我们更多地了解它的全部内容。
编辑：您编辑了您的问题 - 您确实在寻找二维模拟中的碰撞检测。如果您查看 https://en.wikipedia.org/wiki/Collision_detection ，他们会针对您的情况指出几种算法。
我喜欢那个页面上详细的那个，你保留了每个轴的边界间隔列表（“2D”中的 2 个）并且只需要 "work hard" 当这些边界间隔（根据定义它们本身一维）变化（即有"overlap state"）。对于行为良好的情况，这会删除 O(n²)。他们没有给出复杂性的估计，但由于它基本上归结为排序，对我来说它看起来或多或少 O(n logn)，当帧之间只有最小的变化时看起来更少。
鉴于对问题陈述的新解释，我会推荐一种不同的方法。
在战场上叠加一个方形网格，网格步长等于一个圆的直径。每个圆圈最多可以重叠四个单元格。在每个单元格中，保留重叠圆圈的列表（并在每次移动时更新它）。
检测潜在的碰撞现在每圈需要大约四次 cell/circle 测试，即接近线性时间。
我有一个矩形区域，里面有半径相等的圆。我想找出哪些圆圈与其他圆圈重叠（输出是重叠圆圈的 2 元素集列表）。
我知道如何检查两个圆是否重叠（圆心之间的距离小于直径）。我可以对每一对圆圈执行此检查，但我想知道是否有更好的算法（比 O(n^2) 更快）。
编辑
圈数通常在100个左右，重叠的情况不会经常发生。
这里是一些上下文： 矩形是游戏中的战场。单位的移动是小步完成的，我正在尝试检测单位之间的碰撞。
对于一个简单的解决方案，将中心插入二维树中，并围绕每个中心执行圆形范围查询，查询半径为 2R。在良好的条件下，这可以是 O(N Log(N)).
或者，只需对X上的中心进行排序，然后依次尝试所有圆：通过二分法搜索，定位横坐标Xc并扫描到Xc-2R和Xc+2R，然后检查二维距离。
二分搜索的成本将为 O(N Log(N))。如果圆圈均匀分布在 S 边的正方形中，则宽度为 4R 的条带包含 4RN/S 个圆圈，因此总比较成本为 4RN²/S。如果 S 很大，这是一个很好的表现（认为对于正方形中 N 个紧密排列的圆圈，S~2R√N，因此 2N√N 次比较）。
直接答案：一般来说，你不可能比 O(n^2) 更好，因为圆圈可能全部重叠，所以你必须生成 n^2 个答案。
如果你更具体，你可能会得到更好的答案。例如，如果您真正想做的是在 2D 模拟中找到边界球体，您可以从以下事实中获益：实体仅在帧之间移动那么远，如果圆圈稀疏，则与它们紧密堆积时不同，等等.所以让我们更多地了解它的全部内容。
编辑：您编辑了您的问题 - 您确实在寻找二维模拟中的碰撞检测。如果您查看 https://en.wikipedia.org/wiki/Collision_detection ，他们会针对您的情况指出几种算法。
我喜欢那个页面上详细的那个，你保留了每个轴的边界间隔列表（“2D”中的 2 个）并且只需要 "work hard" 当这些边界间隔（根据定义它们本身一维）变化（即有"overlap state"）。对于行为良好的情况，这会删除 O(n²)。他们没有给出复杂性的估计，但由于它基本上归结为排序，对我来说它看起来或多或少 O(n logn)，当帧之间只有最小的变化时看起来更少。
鉴于对问题陈述的新解释，我会推荐一种不同的方法。
在战场上叠加一个方形网格，网格步长等于一个圆的直径。每个圆圈最多可以重叠四个单元格。在每个单元格中，保留重叠圆圈的列表（并在每次移动时更新它）。
检测潜在的碰撞现在每圈需要大约四次 cell/circle 测试，即接近线性时间。