如何无需两两测试判断一组圆中哪些圆与其他圆相交？

当然可以！完全不用做O(n²)的暴力两两测试，我们可以通过空间索引/划分策略大幅减少需要检查的圆对数量，尤其当圆的数量较多（比如你说的100个）时，性能提升会非常明显。

1. 网格划分（Grid Partitioning） #

这是最容易实现的方法，思路很直观：

• 先把整个空间切成大小统一的网格单元格，单元格的边长建议设为所有圆里的最大直径（或者稍大一点）。这样一来，只有在同一个单元格或者相邻单元格里的圆才有可能相交，隔得远的单元格里的圆直接可以排除。
• 具体步骤：
  • 遍历所有圆，把每个圆映射到它覆盖的所有网格单元格里（毕竟圆可能跨好几个单元格）
  • 只对同一个单元格或相邻单元格内的圆进行相交测试
• 优势：实现简单，对均匀分布的圆效果极佳，能把复杂度降到接近O(n)

2. 四叉树/八叉树（Quadtree/Octree） #

如果是2D平面的圆用四叉树，带z轴的3D场景用八叉树，属于递归式的空间划分：

• 思路是把空间递归拆分成4个（四叉树）或8个（八叉树）子区域，每个区域节点存储该范围内的圆；当一个节点里的圆数量超过设定的阈值时，就继续拆分这个节点。
• 检测时，每个圆只需要和它所在节点以及相邻节点里的圆做相交判断
• 优势：适合圆分布不均匀的场景，空间利用率更高，还能动态处理圆的添加或删除

3. R树（R-Tree） #

这个方法更偏向工业级的空间检索，常用在GIS或数据库系统里：

• 先给每个圆生成一个最小包围矩形（MBR），R树会把空间上邻近的MBR分组，形成层级结构。
• 检测时，只需要和那些MBR有重叠的分组里的圆做相交测试——毕竟如果两个圆的包围矩形都不重叠，那圆本身肯定也不相交
• 优势：处理大量空间数据时效率极高，非常适合范围查询类的场景

额外小优化：快速排斥判断 #

就算最后要做圆的相交测试，也可以先做一步快速过滤：
计算两个圆圆心的距离平方，和（r1+r2）的平方比较（不用开根号，减少计算开销）：

• 如果距离平方 > (r1+r2)²：直接判定不相交
• 如果距离平方 < |r1-r2|²：判定为内含（如果你的场景里内含算相交就保留，不算就排除）
• 只有中间的情况才需要进一步确认

总结 #

这些方法的核心都是缩小需要检测的候选圆对范围，把原本O(n²)的暴力复杂度降到O(n log n)甚至更低。比如100个圆用网格划分的话，可能只需要几百次测试，远少于4950次的暴力计算。

内容的提问来源于stack exchange，提问作者G. Pro