Sweep Line
Sweep Line
「掃描線」是離散幾何領域的基礎手法,可以用來解決許多離散幾何的問題,有如圖論中的BFS與DFS一樣經典。它並不是一個物品,而是一個概念。
平移的掃描線
一條(或兩條)無限長平行線,沿其垂直方向不斷移動,從畫面一端移動到另一端,只在頂點處停留。
實作時,通常是先按座標大小排序所有頂點,然後以兩索引值,記錄平行線的位置在哪個頂點上面。兩條平行線,一條為主,穿越整個畫面;一條為輔,跟著主線的狀況進行平移。這是陰陽的道理。
後面章節Closest Pair,將實際示範掃描線的實作方式。
UVa 920 972
旋轉的掃描線
一條(或兩條)從原點射出的射線,做360°旋轉,只在頂點處停留。
實作時,通常是先按極角大小排序所有頂點,然後以兩索引值,記錄射線的位置在哪個頂點上面。兩條射線,一條為主,轉過整個畫面;一條為輔,跟著主線的狀況進行平移。這是陰陽的道理。
UVa 270 10691 10927 11529 11696 11704 ICPC 3259 4064
Sweep Line的基本精神
說穿了,掃描線的基本精神就是:先排序、再搜尋。
離散幾何當中,有一個重要的特性是「區域性」。比如說,距離相近的點,總是群聚在一起;距離相遠的點,總是被距離相近的點隔開。
排序的目的,就是建立「區域性」,使得搜尋的條件更精確,搜尋的速度更快。
觀察問題是否有「不重疊」、「不相交」、「間隔」、「相聚」之類的性質,然後以掃描線進行掃描。或者換句話說,排序所有的頂點,進行搜尋。
平移的掃描線:座標排序
旋轉的掃描線:極角排序
Rotating Caliper
Rotating Caliper
「旋轉卡尺」也是離散幾何領域的基礎手法,它並不是一個物品,而是一個概念。
平面上的圖形,做360°旋轉;以兩條垂直線,隨時從左右夾緊圖形,找到極端頂點。
切換視點,就變成:兩條無限長平行線,做360°旋轉,嘗試夾緊平面上的圖形,找到極端頂點。
實作時,通常是以兩索引值,記錄平行線的位置在哪個頂點上面。兩條平行線,一條為主,轉過整個畫面;一條為輔,跟著主線的狀況進行鬆緊。這是陰陽的道理。
實作時,只需轉180°即可。轉半圈,兩條平行線對調,效果同360°。
後面章節Farthest Pair,將實際示範旋轉卡尺的實作方式。
UVa 303 10173 10416 11243
Rotating Caliper的基本精神
說穿了,旋轉卡尺的基本精神就是:窮舉斜率,判斷目標對象有多斜。
旋轉卡尺:凸包
使用旋轉卡尺夾住圖形,卡尺夾不進的地方,剛好是該圖形的凸包。旋轉卡尺夾到的頂點順序,就是凸包的頂點順序。因此,旋轉卡尺適合用於凸包、凸多邊形的相關問題。
尚未學過凸包的讀者,請見本站文件「Convex Hull」。
Closest Pair
Closest Pair
一群點當中,距離最近的兩個點叫作「最近點對」。
演算法(Enumeration)
窮舉法,時間複雜度O(N²),可以找出所有的最近點對。
Farthest Pair
Farthest Pair
一群點當中,距離最遠的兩個點叫作「最遠點對」。
窮舉法,時間複雜度O(N²),可以找出所有的最遠點對。
旋轉卡尺,時間複雜度O(NlogN),可以找出所有的最遠點對。
距離變遠
距離變遠,就是擴張。無論是擴張兩點連線,或者是擴張邊界,距離都是變遠。
要找最遠點對,可以使用擴張邊界的概念。擴張邊界直到極限,碰觸到最偏遠的點,最後形成凸包。
因此,最遠點對一定是凸包的對角線。就如同日常生活中,邊邊角角的寬度是最寬的、最容易卡到。
凸多邊形範圍內,最遠的距離是對角線距離。
也許方才的論述太過抽象、不夠嚴謹。來詳細推敲一番吧!此處改用擴張兩點連線的概念。
凸多邊形範圍內任一線段,必定短於、等長於某一條對角線:
一、凸多邊形範圍內,任取兩點。
二、延長兩點連線,直到邊界。
三、挪動一點至頂點,盡可能遠離垂足。
四、挪動另一點至頂點,同上。
藉由此性質,以旋轉卡尺,窮舉最長對角線的斜率,量測最長對角線的長度,就能輕鬆找到最遠點對。
凸多邊形的最長對角線們,斜率皆不同。
同一個斜率,如果有兩條以上的最長對角線,就會產生矛盾──以兩條最長對角線描出平行四邊形,可以發現平行四邊形的對角線更長。凸多邊形範圍內一定可以順利描出平行四邊形,請參考凸的定義。
凸多邊形範圍內,同一個斜率,最多只有一條最長對角線。因此,同一個斜率,旋轉卡尺只能夾到一條最長對角線。
凸多邊形的最長對角線數目,不超過頂點數目。
平面上N個點,其凸包最多有N個頂點。隨著卡尺旋轉,每一個頂點,都可能作為下一條最長對角線的端點,可以推理出凸包最多有N條最長對角線,此時形成奇數個頂點的正多角星。
平面上N個點的最遠點對,最多只有N組。
演算法
一、求凸包,過濾出可能是最遠點對的點。O(NlogN) 二、旋轉卡尺,找出最長對角線,即是最遠點對。O(N)
實作旋轉卡尺,習慣用兩個指標記錄旋轉卡尺當前夾到的點。求出凸包之後,首先將兩個指標設定在凸包的最左最下點、最右最上點。要決定旋轉卡尺接下來夾住的點,就觀察夾角:夾角較小者,挪往下一點;夾角一樣者,同時挪往下一點(亦得擇一挪往下一點)。
除了觀察夾角之外,也可以觀察距離。要決定旋轉卡尺接下來夾住的點,就觀察點到直線距離:以另一邊的指標及其下一點作為直線,觀察指標及其下一點分別到直線的距離:距離變長者,挪往下一點;距離一樣者,同時挪往下一點(亦得擇一挪往下一點)。
上述兩種判斷方式都很麻煩,其實只需要一次叉積即可判斷,讀者可以動動腦想想看,謎底於程式碼揭曉。
迴圈部分亦可採一主一副的形式:每窮舉一個頂點,就立即找出對頂的點。
luogu P6247
Segment Intersection
判斷線段們是否相交
窮舉法,時間複雜度O(N²)。
平移的掃描線,時間複雜度O(NlogN)。
隨著掃描線移動,線段增增減減。如果線段沒有相交,線段的上下順序是固定的。如果線段相交,那就一定是上下相鄰的線段相交了。
每當線段增增減減,當下就可以檢查上下相鄰的線段是否相交。使用二元搜尋樹紀錄線段,快速找出上下相鄰的線段。
一、排序所有端點: 甲、X座標,從小到大。 乙、Y座標,從小到大。 丙、左端點先於右端點。 (垂直線段,以下端點為左端點,以上端點為右端點。) 丁、下端點先於上端點。 二、從左往右掃描端點: 甲、若為左端點,把線段塞入二元搜尋樹。 判斷此線段、上一條線段是否相交。 判斷此線段、下一條線段是否相交。 乙、若為右端點,從二元搜尋樹取出線段。 判斷上一條、下一條線段是否相交。
由於set不像vector一樣會自行搬動記憶體位址,所以可以將插入時的iterator記錄起來,稍後刪除時就能直接取用iterator,省下一次搜尋。
Timus 1469 ICPC 8050
找出線段們所有交點
窮舉法,時間複雜度O(N²),可以求出所有交點。
平移的掃描線,時間複雜度O((N+K)logN),可以求出所有交點。K是交點個數,頂多C(N,2)個。
一、建立priority queue,排序所有端點: 甲、X座標,從小到大。 乙、Y座標,從小到大。 丙、左端點先於右端點。 (垂直線段,以下端點為左端點,以上端點為右端點。) 丁、下端點先於上端點。 二、從左往右掃描端點暨交點: 甲、若為左端點,把線段放入二元搜尋樹。 計算此線段、上一條線段的交點,交點塞入priority queue。 計算此線段、下一條線段的交點,交點塞入priority queue。 乙、若為右端點,從二元搜尋樹取出線段。 計算上一條、下一條線段的交點,交點塞入priority queue。 丙、若為交點,顛倒所屬線段在二元搜尋樹當中的順序。 回、甲乙丙都要小心處理多線共點的情況。
每次求得的交點,一定出現在目前的掃描線右側,所以不必擔心掃描線已經錯過了交點。
Point-Line Duality
Point-Line Duality
二維平面上的點和線,可以等價地轉換成線和點。轉換方式有許多種,此處採用第一種:斜率與截距。
一、點 (a,b) 轉換成直線 y = ax - b 直線 y = ax - b 轉換成點 (a,b) 二、點 (a,b) 轉換成直線 ax + by = 1 直線 ax + by = 1 轉換成點 (a,b) 三、點變直線:穿過該點的直線,法向量是(a,b)。 直線變點:原點O投影到直線之後的座標。
一群點=一群線。兩點連線=兩線交點。多點共線=多線共點。
Convex Hull與Envelope互為點線對偶
一群點的上凸包與下凸包=一群直線的下包絡線與上包絡線。
求凸包、求包絡線(半平面交集),同樣困難,複雜度相同。
UVa 11756
Sweep Line與Rotating Caliper互為點線對偶
旋轉卡尺夾住凸包=平移的掃描線經過包絡線。
平移的掃描線能解決的問題,旋轉卡尺也能解決。反之亦然。