给定N×N网格与半径R的圆形，查找被圆形占据的网格块

我们默认前提为：每个网格是边长为1的正方形，编号可根据实际规则调整，核心判断逻辑通用。 #

求解步骤 #

1. 缩小遍历范围 #

不需要遍历全部N×N网格，仅需要遍历圆心周围边长为2R的正方形范围内的网格即可，可大幅降低运算量：

• x轴遍历区间：[max(0, floor(x_c - R)), min(N-1, ceil(x_c + R))]
• y轴遍历区间：[max(0, floor(y_c - R)), min(N-1, ceil(y_c + R))]

2. 单网格覆盖判断 #

判断标准为：网格到圆心的最短距离小于等于半径R，为了避免开根号损耗性能，可直接用距离平方和R的平方比较：

1. 若圆心x坐标落在网格的x区间[x_grid_min, x_grid_max]内，x方向距离为0；若圆心x小于x_grid_min，x方向距离为x_grid_min - x_c；若圆心x大于x_grid_max，x方向距离为x_c - x_grid_max
2. y方向距离计算逻辑和x方向一致
3. 若dx² + dy² ≤ R²，则该网格被圆占据

只要网格和圆存在交集就算被占据，不需要整个网格都落在圆内，该逻辑和你给出的示例完全匹配。

3. 编号转换 #

将符合条件的网格按照你使用的编号规则转换为对应编号即可，你给出的示例中圆心刚好和1、2、5、6四个网格有交集，和预期输出一致。

Python代码示例 #

def get_covered_cells(N, R, x_c, y_c):
    res = []
    # 确定遍历边界
    x_start = max(0, int(x_c - R))
    x_end = min(N - 1, int(x_c + R) + 1)
    y_start = max(0, int(y_c - R))
    y_end = min(N - 1, int(y_c + R) + 1)
    R_square = R ** 2
    for x in range(x_start, x_end + 1):
        for y in range(y_start, y_end + 1):
            # 计算网格到圆心的最短距离平方
            dx = max(x - x_c, 0, x_c - (x + 1))
            dy = max(y - y_c, 0, y_c - (y + 1))
            if dx * dx + dy * dy <= R_square:
                # 此处按逐行从上到下、每行从左到右从1开始编号的规则转换，可根据你的规则调整
                cell_id = (N - 1 - y) * N + x + 1
                res.append(cell_id)
    return sorted(res)

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