How do you ensure uniform random points in a circle?

Use polar coordinates with the radius scaled by the square root of a uniform random number and angle uniformly between 0 and 2π.

Why does simple uniform radius sampling fail?

Sampling the radius directly leads to higher density near the center because area scales with r^2, not linearly.

Is rejection sampling always recommended?

Rejection sampling is simple but can be inefficient, especially for large circles relative to bounding squares.

How is this problem pattern classified?

It follows a math plus geometry pattern with a focus on uniform random point generation inside geometric shapes.

Can GhostInterview help verify points are uniform?

Yes, it can check multiple generated points against expected uniform distributions to ensure the implementation is correct.

#478

Medium

auto_awesome数学·结合·几何

LeetCode 题解工作台

在圆内随机生成点

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。实现 Solution 类: Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_cen…

数学几何拒绝采样随机化

题目描述

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

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self) -> List[float]:
        length = math.sqrt(random.uniform(0, self.radius**2))
        degree = random.uniform(0, 1) * 2 * math.pi
        x = self.x_center + length * math.cos(degree)
        y = self.y_center + length * math.sin(degree)
        return [x, y]

speed

复杂度分析

指标	值
时间	complexity depends on the chosen method: polar coordinate sampling is O(1) per call, while rejection sampling may vary depending on circle density in the bounding square. Space complexity is O(1) as only coordinates and random values are stored.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect questions about uniform distribution and radius scaling for correctness.
question_mark
Interviewers often probe handling of boundary cases near the circle edge.
question_mark
Be prepared to justify polar vs Cartesian or rejection sampling trade-offs.

warning

常见陷阱

外企场景

error
Generating the radius uniformly without square root leads to biased point distribution towards the center.
error
Confusing the circle's bounding square limits with valid circle coordinates.
error
Failing to convert polar coordinates correctly to Cartesian coordinates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generate a random point inside an ellipse instead of a circle.
arrow_right_alt
Generate multiple random points efficiently without repeated function calls.
arrow_right_alt
Modify to generate points only in a specific quadrant of the circle.

help

常见问题

外企场景

继续练习

#470 用 Rand7() 实现 Rand10()#497 非重叠矩形中的随机点 #1515 服务中心的最佳位置