【数学, 随机化, 拒绝采样】在圆内随机生成点

题目

478. 在圆内随机生成点

---

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。

实现 Solution 类:

• Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
• randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

示例 1：

输入: 
["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]

提示：

• 0 < radius <= 10^8
• -10^7 <= x_center, y_center <= 10^7
• randPoint 最多被调用 3 * 10^4 次

解题

方法一：拒绝采样

思路

虽然是这么做出来了但是不懂具体怎么描述，这里就放个官方解题的描述吧：

拒绝采样的意思是说：我们在一个更大的范围内生成随机数，并拒绝掉那些不在题目给定范围内的随机数，此时保留下来的随机数都是在范围内的。为了在一个半径为 $R$ 的圆中生成均匀随机点，我们可以使用一个边长为 $2R$ 的正方形覆盖住圆，并在正方形内生成均匀随机点，此时就只需要对于横坐标和纵坐标分别生成一个随机数即可。

若该点落在圆内，我们就返回这个点，否则我们拒绝这个点，重新生成，直到新的随机点落在圆内。

细节

由于正方形的面积为 $(2R)^2=4R^2$，圆的面积为 $\pi R^2$ ，因此在正方形中随机生成的点，落在圆内的概率为 $\text{Pr}(\cdot)=\dfrac{\pi R^2}{4R^2} \approx 0.785$ ，期望的生成次数为 $\text{E}(\cdot) = \dfrac{1}{0.785} \approx 1.274 = O(1)$。

在正方形中生成点时（正方形中心的坐标简记为原点），如果我们在 $[-R, R)$ 的范围内生成随机数，那么是无法生成到横坐标或纵坐标恰好为 $R$ 的点，对应到圆上时，会有圆周上与正方形边相切的两个点无法随机到。我们可以在生成时稍微提高右边界（例如 $2R + \epsilon$，其中 $\epsilon$ 是一个很小的常数，例如 $10^{-7}$ ），或者直接忽略这两个点，因为它们的勒贝格测度为零。

代码

class Solution {
    private double radius, xCenter, yCenter;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.xCenter = x_center;
        this.yCenter = y_center;
    }
    
    public double[] randPoint() {
        double times = 2 * radius;
        double x, y;
        while (true) {
            x = Math.random() * times - radius;
            y = Math.random() * times - radius;
            if (Math.pow(x, 2) + Math.pow(y, 2) <= Math.pow(radius, 2)) {
                return new double[]{x + xCenter, y + yCenter};
            }
        }
    }
}