先決定凸包程序要回傳甚麼
凸包是一個幾何集合,但程式要回傳有限表示。直邊中間的點要包含嗎?首頂點要在尾端重複嗎?全部點在同一直線時怎樣辦?這些輸出選擇必須先定好,轉向測試才可能組成正確算法。
本節只回傳極頂點,使用按 x 分組的單調鏈構造,分開建立下、上邊界。同 x 點先分組,讓垂直邊明確處理,每次掃描則只面對嚴格單調的 x 座標。
指定幾何、算術與退化情況
定義 8.3.1
(凸包與極頂點輸出)
有限點集 P 的凸包,是 P 中各點的全部凸組合:權重非負且總和為一的加權和。極頂點不能寫成集合中其他點的凸組合;重複座標代表同一幾何點。
程序的輸出約定是:
- 沒有點:回傳空清單。
- 只有一個相異點:只回傳一次。
- 多個相異共線點:回傳線段兩端。
- 其餘情況:從字典序最小點開始,逆時針列極頂點,不重複首點,也不加入直邊上的多餘共線點。
使用普通 Cartesian 座標,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) 在菱形外,也不是輸入頂點。凸性加包含只證一個包含方向;本證明還找出精確上下邊界,且使用輸入頂點,使輸出多邊形也包含於輸入凸包。兩個方向才給等號。