编辑“︁线段与直线（计算几何算法）”︁（章节）

== 相交检测 ==
=== 直线相交 ===
两条直线 <math>L_1: A_1x + B_1y + C_1 = 0</math> 和 <math>L_2: A_2x + B_2y + C_2 = 0</math> 的交点可通过解线性方程组得到：
<math>
\begin{cases}
A_1x + B_1y = -C_1 \\
A_2x + B_2y = -C_2
\end{cases}
</math>

=== 线段相交 ===
判断两条线段是否相交，常用'''跨立实验'''（基于向量叉积）：
1. 检查两条线段的外接矩形是否重叠（快速排除不相交情况）。
2. 计算叉积判断是否跨立。

算法实现（Python）：
<syntaxhighlight lang="python">
def cross_product(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def segments_intersect(p1, p2, p3, p4):
    # 快速排斥实验
    if max(p1[0], p2[0]) < min(p3[0], p4[0]) or \
       max(p3[0], p4[0]) < min(p1[0], p2[0]) or \
       max(p1[1], p2[1]) < min(p3[1], p4[1]) or \
       max(p3[1], p4[1]) < min(p1[1], p2[1]):
        return False

    # 跨立实验
    cp1 = cross_product(p3, p4, p1)
    cp2 = cross_product(p3, p4, p2)
    cp3 = cross_product(p1, p2, p3)
    cp4 = cross_product(p1, p2, p4)

    if ((cp1 * cp2 < 0) and (cp3 * cp4 < 0)):
        return True
    # 处理共线情况
    return False

# 示例
p1, p2 = (0, 0), (2, 2)
p3, p4 = (0, 2), (2, 0)
print(segments_intersect(p1, p2, p3, p4))  # 输出: True
</syntaxhighlight>