线段与直线（计算几何算法）

介绍[编辑 | 编辑源代码]

线段和直线是计算几何中的基础概念，广泛应用于计算机图形学、地理信息系统（GIS）、游戏开发和机器人路径规划等领域。理解它们的数学表示、相交检测及相关算法对解决实际问题至关重要。

直线是无限延伸的一维几何对象，由线性方程 $a x + b y + c = 0$ 或斜截式 $y = k x + b$ 表示。
线段是直线的有限部分，由两个端点 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$ 定义。

数学表示[编辑 | 编辑源代码]

直线方程[编辑 | 编辑源代码]

直线可以通过以下形式表示：

一般式： $A x + B y + C = 0$
斜截式： $y = k x + b$ （斜率 $k$ ，截距 $b$ ）
参数式： ${\begin{cases} x = x_{0} + t \cdot d x \\ y = y_{0} + t \cdot d y \end{cases}$ （ $t \in ℝ$ ）

线段表示[编辑 | 编辑源代码]

线段由两个端点定义：

起点 $P_{1} (x_{1}, y_{1})$ 和终点 $P_{2} (x_{2}, y_{2})$
参数方程： ${\begin{cases} x = x_{1} + t \cdot (x_{2} - x_{1}) \\ y = y_{1} + t \cdot (y_{2} - y_{1}) \end{cases}$ （ $t \in [0, 1]$ ）

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

直线相交[编辑 | 编辑源代码]

两条直线 $L_{1} : A_{1} x + B_{1} y + C_{1} = 0$ 和 $L_{2} : A_{2} x + B_{2} y + C_{2} = 0$ 的交点可通过解线性方程组得到： ${\begin{cases} A_{1} x + B_{1} y = - C_{1} \\ A_{2} x + B_{2} y = - C_{2} \end{cases}$

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

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

算法实现（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

距离计算[编辑 | 编辑源代码]

点到直线距离[编辑 | 编辑源代码]

点 $(x_{0}, y_{0})$ 到直线 $A x + B y + C = 0$ 的距离： $d = \frac{| A x_{0} + B y_{0} + C |}{\sqrt{A^{2} + B^{2}}}$

点到线段距离[编辑 | 编辑源代码]

需要判断点的投影是否在线段上： 1. 若投影在线段上，距离同点到直线距离。 2. 否则，取到两端点的最小距离。

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

游戏开发中的碰撞检测[编辑 | 编辑源代码]

在2D游戏中，判断子弹（线段）是否击中障碍物（多边形）时，需要检测子弹轨迹与多边形各边的相交情况。

地理信息系统（GIS）[编辑 | 编辑源代码]

道路（线段）与河流（线段）的交叉分析是GIS中的常见需求，通过线段相交算法可快速定位交叉点。

进阶主题[编辑 | 编辑源代码]

参数化表示与插值[编辑 | 编辑源代码]

线段的参数方程可用于线性插值：

def lerp(p1, p2, t):
    return (p1[0] + t * (p2[0] - p1[0]), p1[1] + t * (p2[1] - p1[1]))

# 在p1和p2之间30%的位置
print(lerp((0, 0), (10, 10), 0.3))  # 输出: (3.0, 3.0)

直线拟合[编辑 | 编辑源代码]

给定一组点，可通过最小二乘法拟合最佳直线： $\min \sum_{i = 1}^{n} (y_{i} - (k x_{i} + b))^{2}$

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

线段是直线的有限部分，直线是无限延伸的。
相交检测通过跨立实验和快速排斥实验实现。
距离计算需区分点和直线/线段的不同情况。
应用场景广泛，包括图形学、GIS和游戏开发等。

模板:Stub