如何系统查找离散网格中与指定线段相交的单元格？

咱先把核心逻辑说透：不管你的端点在哪、网格分辨率怎么变，要解决这个问题，关键就是精准找出线段穿过的每一个网格单元格，再从中筛选出值为True的那些。这里给你一套系统性的实现方案，绝对靠谱。

具体操作步骤 #

1. 先把坐标映射到网格索引 #

首先得把线段的起点(x_start, y_start)和终点(x_end, y_end)，转换成网格对应的索引位置。这里用numpy的searchsorted函数就能精准搞定，不管坐标落在网格区间内、边缘还是顶点，都能正确找到对应的单元格索引：

import numpy as np

# 示例里的网格离散化数组
xd = np.arange(0, 20, 1)
yd = np.arange(0, 10, 1)

# 把坐标转成网格索引
i_start = np.searchsorted(xd, x_start, side='right') - 1
i_end = np.searchsorted(xd, x_end, side='right') - 1
j_start = np.searchsorted(yd, y_start, side='right') - 1
j_end = np.searchsorted(yd, y_end, side='right') - 1

2. 遍历线段经过的所有单元格 #

这里用类似**数字微分分析（DDA）**的步进思路，沿着线段的方向一步步走，每进入一个新的单元格就记录下来。这个方法不会漏掉任何线段穿过的单元格，也不会重复记录：

def get_line_intersecting_cells(xd, yd, x_start, y_start, x_end, y_end):
    # 第一步：转换为网格索引
    i0 = np.searchsorted(xd, x_start, side='right') - 1
    j0 = np.searchsorted(yd, y_start, side='right') - 1
    i1 = np.searchsorted(xd, x_end, side='right') - 1
    j1 = np.searchsorted(yd, y_end, side='right') - 1

    # 初始化当前所在的单元格索引
    current_i, current_j = i0, j0
    # 用集合存单元格，避免重复
    cells = set()
    cells.add((current_i, current_j))

    # 计算移动方向（左/右/不动，上/下/不动）
    di = np.sign(i1 - i0) if i1 != i0 else 0
    dj = np.sign(j1 - j0) if j1 != j0 else 0

    # 线段的参数方程：x = x0 + t*(x1-x0), y = y0 + t*(y1-y0)，t∈[0,1]
    dx = x_end - x_start
    dy = y_end - y_start

    # 特殊情况：线段是一个点，直接返回当前单元格
    if dx == 0 and dy == 0:
        return list(cells)

    # 计算第一次跨x网格和跨y网格的t值
    t_x_step = (xd[current_i + di + 1] - x_start) / dx if di != 0 else np.inf
    t_y_step = (yd[current_j + dj + 1] - y_start) / dy if dj != 0 else np.inf

    t_current = 0.0
    while t_current <= 1.0:
        # 判断先跨x网格还是y网格，处理刚好经过网格顶点的情况
        if abs(t_x_step - t_y_step) < 1e-9:
            current_i += di
            current_j += dj
            cells.add((current_i, current_j))
            # 更新下一次跨网格的t值
            if di != 0 and (current_i + di + 1) < len(xd):
                t_x_step = (xd[current_i + di + 1] - x_start) / dx
            else:
                t_x_step = np.inf
            if dj != 0 and (current_j + dj + 1) < len(yd):
                t_y_step = (yd[current_j + dj + 1] - y_start) / dy
            else:
                t_y_step = np.inf
        elif t_x_step < t_y_step:
            current_i += di
            cells.add((current_i, current_j))
            # 更新下一次跨x网格的t值
            if di != 0 and (current_i + di + 1) < len(xd):
                t_x_step = (xd[current_i + di + 1] - x_start) / dx
            else:
                t_x_step = np.inf
        else:
            current_j += dj
            cells.add((current_i, current_j))
            # 更新下一次跨y网格的t值
            if dj != 0 and (current_j + dj + 1) < len(yd):
                t_y_step = (yd[current_j + dj + 1] - y_start) / dy
            else:
                t_y_step = np.inf
        t_current = min(t_x_step, t_y_step)

    return list(cells)

3. 筛选出值为True的单元格 #

拿到线段经过的所有单元格索引后，直接遍历检查你的grid数组就行：

# 假设你的grid已经初始化并设置了部分True值
x_start = 2.7
x_end = 4.9
y_start = 1.5
y_end = 5.7

# 获取线段穿过的所有单元格
intersecting_cells = get_line_intersecting_cells(xd, yd, x_start, y_start, x_end, y_end)
# 筛选出其中值为True的单元格
true_intersecting_cells = [(i, j) for i, j in intersecting_cells if grid[i, j]]

print("和线段相交的True单元格索引：", true_intersecting_cells)

为啥这个方法靠谱？ #

• 适配任意端点位置：不管端点在单元格内部、边缘还是顶点，searchsorted都能正确映射索引，步进遍历也能自动处理所有情况。
• 适配任意网格分辨率：只要xd和yd是单调递增的离散数组，不管步长是1还是其他数值，算法都能正常工作。
• 无遗漏无冗余：通过参数t的精准计算，每次只移动到相邻的单元格，不会跳过任何线段穿过的网格，也不会重复记录同一个单元格。

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