478-在圆内随机生成点(Generate Random Point in a Circle)

原文链接: https://leetcode-cn.com/problems/generate-random-point-in-a-circle

英文原文

Given the radius and the position of the center of a circle, implement the function randPoint which generates a uniform random point inside the circle.

Implement the Solution class:

Solution(double radius, double x_center, double y_center) initializes the object with the radius of the circle radius and the position of the center (x_center, y_center).
randPoint() returns a random point inside the circle. A point on the circumference of the circle is considered to be in the circle. The answer is returned as an array [x, y].

Example 1:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

Constraints:

0 < radius <= 10⁸
-10⁷ <= x_center, y_center <= 10⁷
At most 3 * 10⁴ calls will be made to randPoint.

中文题目

给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

说明:

输入值和输出值都将是浮点数。
圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
圆周上的点也认为是在圆中。
randPoint 返回一个包含随机点的x坐标和y坐标的大小为2的数组。

示例 1：

输入: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

示例 2：

输入: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有三个参数，圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

通过代码

官方题解

方法一：拒绝采样

为了在一个半径为 $R$ 的圆 $C$ 中均匀随机生成点，我们可以使用拒绝采样的方法。

我们使用一个边长为 $2R$ 的正方形覆盖住圆 $C$，并在正方形内随机生成点，若该点落在圆内，我们就返回这个点，否则我们拒绝这个点，重新生成知道新的随机点落在圆内。

{:width=400px}

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

[sol1]
class Solution {
public:
    double rad, xc, yc;
    //c++11 random floating point number generation
    mt19937 rng{random_device{}()};
    uniform_real_distribution<double> uni{0, 1};

    Solution(double radius, double x_center, double y_center) {
        rad = radius, xc = x_center, yc = y_center;
    }

    vector<double> randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while(true) {
            double xg = x0 + uni(rng) * 2 * rad;
            double yg = y0 + uni(rng) * 2 * rad;
            if (sqrt(pow((xg - xc), 2) + pow((yg - yc), 2)) <= rad)
                return {xg, yg};
        }
    }
};

[sol1]
class Solution {
    double rad, xc, yc;
    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }

    public double[] randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while(true) {
            double xg = x0 + Math.random() * rad * 2;
            double yg = y0 + Math.random() * rad * 2;
            if (Math.sqrt(Math.pow((xg - xc) , 2) + Math.pow((yg - yc), 2)) <= rad)
                return new double[]{xg, yg};
        }
    }
}

复杂度分析

时间复杂度：期望时间复杂度为 $O(1)$，但最坏情况下会达到 $O(\infty)$（一直被拒绝）。
空间复杂度：$O(1)$。

方法二：计算分布函数

不失一般性，我们只考虑在原点且半径为 1 的单位圆，对于非一般性的情况，我们只需要把生成的点的坐标根据半径等比例放大，再根据圆心坐标进行平移即可。

对于两条线段，我们在它们中均匀随机生成点。如果一条线段的长度是另一条的两倍，那么生成的点在第一条线段上的概率也应当是在第二条线段上的概率的两倍。因此我们考虑单位圆内部的每一个圆环，生成的点落在半径为 $R_1$ 的圆环上的概率应当与圆环的周长成正比，同时也与 $R_1$ 成正比，即 $f(R_1) = k * R_1$，其中 $f(x)$ 为概率密度函数（PDF）。由于 $f(x)$ 在定义域上的积分为 1，因此可以求出 $f(x)$ 的表达式 $f(x) = 2x$。

得到了概率密度函数后，我们计算累计分布函数（CDF），即 $F(x) = \int f(x) = \int 2x = x^2$。累计分布函数 $F(x)$ 告诉我们，在单位圆中随机生成一个点，它离圆心的距离小于等于 $x$ 的概率为 $F(x) = x^2$。对于一个给定的累计分布函数，如果我们想要根据其生成随机变量，我们可以通过 $[0, 1]$ 的均匀分布生成随机变量 $U$，找到满足 $F(X) = U$ 的 $X$，此时 $X$ 即为满足累计分布函数的随机变量。

对于 $F(X) = U$，由于 $F(X)$ 单调递增，因此有 $X = F^{-1}(U)$。由于 $F(x) = x^2$，因此有 $F^{-1}(x) = \sqrt{x}$，即用 $X = \sqrt{U}$ 来生成随机变量 $X$。

除了 $X$（代表到圆心的距离）之外，我们还需要随机生成其与水平轴正方向的夹角 $\theta$，随后我们就可以根据

$$
\text{x_coord} = X \cdot \cos \theta\
\text{y_coord} = X \cdot \sin \theta
$$

得到点在单位圆内的坐标。再经过我们等比例放大坐标和平移两个步骤，就可以得到任意圆内的一个均匀随机生成的点了。

[sol2]
class Solution {
public:
    double rad, xc, yc;
    //c++11 random floating point number generation
    mt19937 rng{random_device{}()};
    uniform_real_distribution<double> uni{0, 1};

    Solution(double radius, double x_center, double y_center) {
        rad = radius, xc = x_center, yc = y_center;
    }

    vector<double> randPoint() {
        double d = rad * sqrt(uni(rng));
        double theta = uni(rng) * (2 * M_PI);
        return {d * cos(theta) + xc, d * sin(theta) + yc};
    }
};

[sol2]
class Solution {
    double rad, xc, yc;
    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }

    public double[] randPoint() {
        double d = rad * Math.sqrt(Math.random());
        double theta = Math.random() * 2 * Math.PI;
        return new double[]{d * Math.cos(theta) + xc, d * Math.sin(theta) + yc};
    }
}

复杂度分析

时间复杂度：$O(1)$。
空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
7479	16844	44.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
非重叠矩形中的随机点	中等

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途