侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-05 / 0 评论 / 0 点赞 / 26 阅读 / 823 字 / 正在检测是否收录...

题目

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

解题

方法一:拒绝采样

思路

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

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

image-20220605004521772

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

细节

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

在正方形中生成点时(正方形中心的坐标简记为原点),如果我们在 [R,R)[-R, R) 的范围内生成随机数,那么是无法生成到横坐标或纵坐标恰好为 RR 的点,对应到圆上时,会有圆周上与正方形边相切的两个点无法随机到。我们可以在生成时稍微提高右边界(例如 2R+ϵ2R + \epsilon,其中 ϵ\epsilon 是一个很小的常数,例如 10710^{-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};
            }
        }
    }
}
0

评论区