【Leetcode】478. Generate Random Point in a Circle（配数学证明）

题目地址：

https://leetcode.com/problems/generate-random-point-in-a-circle/

给定二维圆的圆心坐标$(x_0,y_0)$及其半径$r$，要求等概率产生在圆内的点的坐标。圆周上的点也视为有效。

法1：拒绝采样法。只需要能等概率产生单位圆中的随机点即可，可以用拒绝采样法。产生$[-1,1{]}^2$中的随机点是简单的，每次产生了$(x,y)$之后，只当$x^2+y^2\le 1$的时候才停止采样，那么由于每次采样在范围内的概率$\frac{\pi }{4}<1$，采样次数服从几何分布，所以采样以概率$1$停止，设采样停止这个事件为$A$，设圆内有个小面积$S$，则$P((x,y)\in S|A)=P((x,y)\in S)$即为$S$的面积，从而满足题意。采样次数的期望为$\frac{4}{\pi }$。代码如下：

import java.util.Random;

public class Solution {
    
    
    Random random;
    double xc, yc, r, x, y;
    
    public Solution(double radius, double x_center, double y_center) {
    
        random = new Random();
        xc = x_center;
        yc = y_center;
        r = radius;
    }
    
    public double[] randPoint() {
    
        do {
    
            generate();
        } while (!check(x, y));
        return new double[]{
    xc + r * x, yc + r * y};
    }
    
    void generate() {
    
        x = random.nextDouble() * 2 - 1;
        y = random.nextDouble() * 2 - 1;
    }
    
    boolean check(double x, double y) {
    
        return x * x + y * y <= 1.0;
    }
}

randPoint时空复杂度$O(1)$。

法2：设$(R,\Theta )$满足$[0,1]\times [0,2\pi ]$的均匀分布，则$(X,Y)=(\sqrt{R}\cos \Theta ,\sqrt{R}\sin \Theta )$满足单位圆的均匀分布。

证明：设$(x(r,\theta ),y(r,\theta ))=(\sqrt{r}\cos \theta ,\sqrt{r}\sin \theta )$，设$(X,Y)$的密度函数为$p(x,y)$，那么面积微元$$p(x,y)dxdy=p(r\cos \theta ,r\sin \theta )|J|drd\theta =\frac{1}{2\pi }drd\theta$$其中$J$是Jacobi矩阵，$$J=\left[\begin{array}{cc}\frac{\partial x}{\partial r}& \frac{\partial x}{\partial \theta }\\ \frac{\partial y}{\partial r}& \frac{\partial y}{\partial \theta }\end{array}\right]=\left[\begin{array}{cc}\frac{\cos \theta }{2\sqrt{r}}& -\sqrt{r}\sin \theta \\ \frac{\sin \theta }{2\sqrt{r}}& \sqrt{r}\cos \theta \end{array}\right]$$$|J|=\frac{1}{2}$，从而$p(x,y)=\frac{1}{\pi }$，满足题意。代码如下：

import java.util.Random;

public class Solution {
    
    
    Random random;
    double r, x, y;
    
    public Solution(double radius, double x_center, double y_center) {
    
        random = new Random();
        this.r = radius;
        this.x = x_center;
        this.y = y_center;
    }
    
    public double[] randPoint() {
    
        double theta = random.nextDouble() * 2 * Math.PI;
        double randomR = r * Math.sqrt(random.nextDouble());
        return new double[]{
    x + randomR * Math.cos(theta), y + randomR * Math.sin(theta)};
    }
}

randPoint时空复杂度$O(1)$。

法1：C++：

class Solution {
    
 public:
  double r, xc, yc, x, y;

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

  vector<double> randPoint() {
    
    double x, y;
    do {
    
      x = (double)rand() / RAND_MAX * 2 - 1;
      y = (double)rand() / RAND_MAX * 2 - 1;
    } while (x * x + y * y > 1);
    return {
    xc + x * r, yc + y * r};
  }
};

时空复杂度一样。

法2：C++（C++里的$\pi$可以由$\arccos -1$得到）：

class Solution {
    
 public:
  double r, xc, yc, x, y;

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

  vector<double> randPoint() {
    
    double radius = sqrt((double)rand() / RAND_MAX) * r;
    double theta = ((double)rand() / RAND_MAX) * 2 * acos(-1);
    return {
    xc + radius * cos(theta), yc + radius * sin(theta)};
  }
};

时空复杂度一样。