已知同半径圆的位置列表，如何检测圆间碰撞？求最快实现方案

核心碰撞判断逻辑 #

因为所有圆半径相同（设为r），两个圆碰撞的充要条件是圆心间距 ≤ 2r。为了避免开根号的性能损耗，实际计算时会比较距离的平方与(2r)²的大小，即：

(x₁ - x₂)² + (y₁ - y₂)² ≤ (2r)²

这个计算完全用整数/浮点数运算，比开根号快得多。

暴力法的局限性 #

如果直接遍历所有圆对（双重循环），时间复杂度是O(n²)——当圆的数量超过几百个时，这个方法会变得极慢，完全不适合处理“大量圆”的场景。

最快实现：空间分区（网格划分） #

这是处理大规模空间物体碰撞的标准优化手段，核心思路是只让可能发生碰撞的圆互相检测，避免无意义的计算。具体步骤如下：

1. 构建网格

   • 将整个空间划分为边长为2r的正方形网格：两个圆如果能碰撞，它们的圆心必然落在同一个网格或相邻的8个网格里（超过这个范围的圆，圆心间距肯定大于2r，不可能碰撞）。
   • 用哈希表（比如Python的字典）存储每个网格对应的圆列表，键是网格的坐标(grid_x, grid_y)，计算方式为：

     grid_x = int(x // (2*r))
     grid_y = int(y // (2*r))
     

2. 碰撞检测流程

   • 遍历每个圆，找到它所在的网格及周围8个相邻网格（共9个）。
   • 只和这9个网格内的其他圆做距离平方的比较，判断是否碰撞。
   • 如果只需要判断“是否存在任意碰撞”，一旦找到碰撞就立即返回结果，无需继续遍历。

示例代码（Python） #

def has_any_circle_collision(circles, radius):
    grid = {}
    double_r = 2 * radius
    double_r_sq = double_r ** 2

    for (x, y) in circles:
        # 计算当前圆所在的网格坐标
        grid_x = int(x // double_r)
        grid_y = int(y // double_r)
        
        # 检查当前网格及相邻8个网格内的圆
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                current_grid_key = (grid_x + dx, grid_y + dy)
                if current_grid_key in grid:
                    # 和网格内已有的圆做碰撞检测
                    for (other_x, other_y) in grid[current_grid_key]:
                        dx_dist = x - other_x
                        dy_dist = y - other_y
                        dist_sq = dx_dist ** 2 + dy_dist ** 2
                        if dist_sq <= double_r_sq:
                            return True  # 找到碰撞，直接返回
        
        # 将当前圆加入对应网格
        grid_key = (grid_x, grid_y)
        if grid_key not in grid:
            grid[grid_key] = []
        grid[grid_key].append((x, y))
    
    return False  # 遍历完所有圆，未发现碰撞

额外优化点 #

• 提前计算double_r和double_r_sq，避免重复计算，节省CPU开销。
• 如果需要找出所有碰撞对，可以在检测时只和“已加入网格的圆”比较，避免重复检测同一对圆。
• 对于动态场景（圆位置会更新），无需重建整个网格，只需将移动的圆从旧网格移除，加入新网格即可。

内容的提问来源于stack exchange，提问作者Theos