478. 在圆内随机生成点

Desciption

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

Solution

构造

  1. 容易想到一个解决方案:随机生成一个角度,再随机一个半径rr,根据这个角度和半径得到一个x,y坐标
  2. 上面的方案有一个问题是:在圆中间的点是比较密集的。原因是 rr是在[0,r]之间等概率产生的,所以可以认为同一个r的生成的随机点是相同的,但是圆的半径会变大,同样数量的点就会显得稀疏了
  3. 考虑圆的面积公式:Pi * r * r, 其实半径在圆里面是做了两次贡献的,可以对随机生成出来的半径 rr 开根,则生成出来的点就是均匀的了

第二种方法:

  1. 随机生成两个范围在[0,r]的值,作为x,y,判断(x, y) 是不是在圆里,如果是的话则留下,不是的话丢弃。
  2. 上述的方法,本质上就是随机生成在边长为r的正方形里的点,对于是不是在边长为r的圆里,也是随机的

Code

class Solution {
    double r, x0, y0;
    public Solution(double radius, double x_center, double y_center) {
        r = radius;
        x0 = x_center;
        y0 = y_center;
    }
    
    public double[] randPoint() {
        int tot = 360000;
        Random random = new Random();
        double ang = 1.0 * random.nextInt(tot) / tot * Math.PI * 2;
        double rr = Math.sqrt(1.0 * random.nextInt(tot) / tot) * r;
        double ret[] = new double[2];
        ret[0] = (rr * Math.cos(ang)) + x0;
        ret[1] = (rr * Math.sin(ang)) + y0;
        return ret;
    }
}