對於初學程式的人來說,透過一些繪圖的處理來認識程式設計的元素,是常見的作法,例如,在接觸遞迴觀念時,也經常透過碎形圖案的繪製來熟悉遞迴的實作,而我這次想特別介紹的希爾伯特曲線(Hilbert curve),就是常見的碎形圖案之一。

基本上,這種曲線是一種碎形曲線,若要從程式設計上,透過遞迴來實現,我們可使用L-system正式地描述,而這亦是Google S2幾何程式庫中空間索引演算的原理。

希爾伯特曲線

希爾伯特曲線不單只是個美麗的圖像藝術,它與皮亞諾曲線(Peano curve)、Z階曲線(Z-order curve)等,都想解決一個數學難題:可否使用一條無限長的線,連接空間中全部的點?

不過,開始介紹希爾伯特曲線之前,我們可以先來談談皮亞諾曲線。它是Giuseppe Peano在1890年提出,依照當時大家對於維度的認識而言,曲線的維度是1,正方形的維度是2,而「線」不可能填滿正方形,然而,皮亞諾曲線在極限情況下,卻是個可以填滿正方形的曲線,也就是說,若以碎形維數計算(可參考先前專欄〈遞迴、碎形與數學〉),皮亞諾曲線的維度會是2。

至於希爾伯特曲線,是由David Hilbert在1891年提出,也是個可以填滿正方形的曲線,維度是2,與皮亞諾曲線相比之下,差異之一在於,希爾伯特曲線的每個頂點可屬於一個小正方形。

例如,一階希爾伯特曲線是個通過四個網格中心點的⊓曲線,二階是透過將一階的曲線位移、旋轉,畫出四個曲線並頭尾連接而成,依此類推,三階是透過將二階的曲線位移、旋轉、頭尾連接而成。

顯然地,上述的每一階都是小任務,程式設計上,我們可以透過遞迴來簡單地實現,相關圖片與程式碼可參考〈希爾伯特曲線〉

我在先前專欄〈碎形與L-system〉中談過,若想以簡約語言來記錄碎形生成過程,可以採用L-system制定正式文法。因此,若公理為L,轉動角度為90,那麼,希爾伯特曲線的L-system衍生規則是「L→−RF+LFL+FR−」與「R→+LF-RFR-FL+」。

打造希爾伯特龍

最初提出的希爾伯特是二維版本,實際上,也可以擴充為三維曲線。

例如,一階可由z軸的上下兩個曲線,連接上下同一個(x, y)座標的頂點來構造;類似的道理,二階是透過將一階的曲線旋轉、位移與連線,三階是透過將二階的曲線旋轉、位移與連線,如果要使用L-System描述,可參考〈lsystem3_collection〉

而三維的希爾伯特曲線,理論上,可填滿整個立方體,例如,在〈Three.js WebGL 3D Hilbert curve〉中,就有三維版本的希爾伯特曲線的示範,其中,亦有平滑版本的曲線,於是,這就讓我有了個靈感:如果這曲線是一條填滿整個立方體的龍,而且,還可以列印出來的話,會有多酷呢?

為了能構造龍身,曲線必須連續,而希爾伯特曲線滿足這個條件;另一個問題是,原本的希爾伯特曲線轉角處是90度,而作為一條龍,龍身直接轉90度可不好看,因此我必須先令曲線平滑,這時,我可以使用貝茲曲線(Bezier curve),取轉角兩側兩個點,加上轉角處45度往外延伸上的一個點,就有了三個控制點,透過貝茲曲線公式內插,就可以求得平滑的希爾伯特曲線。

為了令龍更有真實感,龍身必須隨著曲線轉動,因而不能單純連接曲線上每個點,這需要有個路徑推移的模組,可以計算龍腹與龍背等必須轉動的角度。由於L-System、貝茲曲線與路徑推移模組,在我的dotSCAD程式庫中都有了,因此,實現第一個版本的希爾伯特龍,並不困難。

只不過,在第一個版本當中,龍身上的麟片過多,算圖耗費時間很長(十幾個小時),而且龍麟因為龍身的轉動,會產生各個角度,對熔融沉積成型(FDM)的3D列印機來說,列印上難度太高了,因而我又打造了第二個低面數的希爾伯特龍,列印出來算是帥氣,也有了幾分幾何之美。

空間填充曲線

不管是二維或三維,都可以使用一條希爾伯特曲線來填滿,意味著希爾伯特曲線是一種空間填充曲線(Space-Filling Curve),代表了二維或三維的資訊,可以使用這類曲線來編碼,換言之,這類曲線具有「降維」的特性。

例如,在地圖應用程式中,若使用者想搜尋目前位置附近的餐廳,透過查找資料庫中全部的餐廳,並且計算出相對位置小於某範圍的方式,雖然可行,然而,會因資料量過於龐大而顯得沒有效率;此時,如果我們可以將地圖切割為小範圍的格子,並且為這些格子編上索引,之後在查找資料時,就可以根據這些索引,只搜尋格子內的資料,而能增加查詢效率。

這時就會有個疑問,為什麼要用希爾伯特曲線?其他曲線不行嗎?我在先前專欄〈隨機演算之美〉中提過的哈密頓路徑(Hamiltonian path),不也是在求不重複地走過每個網格的路線?甚至更簡單地,逐列由下而上繪製S形曲線,不也能填滿整個空間嗎?

要能做為有效率的空間索引曲線,降維只是其中一個要求,因為,希爾伯特曲線還有的另一特性是「穩定」,也就是在階數變化時,某點在曲線中相對的位置,不會有過劇的變化。

例如,我們在〈高效的多維空間點索引算法〉中,就可以看到:如果使用S形曲線的話,階數變化時,某點的位置會是忽左、忽右地變化;然而,若是希爾伯特曲線,變化就會很小。

在該篇文件中,我們也可以看到,Google的S2 Geometry程式庫中,是基於希爾伯特曲線進行空間索引;此外,我們還可以看到:Geohash採用的Z階曲線也是一種空間索引,而且,它具有一個特性:某點附近的區域,編碼後的雜湊值總會有相同的前置,而且,相同的前置越長,表示越接近,這就適合用來快速搜尋鄰近的區域。

出自好奇的一連串探索

會有這一連串的探索,主要是來自我實現出希爾伯特龍後的一個好奇:希爾伯特曲線最初是為了什麼而發明出來的?

事實上,常作為遞迴練習對象的科赫曲線(Koch curve)、龍曲線(Dragon curve)、謝爾平斯基曲線(Sierpiński curve)等,其實,也都是空間填充曲線,或許各自去探究的話,也都會有各個有趣的事物與應用。

除此之外,我還有一個有趣的事想跟大家分享。據說有個遊戲玩家運用了希爾伯特曲線,將《薩爾達傳說曠野之息》的完成度,從98.59%拉到100%,有興趣的話,可參考〈Using Hilbert Curves to 100% Zelda〉

看來這類空間填充曲線真有其意想不到的用途,不只是畫出來好看而已呢!

作者簡介


Advertisement

更多 iThome相關內容