如何利用Bresenham's line algorithm获取线段穿过的10×10网格单元

现有存储在变量matrix中的10×10网格，每个元素的数据结构为：

{"distance": distance, "topLeft": (xmin, ymin), "bottomRight": (xmax, ymax)}

已知224×224图像中的两点X1(x1,y1)、X2(x2,y2)，需找出包含X1到X2路径的所有网格单元（例如matrix[0][7]包含路径片段，应纳入结果）。

当前已实现Bresenham直线算法，代码如下：

def _find_crossed_cells(self, point0, point1, matrix) -> List(tuple):
        path_cells = []
        x0, y0 = point0
        x1, y1 = point1
        dx = abs(x1 - x0)
        sx = 1 if x0 < x1 else -1
        dy = abs(y1 - y0)
        sy = 1 if y0 < y1 else -1
        error = dx + dy

        while True:
            path_cells.append((x0, y0))
            if x0 == x1 and y0 == y1:
                break
            e2 = 2 * error

            if e2 >= dy:
                if x0 == x1:
                    break
                error = error + dy
                x0 = x0 + sx
            
            if e2 <= dx:
                if y0 == y1:
                    break
                error += dx
                y0 += sy
        
        return path_cells

该代码可生成图像上的像素坐标列表，但需转换为10×10网格的对应单元。此外，代码将在树莓派（RPi）的视频流中运行，需避免逐像素检查的算法。请说明如何调整现有代码以获取线段穿过的网格单元列表。

解决方案 #

核心思路 #

无需遍历所有像素，直接计算像素坐标对应的网格索引，同时在Bresenham算法的步进过程中，仅记录首次进入的网格单元，避免重复添加同一网格，大幅降低计算量。

具体调整步骤 #

1. 预计算网格尺寸：224×224图像划分为10×10网格，每个网格的宽度为224/10=22.4，高度同理。可直接通过像素坐标推导网格索引：

   • 像素(x,y)对应的网格行索引：row = int(y // 22.4)
   • 像素(x,y)对应的网格列索引：col = int(x // 22.4)
   • 需确保索引在0-9范围内，避免边界像素越界

2. 修改Bresenham算法逻辑：

   • 循环中实时计算当前像素对应的网格索引
   • 用变量跟踪当前所在网格，仅当网格变化时才添加到结果列表，避免冗余

修改后的代码 #

from typing import List, Tuple

def _find_crossed_cells(self, point0: Tuple[int, int], point1: Tuple[int, int], matrix) -> List[Tuple[int, int]]:
    path_cells = []
    x0, y0 = point0
    x1, y1 = point1
    dx = abs(x1 - x0)
    sx = 1 if x0 < x1 else -1
    dy = abs(y1 - y0)
    sy = 1 if y0 < y1 else -1
    error = dx + dy

    # 预计算网格尺寸
    grid_size = 224 / 10
    # 跟踪当前所在网格，避免重复添加
    current_grid = None

    while True:
        # 计算当前像素对应的网格索引（行，列）
        row = int(y0 // grid_size)
        col = int(x0 // grid_size)
        # 确保索引在0-9的合法范围内
        row = max(0, min(9, row))
        col = max(0, min(9, col))
        grid_idx = (row, col)

        if grid_idx != current_grid:
            path_cells.append(grid_idx)
            current_grid = grid_idx

        # 到达终点则退出循环
        if x0 == x1 and y0 == y1:
            break
        e2 = 2 * error

        if e2 >= dy:
            if x0 == x1:
                break
            error += dy
            x0 += sx
        
        if e2 <= dx:
            if y0 == y1:
                break
            error += dx
            y0 += sy
    
    return path_cells

优化说明 #

• 实时计算网格索引，避免了先生成所有像素再批量转换的冗余操作
• 通过current_grid去重，确保每个网格仅被记录一次，减少结果列表的无效数据
• 预计算网格尺寸，避免循环内重复计算除法，降低CPU负载，适配树莓派视频流的实时处理需求

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