网格中穿过所有标记方格的单一直线判定算法

核心思路 #

把每个标记的网格单元格转化为轴对齐的矩形边界框（比如单元格(i,j)对应左下角(i,j)、右上角(i+1,j+1)的矩形），问题就转化为：是否存在一条直线与所有这些矩形都相交。

具体判定步骤 #

1. 特殊情况处理：如果标记单元格数量≤2，直接返回存在（单个单元格随便画一条穿过它的直线；两个单元格可以用直线连接它们的任意两点）。
2. 生成候选直线：
   • 取前两个标记单元格的所有顶点（每个矩形有4个顶点），两两组合生成直线（跳过两点重合的情况）。
   • 之所以只取前两个单元格的顶点组合，是因为如果存在符合要求的直线，它必然同时穿过前两个单元格，而穿过矩形的直线必然经过矩形边界上的点（顶点足够覆盖所有可能的直线方向）。
3. 验证候选直线：对每条候选直线，检查它是否与所有剩余的标记单元格的矩形边界框相交。只要有一条直线满足条件，就说明存在这样的直线。

矩形与直线相交的判定方法 #

对于轴对齐矩形，直线与它相交的充要条件是：

• 直线经过矩形的顶点/边，或者
• 直线穿过矩形内部（即矩形四个顶点代入直线方程后，既有正值也有负值）

可以用以下方式实现：
将直线表示为 ax + by + c = 0，计算矩形四个顶点代入后的符号：

• 如果存在顶点代入后结果为0，说明直线经过该顶点/边，判定相交；
• 如果四个顶点的符号有正有负，说明直线穿过矩形内部，判定相交；
• 否则（符号全正或全负），直线在矩形一侧，不相交。

优化与伪代码实现 #

伪代码（Python风格） #

import math

def line_intersects_rect(line, rect):
    """判断直线ax+by+c=0是否与轴对齐矩形相交"""
    a, b, c = line
    # 矩形四个顶点坐标
    pts = [
        (rect[0], rect[1]), (rect[0], rect[3]),
        (rect[2], rect[1]), (rect[2], rect[3])
    ]
    signs = []
    for x, y in pts:
        val = a * x + b * y + c
        if val > 0:
            signs.append(1)
        elif val < 0:
            signs.append(-1)
        else:
            # 经过顶点或边，直接判定相交
            return True
    # 存在正负两种符号，说明穿过矩形
    return max(signs) != min(signs)

def has_common_line(gray_cells):
    """判断是否存在直线穿过所有标记单元格"""
    n = len(gray_cells)
    if n <= 2:
        return True
    
    # 提取前两个单元格的所有顶点
    rect1 = gray_cells[0]
    pts1 = [
        (rect1[0], rect1[1]), (rect1[0], rect1[3]),
        (rect1[2], rect1[1]), (rect1[2], rect1[3])
    ]
    rect2 = gray_cells[1]
    pts2 = [
        (rect2[0], rect2[1]), (rect2[0], rect2[3]),
        (rect2[2], rect2[1]), (rect2[2], rect2[3])
    ]
    
    # 生成候选直线并去重
    unique_lines = set()
    for x1, y1 in pts1:
        for x2, y2 in pts2:
            if (x1, y1) == (x2, y2):
                continue
            # 构造直线方程ax+by+c=0
            a = y2 - y1
            b = x1 - x2
            c = x2 * y1 - x1 * y2
            # 归一化避免重复直线
            gcd_val = abs(math.gcd(math.gcd(a, b), c)) if (a or b or c) else 1
            norm = (a//gcd_val, b//gcd_val, c//gcd_val)
            # 统一符号，确保相同方向的直线只保留一份
            first_non_zero = next((v for v in norm if v != 0), 0)
            if first_non_zero < 0:
                norm = (-norm[0], -norm[1], -norm[2])
            unique_lines.add(norm)
    
    # 验证每条候选直线
    for line in unique_lines:
        valid = True
        for rect in gray_cells[2:]:
            if not line_intersects_rect(line, rect):
                valid = False
                break
        if valid:
            return True
    return False

优化说明 #

• 直线去重：通过归一化直线方程的系数，避免重复检查相同方向的直线，提升效率。
• 大规模场景优化：如果标记单元格数量极大，可以先计算所有单元格的凸包——若存在符合要求的直线，它必然与凸包相交，可先通过凸包快速排除明显不可能的情况。

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