线段相交检测[编辑 | 编辑源代码]

线段相交检测是计算几何中的基础算法，用于判断二维平面上的两条线段是否相交。该算法在计算机图形学、游戏开发、地理信息系统（GIS）和碰撞检测等领域有广泛应用。

基本概念[编辑 | 编辑源代码]

在二维平面中，线段由两个端点定义。给定两条线段 $A B$ 和 $C D$ ，我们需要判断它们是否相交。相交的定义是两条线段有且仅有一个公共点，且该点不是端点。

数学基础[编辑 | 编辑源代码]

判断线段相交的核心思想是利用向量叉积（Cross Product）来确定点的相对位置关系。叉积可以帮助我们判断一个点是在线段的左侧还是右侧。

对于向量 $\vec{u} = (u_{x}, u_{y})$ 和 $\vec{v} = (v_{x}, v_{y})$ ，其叉积定义为： $\vec{u} \times \vec{v} = u_{x} v_{y} - u_{y} v_{x}$

算法步骤[编辑 | 编辑源代码]

线段相交检测可以通过以下步骤实现：

1. 快速排斥实验：先检查两条线段的外接矩形是否相交。如果不相交，则线段一定不相交。 2. 跨立实验：利用叉积判断两条线段是否互相跨立。

快速排斥实验[编辑 | 编辑源代码]

两条线段 $A B$ 和 $C D$ 的外接矩形分别为：

$A B$ 的矩形范围： $[\min (A_{x}, B_{x}), \max (A_{x}, B_{x})] \times [\min (A_{y}, B_{y}), \max (A_{y}, B_{y})]$
$C D$ 的矩形范围： $[\min (C_{x}, D_{x}), \max (C_{x}, D_{x})] \times [\min (C_{y}, D_{y}), \max (C_{y}, D_{y})]$

如果这两个矩形不相交，则线段一定不相交。

如果两条线段的外接矩形相交，则进一步进行跨立实验： 1. 计算 $(C - A) \times (B - A)$ 和 $(D - A) \times (B - A)$ ，判断点 $C$ 和 $D$ 是否在 $A B$ 的两侧。 2. 计算 $(A - C) \times (D - C)$ 和 $(B - C) \times (D - C)$ ，判断点 $A$ 和 $B$ 是否在 $C D$ 的两侧。

如果两个条件均满足，则线段相交。

代码实现[编辑 | 编辑源代码]

以下是 Python 实现线段相交检测的代码示例：

def cross_product(a, b, c):
    """计算向量 (b - a) 和 (c - a) 的叉积"""
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def segments_intersect(segment1, segment2):
    """判断两条线段是否相交"""
    A, B = segment1
    C, D = segment2

    # 快速排斥实验
    if (max(A[0], B[0]) < min(C[0], D[0]) or
        max(C[0], D[0]) < min(A[0], B[0]) or
        max(A[1], B[1]) < min(C[1], D[1]) or
        max(C[1], D[1]) < min(A[1], B[1])):
        return False

    # 跨立实验
    cross1 = cross_product(A, B, C)
    cross2 = cross_product(A, B, D)
    cross3 = cross_product(C, D, A)
    cross4 = cross_product(C, D, B)

    # 判断是否跨立
    if ((cross1 * cross2 < 0) and (cross3 * cross4 < 0)):
        return True

    # 处理共线或端点相交的情况
    if cross1 == 0 and on_segment(A, B, C):
        return True
    if cross2 == 0 and on_segment(A, B, D):
        return True
    if cross3 == 0 and on_segment(C, D, A):
        return True
    if cross4 == 0 and on_segment(C, D, B):
        return True

    return False

def on_segment(a, b, c):
    """判断点 c 是否在线段 ab 上"""
    return (min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and
            min(a[1], b[1]) <= c[1] <= max(a[1], b[1]))

输入输出示例[编辑 | 编辑源代码]

输入：

segment1 = ((1, 1), (4, 4))
segment2 = ((1, 4), (4, 1))
print(segments_intersect(segment1, segment2))  # 输出 True

输出：

True

可视化示例[编辑 | 编辑源代码]

以下是一个简单的线段相交示例：

实际应用[编辑 | 编辑源代码]

线段相交检测在以下场景中有广泛应用： 1. 计算机图形学：判断多边形是否自相交。 2. 游戏开发：检测子弹是否击中障碍物。 3. 机器人路径规划：避免机器人与障碍物碰撞。 4. 地理信息系统：判断道路或河流是否交叉。

特殊情况处理[编辑 | 编辑源代码]

1. 共线线段：如果两条线段共线，需要额外判断是否有重叠部分。 2. 端点相交：如果两条线段仅在端点相交，算法也能正确检测。

性能优化[编辑 | 编辑源代码]

对于需要检测大量线段相交的场景（如碰撞检测），可以使用空间分割技术（如四叉树或网格）来减少检测次数。

总结[编辑 | 编辑源代码]

线段相交检测是计算几何中的基础问题，通过向量叉积和快速排斥实验可以高效解决。理解该算法有助于进一步学习更复杂的几何算法。