一次有趣的面試（下）

06-04

一次有趣的面試（下）

續上：

周六發表了文章，一次有趣的面試（上）就趕回寢室dota2了，最近又沉迷了起來。不過一些很精彩的評論讓我很想再把這個球面採樣的問題深入一些，所以原定的（下）是用來寫面試第三題的，現在繼續討論這個球面採樣的問題。

題解：

<一> 高斯分布：

在上一篇中，最後在面試官的解答下，我們完成了一個蒙特卡洛模擬高斯分布的方法，去完成了對立方體內單位球的均勻採樣，然後通過把球體內部的點映射回球面，即可完成對球面的均勻採樣。

def sphere_3(radius): x = radius y = radius z = radius while (x ** 2 + y ** 2 + z ** 2) > radius ** 2: x = (random.random() - 0.5) * 2 * radius y = (random.random() - 0.5) * 2 * radius z = (random.random() - 0.5) * 2 * radius scale = math.sqrt((radius ** 2) / (x ** 2 + y ** 2 + z ** 2)) return [int(scale * x), int(scale * y), int(scale * z)]

實際上這是一個很高效實現很簡潔的方法,其採樣效率為

$eta = pi / 6 quad (frac{4 pi}{3}(1)^3/2^3)$

當然如果你已經熟悉這個問題的本質，那你完全可以直接調用函數去生成三個零均值同sigma的高斯分布，然後疊加歸一化得到我們的結果（也就是評論中說的三個高斯分布疊加即可）：

def sphere_4(radius): p = np.random.normal(0, 1, 3) scale = math.sqrt((radius ** 2) / (p[0] ** 2 + p[1] ** 2 + p[2] ** 2)) return [int(scale * p[0]), int(scale * p[1]), int(scale * p[2])]

原因也很簡單對於空間中的任意的點Z(x,y,z):

$p(Z) = frac{1}{sqrt(2pi) sigma}e^{-frac{(x-0)^2+(y-0)^2+(z-0)^2}{2 sigma^2}}$

所以很明顯，對於空間的任意一個球面都是均勻的，我們可以限制落在某一個平面上，當然這樣效率會很低，所以我們歸一化就好了。可以在下圖右看到結果是相同的。

高斯分布的兩種方法

<二> sin(alpha)分布

上一篇文章的評論區另一種主流的解法是萬里 @萬里提到的抽樣一個sin(theta)分布，具體說來就是按照sin(theta)在z軸上的每一個環（r=R*sin(theta)）截面。這樣每一個環的取到的概率和他們的周長是成比例的，然後在環內均勻分布取一角度即可完成對球面的均勻採樣。

接下來的問題變成利用均勻分布生成一個sin(theta)分布

實際上評論區的大神們都說了，任意分布都可以用均勻分布生成，這裡時間有限，直接說我們用了CDF（累計分布函數）的方法，去生成sin(alpha)分布。

對於:

$p( heta) = frac{sin( heta)}{int_0^pi sin( heta)d heta} =0.5*sin( heta), hetain(0,pi )$

其累計分布函數：

$f( heta) = int_0^ heta0.5 sin( heta)*d( heta) = frac{1}{2}*(1-cos( heta)), hetain(0,pi)$

均勻分布：

$int_0^x mu(x) = x = f( heta)$

然後計算得到

$cos( heta) = 1-2x$

事實上，按照我們的推導我們並不需要計算出theta,得到cos(theta)既可完成我們的採樣，具體代碼如下：

def sphere_5(radius): u = random.random() alpha = random.random()*2*math.pi #cos(theta) = (1-2u), sin(theta) = (1-(1-2u)**2)**(1/2) z = radius*(1-2*u) r = radius*math.sqrt(1-(1-2*u)**2) x = r*math.sin(alpha) y = r*math.cos(alpha) return [int(x), int(y), int(z)]

當然，這個方法，我們也會放一個圖給大家看一下：

sin(theta)

小結

這一篇小小的文章讓我發現和知友討論還是蠻有意思的，一方面能意識到自己的不足，一方面也確確實實能找到一些有意思的東西。

本來周日就想把這些東西寫一下，無奈大於瓢潑不想去實驗室，寢室又沒有工作環境，所以只能委屈（痛快）沉迷了一天的dota2～，由於11點多要去趕火車，早上來一個多小時，從寫代碼到畫圖到文章，實在有些匆忙，所以還望大家發現錯誤及時告知～