摘要訊息 : 一個點集的最小外接凸多邊形被稱為凸包.

0. 前言

更新紀錄 :

• 2022 年 4 月 29 日進行第一次更新和修正. 由於凸包問題的複雜性, 本次更新只是增加了第 0 節, 內容沒有進行修改, 內容的修正和更新將在下一次更新進行. 如果出現圖像失效的問題, 大家可以在搜尋引擎上搜尋其它文章來閱讀. 文章在 2022 年 4 月 29 日暫時歸檔, 在下一次更新之後移除歸檔.

1. 原文內容

在幾何中, 我們稱至少有三條直線邊組成的平面封閉圖形為多邊形. 而多邊形又有多種分類, 其中一種分類方法將所有多邊形歸類為凸多邊形和非凸多邊形. 凸多邊形的嚴格定義我們這裡不講, 不過我們可以通過凸多邊形的性質來了解它 :

• 凸多邊形的所有內角都小於 180°
• 任取平面內的一條直線 l, l 與凸多邊形有四種關係 : 第一種是無論 l 怎麼延長, 總是和凸多邊形不相交; 第二種是 l 與凸多邊形的某一個頂點重合; 第三種是 l 與凸多邊形的某一條邊重合; 第四種是 l 穿過凸多邊形的內部. 我們拿第四種情況來說, 當 l 穿過凸多邊形內部時, l 與凸多邊形的邊的交點總數總是兩個. 而對於非凸多邊形, 交點的個數可能高於兩個

在一個實數向量空間 \mathscr{V} 中 (目前我們只討論平面空間), 對於任意給定的集合 \mathscr{X}, 包含所有 \mathscr{X} 元素的凸多邊形的點的集合 \mathscr{S} 稱為 \mathscr{X} 的凸包. 其中, \mathscr{S} \subseteq \mathscr{X}. 簡單地來說, 凸包就是由 \mathscr{X} 中的元素組成的, 包含 \mathscr{X} 中所有元素的最小凸多邊形 集合 \mathscr{S} 中的任意元素稱為 \mathscr{X} 的極點, 也就是集合 \mathscr{X} 組成的凸多邊形的頂點

如果那些極點都落在一條線段上, 那麼集合 \mathscr{X} 的凸包就退化稱為包含 \mathscr{X} 的最短直線 尋找一個實數向量空間中集合的凸包是屬於計算幾何中的基本問題, 關於幾何的欄目, Jonny'Blog 已經開通, 但是目前暫時未有文章 要獲得一個實數向量空間中的集合的凸包, 首先在凸包的內部去一個點 X, 然後從 X 向下作一條垂線 (讓電腦螢幕垂直於地面, 你可以認為這條線與地面垂直) 

將這條線逆時針 360º 旋轉一圈

設垂線為 L, 它在旋轉的過程中和 \mathscr{X} 中的點形成一個逆時針的夾角, 稱為極角, 用 \alpha_{i} 來表示

此時, \alpha_{1} = \angle LXC, \alpha_{2} = \angle LXB, \alpha_{3} = \angle LXA, \alpha_{4} = \angle LXE, \alpha_{5} = \angle LXD 根據極角從小到大, 重新給各個點編號 :

如果出現極角相同的情況, 那麼按照它們與 X 的距離從小到大來排列. 在上述情況中, 點 A、B、C、D 和 E 依次被編號為 (1) \sim (5) 在 L 掃描的過程中, 按照極角的次序一定會依次遇到 \mathscr{X} 的極點, 那麼應該如何從這些點中選出極點呢? 對於任意三個點 u、v 和 w 按照逆時針排列, 即有極角 \angle XLu \leq \angle XLv \leq \angle XLw. 連接 u、v 和 v、w 得到線段 uv 和 vw, 從包含極角最小的點的那條線段中任取一點, 逆時針畫圓弧, 直到遇到另外一條線段 :

上圖中 C 是起始點, B 是中間點, A 是結尾點. 連結 BC 和 BA, 得到線段 BC 和 線段 BA, 從線段 BC 上任意選區一點逆時針畫圓弧直到遇到線段 AB 為止, 得到一個逆時針的角度, 這個角度是大於 180º 的, 顯然是向外凸出的, 因此 B 點可能是極點之一 接著考慮點 B、A 和 E, 還有點 A、E 和 D, 同樣會出現上述情況 最後考慮點 E、D 和 C :

連接 ED 和 DC, 從線段 ED 上任意一點逆時針出發畫圓弧到線段 DC 為止, 我們發現這個這個角度小於 180º, 顯然向內凹陷, 因此 D 不是極點 根據上述分析, 我們得到了尋找凸包的演算法步驟 :

1. 處理退化的情況
2. 按照極角對點排序
3. 從序列中刪除不構成極點的點
4. 連接相鄰兩個點, 得到凸包

1. 處理退化的情況

當集合 \mathscr{X} 中的點不多於 2 個, 那麼直接回傳 \mathscr{X}. 否則, 判定集合 \mathscr{X} 中的點是否共線, 即任取 x_{i} \in \mathscr{X}, x_{j} \in \mathscr{X} 和 x_{k} \in \mathscr{X}, 若總有

\overrightarrow{x_{i}x_{j}} = k\overrightarrow{x_{j}x_{k}}

則 x_{i}, x_{j} 和 x_{k} 三點共線. 如果共線, 那麼尋找最左邊的端點 x_{m} 和最右邊的端點 x_{n}, 回傳 {x_{m}, x_{n}}. 其中, x_{m} 和 x_{n} 滿足

\max{\left \{ \left \| \overrightarrow{x_{i}x_{j}} \right \| \right \}} = \left \| \overrightarrow{x_{m}x_{n}} \right \|

2. 按照極角對點排序

在凸包內找到一個點 X^①, 向下作垂線, 將垂線圍繞點 X 逆時針旋轉 360º, 按照形成的極角的大小從小到大排列 \mathscr{X} 中的點, 對於極角相同的點, 按照它們的距離從小到大排列, 並且將排列好的點放入一個 序列^② 中

3. 從序列中刪除不構成極點的點

從頭至尾尋訪序列中已經排好序的點, 三個一組, 第一個點為起始點, 第二個點為中間點, 第三個點為結尾點. 連接第一個點和第二個點得到線段 l_{1}, 連接第二個點和點三個點 l_{2}. 在 l_{1} 上任取一點逆時針畫圓弧至 l_{2}, 測定圓弧的度數是否大於 180º : 如果大於 180º, 那麼第二個點、第三個點和第四個點重新組成一組, 以此類推; 如果圓弧的度數小於等於 180º, 那麼刪除中間那個點, 也就是第二個點, 接著第一個點、第三個點和第四個點重新組成一組, 以此類推. 重複上述步驟直到全部的點都被尋訪完. 測定角度不一定使用上述方法, 也可以使用其它方法, 只要能夠測定兩線段之間的逆時針夾角即可. 完成測定之後, 回傳最終得到的序列

4. 連接相鄰兩個點, 得到凸包

接收上面得到的序列, 連接相鄰兩點, 得到 \mathscr{X} 的最小凸多邊形, 也就是凸包

接下來還有幾個問題, 有幾個在前面我已經用類似於 ①, ② 的序列號標出了 首先就是如何在凸包內找到點 X. 我們考慮實數向量空間內, 不共線的點的集合 \mathscr{X} : 當 \mathscr{X} 中有三個元素, 那麼其凸包是一個三角形, 此時我們可以取內心、外心、重心和垂心甚至是隨機取點作為 X; 當 \mathscr{X} 中的元素大於三個, 那麼可以任選三個不共線的點, 用上述方法取一點作為 X. 不同的取點方式是否對結果有影響呢? 確實, 不同的取點方式使得序列中的排序會得到不同的結果. 但是, 無論點如何被排列, 只要按照逆時針的方式排列, 那麼非極點一定是可以去掉的. 因此, 不同的取點方式只會影響序列中的排序, 而不會影響最終的結果. 這個斷言我們暫時不證 其次, 如果在程式設計中, 我們應該拿什麼資料結構來存儲這個序列? 我們發現, 當序列固定之後, 我們只會進行從前往後的尋訪, 而不進行搜尋, 而且, 中間伴隨著刪除點的操作. 此時, 使用普通的陣列就顯得不那麼合適了, 因為從陣列中刪除元素需要移動刪除位置之後的元素. 因此, 連結串列成為了優選. 對於上述需求來說, 前項連結串列已經足以, 使用連結串列也可以 最後, 凸包在圖像處理、統計學甚至地理信息系統等中都有著一定的應用

以圖像處理為例. 我們希望在圖像中對一定的區域進行描邊, 比如下面的圖像中, 我們對零件進行描邊. 首先我們通常會大致確定圖像中的目標區域. 在顏色反差較大的圖像中, 我們可以首先將圖像灰度處理

原始圖像

灰度處理圖像之後的結果

接著使用使圖像二元化, 得到一副二元影像 (對於灰度圖像, 每一個像素都有自己的灰度值, 灰度值越高顏色越白, 灰度值越低顏色越黑. 二元化是將大於一定灰度值的像素使用一種顏色填充, 小於一定灰度值的像素使用另外一種顏色填充)

圖像二元化之後的結果

我們的最終目標是提取中間那個零件, 所以還會對圖像的其餘地方進行一定的處理, 這個特徵處理我們暫時不講. 處理之後得到的結果是

特徵選定之後得到的圖像結果

我們發現, 周圍的干擾像素已經被去除, 得到了中間這個零件. 如果我們想要得到零件在這幅圖像中的橫向長度, 那麼可以找到這些像素集合的凸包, 計算凸包的橫向長度即可. 因為零件比較規則, 因此不需要額外的演算法, 可以將凸包大致當作一個矩形

最後來說一說凸包在統計學中的應用. 在對樣本進行統計之後, 通常會得到一副統計圖表, 對圖表的橫軸劃定區域, 計算一定區域內點的集合的凸包, 如果凸包越接近於一個圓, 那麼就說明落在這個區域中的元素可能比較多 (在大量樣本的情況下). 另外, 還可以通過計算全部點的集合的凸包, 來確定這些點落在哪個區域之內