编辑“︁Jarvis步进法（凸包算法）”︁

{{DISPLAYTITLE:Jarvis步进法（凸包算法）}}

'''Jarvis步进法'''（又称'''礼物包装算法'''）是计算几何中求解[[凸包]]问题的经典算法之一。该算法通过模拟“用包装纸包裹礼物”的过程，逐步构造凸包的边界。其时间复杂度为<math>O(nh)</math>，其中<math>n</math>是点集大小，<math>h</math>是凸包顶点数，适合处理凸包顶点较少的场景。

== 算法原理 ==
Jarvis步进法的核心思想是：
# 从点集中确定一个必然在凸包上的点（如最左下点）作为起点。
# 以当前点为基准，寻找下一个极角最小的点（或通过向量叉积判断）。
# 重复上述过程，直到回到起点形成闭合多边形。

=== 数学基础 ===
关键判断使用'''向量叉积'''：
* 对于点<math>A(x_1,y_1)</math>、<math>B(x_2,y_2)</math>、<math>C(x_3,y_3)</math>，叉积值为：
<math>
\text{叉积} = (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)
</math>
* 若结果为正，则<math>C</math>在向量<math>AB</math>的左侧；为负则在右侧；为零则共线。

== 算法步骤 ==
1. '''初始化'''：找到最左下点<math>p_0</math>（<math>y</math>坐标最小，相同时取<math>x</math>最小）
2. '''循环构造'''：
   a. 将当前点<math>p_i</math>加入凸包
   b. 选择点<math>q</math>使得所有其他点都在向量<math>p_iq</math>的右侧
   c. 令<math>p_{i+1} = q</math>
3. '''终止条件'''：当回到起点<math>p_0</math>时结束

<mermaid>
graph TD
    A[找到最左下点p0] --> B[加入凸包列表]
    B --> C[初始化当前点p=p0]
    C --> D[寻找下一个点q]
    D --> E{q==p0?}
    E -->|否| F[将q加入凸包并更新p=q]
    F --> D
    E -->|是| G[算法结束]
</mermaid>

== 代码实现 ==
以下是Python实现示例：

<syntaxhighlight lang="python">
def jarvis_march(points):
    n = len(points)
    if n < 3:
        return points  # 凸包退化情况
    
    # 找到最左下点
    start = min(points, key=lambda p: (p[1], p[0]))
    hull = []
    current = start
    
    while True:
        hull.append(current)
        next_point = points[0]
        
        for candidate in points[1:]:
            if next_point == current:
                next_point = candidate
                continue
            
            # 计算叉积
            cross = (next_point[0]-current[0])*(candidate[1]-current[1]) - \
                    (next_point[1]-current[1])*(candidate[0]-current[0])
            
            # 如果候选点在当前向量的右侧，或共线但更远
            if cross < 0 or \
               (cross == 0 and ((candidate[0]-current[0])**2 + (candidate[1]-current[1])**2 > \
                                (next_point[0]-current[0])**2 + (next_point[1]-current[1])**2):
                next_point = candidate
        
        current = next_point
        if current == start:
            break
    
    return hull
</syntaxhighlight>

=== 输入输出示例 ===
'''输入'''：<code>[(0, 3), (2, 2), (1, 1), (2, 1), (3, 0), (0, 0), (3, 3)]</code>
'''输出'''：<code>[(0, 0), (3, 0), (3, 3), (0, 3)]</code>

执行过程：
1. 选择<math>(0, 0)</math>为起点
2. 依次找到<math>(3, 0)</math>（极角最小）
3. 接着找到<math>(3, 3)</math>（相对于前向量的极角最小）
4. 最后找到<math>(0, 3)</math>并回到起点

== 复杂度分析 ==
* '''时间复杂度'''：<math>O(nh)</math>，最坏情况（所有点都在凸包上）为<math>O(n^2)</math>
* '''空间复杂度'''：<math>O(h)</math>，仅存储凸包顶点

== 应用场景 ==
1. '''计算机图形学'''：物体碰撞检测的预处理
2. '''地理信息系统'''（GIS）：计算多个地理坐标的最小包围区域
3. '''机器人路径规划'''：确定工作区域的边界
4. '''模式识别'''：形状特征提取

== 与其他算法对比 ==
{| class="wikitable"
|-
! 算法 !! 时间复杂度 !! 适用场景
|-
| Jarvis步进法 || <math>O(nh)</math> || 凸包顶点少时高效
|-
| Graham扫描法 || <math>O(n \log n)</math> || 通用场景
|-
| Andrew算法 || <math>O(n \log n)</math> || 处理简单多边形
|}

== 优化变种 ==
1. '''预处理排序'''：按极角预先排序可加速查找过程
2. '''并行化'''：在多核系统中可并行计算候选点
3. '''混合策略'''：当<math>h > \log n</math>时切换至Graham扫描法

== 练习建议 ==
1. 手动模拟算法在简单点集（如4-5个点）上的执行过程
2. 实现共线点处理的改进版本
3. 可视化算法每一步的候选点选择过程

通过理解Jarvis步进法，学习者可以掌握计算几何中最基础的极角排序和凸包构造思想，为后续更复杂的几何算法打下基础。

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