echo

任生命穿梭 时间的角落

0%

在圆内随机生成点

Posted on In Valine:

478. 在圆内随机生成点

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

说明:

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

示例 1：

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

示例 2：

1
2
3
4
输入: 
["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 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

方法一：拒绝采样

在矩形中随机生成一个点的方法：随机选取一个 0 ~ 1的浮点数，乘以矩形的边长。使用该方法生成随机点的横纵坐标。我们可以得到第一种在圆内生成随机点的方法，即在这个圆外画一个外接矩形，在矩形内生成随机点，拒绝掉那些落在圆外的点，得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    private double xc, yc, rad;

    public Solution(double radius, double x_center, double y_center) {
        xc = x_center;
        yc = y_center;
        rad = radius;
    }
    
    public double[] randPoint() {
        //获得坐标原点的坐标(矩形的一个角的坐标)
        double x0 = xc - rad;
        double y0 = yc - rad;

        while(true){
            //在矩形中生成随机点(xr, yr)
            double xr = x0 + Math.random() * rad * 2;
            double yr = y0 + Math.random() * rad * 2;
            //拒绝掉不在圆内的随机点
            if(Math.sqrt(Math.pow(xr - xc, 2) + Math.pow(yr - yc, 2)) < rad){
                return new double[]{xr, yr};
            }
        }
    }
}
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(radius, x_center, y_center);
 * double[] param_1 = obj.randPoint();
 */

期望时间复杂度O(1)，最坏的情况是一直被拒绝，时间复杂度为O(n)。

空间复杂度为O(1)。