LeetCode478. 在圆内随机生成点

题目描述

给定圆的半径和圆心，实现一个函数，可以在圆中产生均匀随机点。

示例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]

题解

如果不考虑等概率，直接返回圆心就行（笑

考虑等概率的话，就需要一番分析啦，本文从两个角度进行讲解。

角度1 - 几何概型角度

首先考虑一个朴素的几何概型想法：

在 $[0,r]$ 的线段上随机取值，取到 $[0,\frac{r}{2}]$ 的概率为 $\frac{1}{2}$，现在将这个线段的一端固定，另一端旋转一周，线段扫过的图形为一个以 $r$ 为半径的圆，此时线段 $[0,\frac{r}{2}]$ 扫过的圆面积为整个圆面积的 $\frac{1}{4}$，圆内随机取一个点，这个点落在小圆的概率为 $\frac{1}{4}$。因此，在一维中等概率取一点，旋转成圆之后就不是等概率了。

角度2 - 概率论角度

下面从概率论角度分析。

不失一般性，我们以单位圆为例，在单位圆上任取一点，这个点落到某一圆周上的长度与该圆周的周长成正比，从而也就与该圆周的半径成正比，设单位圆的概率密度函数 $f(r)=kr$，因此：

$$1=P(0\leq r\leq 1)=\int_0^1kr\ dr=\frac{1}{2}k$$

得 $k=2$，PDF：$f(r)=2r$

得到PDF后，就可以算出分布函数CDF：

$$F(r)=\int_0^rf(t)\ dt=r^2$$

通过上面的分析，想要得到等概率，需要在 $[0,1]$ 内等概率取 $F(r)$ 的值，$r=\sqrt{F(r)}$，然后再对单位圆进行放缩。

坐标生成

根据极坐标生成圆心的坐标：

${\begin{aligned} ρ^{2} & = x^{2} + y^{2} \\ x & = ρ \cos θ \\ y & = ρ \sin θ \end{aligned}$

其中，$\theta$ 可在 $[0, 2\pi]$ 中等概率生成。

代码

class Solution {
private:
    const double PI = acos(-1);
    double r, x, y;
    mt19937 gen{ random_device{}() };
    uniform_real_distribution<double> dis;
public:
    Solution(double radius, double x_center, double y_center) :
    r(radius), x(x_center), y(y_center), dis(0, 1) { }
    
    vector<double> randPoint() {
        double theta = dis(gen) * 2 * PI;
        double rho = sqrt(dis(gen)) * r;
        return {x + rho * cos(theta), y + rho * sin(theta)};
    }
};