Watch 10 video solutions for Generate Random Point in a Circle, a medium level problem involving Math, Geometry, Rejection Sampling. This walkthrough by Timothy H Chang has 2,318 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the radius and the position of the center of a circle, implement the function randPoint which generates a uniform random point inside the circle.
Implement the Solution class:
Solution(double radius, double x_center, double y_center) initializes the object with the radius of the circle radius and the position of the center (x_center, y_center).randPoint() returns a random point inside the circle. A point on the circumference of the circle is considered to be in the circle. The answer is returned as an array [x, y].
Example 1:
Input ["Solution", "randPoint", "randPoint", "randPoint"] [[1.0, 0.0, 0.0], [], [], []] Output [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]] Explanation Solution solution = new Solution(1.0, 0.0, 0.0); solution.randPoint(); // return [-0.02493, -0.38077] solution.randPoint(); // return [0.82314, 0.38945] solution.randPoint(); // return [0.36572, 0.17248]
Constraints:
0 < radius <= 108-107 <= x_center, y_center <= 1073 * 104 calls will be made to randPoint.Problem Overview: You need to generate a random point uniformly distributed inside a circle defined by radius and center (x_center, y_center). The key challenge is ensuring every location inside the circle has equal probability, not just points near the center.
Approach 1: Rejection Sampling (Expected O(1) time, O(1) space)
This approach samples points from the bounding square around the circle. Generate random x and y offsets uniformly in the range [-radius, radius]. If the sampled point satisfies x^2 + y^2 <= radius^2, it lies inside the circle and is accepted. Otherwise discard it and sample again. The acceptance probability is roughly π/4 ≈ 0.785, so the expected number of iterations is constant.
The key insight is that uniform sampling from the square combined with a geometric filter preserves uniform distribution inside the circle. The algorithm repeatedly performs random generation and a simple distance check. This technique is widely used in rejection sampling problems where generating a direct distribution is difficult.
Approach 2: Polar Coordinates (O(1) time, O(1) space)
A more mathematically direct method uses polar coordinates. Generate a random angle θ uniformly in [0, 2π]. For the radius, generate a random value r = sqrt(U) * radius where U is uniform in [0,1]. The square root is crucial because area grows with r², so naive uniform sampling of r would cluster points near the center.
Convert the polar coordinate to Cartesian form using x = x_center + r * cos(θ) and y = y_center + r * sin(θ). This guarantees uniform distribution across the entire circle in a single step. The approach relies on geometric reasoning and is common in problems involving math and geometry.
Recommended for interviews: Both approaches are acceptable. Rejection sampling is easy to derive and demonstrates understanding of geometric filtering. The polar coordinate method is more elegant and avoids repeated sampling, which often impresses interviewers because it shows deeper mathematical reasoning about uniform distributions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Rejection Sampling | Expected O(1) | O(1) | When a simple geometric filter is acceptable and implementation simplicity matters |
| Polar Coordinates | O(1) | O(1) | When you want a direct mathematical solution without repeated sampling |