跳到主要内容

Jarvis步进法

Jarvis步进法（Jarvis March），也称为礼品包装算法（Gift Wrapping Algorithm），是一种用于计算二维点集凸包的经典算法。它的核心思想是通过逐步“包裹”点集来找到凸包的边界。对于初学者来说，这是一个直观且易于理解的算法。

什么是凸包？​

在开始讲解Jarvis步进法之前，我们需要先了解什么是凸包。凸包是包含给定点集的最小凸多边形。换句话说，它是将所有点“包裹”起来的最小凸形状。凸包在计算几何中有着广泛的应用，例如碰撞检测、路径规划和图像处理等。

Jarvis步进法的基本思想​

Jarvis步进法的核心思想是从点集中选择一个起始点（通常是x坐标最小的点），然后逐步找到下一个凸包顶点，直到回到起始点，形成一个闭合的凸包。

算法的步骤如下：

  1. 选择起始点：找到点集中x坐标最小的点，作为凸包的起始点。
  2. 寻找下一个顶点：从当前点出发，找到与当前点形成的向量角度最小的点，作为下一个凸包顶点。
  3. 重复步骤2：将找到的点作为新的当前点，继续寻找下一个顶点，直到回到起始点。

算法实现​

下面是一个用Python实现的Jarvis步进法示例：

python
def cross_product(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def jarvis_march(points):
    n = len(points)
    if n < 3:
        return points

    # 找到起始点（x坐标最小的点）
    start = min(points, key=lambda p: p[0])
    hull = [start]

    while True:
        current = hull[-1]
        next_point = points[0]

        for p in points:
            if p == current:
                continue
            cross = cross_product(current, next_point, p)
            if cross < 0 or (cross == 0 and distance(current, p) > distance(current, next_point)):
                next_point = p

        if next_point == start:
            break
        hull.append(next_point)

    return hull

def distance(a, b):
    return (a[0] - b[0])**2 + (a[1] - b[1])**2

输入和输出示例​

假设我们有以下点集：

python
points = [(0, 3), (2, 2), (1, 1), (2, 1), (3, 0), (0, 0), (3, 3)]

调用 jarvis_march(points) 将返回凸包的顶点：

python
[(0, 0), (3, 0), (3, 3), (0, 3)]

逐步讲解​

1. 选择起始点​

我们首先选择x坐标最小的点作为起始点。在上面的示例中，起始点是 (0, 0)。

2. 寻找下一个顶点​

从起始点出发，我们遍历所有其他点，找到与当前点形成的向量角度最小的点。这个点就是下一个凸包顶点。

3. 重复步骤2​

我们将找到的点作为新的当前点，继续寻找下一个顶点，直到回到起始点。

实际应用场景​

Jarvis步进法在以下场景中非常有用：

  • 碰撞检测：在游戏开发中，凸包可以用于检测两个物体是否可能发生碰撞。
  • 路径规划：在机器人导航中，凸包可以用于确定机器人的安全路径。
  • 图像处理：在图像识别中，凸包可以用于提取物体的轮廓。

总结​

Jarvis步进法是一种简单直观的凸包算法，适合初学者理解和实现。虽然它的时间复杂度为O(nh)，其中n是点集的大小，h是凸包的顶点数，但对于小规模的点集来说，它的性能是可以接受的。

附加资源与练习​

  • 练习1：尝试用Jarvis步进法计算以下点集的凸包：[(1, 1), (2, 3), (4, 2), (3, 1), (5, 4)]。
  • 练习2：比较Jarvis步进法与Graham扫描法的性能差异。
  • 进一步阅读：了解更多关于凸包算法的内容，例如Graham扫描法和Andrew's monotone chain算法。
提示

如果你对计算几何的其他算法感兴趣，可以继续学习Graham扫描法或Andrew's monotone chain算法，它们在某些情况下比Jarvis步进法更高效。