跳到主要内容

凸包算法

介绍​

凸包（Convex Hull）是计算几何中的一个重要概念。简单来说，凸包是指在一个平面或空间中，包含所有给定点的最小凸多边形或凸多面体。凸包算法则是用来计算这些点的凸包的算法。

凸包算法在计算机图形学、地理信息系统（GIS）、机器人路径规划等领域有着广泛的应用。例如，在机器人路径规划中，凸包可以用来确定机器人的安全区域；在GIS中，凸包可以用来简化地图数据。

凸包的定义​

给定平面上的一个点集，凸包是包含所有点的最小凸多边形。凸多边形的定义是：任意两点之间的连线都在多边形内部。

凸包算法​

常见的凸包算法包括：

  1. Graham扫描法（Graham's Scan）
  2. Andrew单调链算法（Andrew's Monotone Chain Algorithm）
  3. Jarvis步进法（Jarvis March）

Graham扫描法​

Graham扫描法是一种高效的凸包算法，时间复杂度为O(n log n)。其基本步骤如下：

  1. 找到点集中最下方的点（如果有多个，选择最左边的点）。
  2. 按照该点与其他点的极角进行排序。
  3. 使用栈来构建凸包，依次检查每个点是否在凸包的边界上。

代码示例​

python
import math

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

def convex_hull(points):
    if len(points) <= 3:
        return points
    # 找到最下方的点
    start = min(points, key=lambda p: (p[1], p[0]))
    points.pop(points.index(start))
    # 按极角排序
    points.sort(key=lambda p: (math.atan2(p[1] - start[1], p[0] - start[0]), p[0])
    # 构建凸包
    hull = [start]
    for p in points:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

# 示例输入
points = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]
# 计算凸包
hull = convex_hull(points)
print(hull)

输出​

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

Andrew单调链算法​

Andrew单调链算法是另一种高效的凸包算法，时间复杂度同样为O(n log n)。其基本步骤如下：

  1. 将所有点按照x坐标排序（如果x坐标相同，则按y坐标排序）。
  2. 构建下凸包和上凸包。
  3. 合并下凸包和上凸包得到最终的凸包。

代码示例​

python
def convex_hull(points):
    if len(points) <= 3:
        return points
    # 按x坐标排序
    points = sorted(points)
    # 构建下凸包
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    # 构建上凸包
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    # 合并下凸包和上凸包
    return lower[:-1] + upper[:-1]

# 示例输入
points = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]
# 计算凸包
hull = convex_hull(points)
print(hull)

输出​

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

Jarvis步进法​

Jarvis步进法是一种简单的凸包算法，时间复杂度为O(nh)，其中h是凸包上的点数。其基本步骤如下：

  1. 找到点集中最左边的点。
  2. 从该点开始，依次找到下一个凸包上的点，直到回到起点。

代码示例​

python
def convex_hull(points):
    if len(points) <= 3:
        return points
    # 找到最左边的点
    start = min(points, key=lambda p: p[0])
    hull = []
    current = start
    while True:
        hull.append(current)
        next_point = points[0]
        for p in points:
            if p == current:
                continue
            cross_prod = cross(current, next_point, p)
            if next_point == current or cross_prod > 0:
                next_point = p
        current = next_point
        if current == start:
            break
    return hull

# 示例输入
points = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]
# 计算凸包
hull = convex_hull(points)
print(hull)

输出​

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

实际应用场景​

机器人路径规划​

在机器人路径规划中，凸包可以用来确定机器人的安全区域。例如，给定一组障碍物的位置，凸包可以帮助机器人找到一个安全的路径，避开所有障碍物。

地理信息系统（GIS）​

在GIS中，凸包可以用来简化地图数据。例如，给定一组地理坐标点，凸包可以帮助我们快速确定这些点的边界，从而简化地图的显示。

总结​

凸包算法是计算几何中的一个重要工具，广泛应用于计算机图形学、地理信息系统、机器人路径规划等领域。本文介绍了三种常见的凸包算法：Graham扫描法、Andrew单调链算法和Jarvis步进法，并提供了相应的代码示例和实际应用场景。

附加资源与练习​

  • 练习1：实现Graham扫描法，并测试其在不同点集上的表现。
  • 练习2：比较Graham扫描法、Andrew单调链算法和Jarvis步进法的性能。
  • 附加资源：
提示

建议初学者从Graham扫描法开始学习，因为它的实现相对简单，且效率较高。