主題

LeetCode - 478. Generate Random Point in a Circle 解題心得

Not In My Back Yard | 2021-08-13 00:00:01 | 巴幣 0 | 人氣 125

題目連結:


題目意譯:
給定一個圓的半徑以及其圓心之位置,實作函式 randPoint 其將產生一個圓中的均勻(Uniform)隨機點。

實作類別 Solution:
Solution(double radius, double x_center, double y_center) 初始化一個物件,有著圓半徑 radius 以及圓心位置 (x_center, y_center) 。
randPoint() 回傳圓中的一個隨機的點。一個位於圓周上的點視為在圓內。答案以陣列形式 [x, y] 回傳。

限制:
0 < radius ≦ 10 ^ 8
-10 ^ 7 ≦ x_center 、 y_center ≦ 10 ^ 7
最多有 3 × 10 ^ 4 次呼叫為 randPoint。



範例測資:
輸入
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
輸出
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解釋
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // 回傳 [-0.02493, -0.38077]
solution.randPoint(); // 回傳 [0.82314, 0.38945]
solution.randPoint(); // 回傳 [0.36572, 0.17248]


解題思維:
假設 RAN 為一個介於 0 ~ 1 之間的隨機數(C++ 可能會寫 double(rand()) / RAND_MAX 來得到這樣的 R 值,python 則為 random.random())。

雖然你可以直接生成一個點為 (x_center + (2RAN - 1) × radius, y_center + (2RAN - 1) × radius) (2RAN - 1 代表著 -1 ~ 1 之間的一個隨機數)然後判斷該點有沒有在圓內。如果在就回傳該點座標;反之就繼續隨機產生另一個點直到在圓內。

這樣依然可以確保圓內的點有著均勻分布的機率會被選到,儘管看似有些點被拋棄了。但是因為整體是均勻分布的,所以就算現在侷限範圍於一圓仍是均勻分布。上述方法稱為棄卻抽樣(Rejection Sampling)。

但是這樣如果運氣不好的話,有機會需要重複挑選相當多次的點才會落在圓內,意即生成單一一個隨機點的最差時間複雜度為 O(∞)。



因此我們可以採取極座標(Polar Coordinate)隨機取點——即標準座標平面上的點 (x, y) 會被改寫為 (dcos(θ), dsin(θ)) ,其中 θ 為向量 (x, y) 與 X 軸之夾角 、 d 為 sqrt(x ^ 2 + y ^ 2),即點 (x, y) 到原點 (0, 0) 之距離。

所以我們可以改為隨機產生出兩個變數值 L = RAN × radius 、 A = RAN × 2π ,然後套入上面的極座標格式便可以得到一點 (x_center + Lcos(A), y_center + Lsin(A)) 。而此點保證在圓內,不需特別判斷。

但是這樣會有一個大問題,即現在點不再是均勻分布了(儘管看起來應該要是均勻的)。如果我們真的按照上述方式取點,我們會看到:
(上圖的取點數為 5000 個)

而將 L 的值改為 sqrt(RAN) × radius 即可以得到類似以下的均勻分布:
(取點數同樣是 5000 個點)

原因可以從下圖看出:
可以看到,原本 L 之值落在 [0, r] 或是 [r, 2r] 這兩個範圍是均等的,而角度 θ 從 0 度 ~ 360 度(或是弧度 0 ~ 2π)也是均等的機率。

但是圖中兩個同心圓,中間的圓因面積為較小所以只需要較少的點便可以填滿(也就是點密度會較大);相對的較外層的圓,因為面積大,所以需要較多的點填滿(也就是點密度會較小)。而密度差便造成了機率分布的不均勻(機率的「本質」與密度有著密切關係)。

而密度與距離圓心的距離 r ^ 2 成正比。因此當我們將 RAN 取 sqrt() (即取其平方根),我們便可以抵銷掉 r ^ 2 所帶來的密度差(因為 0 ~ 1 之間的數字取平方根後會更靠近 1,例如 sqrt(0.25) = 0.5)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作