整数网格上千点集的快速凹包求解方案问询

优化边界点检测效率 #

你的思路方向正确，但核心问题在于用列表执行in操作的效率极低——列表的成员判断是O(n)复杂度，数千个点的情况下，每个点检查四个方向相当于4*O(n)的开销，整体复杂度达O(4n²)，扩展性自然差。

解决办法是先将点集转换为集合（set），集合的in操作是O(1)复杂度，能把边界检测的时间复杂度直接降到O(n)：

# 转换为集合，加速邻点查找
full_pixels_set = set(full_pixels)
boundary_pixels = [
    (r, c)
    for (r, c) in full_pixels
    if not (
        (r+1, c) in full_pixels_set and
        (r-1, c) in full_pixels_set and
        (r, c+1) in full_pixels_set and
        (r, c-1) in full_pixels_set
    )
]

注意：将原代码中的&替换为and，逻辑更清晰，执行效果一致。

边界点排序（生成有序凹包） #

由于你的点集无内部孔洞，无需复杂的通用凹包算法，用邻域追踪法即可快速生成顺时针/逆时针的有序边界：

1. 找到起始点：取最靠下且最靠左的边界点（确保是凹包的一个顶点）
2. 按固定方向优先级遍历边界，通过调整方向避免走回头路，直到回到起始点

具体实现代码：

def sort_boundary_points(boundary_points, full_pixels_set):
    # 确定起始点：最靠下、最靠左的边界点
    start = min(boundary_points, key=lambda p: (p[0], p[1]))
    current = start
    visited = set([current])
    sorted_boundary = [current]
    # 顺时针方向优先级：右、下、左、上
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dir_idx = 0

    while True:
        dr, dc = directions[dir_idx]
        next_point = (current[0] + dr, current[1] + dc)
        # 检查下一个点是否为未访问的边界点
        if next_point in boundary_points and next_point not in visited:
            current = next_point
            visited.add(current)
            sorted_boundary.append(current)
            # 微调方向，避免走回头路
            dir_idx = (dir_idx - 1) % 4
        else:
            # 当前方向走不通，顺时针切换方向
            dir_idx = (dir_idx + 1) % 4
        # 回到起始点，结束遍历
        if current == start and len(sorted_boundary) > 1:
            break
    return sorted_boundary

该方法的时间复杂度为O(m)，m是边界点数量，远小于总点数n，效率极高。

极致速度的替代方案 #

如果点集在网格上分布密集，还可以用扫描线法进一步提速：

• 遍历每一行，记录该行最左和最右的点（均为边界点）
• 遍历每一列，记录该列最上和最下的点（去重后加入边界点集合）
• 对收集到的边界点按顺时针/逆时针规则排序

这种方法的时间复杂度为O(w + h)，w为网格宽度，h为网格高度，在点集密集时，效率比遍历所有点更高。

内容的提问来源于stack exchange，提问作者Josh Kidd