在圆内随机生成点

难度: Medium

给定圆的半径和圆心的位置，实现函数 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⁴ 次

Submission

运行时间: 116 ms

内存: 26.4 MB

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.x = x_center
        self.y = y_center
        self.size = math.pi * radius ** 2

    def randPoint(self) -> List[float]:
        theta, r = random.uniform(0.0, math.pi * 2), sqrt(random.uniform(0.0, self.size) / math.pi)
        return [self.x + math.cos(theta) * r, self.y + math.sin(theta) * r]

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

Explain

该题解采用极坐标系统来在圆内生成随机点。首先，随机选择一个角度 \(\theta\) 从 0 到 \(2\pi\)。然后，为了保证点在圆内均匀分布，使用开方函数来调整半径的分布，使用 \(r = \sqrt{random.uniform(0.0, self.size) / \pi}\) 来计算半径 r。self.size 是圆的面积，通过开方处理后的 r 可以确保点在圆内均匀分布。最后，通过 \(x = x_{center} + r \cos(\theta)\) 和 \(y = y_{center} + r \sin(\theta)\) 来计算点的坐标。

时间复杂度: O(1)

空间复杂度: O(1)

python
import math
import random
from typing import List

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.x = x_center  # 圆心的 x 坐标
        self.y = y_center  # 圆心的 y 坐标
        self.size = math.pi * radius ** 2  # 计算圆的面积，用于半径随机分布的计算

    def randPoint(self) -> List[float]:
        # 生成随机角度和随机半径
        theta = random.uniform(0.0, math.pi * 2)  # 从 0 到 2π 中随机选择一个角度
        r = sqrt(random.uniform(0.0, self.size) / math.pi)  # 根据圆面积和π计算半径，确保点的均匀分布
        # 计算并返回随机点的坐标
        return [self.x + math.cos(theta) * r, self.y + math.sin(theta) * r]

# 示例用法
# obj = Solution(radius, x_center, y_center)
# param_1 = obj.randPoint()

Explore

在圆内随机生成点时，如果半径 r 是线性分布的（即直接从 [0, R] 中等概率选取），那么生成的点会在圆心附近过于密集，而在圆的边缘较为稀疏。这是因为圆的面积与半径的平方成正比（面积公式为 \(A = \pi r^2\)）。如果半径 r 均匀分布，那么小半径对应的圆环面积远小于大半径对应的圆环面积，导致单位面积内的点数不一致。通过使用平方根函数 \(r = \sqrt{R}\)，可以调整半径的分布，使得任意半径 r 对应的圆环面积（由微积分中的环形面积公式 \(dA = 2\pi r dr\) 所表示）对应的概率密度保持一致，从而使得圆内各处的点密度均匀。

在这个公式中，`self.size` 是圆的面积，计算公式为 \(\pi R^2\)，其中 R 是圆的半径。因此，公式中的 `random.uniform(0.0, self.size)` 产生一个从 0 到圆的面积 \(\pi R^2\) 的随机数。将这个值除以 \(\pi\) 后，得到的是一个从 0 到 \(R^2\) 的值。对这个结果取平方根（即 `sqrt` 函数），得到的是一个从 0 到 R 的值，这个值正好是圆的半径。这样处理后，随机半径 r 的分布符合均匀分布的平方根，确保了点的均匀分布。

角度 \(\theta\) 的选择范围为从 0 到 \(2\pi\) 是因为这代表了圆的完整旋转，即 360 度。这样的范围确保了角度的随机选择可以覆盖圆的整个周围，无论是任何半径值，点都能均匀分布在圆的任意位置。如果角度的选择范围被限制或不足 \(2\pi\)，那么生成的点将不会均匀覆盖整个圆，从而影响到点的均匀分布。