Jarvis步进法（凸包算法）

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

算法原理

Jarvis步进法的核心思想是：

1. 从点集中确定一个必然在凸包上的点（如最左下点）作为起点。
2. 以当前点为基准，寻找下一个极角最小的点（或通过向量叉积判断）。
3. 重复上述过程，直到回到起点形成闭合多边形。

数学基础

关键判断使用向量叉积：

• 对于点$A(x_1,y_1)$、$B(x_2,y_2)$、$C(x_3,y_3)$，叉积值为：

$\text{叉积}=(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)$

• 若结果为正，则$C$在向量$AB$的左侧；为负则在右侧；为零则共线。

算法步骤

1. 初始化：找到最左下点$p_0$（$y$坐标最小，相同时取$x$最小） 2. 循环构造：

  a. 将当前点$p_i$加入凸包
  b. 选择点$q$使得所有其他点都在向量$p_{i}q$的右侧
  c. 令$p_{i+1}=q$

3. 终止条件：当回到起点$p_0$时结束

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[算法结束]

代码实现

以下是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

输入输出示例

输入：[(0, 3), (2, 2), (1, 1), (2, 1), (3, 0), (0, 0), (3, 3)] 输出：[(0, 0), (3, 0), (3, 3), (0, 3)]

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

复杂度分析

• 时间复杂度：$O(nh)$，最坏情况（所有点都在凸包上）为$O(n^2)$
• 空间复杂度：$O(h)$，仅存储凸包顶点

应用场景

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

与其他算法对比

算法	时间复杂度	适用场景
Jarvis步进法	$O(nh)$	凸包顶点少时高效
Graham扫描法	$O(n\log n)$	通用场景
Andrew算法	$O(n\log n)$	处理简单多边形

优化变种

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

练习建议

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

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