從凹包到alpha shape

在二維平面散布一組點，如果要建立一個殼（hull）來圍住這些點（三個點以上，因為兩點是退化為線），殼的頂點必須來自於被散布的點，此時，我們該怎麼做呢？

將點看成是釘在板子上的釘子，要建立這樣的殼，最簡單的方式就是撐開橡皮筋至能涵蓋全部釘子，套上去之後，放開橡皮筋，自然而然地就能構成一個殼。

隨機散布點的殼

透過套橡皮筋的方式形成的殼，會是各種殼裡周長最小的殼，它一定是個凸多邊形，也就是邊不會自我相交，內角都小於或等於180度、內部沒有洞的多邊形，稱為convex Hul，中文常譯為「凸包」或「凸殼」。

由於凸包目的明確，建立的殼就是凸多邊形，只有一種可能，在演算法上，已有不少實現方式，有興趣的人可參考〈Convex Hull〉裡的說明與範例。事實上，凸包有許多的應用，在一些場合裡，使用hull這個單字時，通常就是指建立凸包。

使用一組點所建立而成的殼，也可以是凹多邊形，亦即至少有一個內角大於180度、小於360度、內部沒有洞的多邊形，稱為concave hull，中文常譯為凹包或凹殼；如果在一組點裡面，某些點明顯密集地構成線狀分布，許多人可能會想使用這些點來構成凹包，作為尋找輪廓線的方式之一。

然而，從一組點建立凹包，有多種可能性，不同人依據其目的的差異，會有各自的包法，例如，方才談到「密集」的定義到底為何呢？在人類肉眼判斷下，每個人對密集的感受並不相同，也就是單就凹包這個詞而言，需要進一步的變數定義，才能確定性地對一組點建立凹包。

認識alpha shape

我們如果試著去搜尋凹包的演算，在找到的文件中，常會看到alpha shape名詞。基本上，它是Herbert Edelsbrunner在1983年定義出來的，其中的alpha就是個決定形狀的變數，變數值會是個實數，在適當的點集合與alpha值下，確實能構成凹包形狀，而這也是為何它經常與凹包相伴出現的原因。

不過，別誤會了，alpha shape並非用來定義凹包，因為「凸包必定是alpha shape」（然而alpha shape不一定是凸包）。

實際上，alpha定義了一個半徑為1/alpha的圓（若alpha為負值，會是半徑-1/alpha圓的互補），從點集合建立的形狀，各邊會是點集合裡的兩個點構成，若用半徑為1/alpha的圓去套構成各邊的兩個點，不會有第三個點出現在圓內，這樣的形狀就是alpha shape。

alpha變數可能是大於零、等於零或小於零的值，在alpha大於零的情況下，我們可以想像：有個半徑1/alpha的圓在點集合外滾動，alpha越大圓越小，滾出來的形狀就越能深入點集合，也就有可能構成不同形狀凹包，1/alpha越小圓越大，越難滾入點集合，小於某值時完全滾不進點集合時，滾出的形狀就是凸包，alpha為0時是個無限大的圓（一個無限大的半平面），滾出來的形狀必然就是凸包。

這種構造alpha shape的方式被稱為滾球法，實作時通常指定圓半徑r，選擇點集合裡任兩點，如果距離大於限定的球直徑（r*2）可以直接略過（顯然球能滾入兩點之間），否則就找出半徑為r且兩點在圓周上的兩個圓形，若圓形內不包含點集合裡兩點外的其他點，這兩個點就構成alpha shape的邊，有興趣看看程式實作的話，大家可參考〈ALPHA SHAPES〉。

然而，從演算法也可看出邊與邊連接後實際建立的形狀，可能會是有洞多邊形（因此方才說到，alpha shape並非用來定義凹包），甚至可能是分離的多個形狀，某些程度上會是分群（clustering），確實！也有人將alpha shape作為分群的方法之一。

另一方面，不少文件會將圓半徑稱為alpha，嚴格來說，這並不符合alpha shape裡的alpha定義，只是就程式實作而言，無傷大雅，目的也可達到罷了。

Delaunay三角與alpha complex

若點集合的數量大，滾球法的演算會缺乏效率。從alpha shape的定義當中，我們可以知道，點集合構成的alpha shape是包含在凸包裡的形狀，那麼，我們有辦法從凸包得到alpha shape嗎？若我們朝這個方向去尋找方案，經常會談到Delaunay三角分割。

我在先前專欄文章〈Voronoi與Delaunay〉談過，從點集合進行Delaunay三角分割後，每個三角形的外接圓不會包含頂點以外的其他點；另一個事實是，若將全部三角形進行聯集，會得到點集合的凸包，只不過若單純要建立凸包，求Delaunay三角之後再進行聯集，並沒有效率。

然而，如果已經建立了Delaunay三角，若三角形的外接圓不大於某值就保留下來，最後留下的三角形在聯集後，看來似乎是個α shape，由於這時只需要判斷外接圓大小，速度比較快，對此，在〈alpha shape from the Delaunay triangulation〉有個Python實作，可以參考看看。

另一個方式是，對於Delaunay三角化後構成凸包的邊，若小於某長度，包含該邊的三角形就予以保留，由於有些邊界的三角形被去除，剩餘的三角形會有新的形狀邊界，這時依以上步驟重複迭代，直到沒有可去除的三角形，最後留下的三角形聯集，似乎也是個α shape，只不過這必須判斷哪些是邊是在凸包邊界，處理速度會變得稍慢，程式實作部分可參考〈淺議凹包算法〉。

嚴格來說，這些留下來的三角形，組成了alpha complex，維基百科條目〈Alpha shape〉提到：組成alpha complex的邊或三角形，若有能包含邊或三角形的圓，其半徑最大不能超過1/alpha；alpha complex與alpha shape非常相似，差別在於前者是由多邊形的邊組成，後者是由可構成圓弧的邊組成。

Herbert Edelsbrunner在1995年表明，alpha shape與alpha complex在拓樸學上具有等價關係，而且，後續也使用alpha shape來代表alpha complex各細胞聯集後的結果；也就是說，就目的與定義而言，基於Delaunay三角求得alpha complex後予以聯集，是可以視為alpha shape。

事實上，我們只要使用有效率的Delaunay三角分割演算，求alpha shape時的效率會比滾球法來得好，而方才兩種演算方式可視為取不同的alpha，過濾到不合格的三角形，得到的形狀也就不同

想要凹包？alpha shape？

確實地，在適當的點集合與alpha選擇下，無論是基於滾球法，或者是基於Delaunay三角分割，求得的alpha shape會是凹包；然而，正確來說，alpha shape是基於點集合，建立一組邊的方式，並不是專門用來建立凹包的方式。

如果我們對於點集合的認識不夠（對資料沒有足夠瞭解），沒有選擇適當的alpha，單是想建立腦海裡想要的凹包，可能只是在賭運氣，畢竟也有可能我們需要的並非alpha shape。

這就讓我想起先前專欄文章〈別對問題存在幻想〉最後談到的：如果從一開始就無法定義問題，或者對解決方案的定義不清不楚，計算後的執行結果不正確，也只是剛好而已。或許我們需要定義的變數不只是alpha，可能還有beta等其他變數呢！