在二維平面散布一組點,如果要建立一個殼(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等其他變數呢!

專欄作者

熱門新聞

Advertisement