Python 线段相交判断算法优化：解决垂直线段判断问题

本文介绍了 Python 线段相交判断算法的优化方法，重点解决当两个线段的直线是垂直时判断错误的问题。

原始代码:

def intersect(edge1, edge2):
    # 计算边的斜率和截距
    x1, y1 = edge1[0]
    x2, y2 = edge1[1]
    if x2-x1==0:  # 检查分母是否为零
        m1 = float('inf')  # 返回一个大数或NaN
    else:
        m1 = (y2 - y1) / (x2 - x1)
    b1 = y1 - m1 * x1  #截距
    if math.isnan(b1):
        b1 = x1
        
    x3, y3 = edge2[0]
    x4, y4 = edge2[1]
    if x4-x3==0:  # 检查分母是否为零
        m2 = float('inf')  # 返回一个大数或NaN
    else:
        m2 = (y4 - y3) / (x4 - x3)
    b2 = y3 - m2 * x3
    if math.isnan(b2):
        b2 = x3
    
    # 检查是否有交点
    if m1 == m2:  # 检查斜率是否相等
        if b1 != b2:
            return False
        else:  #是否重叠
            if x1 <= x3 <= x2 or x2 <= x3 <= x1 or x3 <= x1 <= x4 or x4 <= x1 <= x3:
                return True
            else:
                return False
    else:
        print(m1,m2,b1,b2)
        x = (b2 - b1) / (m1 - m2)  #交点
        print(x)
        if x < min(x1, x2) or x > max(x1, x2) or x < min(x3, x4) or x > max(x3, x4):
            return False
        else:
            return True

问题分析:

当两个线段的直线是垂直的时候，斜率为无穷大，会进入第一个if语句块。这时需要判断两个线段是否有重叠部分，但是当前的判断条件只判断了x坐标是否有重叠，没有判断y坐标是否有重叠。

解决方案:

修改判断条件，将x坐标和y坐标的判断条件合并起来，如下所示：

def intersect(edge1, edge2):
    # 计算边的斜率和截距
    x1, y1 = edge1[0]
    x2, y2 = edge1[1]
    if x2-x1==0:  # 检查分母是否为零
        m1 = float('inf')  # 返回一个大数或NaN
    else:
        m1 = (y2 - y1) / (x2 - x1)
    b1 = y1 - m1 * x1  #截距
    if math.isnan(b1):
        b1 = x1
        
    x3, y3 = edge2[0]
    x4, y4 = edge2[1]
    if x4-x3==0:  # 检查分母是否为零
        m2 = float('inf')  # 返回一个大数或NaN
    else:
        m2 = (y4 - y3) / (x4 - x3)
    b2 = y3 - m2 * x3
    if math.isnan(b2):
        b2 = x3
    
    # 检查是否有交点
    if x1 == x2 and x3 == x4:  # 两个线段都垂直x轴
        if x1 != x3:  # 不在同一条直线上
            return False
        else:  # 在同一条直线上
            if y1 <= y3 <= y2 or y2 <= y3 <= y1 or y3 <= y1 <= y4 or y4 <= y1 <= y3:
                return True
            else:
                return False
    elif x1 == x2:  # 第一个线段垂直x轴
        y = m2 * x1 + b2
        if y < min(y1, y2) or y > max(y1, y2) or y < min(y3, y4) or y > max(y3, y4):
            return False
        else:
            return True
    elif x3 == x4:  # 第二个线段垂直x轴
        y = m1 * x3 + b1
        if y < min(y1, y2) or y > max(y1, y2) or y < min(y3, y4) or y > max(y3, y4):
            return False
        else:
            return True
    else:  # 两个线段都不垂直x轴
        x = (b2 - b1) / (m1 - m2)
        if x < min(x1, x2) or x > max(x1, x2) or x < min(x3, x4) or x > max(x3, x4):
            return False
        else:
            return True

这样修改后，即使两个线段的直线是垂直的，也能够正确判断它们是否相交。