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;
    }
}