10561 怎樣在球面上「均勻」排列許多點？（下）

。

在這篇文章中，我們首先來分析一下公式（4，5）產生的平面點陣是怎樣受轉角

$\phi$

影響的，然後把結論拓展到公式（1~3）產生的球面點陣上去。

★

$\begin{align} z_n &= (2n-1)/N - 1 & (1) \\ x_n &= \sqrt{1 - z_n^2} \cdot \cos(2 \pi n \phi) & (2) \\ y_n &= \sqrt{1 - z_n^2} \cdot \sin(2 \pi n \phi) & (3) \end{align}$

，

$\begin{align} x_n &= \sqrt{n} \cos(2\pi n \phi) & (4)\\ y_n &= \sqrt{n} \sin(2\pi n \phi) & (5) \end{align}$

分析的過程主要依賴連分式（Continued fraction），在此先列舉一些連分式的基礎知識。任何一個實數

可以展開成如下形式的連分式：

其中各層的分子均為 1；

是

的整數部分（取下整）；其它的各個

都是正整數。如果

是有理數，連分式就會像上面一樣是有限的；如果

是無理數，連分式則是無限的。上面的式子寫起來很麻煩，常常簡記為

$[a_0; a_1, a_2, \ldots, a_n]$

，即寫成數列的形式，

也稱為連分式的項。

舉幾個例子：有理數 10/23 寫成連分式是

$0 + \frac{1}{\displaystyle 2 + \frac{1}{\displaystyle 3 + \frac{1}{3}}}$

，是有限的，簡記為

。而黃金分割比

$\phi = (\sqrt{5} - 1)/2 \approx 0.618$

寫成連分式是

$0 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{\ddots}}}}$

，是無限的，簡記為

$[0; 1, 1, 1, \ldots]$

。連分式的項不一定有規律，例如圓周率

$\pi$

的連分式為

$[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, \ldots]$

（A001203 - OEIS）。

把

的連分式在某一項處截斷，即可得到

的一個有理逼近，稱為

丟番圖逼近

（Diophantine approximation）。例如，把

$\pi$

的連分式截斷為

，則可以得到「約率」22/7；截斷為

，則可以得到「密率」355/113（請讀者自行驗證）。一般地，若在連分式中保留到

這一項，化簡後可以得到最簡分數

，其中分子和分母可以透過以下的遞推式得到：

★

$\begin{align} p_k &= a_k p_{k-1} + p_{k-2} & (6) \\ q_k &= a_k q_{k-1} + q_{k-2} & (7) \end{align}$

遞推式的初值為

$p_0 = a_0, q_0 = 1; p_{-1} = 1; q_{-1} = 0$

。

丟番圖逼近在某種意義下是

的

最佳逼近

。這裡「最佳」的意義是：定義

的逼近誤差

$\epsilon_k = |q_ka-p_k|$

，則不存在另一個分母不超過

的分數，逼近誤差比

$\epsilon_k$

小。如果把

的各個丟番圖逼近排成一個數列

$\frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \ldots$

，則各項的逼近誤差

$\epsilon_0, \epsilon_1, \epsilon_2, \ldots$

是遞減的。

（注意，在此我們把誤差定義成了

$\epsilon_k = |q_ka-p_k|$

，而不是

$\left| a - \frac{p_k}{q_k} \right|$

。前一種定義更適合本文的討論，因為若把

看成每產生一個點旋轉的圈數，那麼誤差

$\epsilon_k$

的含義就是：連續產生

個點轉過的總圈數，與

圈差了多少。）

有了上面的基礎知識，我們來分析一些平面點陣。比如，我們取

$\phi = 0.617$

。作為準備，我們把 0。617 表示成連分式：

，並計算出它的各階丟番圖逼近及誤差：

下面是

$\phi = 0.617$

時，最靠近原點的 400 個點。可以看到，在原點附近，點陣形成螺旋，共有 13 條旋臂；而在外圍，點陣呈放射狀，共有 47 條射線。不難發現，13 和 47 都是丟番圖逼近的分母。我們把螺旋、射線這種有規律的排列稱為「

模式

」（pattern），並用丟番圖逼近來命名，例如本圖中的兩種模式分別稱為 8/13 模式和 29/47 模式。

200 號點大約處在兩種模式的分界線上。觀察 200 號點附近的情況：離它最近的點有 153 號、187 號、213 號、247 號，它們的編號與 200 的差恰好也是 13 和 47。把這些點用線連起來，可以發現編號公差為 13 的點列（174 - 187 - 200 - 213 - 226）落在一條 8/13 模式（螺旋）上，而編號公差為 47 的點列（106 -153 - 200 - 247 - 294）落在一條 29/47 模式（射線）上。之所以 8/13 模式產生了明顯的旋轉，而 29/47 模式不產生明顯的旋轉，是因為 29/47 的逼近誤差遠小於 8/13 模式，即：連續產生 47 個點轉過的角度與 29 圈的誤差，遠小於連續產生 13 個點轉過的角度與 8 圈的誤差。另外還可以發現，在 200 號點附近，8/13 模式上的點的間距隨點的編號在增大，而 29/47 模式上的點間距在減小。因此，隨著點編號的增大，8/13 模式越來越模糊，而 29/47 模式越來越清晰，導致螺旋被射線所取代。

有人會說：「140、166、234、260 這幾個點，離 200 號點的距離也不遠呀！」這幾個點的編號與 200 的差是 34 和 60 —— 發現了沒有，它們是 13 與 47 的和與差！把它們對應的 21/34 模式和 37/60 模式也畫出來可以發現，這些模式上點的間距比 8/13 模式和 29/47 模式大，因此不如後者顯著，可以忽略。這正是因為 21/34 和 37/60 不是 0。617 的最佳逼近 —— 21/34 的逼近誤差大於 8/13，37/60 的逼近誤差大於 29/47。

經過上面的分析，我們可以得到如下的經驗：

每個最佳逼近

，對應著一種比較顯著的模式；

模式上的點間距越小，模式越顯著；

同一個模式上的點間距隨位置會發生變化，導致最顯著模式的切換。

為了發掘模式切換的規律，下面我們來定量地計算模式上點的間距。

考慮

號點，以及它所處的

模式。在該模式上，下一個點的編號是

。把這兩個點的編號代入公式（4，5），就能得到兩點的座標和距離了。但是這樣得到的公式太複雜，我們換一個角度來思考。

號點距原點的距離為

$r=\sqrt{n}$

，在

號點附近，編號每增加 1，距原點的距離增加

$\frac{\mathrm{d}r}{\mathrm{d}n} = \frac{1}{2\sqrt{n}} = \frac{1}{2r}$

。當

$q_k \ll n$

時，從

號點到

號點，徑向距離就是

$\frac{q_k}{2r}$

。而從

號點到

號點轉過的總圈數為

$q_k\phi$

，它大約是

整圈，誤差為

$\epsilon_k = |q_k \phi - p_k|$

，於是這兩點間的切向距離就是

$2\pi r \epsilon_k$

。當

$\epsilon_k \ll 1$

時，可以把這個切向距離看成與徑向垂直的直線段，由此得到

模式在距原點

處的點間距：

★

$\begin{align} d_k &= \sqrt{\left(\frac{q_k}{2r}\right)^2 + (2\pi r \epsilon_k)^2} & (8) \end{align}$

這裡我選擇距原點距離

而不是點的編號

為自變數，顯得更直觀。

如果選定某一種模式（即固定

$q_k, \epsilon_k$

），則

是

的函式。根號下的第一項隨

遞減，第二項隨

遞增，整體上則呈現先減後增的「V」字形。

的最小值為

$d_{k,\min} = \sqrt{2 \cdot \frac{q_k}{2r} \cdot 2\pi r \epsilon_k} = \sqrt{2\pi q_k \epsilon_k}$

，它在

$\frac{q_k}{2r} = 2\pi r \epsilon_k$

即

$r_{k,\min} = \sqrt{\frac{q_k}{4\pi\epsilon_k}}$

處取得。由此可知，從原點向外，各種模式會先變得越來越顯著，這是因為半徑

的增長越來越慢，使得模式上的點靠得越來越近；然後會變得越來越模糊，因為轉角

$q_k\phi$

與

整圈的微小偏差被越來越大的半徑放大成越來越遠的距離。這個規律也可以通俗地描述成：每個模式先是形成越來越清晰的射線，然後射線彎曲成螺旋，最後「被風吹散」。根據

$r_{k,\min} = \sqrt{\frac{q_k}{4\pi\epsilon_k}}$

，

值越大的模式，分母

越大，而誤差

$\epsilon_k$

越小，故使得該模式最顯著的半徑

$r_{k,\min}$

越大。也就是說，

值越大的模式，就會在離原點越遠處顯現，這造成了模式的交替。

我們用上面

$\phi = 0.617$

時的平面點陣檢驗一下上面的結論。下表計算了各個模式最顯著處的半徑

$r_{k,\min}$

（稱為「

最顯著半徑

」）和此處的點間距

$d_{k,\min}$

（稱為「

最密點間距

」）。

$k \le 5$

的各個模式（包括 0/1， 1/1， 1/2， 2/3， 3/5， 5/8），誤差都太大，同時

$r_{k,\min}$

太小、

$d_{k,\min}$

太大，所以在圖上顯現不出來。8/13 模式在半徑約為 7 處（50 號點附近）最顯著，這與圖示相符；29/47 模式在半徑約為 61 處最顯著，但前文的圖中只畫出了半徑為 20 以內的部分，所以這一點就看不出來了。從表中可以看到 8/13 模式的最密點間距為 1。310，而 29/47 模式的最密點間距為 0。543，所以若把點陣繼續畫下去， 29/47 模式會變得比 8/13 模式更顯著。最後還有一個模式 617/1000，它將在 29/47 模式消散後顯現出來。並且因為 617/1000 就是

$\phi$

的精確值，此模式將永不消散，並越來越顯著。

令

$d_k = d_{k+1}$

，可以求出模式

向

$p_{k+1}/q_{k+1}$

過渡處的半徑。仍然研究

$\phi = 0.617$

的例子，取

，可以求得模式 8/13 與 29/47 之間的過渡發生在半徑為 13。090 處（170 號點附近）。我們前面觀察過的 200 號點離這兒也不遠，從圖上可以看到這裡確實發生了模式的過渡。同樣，取

，可以求得模式 29/47 到 617/1000 的過渡發生在半徑為 281。939 處，也就是說，要畫到 80000 號點，才能觀察到這個過渡。

為了讓大家一飽眼福，我把點陣畫到了 30 萬個點，並截取了橫軸正半軸周圍的區域性。請點開大圖觀察，否則圖片上會產生摩爾紋（Moiré pattern）。從圖中可以清楚地看到原點附近的 8/13 模式（螺旋），它在半徑為 13 處過渡為 29/47 模式，後者在半徑 60 左右最顯著，且比 8/13 模式更顯著。29/47 模式的豎紋在半徑 250 處基本消散，到半徑 350 處開始產生 617/1000 模式的橫紋。

當

$\phi = 0.617$

時各模式的點間距隨半徑的變化可以總結成下圖，注意橫、縱軸均為對數刻度。從圖中可以清楚地看出 8/13、29/47、617/1000 三種主要模式的最顯著半徑、最密點間距，以及模式之間過渡的位置。一圖勝千言，下文中我將主要使用這種圖（稱為

模式圖

）來說明模式的變化。

下面，我們來探究連分式中項的大小對模式的影響。我們選取

$\phi = \pi - 3 \approx 0.1416$

。這個值的連分式為

$[0; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, \ldots]$

，其中 15、292 這樣的大項，會帶給我們新的發現。

先畫個點陣看看：

圖中可以觀察到兩種模式：中心的模式有 7 條腿，外圍的模式腿太多了，數不清。

按上文給出的公式，計算

$\phi$

的丟番圖逼近序列、各個逼近的誤差，以及各個模式的最顯著半徑和最密點間距，並作出模式圖，如下所示。

從模式圖中觀察到，1/7 和 16/113 這兩個模式十分顯著，它們在半徑為 30 處左右發生過渡，這與點陣圖完全相符。注意，在這兩個模式發生過渡的時候，有一個 15/106 模式被完全掩蓋過去了。16/113 這個模式會一直持續到半徑接近 10000 的時候才會過渡到 4703/33215 這個模式，哪怕畫大圖也無緣查看了。

1/7 和 16/113 這兩個模式，正是連分式中 15 和 292 這兩個大項產生的。這裡的「大」，其實並不是指絕對數值很大，而是指相對於周圍的項來說很大。回憶模式最密點間距公式

$d_{k,\min} = \sqrt{2\pi q_k \epsilon_k}$

，其中

是遞增的，

$\epsilon_k$

是遞減的。再回憶丟番圖逼近中分母的遞推式

$q_k = a_k q_{k-1} + q_{k-2}$

：當

是一個大項時，

與

$q_{k-1}$

相比，就會猛然增大。但當

很大時，若把連分式截斷至

$a_{k-1}$

，那麼捨棄的

$\frac{1}{a_k + \ddots}$

就很小，所以

$\epsilon_{k-1}$

與之前的

$\epsilon_{k-2}$

相比就會猛然減小。誤差的減小比分母的增大早一步發生，這就使得

$d_{k-1, \min}$

明顯小於相鄰模式的最密點間距，產生一個十分顯著的模式

$p_{k-1}/q_{k-1}$

。另外觀察模式圖可以發現，各個模式的「V」字形的兩臂斜率都是一樣的，所以越是顯著的模式，覆蓋的半徑範圍往往也越大。

上面的計算告訴我們，連分式中每出現一個大項，在它之前截斷就會產生一個十分顯著的模式。那麼，若要不產生顯著的模式，連分式中就不能出現大項，所以令所有的

都等於 1 就是最好的選擇了。這就給出了最優的轉角 —— 黃金角。當

$\phi = (\sqrt{5} - 1) / 2 \approx 0.618$

時，模式圖如下（注意，各模式的分子、分母都是菲波那契數）：

可以看出，各個模式的顯著程度都差不多，並且模式切換頻繁。觀察下面點陣圖的中心，似乎能看出許多層層疊疊的花瓣，這正是模式頻繁切換的體現。到了外圍，模式持續的長度就長了些（注意模式圖的橫座標是對數刻度），能看出一些模式了；這些模式都呈螺旋而不是射線狀，因為各階丟番圖逼近的誤差都不小。

模式切換頻繁正是點陣混亂和密集的原因：混亂是因為任何一種模式（規律）都不會持續很久；密集是因為在任一半徑處，都並沒有單獨一種模式的點間距比別的模式小得多，所以不會出現大的縫隙。

可以證明，對於黃金分割比

$\phi$

，丟番圖逼近

的誤差

$\epsilon_k \approx \frac{1}{\sqrt{5}q_k}$

，於是各模式的最密點間距就都約等於

$\sqrt{2 \pi / \sqrt{5}} \approx 1.676$

。這其實是用形如（4，5）的公式能生成的點陣中，模式最密點間距的「上界」—— 加引號是因為，可能出現個別模式的最密點間距大於這個值，但這樣的個別模式至多隻有有限個。

話說回來，公式（4，5）並不是平面上點陣密鋪問題的最優解。在保證同樣點陣密度（每

$\pi$

面積上有一個點）的情況下，正方形網格的最密點間距是

$d_\text{square} = \sqrt{\pi} \approx 1.772$

，而最優解六邊形網格的最密點間距是

$d_\text{hex} = \sqrt{2\pi/\sqrt{3}} \approx 1.905$

（如下圖）。這兩種網格滿足均勻、密集，但不滿足混亂，因為同一種排列規律遍佈了整個平面。從 1。905 到 1。676，就是「混亂」需要付出的代價。

現在來看一下我在試探過程中發現的另一個不錯的

$\phi$

值：

$\phi = \sqrt{2} - 1 \approx 0.414$

。此時的點陣圖與模式圖如下：

把

$\phi = \sqrt{2} - 1 \approx 0.414$

寫成連分式，是

$[0; 2, 2, 2, \ldots]$

，各項都相等，所以沒有「大項」。模式圖上也顯示出，各個模式的最密點間距都相等，且模式切換頻繁。但是，與黃金分割比相比，

$\phi = \sqrt{2} - 1 \approx 0.414$

的各個模式的最密點間距偏小（約為

$\sqrt{\pi/\sqrt{2}} \approx 1.490$

），故模式還是稍微明顯了一些；模式之間的切換也不如黃金分割比頻繁（注意兩張模式圖的橫、縱座標範圍是相同的）。黃金分割比以微弱的優勢戰勝

$\sqrt{2} - 1$

。

上面我們詳細地分析了

$\phi = 0.617,\,\, \pi - 3,\,\, \frac{\sqrt{5} - 1}{2},\,\, \sqrt{2} - 1$

各值時的點陣圖與模式圖，得到了如下一些結論：

每個點轉過的圈數

$\phi$

的每個丟番圖逼近對應著一種模式；

隨半徑增加，每種模式先變得顯著，然後消散，存在一個

最顯著半徑

；

分母越大的模式，最顯著半徑也越大，所以各模式會

依次顯現

；

當連分式中有大項的時候，

大項之前

的那個丟番圖逼近對應的模式會非常顯著，且持續的長度也很長；

黃金分割比的連分式中所有項都是 1，這導致

沒有顯著的模式

且

模式切換頻繁

，於是點陣顯得密集而混亂。

終於到了把結論拓展到球面的時候了。在平面上，我們選擇了到原點的距離

作為自變數；在球面上，我們選擇緯度

$\theta$

作為自變數。設整個點陣的點數為

，考慮模式

上的

號點和

號點。在緯度為

$\theta$

處，這兩個點在經線方向上的距離為

$\frac{2q_k}{N\cos\theta}$

，在緯線方向上的距離為

$2 \pi \epsilon_k \cos\theta$

。由此可得

模式在豎座標為

處的點間距：

★

$\begin{align} d_k &= \sqrt{\left(\frac{2q_k}{N \cos\theta}\right)^2 + (2\pi \epsilon_k \cos\theta)^2} & (9) \end{align}$

此式的最小值為

$d_{k,\min} = \sqrt{8\pi q_k \epsilon_k / N}$

，在

$\theta_{k,\min} = \pm \arccos\sqrt{\frac{q_k}{N\pi\epsilon_k}}$

處取得。作為對比，平面上

模式的最小點間距為

$d_{k,\min} = \sqrt{2\pi q_k \epsilon_k}$

，在

$r_{k,\min} = \sqrt{\frac{q_k}{4\pi\epsilon_k}}$

處取得。兩個最小點間距的公式是相似的，只是係數不同；但最顯著位置的公式則有形式上的差別：球面上的公式多了個反餘弦。反餘弦函式是單調遞減的，且定義域有限，這說明，各個模式是從兩極到赤道依次顯現的，而有些高階的模式，哪怕到了赤道處也來不及顯現。除此以外，平面點陣的各個結論都適用於球面點陣。

例如，下面是

$\phi = 0.617$

時，在球面上取 1000 個點生成的點陣，以及相應的模式圖。可以看到 8/13 模式（螺旋）在緯度 64 度時最顯著，並在 35 度左右過渡成 29/47 模式（射線）。但在低緯度區域，8/13 模式並沒有消散得很厲害，它與 29/47 模式共同組成了方形網格。617/1000 模式來不及顯現出來。

下圖是

$\phi$

取黃金分割比時，由 1000 個點組成的球面點陣和模式圖。與平面的情況類似，這裡沒有特別顯著的模式，且模式切換頻繁，所以點陣的分佈密集且混亂。不過，由於 arccos 定義域的影響，21/34 這個模式從北緯 40 度一直到南緯 40 度都是最顯著的；但與此同時，相鄰的 13/21 模式和 34/55 模式的顯著程度也差不多，所以在低緯度區域的點陣中能找到正方形或六邊形網格的影子。

小蜜蜂問答

小蜜蜂問答

10561 怎樣在球面上「均勻」排列許多點？（下）

推薦文章

小蜜蜂問答

小蜜蜂問答

10561 怎樣在球面上「均勻」排列許多點？（下）

相關文章

數顯表的使用方法和技巧？

31歲的別稱？

路亞釣鰱鱅漂相看不清？

為什麼a2也是單項式？

推薦文章