Chan算法中二进制Jarvis步进的实现方法问询

核心原理 #

将原始点集P划分为$n//m$个子集，对每个子集执行Graham扫描得到逆时针排序的子凸包。由于子凸包的有序性，可通过二分搜索替代Jarvis步进中的线性遍历，快速找到每个子凸包上的支撑点（即能与当前边形成最大逆时针夹角的点），将单次Jarvis步进的时间复杂度从$O(n)$优化到$O((n/m)\log m)$。

引用原文 #

维基百科原文：
……已知集合$Q_k$的凸包$C_k$最多包含$m$个点（按顺时针或逆时针顺序排列），这使得可以通过二分搜索在$O(\log m)$时间内计算$f(p_{i},Q_{k})$。

Chan论文原文：
由于通过二分或斐波那契搜索在凸多边形上寻找切线的时间为对数时间[5]、[25***]（对偶问题是凸多边形与射线相交），因此一次包裹步骤的时间复杂度为$O ((n/m) \log m)$。[pg 2]
此外，通过在conv($P_i$)的顶点上执行二分搜索，计算出最大化$\angle p_{k-1}p_k q_i$的点$q_i\in P_i$[pg 3]

关键几何工具：叉积判断方向 #

对于三个点$a, b, c$，叉积公式为：

cross(a, b, c) = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)

• 结果>0：$c$在向量$\overrightarrow{ab}$的逆时针方向（左转）
• 结果=0：三点共线
• 结果<0：$c$在向量$\overrightarrow{ab}$的顺时针方向（右转）

我们要找的支撑点，就是使cross(p_prev, p_curr, q)最大的点$q$（对应最大逆时针夹角）。

伪代码 #

# 输入：所有子凸包的列表convex_hulls（每个凸包为逆时针排序的点列表），当前边的两个端点p_prev、p_curr
# 输出：所有子凸包中选出的下一个凸包点

function binary_jarvis_step(convex_hulls, p_prev, p_curr):
    best_point = None
    max_cross = -∞
    
    for each hull in convex_hulls:
        left = 0
        right = len(hull) - 1
        n_hull = len(hull)
        
        while left <= right:
            mid = (left + right) // 2
            curr_cross = cross(p_prev, p_curr, hull[mid])
            next_cross = cross(p_prev, p_curr, hull[(mid+1)%n_hull])
            
            if curr_cross < next_cross:
                # 支撑点在右侧区间
                left = mid + 1
            else:
                # 支撑点在左侧区间或就是mid
                right = mid - 1
        
        # 循环结束后left即为最优点索引
        candidate = hull[left % n_hull]
        candidate_cross = cross(p_prev, p_curr, candidate)
        
        if candidate_cross > max_cross:
            max_cross = candidate_cross
            best_point = candidate
    
    return best_point

Python实现 #

from typing import List, Tuple

Point = Tuple[float, float]

def cross(a: Point, b: Point, c: Point) -> float:
    """计算叉积 (b - a) × (c - a)"""
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def find_support_point(hull: List[Point], p_prev: Point, p_curr: Point) -> Point:
    """在单个逆时针凸包上，找到对边p_prev->p_curr的支撑点"""
    n = len(hull)
    left, right = 0, n - 1
    
    while left <= right:
        mid = (left + right) // 2
        # 比较当前中点与下一个点的叉积，判断搜索方向
        curr_cross = cross(p_prev, p_curr, hull[mid])
        next_cross = cross(p_prev, p_curr, hull[(mid + 1) % n])
        
        if curr_cross < next_cross:
            left = mid + 1
        else:
            right = mid - 1
    
    # 取模处理索引越界（如left等于n时回到0）
    return hull[left % n]

def binary_jarvis_step(convex_hulls: List[List[Point]], p_prev: Point, p_curr: Point) -> Point:
    """执行一次二分Jarvis步进，从所有子凸包中选出下一个凸包点"""
    best_point = None
    max_cross = -float('inf')
    
    for hull in convex_hulls:
        candidate = find_support_point(hull, p_prev, p_curr)
        current_cross = cross(p_prev, p_curr, candidate)
        
        if current_cross > max_cross:
            max_cross = current_cross
            best_point = candidate
    
    return best_point

注意事项 #

1. 所有子凸包必须保证逆时针排序，这是Graham扫描的标准输出，是二分搜索正确执行的前提。
2. 二分搜索的核心逻辑是通过比较相邻点的叉积大小，逐步缩小最优点的搜索范围，最终定位到支撑点。
3. 最终从所有子凸包的支撑点中，选出叉积最大的点，即为Jarvis步进的下一个凸包顶点。

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