先决定凸包过程要返回什么
凸包是一个几何集合,但程序要返回有限表示。直边中间的点要包含吗?首顶点要在尾端重复吗?全部点在同一直线时怎么办?这些输出选择必须先定好,转向测试才可能组成正确算法。
本节只返回极点,使用按 x 分组的单调链构造,分开建立下、上边界。同 x 点先分组,让垂直边明确处理,每次扫描则只面对严格单调的 x 坐标。
指定几何、算术与退化情况
定义 8.3.1
(凸包与极点输出)
有限点集 P 的凸包,是 P 中各点的全部凸组合:权重非负且总和为一的加权和。极点不能写成集合中其他点的凸组合;重复坐标代表同一几何点。
过程的输出约定是:
- 没有点:返回空列表。
- 只有一个不同点:只返回一次。
- 多个不同共线点:返回线段两端。
- 其余情况:从字典序最小点开始,逆时针列极点,不重复首点,也不加入直边上的多余共线点。
使用普通笛卡尔(Descartes)坐标,y 向上增加。字典序先比 x 再比 y。假设比较与算术精确,例如适当实现的整数或有理数。定向行列式的符号也是条件的一部分,以下证明不能为浮点舍入错误辩护。
对点 a、b、c,定义
正值是左转,负值是右转;a、b 不同时,零表示共线。扫描中的 x 不同,所以边方向不会为零。本节使用定向判定;线段相交算法是另一个主题。
每个 x 列至多贡献两个边界端点
对每个不同 x,保留最低点作下链候选,最高点作上链候选。同一直线两者之间的点是它们的凸组合,不可能是极点。
更具体地,比列最低点更高的点,不可能是该 x 的最低边界;上边界对称。在最左、最右 x,最高与最低点却可能都是顶点,形成垂直凸包边,所以两个候选都要保留,不能删掉整条端边。
若只有一个不同 x,所有点都在垂直线段上,底、顶端点已解决问题。否则下候选按 x 严格递增扫描,上候选按 x 严格递减扫描。
非左转时弹出中间点
SCAN_CHAIN(points_in_scan_order):
stack = empty list
for q in points_in_scan_order:
while length(stack) >= 2 and orient(stack[-2], stack[-1], q) <= 0:
remove last point from stack
append q to stack
return stack
保留的连续三点严格左转;x 递增时,等价于边斜率严格递增。<= 0 会删共线中间点,配合只返回极点的约定。
定理 8.3.2
(被弹出的下候选不是下边界极点)
若递增 x 候选满足 且 ,中间候选点 b 位于 a 到 q 弦上或其上方,不可能是完整输入凸包下边界的极点。
证明
(弦已是最终凸包内的见证)
设 ,故 。弦点 与 b 有同一 x,直接展开得
非正转向给出 。若严格大于,凸包内同 x 已有比 b 更低的 z,所以 b 不在下边界;若相等,b 是不同 a、q 的内部凸组合,不是极点。
a、q 都是输入点,所以其弦一直在最终凸包内,即使稍后从扫描栈移除也一样。此证书不会因继续处理点而失效。
弹出只针对此边界。下扫描移除的点仍可为上凸包顶点;两扫描不能共用一个“被弹出就全局无用”标记。
为何保留的下链正好是下凸包
定理 8.3.3
(扫描恰好返回下极点)
设下候选的 坐标严格递增。则 SCAN_CHAIN 按 递增顺序返回的,恰是它们凸包下边界的全部极点,包括下边界的两个端点。
证明
(结合移除证书与凸链不变量)
栈始终按 x 递增。While 结束后,最新末端三点严格左转,较早保留的三点不变,所以归纳得每次插入后整链边斜率严格递增。
最终下凸包的真正极点不会丢失:分组保留每个可能的下顶点,出栈证书则不允许移除真正下极点。首、尾下候选也保留,因此包含下边界两端。
还要排除多余顶点。取相邻的真正下极点 a、c;其间真实下边界为直边,中间 x 的全部输入点都在该边上或以上。斜率递增链在任两顶点的弦上或以下:到一个中间点之前的平均斜率不大于之后的平均斜率,等价于此弦不等式。
保留链包含 a、c,所以中间保留点须同时在真凸包边上/以上及端点弦上/以下,只能在该边上。严格递增斜率又排除额外共线中间点。因此保留点恰是按顺序相连的下极点。
证明透视
没有丢失真顶点,也没有多留顶点
这个证明合并两项互相独立的保证。移除证书说明出栈从不丢掉真正的下顶点;它需要 严格递增,因为弦的构造要除以 ,两个候选若同 便为零。凸链不变量说明保留链的斜率严格递增;使斜率严格、从而排除共线中间点的,是出栈条件取 <= 0 而非 < 0。非常规的一步是弦不等式:斜率递增的链在其任意两顶点的弦上或以下,而每个输入点都在某条真凸包边上或以上。夹在两个真顶点之间的多余顶点,因此被挤到该边上,但严格斜率不允许它存在。论证能够收尾,是因为首、尾候选从不被弹出,两个端点必定在链中。
上边界证明可用 。此旋转把各列的最高点转为各列的最低点、反转 x 顺序,且行列式为正而保留定向。所以同一左转扫描,从右至左处理上候选,正好得到上边界。
概念视角分析
下凸包是点集下方最大的凸函数
设 为 上满足 (对每个下候选点)的最大凸函数。它的图像就是凸包的下边界,而 是分段线性的。下方极点就是两个端点,加上 的斜率严格增加之处。这正是扫描不变量的函数写法:斜率严格递增,所以共线的中间点不是折点。
连接边界,不重复端点
EXTREME_HULL(input_points):
P = lexicographically sorted distinct input points
if length(P) <= 1:
return P
lower_candidates = empty list
upper_candidates = empty list
for each group of P with one common x-coordinate:
append its minimum-y point to lower_candidates
append its maximum-y point to upper_candidates
if length(lower_candidates) == 1:
return [lower_candidates[0], upper_candidates[0]]
lower = SCAN_CHAIN(lower_candidates)
upper = SCAN_CHAIN(reverse(upper_candidates))
hull = empty list
for p in lower followed by upper:
if hull is empty or p != hull[-1]:
append p to hull
if length(hull) > 1 and hull[0] == hull[-1]:
remove last point from hull
return hull
上下端点相同时,连接移除重复;同一端 x 的两点不同时,其垂直连线是真凸包边,两端都保留。全部点都在精确下、上边界之间。下链从左到右、上链从右到左,使区域保持在左侧,所以非共线时是逆时针。
非垂直共线输入时,每扫描只保留两端,连接去重后返回两点,没有把线段当逆时针多边形。单列分支处理垂直情况;去重则处理同一点的多份副本。
例题 8.3.4
(网格返回角,不是全部边界样本)
取全部九个 的点,再加一份 (0,0)。三个列最低点是 (0,0)、(1,0)、(2,0),列最高点是 (0,2)、(1,2)、(2,2)。
下扫描因为零转向移除 (1,0),反向上扫描同样移除 (1,2)。连接得 (0,0)、(2,0)、(2,2)、(0,2)。分组早已排除 (0,1)、(2,1),(1,1) 也不是边界候选;重复 (0,0) 只出现一次。
输出所填多边形就是全部输入的凸包。四个顶点不表示只有四个输入点在边界,而是只有四个为极点。
例题 8.3.5
(下链弹出的点仍可为上极点)
取 (0,0)、(1,2)、(2,0)、(3,1)。下扫描加入 (2,0) 时,经 (1,2) 的转向为 ,所以移除中间点。下链最后为 (0,0)、(2,0)、(3,1)。
上扫描保留 (3,1)、(1,2)、(0,0),所以完整凸包为 (0,0)、(2,0)、(3,1)、(1,2)。排除 (1,2) 作下边界有充分理由,它却仍是整体凸包的极点;全局删掉它就错。
例题 8.3.6
(左侧的垂直边)
取点 、、。列 贡献下候选 和上候选 ;列 把 同时放入两个列表。下扫描只有两点,返回 。反向的上候选列表是 ,返回 。拼接时重复的 被去掉,得 ;由于 ,不必移除结尾点。这里 ,所以顺序为逆时针,而从 回到 的封闭边正是垂直凸包边。两端列的两个候选都保留,才保住这条边。
常见错误
(略去对重复点的去重)
对五份 ,只有一个 列,单列分支返回该列最低与最高点,两者都是 。若不去重,输出会把同一点列两次,而不是一次。应在排序后、分组前去重。
常见错误
(把出栈当作全局判断)
下扫描弹出的点,只是被排除在下边界之外。以 为例, 被下扫描弹出,却是整体凸包的极点。若在上扫描中也把它当作无用,就会丢掉一个凸包顶点。
嵌套 while 不会让扫描变成平方时间
命题 8.3.7
(单次扫描的线性成本)
对 个候选的一次扫描,至多进行 次定向测试和 次入栈,所以耗时 。
证明
(出栈由入栈支付)
每候选只入栈一次;从某扫描弹出后,不会重入该扫描,所以总出栈数不超过总入栈数。每次成功 while 测试支付一次出栈;每个新点入栈前至多有一次最后失败测试。因此每扫描对候选数是线性时间。
N 个输入项的排序/去重花 次比较,分组、连接各 ,两扫描合计也为 。实现存储已排序点、候选与栈,用 空间。此计数假设精确坐标比较及定向运算为常数成本;大整数的比特成本须另算。
反例模式
只改一个不等号,不会改好整个输出约定
有人可能把出栈条件改为 < 0,想保留共线点。但在本分组算法中,仍不会保留全部边界点:网格 (0,1) 在任何转向测试前已被分组排除。
要返回全部边界点,必须另处理垂直列、共线段及退化连接。本节证明的接口只返回极点;只改比较符号,不会自动证明整个流程符合另一约定。
附解答练习
快速检查
(设 、、。求定向值,找出与 同 的下方弦点,说明出栈究竟证明什么。它是否证明 永远不在完整凸包?)
使用公式 。
解答 · 答案
行列式为 。x=1 时,a 到 q 的弦包含 z=(1,0),严格低于 b。因此有 a、q 后,b 不能为下边界顶点;它仍可为上极点,正如第二例。证书只针对指定边界。
快速检查
(给出无点、五份 、以及可有副本的 的输出。另给 的输出。哪些输出有逆时针多边形顺序?)
按输出约定逐一处理各种情况。
解答 · 答案
依次为空列表、[(2,3)]、[(2,-1),(2,4)]、[(0,0),(3,3)]。去重解决重复点,单列分支处理垂直线段,零转向弹出非垂直共线中间点。这些都不是非退化多边形,所以没有声称逆时针多边形顺序。
快速检查
(新点一次令十个候选出栈,为何不违反线性扫描界?输入未排序时,还有什么主要成本?)
数一数整个扫描的入栈与出栈次数。
解答 · 答案
十次出栈对应十个先前入栈的不同候选,它们不能在同一扫描再次出栈。全扫描总出栈至多总入栈,合计仍线性,虽然某一轮很昂贵。本实现仍须以 次比较排序未排输入;线性栈阶段没有消除排序成本。
快速检查
(输入 ,程序返回矩形 ,理由是凸且包含全部输入。它是凸包吗?给真实极点输出并说明欠缺什么理由。)
矩形的每个顶点都是输入点吗?
解答 · 答案
正确输出为 (0,1)、(1,0)、(2,1)、(1,2),按逆时针成菱形。矩形是严格更大的凸超集,例如 (0,0) 在菱形外,也不是输入顶点。凸性加包含只证一个包含方向;本证明还找出精确上下边界,且使用输入顶点,使输出多边形也包含于输入凸包。两个方向才给等号。