Medium
478. Generate Random Point in a Circle
mathgeometryrejection-samplingrandomized
解題說明
Generate Random Point in a Circle
題目描述:給定一個圓的半徑 radius 和圓心座標 (x_center, y_center),實作一個函式 randPoint() 在圓內均勻隨機生成一個點。
解題思路:最直觀的方法是拒絕採樣(Rejection Sampling):在包圍圓的正方形內均勻隨機生成點,若該點落在圓內則接受,否則拒絕並重新生成。正方形面積為 (2r)^2 = 4r^2,圓面積為 pi*r^2,接受率約為 pi/4 ≈ 78.5%,因此期望只需約 1.27 次採樣。這種方法簡單且不涉及三角函式計算。
C++ 解法
複雜度分析
時間複雜度:O(1) 期望 — 每次呼叫期望採樣約 1.27 次(4/pi),為常數時間。
空間複雜度:O(1) — 僅使用常數個變數。
虛擬碼
1. Constructor: store radius r, center (cx, cy)
2. randPoint():
a. Loop:
- Generate random x in [cx - r, cx + r]
- Generate random y in [cy - r, cy + r]
- If (x - cx)^2 + (y - cy)^2 <= r^2, return [x, y]
- Else reject and repeat其他解法
極座標法 O(1):隨機生成角度 theta 在 [0, 2pi),半徑 rr = r * sqrt(random(0,1))。轉換為直角座標 (cx + rrcos(theta), cy + rr*sin(theta))。注意半徑需取 sqrt 以確保均勻分佈(因為面積與半徑的平方成正比)。無需拒絕採樣但需要三角函式。
逆變換採樣:直接推導 CDF 的逆函式,分別生成半徑和角度。數學上等價於極座標法,但從概率論角度更嚴謹。
延伸思考
- 為什麼極座標法中半徑要取 sqrt(random()) 而不是直接用 random()*r?
- 如果要在圓環(annulus)內均勻取點,該如何修改?
- 拒絕採樣法的最壞情況時間複雜度是什麼?在實務中會是問題嗎?