『LeetCode』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⁸
−10⁷ < = x_center, y_center < = 10⁷
randPoint 最多被调用 3 * 10⁴ 次

相似题目

非重叠矩形中的随机点 (中等)

题解

【在圆内随机生成点】拒绝采样及其期望

拒绝采样

简单的想法：在 x 轴和 y 轴分别均匀采样，但这样得到的数不一定会在圆内，如下图所示，有可能会随机到蓝色部分。

最简单的处理方法是，检查一下随机出的点在不在圆中，不在的话就重新再采样一次，直到成功随机出结果。

经典的蒙特卡洛方法就是通过随机投点的方法计算圆的圆周率的，我们也很容易根据几何概型计算出随机投点落在圆内的概率为 $\dfrac{\pi}{4}$, 并且落在圆内任意一点也是随机的。

期望投点次数可以通过全概率公式计算：

$$ \begin{aligned} E &= \sum\limits_{k=1}^\infty k \times \dfrac{\pi}{4} \times (1 - \dfrac{\pi}{4})^{k - 1} \\ &= \dfrac{\pi}{4} \sum\limits_{k=1}^\infty k \times (1 - \dfrac{\pi}{4})^{k - 1} \\ &= \dfrac{\pi}{4} (\sum\limits_{k=1}^\infty \int k \times x^{k - 1} dx)^{'}_{x=1 - \frac{\pi}{4}} \\ &= \dfrac{\pi}{4} (\sum\limits_{k=1}^\infty x^{k})^{'}_{x=1 - \frac{\pi}{4}} \\ &= \dfrac{\pi}{4} (\dfrac{1}{1 - x})^{'}_{x=1 - \frac{\pi}{4}} \\ &= \dfrac{\pi}{4} \dfrac{1}{(1 - x)^2} |_{x=1 - \frac{\pi}{4}} \\ &= \dfrac{4}{\pi} \end{aligned} $$

其中等号 3-6 使用了泰勒展开的微积分变换，由期望和概率我们可以推测，几乎绝大多数采样都会在 1 ~ 2 次内取得，这个结果是可以接受的。

# Code language: Python
class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.r = radius
        self.r2 = radius ** 2
        self.x = x_center
        self.y = y_center

    def randPoint(self) -> List[float]:
        while True:
            rx = random.random() * self.r * 2 - self.r + self.x
            ry = random.random() * self.r * 2 - self.r + self.y
            if (rx - self.x) ** 2 + (ry - self.y) ** 2 <= self.r2:
                return [rx, ry]

// Code language: Cpp
class Solution {
public:
    double r, r2, x, y;
    Solution(double radius, double x_center, double y_center): r(radius), x(x_center), y(y_center) {
        r2 = pow(radius, 2);
    }
    
    vector<double> randPoint() {
        while (1) {
            double rx = rand() / double(RAND_MAX) * 2 * r - r + x;
            double ry = rand() / double(RAND_MAX) * 2 * r - r + y;
            if (pow(x - rx, 2) + pow(y - ry, 2) <= r2) 
                return vector<double> {rx, ry};
        }
        return vector<double>();
    }
};

// Code language: Java
class Solution {
    double r, r2, x, y;
    Random random = new Random();
    public Solution(double radius, double x_center, double y_center) {
        r = radius;
        r2 = Math.pow(r, 2);
        x = x_center;
        y = y_center;
    }
    
    public double[] randPoint() {
        while (true) {
            double rx = random.nextDouble() * r * 2 - r + x;
            double ry = random.nextDouble() * r * 2 - r + y;
            if (Math.pow(x - rx, 2) + Math.pow(y - ry, 2) <= r2)
                return new double[] {rx, ry};
        }
    }
}

时间复杂度: $O(\dfrac{4}{\pi})$
空间复杂度: O(1)

最后

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』478 在圆内随机生成点

题目

标签

相似题目

题解

拒绝采样

最后