在資料視覺化的場合中,你可能看過使用大小不等的圓,來表現資料在數值上的差異或層次,這類圖表稱為泡泡圖(bubble chart),其中一個有趣的展現方式是,讓圓與圓之間不重疊卻又緊密,可用來構成文字雲或層層嵌套的圖表,看來甚是迷人,這類圖表的共同關鍵字,往往就是「圓堆砌(circular packing)」。

目前,D3.js程式庫已提供了圓堆砌的實現方式,在〈Circular Packing〉就示範了從簡單到複雜的幾種不同實現方式;擅長資料科學領域的Python,也有著circlify這類程式庫,可協助完成基於圓堆砌的計算,以完成後續資料視覺化的需求。

圓堆砌的繪製

若查詢維基百科〈Circular Packing〉條目的話,我們會發現,圓堆砌是幾何學的研究方向,探討如何在指定的面上排列圓,令圓與圓間不重疊且彼此間無法再擴張,相對應的研究是,哪種排列可以得到最大堆砌密度,也就是圓覆蓋的面積與指定範圍面積間的比例。

對於大小相同的圓來說,數學家Axel Thue證明了正六角形密堆砌,也就是以正六角形的六個頂點及中心為六個圓心,六角形邊長為圓直徑,堆砌的結果在各種圓堆砌會具有最大堆砌密度0.9069,證明過程與Voronoi空間分割有關,有興趣的人,可以參考〈六角密堆砌證明及其它〉

進一步地,也有大小不等圓的堆砌研究,例如兩種大小不等的圓,在資料視覺化的場合,我們經常看到的則是隨機大小的圓,依不同的需求,也有著許多分析演算方式,確定需求是必要的。如果想要隨機大小、視覺上看來緊密的圓堆砌?若可以的話,還要能在指定的任意形狀中進行堆砌呢?

D3.js的力模擬器

實現隨機的圓堆砌時,我們直覺上會想到,以隨機位置為圓心,隨機值為半徑建立圓,後續建立的圓必須檢查是否與既有的圓重疊,這個方式是行得通,但速度非常緩慢,原因不僅在既有圓的數量會越來越多,也在於後期想找到可以放置的圓,試誤的次數也會越來越多。

為了避免無止盡地進行試誤,一般而言,我們會設定嘗試次數的上限,一旦到達上限之後就停止,從而導致希望達到的圓數量不足,在〈generative artistry - Circle Packing〉的HTML5實作,就是如此。

有一個折衷的方式,那就是:先隨機產生一組半徑並由大到小排序,從第一個半徑值開始,隨機找一個點作為圓心建立圓,後續的圓必須檢查是否與既有的圓重疊,基本上,後續的圓會越來越小,嘗試失敗的機率小一些,〈Packing circles in a circle〉就是基於此原理並使用Python實作,雖然有機會比方才的方式快一些,但試誤仍然是必需的,而且,設定試誤上限從而導致希望達到的圓數量不足,這個問題還是存在。

那麼,方才D3.js的實現方式呢?它使用d3-force,這是個物理模擬粒子系統,可以將圓看成是粒子,賦予各圓速度,圓彼此間可指定斥力與碰撞等屬性,在〈Most basic circular packing〉示範了最基本的一組圓,起初圓彼此重疊,到最後因互斥而彼此不接合,這種實現的好處是,可以在一開始的圓數量與大小,最後達到緊密的圓堆砌。

想自行實現這樣的物理模擬也不是難事,作法類似先前專欄〈實現差別生長演算〉談到的力模擬,這只需要區隔(seperation)的指向力,然而,要增加圓與圓間,以及圓與邊界間的碰撞偵測。

〈Controlled Circle Packing with Processing〉就提供了Processing的實作方式,由於是基於物理模擬,還可以用滑鼠點選新增圓,新的圓會自動找到合適的位置。為了瞭解每段程式碼的作用,我重構一個p5.js的版本,有興趣的人可以參考。

基於力的模擬,還可以模仿出自然風格,最初的一組圓半徑可以都相同,然而每次的迭代過程,圓排斥後的新位置,會用來計算Perlin雜訊,得到的雜訊值會作為新的半徑值,Perlin雜訊會有高低之分,圓就會有大小之別,從而構成或密或疏的堆砌結果,Perlin雜訊是連續的,最後結果就像是翻攪肥皂泡泡水後的結果。

基於Delaunay三角分割

方才談到數學家Axel Thue證明正六角形密堆砌,擁有最大堆砌密度的方式,是基於Voronoi空間分割,這就讓我聯想到,可否基於分割後的空間來進行圓堆砌?好處是可以使用點來指定範圍甚至形狀,而且空間分割後會是各個凸多邊形,問題也就可以切分為,在凸多邊形中進行圓堆砌的子問題。

在凸多邊形當中,如果我們尋找最大圓,基本方式是找Chebyshev中心,然後計算中心至邊的距離作為半徑,不過除了最大圓之外,如何在凸多邊形的其他區域堆砌小圓,計算上都會比較麻煩。

為了簡化問題,我轉而思考與Voronoi空間分割具有對偶關係的Delaunay三角分割,如此一來,問題可以切分為:在三角形中進行圓堆砌的子問題。

方式之一是計算三角形內接圓,這是個簡單任務,至於內接圓以外的圓堆砌問題,我們可以沿著內接圓心至三個頂點間的直線,逐一放置圓,由於Delaunay三角分割後的三角形,可能會有狹長形,為了避免生成過小的圓,可以設定圓的最小半徑。

要在三角形中進行圓堆砌,另一個方式是將既有的三角形再細分,然後只求切分後三角形的內接圓,不過,若原三角形過於狹長,切分後再放置的圓就會過小,而且彼此間的距離過疏;然而,我們可結合方才的做法,也就是進一步沿著圓心至三個頂點間的直線逐一放置圓,密度上會比第一種做法高,而且,外觀上會呈現Voronoi的結果。

在我撰寫的〈experimental〉,可以看到circle_packing為開頭的三個.scad原始碼,分別代表方才三種方式的OpenSCAD實作,大家可以試著運行看看,比較三種方式的執行結果。

只要Delaunay三角分割的演算夠有效率,以上三種圓堆砌的方式,在速度上就會有相對應的表現,因為一旦三角分割完成,就沒有試誤的問題,而且可以自行指定點的位置,這就表示可以控制圓堆砌後的樣貌,例如〈Golden Spiral & Circle packing 〉就示範了,如何結合黃金螺線來構成銀河系般的圓堆砌效果。

圓堆砌的應用

我會開始研究圓堆砌,一開始是看到基於圓的文字雲,基本作法是將圓堆砌結果依半徑排序,如此就可以與文字雲的關鍵字數值進行配對。

正如一開始談到的,圓堆砌在資料視覺化有著廣泛的應用,其實,也會用於影像處理(通常作為濾鏡),在生成藝術上也經常可見,例如,在Google圖片搜尋circle packing,就會看到各式各樣的應用,結合data visualization關鍵字,可以看到更多資料視覺化的案例,從中也可以找到相關實現範例。

當然,隨機圓堆砌還有其他許多的呈現與處理方式,即便是等圓的堆砌,也有許多值得研究的主題,大家也可以從MathWorld的〈Circle Packing〉,從中進行探索。

專欄作者


熱門新聞

Advertisement