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

{{DISPLAYTITLE:线段与直线（计算几何算法）}}

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

* '''直线'''是无限延伸的一维几何对象，由线性方程 <math>ax + by + c = 0</math> 或斜截式 <math>y = kx + b</math> 表示。
* '''线段'''是直线的有限部分，由两个端点 <math>(x_1, y_1)</math> 和 <math>(x_2, y_2)</math> 定义。

== 数学表示 ==
=== 直线方程 ===
直线可以通过以下形式表示：
* '''一般式'''：<math>Ax + By + C = 0</math>
* '''斜截式'''：<math>y = kx + b</math>（斜率 <math>k</math>，截距 <math>b</math>）
* '''参数式'''：<math>\begin{cases} x = x_0 + t \cdot dx \\ y = y_0 + t \cdot dy \end{cases}</math>（<math>t \in \mathbb{R}</math>）

=== 线段表示 ===
线段由两个端点定义：
* 起点 <math>P_1(x_1, y_1)</math> 和终点 <math>P_2(x_2, y_2)</math>
* 参数方程：<math>\begin{cases} x = x_1 + t \cdot (x_2 - x_1) \\ y = y_1 + t \cdot (y_2 - y_1) \end{cases}</math>（<math>t \in [0, 1]</math>）

== 相交检测 ==
=== 直线相交 ===
两条直线 <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>

== 距离计算 ==
=== 点到直线距离 ===
点 <math>(x_0, y_0)</math> 到直线 <math>Ax + By + C = 0</math> 的距离：
<math>d = \frac{|Ax_0 + By_0 + C|}{\sqrt{A^2 + B^2}}</math>

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

<mermaid>
graph TD
    A[计算投影点] --> B{投影在线段上?}
    B -->|是| C[点到直线距离]
    B -->|否| D[min(到P1距离, 到P2距离)]
</mermaid>

== 实际应用案例 ==
=== 游戏开发中的碰撞检测 ===
在2D游戏中，判断子弹（线段）是否击中障碍物（多边形）时，需要检测子弹轨迹与多边形各边的相交情况。

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

== 进阶主题 ==
=== 参数化表示与插值 ===
线段的参数方程可用于线性插值：
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

=== 直线拟合 ===
给定一组点，可通过'''最小二乘法'''拟合最佳直线：
<math>
\min \sum_{i=1}^n (y_i - (kx_i + b))^2
</math>

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

{{Stub|algorithm}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:计算几何算法]]