在圆内随机生成点

难度:

标签:

题目描述

代码结果

运行时间: 116 ms, 内存: 26.4 MB

/*
 * 思路：
 * 1. 使用Java Stream来生成随机点。
 * 2. 和普通Java方法类似，生成theta和r，然后计算x和y。
 * 3. 使用Stream.generate()方法生成需要的随机数。
 */
import java.util.Random;
import java.util.stream.DoubleStream;

class Solution {
    private double radius;
    private double x_center;
    private double y_center;
    private Random rand;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
        this.rand = new Random();
    }

    public double[] randPoint() {
        double[] point = DoubleStream.generate(() -> rand.nextDouble())
                                     .limit(2)
                                     .toArray();
        double theta = 2 * Math.PI * point[0];
        double r = Math.sqrt(point[1]) * radius;
        double x = r * Math.cos(theta) + x_center;
        double y = r * Math.sin(theta) + y_center;
        return new double[]{x, y};
    }
}

解释

方法:

该题解采用极坐标系统来在圆内生成随机点。首先，随机选择一个角度 \(\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)

代码细节讲解

🦆

为什么使用平方根函数来调整半径的分布能够保证随机点在圆内的均匀分布？

▷

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

🦆

在计算随机半径时使用的公式 `r = sqrt(random.uniform(0.0, self.size) / pi)` 中，self.size 代表圆的面积，请问这个面积与半径生成的关系是怎样的？

▷

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

🦆

为何在选择随机角度时，范围是从 0 到 `2π`，这样的范围设定对于点的分布有何影响？

▷

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

相关问题

非重叠矩形中的随机点

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

请注意 ，整数点是具有整数坐标的点。

实现 Solution 类:

Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

示例 1：

输入: 
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输出: 
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

解释：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]

提示：

1 <= rects.length <= 100
rects[i].length == 4
-10⁹ <= a_i < x_i <= 10⁹
-10⁹ <= b_i < y_i <= 10⁹
x_i - a_i <= 2000
y_i - b_i <= 2000
所有的矩形不重叠。
pick 最多被调用 10⁴ 次。

非重叠矩形中的随机点索引处的解码字符串