Python线段相交算法详解（小白也能学会的线段交叉检测方法）

什么是线段相交？

线段是由两个端点确定的一段直线。当两条线段在平面上有至少一个公共点时，我们就说它们“相交”。注意：这里包括端点重合或一条线段的端点落在另一条线段上的情况。

核心思路：使用向量叉积

判断线段是否相交的经典方法是基于计算几何中的“方向”概念，通过向量的叉积（Cross Product）来判断点相对于线段的位置关系。

我们定义一个函数 direction(p, q, r)，它返回三个点 p、q、r 的相对方向：

• 如果结果为 0：三点共线
• 如果结果 > 0：r 在向量 pq 的左侧（逆时针方向）
• 如果结果 < 0：r 在向量 pq 的右侧（顺时针方向）

完整代码实现

下面是一个完整的、可运行的 Python编程教程示例，包含详细注释：

def direction(p, q, r):    """    计算向量pq和pr的叉积    返回值：        0 —— 共线        正数 —— 逆时针（左侧）        负数 —— 顺时针（右侧）    """    return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])def on_segment(p, q, r):    """    判断点q是否在线段pr上（前提是已知三点共线）    """    if (        min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and        min(p[1], r[1]) <= q[1] <= max(p[1], r[1])    ):        return True    return Falsedef segments_intersect(seg1, seg2):    """    判断两条线段是否相交    参数：        seg1 = ((x1, y1), (x2, y2))        seg2 = ((x3, y3), (x4, y4))    返回：        True 或 False    """    p1, q1 = seg1    p2, q2 = seg2    d1 = direction(p1, q1, p2)    d2 = direction(p1, q1, q2)    d3 = direction(p2, q2, p1)    d4 = direction(p2, q2, q1)    # 一般情况：两个端点分别在另一条线段的两侧    if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and \       ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):        return True    # 特殊情况：共线且点在线段上    if d1 == 0 and on_segment(p1, p2, q1):        return True    if d2 == 0 and on_segment(p1, q2, q1):        return True    if d3 == 0 and on_segment(p2, p1, q2):        return True    if d4 == 0 and on_segment(p2, q1, q2):        return True    return False# 测试示例if __name__ == "__main__":    segment_a = ((0, 0), (4, 4))    segment_b = ((0, 4), (4, 0))    print(segments_intersect(segment_a, segment_b))  # 输出: True    segment_c = ((0, 0), (2, 2))    segment_d = ((3, 3), (5, 5))    print(segments_intersect(segment_c, segment_d))  # 输出: False

代码解析

1. direction() 函数通过叉积判断三点的方向关系。
2. on_segment() 用于处理共线情况，确保点确实落在该线段范围内。
3. segments_intersect() 是主函数，先判断一般相交情况（端点分居两侧），再处理边界情况（共线重叠）。

为什么这个算法可靠？

该算法基于线段交叉检测的经典几何原理，时间复杂度为 O(1)，无需浮点运算，避免了精度误差，适用于各种实际应用场景。

总结

通过本教程，你已经掌握了如何用 Python 实现高效的线段相交判断算法。无论你是学习Python线段相交算法的新手，还是需要在项目中应用计算几何知识的开发者，这套方法都值得收藏和复用。

动手试试吧！修改测试数据，观察不同线段组合的结果，加深理解。