[2022-06-05]915. 在圆内随机生成点👋几何👋数学👋拒绝采样👋随机化

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/generate-random-point-in-a-circle

难度: Medium
标签: 几何 数学 拒绝采样 随机化

[dreamjean]

478. 在圆内随机生成点

Description

Difficulty: 中等

Related Topics: 几何, 数学, 拒绝采样, 随机化

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。

实现 Solution 类:

• Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
• randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。

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

提示：

• 0 < radius <= 10⁸
• -10⁷ <= x_center, y_center <= 10⁷
• randPoint 最多被调用 3 * 10⁴ 次

Solution

参考 Generate Uniform Random Points within a Circle

• 注意防止随机密集分布在圆的点心点周围
• 随机点 x 分布公式 x=sqrt(rand(len))*cos(rand(degree))

Language: JavaScript

/**
 * @param {number} radius
 * @param {number} x_center
 * @param {number} y_center
 */
var Solution = function(radius, x_center, y_center) {
    this.radius = radius;
    this.x_center = x_center;
    this.y_center = y_center;
};

/**
 * @return {number[]}
 */
Solution.prototype.randPoint = function() {
    const len = Math.sqrt(Math.random()) * this.radius;
    const deg = Math.random() * Math.PI * 2;
    const x = this.x_center + len * Math.cos(deg);
    const y = this.y_center + len * Math.sin(deg);

    return [x, y];
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(radius, x_center, y_center)
 * var param_1 = obj.randPoint()
 */