Python实现两条线段相交计算 覆盖共线交点及重叠特殊场景

常规实现线段相交判断的方案通常只处理了非共线的相交场景，对共线端点相交、共线重叠两类特殊场景的支持普遍不完善，以下是两类场景的处理逻辑和实现：

场景1：共线线段端点相交 #

给定线段：

a = [(0, 2), (2, 4)]
b = [(-2, 0), (0, 2)]

两条线段斜率相同完全共线，仅在端点(0, 2)处相交，处理逻辑如下：

1. 先通过叉积判断两条线段是否共线：取线段a的向量、线段a端点到线段b端点的向量做叉积，若叉积为0则说明三点共线，依次验证两条线段的所有端点都满足共线条件，即可确认两条线段整体共线
2. 共线前提下，判断某条线段的端点是否落在另一条线段的坐标范围内：即端点的x值介于另一条线段两个端点x的最大值和最小值之间，y值同理，同时满足则说明该端点是交点
   本场景中(0, 2)同时属于两条线段的端点，且满足坐标范围要求，即为唯一交点。

场景2：共线线段部分/完全重叠 #

给定线段：

a = [(0, 2), (2, 4)]
b = [(-2, 0), (1, 3)]

两条线段共线且存在一段重叠区域，处理逻辑如下：

1. 确认两条线段共线后，将线段上的点转换为参数化表示：例如线段a可表示为(a[0][0] + t*(a[1][0]-a[0][0]), a[0][1] + t*(a[1][1]-a[0][1]))，其中t∈[0,1]
2. 将另一条线段的两个端点代入上述参数化公式，计算对应的t值，再结合t的取值范围[0,1]得到两个线段参数的交集区间
3. 若交集区间为空则说明无交点；若交集区间左右边界相等则为单点交点；若区间长度大于0则说明存在重叠线段，区间左右边界对应的两个点就是重叠区域的两个端点
   本场景中参数交集为t∈[0, 0.5]，对应的重叠区域为线段[(0,2), (1,3)]。

完整参考实现 #

def cross(o, a, b):
    # 计算叉积 (a-o) × (b-o)
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def point_on_segment(p, a, b):
    # 判断点p是否在线段ab上
    if cross(a, b, p) != 0:
        return False
    return (min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and
            min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))

def segment_intersection(a, b):
    a1, a2 = a
    b1, b2 = b
    # 先判断非共线相交
    c1 = cross(a1, a2, b1)
    c2 = cross(a1, a2, b2)
    c3 = cross(b1, b2, a1)
    c4 = cross(b1, b2, a2)
    
    if (c1 * c2 < 0) and (c3 * c4 < 0):
        # 计算非共线交点
        denom = (a1[0]-a2[0])*(b1[1]-b2[1]) - (a1[1]-a2[1])*(b1[0]-b2[0])
        t_num = (a1[0]-b1[0])*(b1[1]-b2[1]) - (a1[1]-b1[1])*(b1[0]-b2[0])
        t = t_num / denom
        x = a1[0] + t*(a2[0]-a1[0])
        y = a1[1] + t*(a2[1]-a1[1])
        return [(round(x,9), round(y,9))]
    
    # 处理共线场景
    if c1 == 0 and c2 == 0 and c3 == 0 and c4 == 0:
        # 参数化线段a
        dx = a2[0] - a1[0]
        dy = a2[1] - a1[1]
        def get_t(p):
            if dx != 0:
                return (p[0] - a1[0])/dx
            elif dy !=0:
                return (p[1] - a1[1])/dy
            else:
                return 0 if p == a1 else 1
        t_b1 = get_t(b1)
        t_b2 = get_t(b2)
        t_min = max(0, min(t_b1, t_b2))
        t_max = min(1, max(t_b1, t_b2))
        if t_min > t_max:
            return []
        elif abs(t_min - t_max) < 1e-9:
            x = a1[0] + t_min * dx
            y = a1[1] + t_min * dy
            return [(round(x,9), round(y,9))]
        else:
            p1 = (round(a1[0] + t_min*dx,9), round(a1[1] + t_min*dy,9))
            p2 = (round(a1[0] + t_max*dx,9), round(a1[1] + t_max*dy,9))
            return [p1, p2]
    
    # 处理端点相交的非重叠共线场景
    res = []
    if point_on_segment(b1, a1, a2):
        res.append(b1)
    if point_on_segment(b2, a1, a2):
        res.append(b2)
    if point_on_segment(a1, b1, b2):
        res.append(a1)
    if point_on_segment(a2, b1, b2):
        res.append(a2)
    # 去重
    unique_res = []
    seen = set()
    for p in res:
        key = (round(p[0],9), round(p[1],9))
        if key not in seen:
            seen.add(key)
            unique_res.append(key)
    return unique_res

# 测试场景1
a = [(0, 2), (2, 4)]
b = [(-2, 0), (0, 2)]
print(segment_intersection(a,b)) # 输出 [(0.0, 2.0)]

# 测试场景2
a = [(0, 2), (2, 4)]
b = [(-2, 0), (1, 3)]
print(segment_intersection(a,b)) # 输出 [(0.0, 2.0), (1.0, 3.0)]

内容的提问来源于stack exchange，提问作者Javad.Rad