Generate Random Point in a Circle

Med

#0465Time: O(1) - Each call to `randPoint` involves a fixed number of operations: two random number generations, one square root, one sine, one cosine, and a few multiplications and additions.Space: O(1) - We only store the initial parameters of the circle.

Patterns

Math Geometry Randomized

Algorithms

Rejection Sampling

Prompt

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 <= 10⁸
-10⁷ <= x_center, y_center <= 10⁷
At most 3 * 10⁴ calls will be made to randPoint.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses polar coordinates (r, θ) to represent a point in the circle. A naive attempt would be to pick both the radius r and the angle θ uniformly. However, this would incorrectly cluster points towards the center. The correct method, derived from the fact that the area element in polar coordinates is r dr dθ, requires a non-uniform distribution for the radius.

By using a technique called Inverse Transform Sampling, we can find the correct way to generate the radius r to ensure the final (x, y) point is uniformly distributed over the circle's area. This involves taking the square root of a uniform random number. The angle θ can be chosen uniformly.

Algorithm

Generate a random angle angle uniformly in the range [0, 2π).
Generate a random length len for the radius. To ensure uniform distribution across the circle's area, the length cannot be chosen uniformly. Instead, we use the inverse transform sampling method. The correct formula is len = radius * sqrt(random()), where random() is a uniform random number in [0, 1).
Convert the polar coordinates (len, angle) to Cartesian coordinates relative to the origin: x_offset = len * cos(angle) and y_offset = len * sin(angle).
Translate the point by the circle's center coordinates: x = x_center + x_offset and y = y_center + y_offset.
Return the point [x, y].

Walkthrough

This method generates a random point by first picking a random direction (angle) and a random distance from the center (radius), and then converting these polar coordinates to Cartesian coordinates.

A crucial detail is how the random distance len is generated. A simple uniform selection of len from [0, radius] would result in points being denser near the center. To ensure a uniform distribution of points over the entire area of the circle, the probability of a point being at a certain radius must be proportional to that radius (since the circumference, and thus the available space, grows with the radius). This is achieved by generating the radius len as radius * sqrt(u), where u is a uniformly distributed random number in [0, 1).

The full algorithm is:

Generate a random angle angle = Math.random() * 2 * Math.PI.
Generate a random value u = Math.random() and calculate the correctly distributed length len = radius * Math.sqrt(u).
Calculate the Cartesian offsets: x_offset = len * Math.cos(angle) and y_offset = len * Math.sin(angle).
Add the center coordinates to get the final point: x = x_center + x_offset, y = y_center + y_offset.

This method has a deterministic runtime for each call, as it always performs the same set of calculations.

1class Solution {2    private double radius;3    private double x_center;4    private double y_center;5 6    public Solution(double radius, double x_center, double y_center) {7        this.radius = radius;8        this.x_center = x_center;9        this.y_center = y_center;10    }11 12    public double[] randPoint() {13        double angle = Math.random() * 2 * Math.PI;14        double len = Math.sqrt(Math.random()) * radius;15        double x = x_center + len * Math.cos(angle);16        double y = y_center + len * Math.sin(angle);17        return new double[]{x, y};18    }19}

Complexity

Time

O(1) - Each call to `randPoint` involves a fixed number of operations: two random number generations, one square root, one sine, one cosine, and a few multiplications and additions.

Space

O(1) - We only store the initial parameters of the circle.

Trade-offs

Pros

Provides a uniform distribution of points.
The runtime is deterministic for each generated point, which can be important for real-time applications.

Cons

Relies on trigonometric functions (sin, cos) and a square root (sqrt), which are generally more computationally expensive than basic arithmetic operations.
The mathematical reasoning behind using sqrt(random()) for the radius is less intuitive than the rejection sampling method.

Rejection Sampling is a simple and powerful Monte Carlo method. The idea is to generate random points in a larger, simpler shape (a bounding box, in this case, a square) and only accept the points that fall within the desired, more complex shape (the circle). By repeatedly 'throwing darts' at the square and keeping only those that land in the circle, we ensure the resulting points are uniformly distributed within the circle.

Algorithm

Define a square that bounds the circle. The square will be centered at (x_center, y_center) and have a side length of 2 * radius.
Enter a loop that continues until a valid point is found.
Inside the loop, generate a random point (x, y) uniformly within the bounding square. This can be done by generating x in [x_center - radius, x_center + radius] and y in [y_center - radius, y_center + radius].
Check if the generated point lies inside the circle. To do this efficiently, we check if the squared distance from the center is less than or equal to the squared radius: (x - x_center)² + (y - y_center)² ≤ radius².
If the point is inside the circle, return it and exit the loop.
If the point is outside, the loop continues, and a new point is generated.

Walkthrough

This approach works by generating random points in a square that encloses the circle and rejecting any points that fall outside the circle.

The algorithm proceeds as follows:

We imagine a square centered at (x_center, y_center) with sides of length 2 * radius. The x-coordinates of this square range from x_center - radius to x_center + radius, and the y-coordinates range from y_center - radius to y_center + radius.
We repeatedly generate a random point within this square.
- Generate a random x-offset dx from -radius to +radius.
- Generate a random y-offset dy from -radius to +radius.
For each generated point (x_center + dx, y_center + dy), we check if it's inside the circle.
The condition for a point to be inside the circle is that its distance from the center is at most radius. To avoid a costly square root operation, we compare the squared distances: dx² + dy² ≤ radius².
If the condition is met, we have found a valid point, and we return [x_center + dx, y_center + dy].
If the condition is not met, the point is 'rejected', and we loop again to generate a new candidate point.

The probability of a random point in the square also being in the circle is the ratio of their areas: Area(circle) / Area(square) = (π * r²) / (2r)² = π / 4 ≈ 0.785. This means we expect to find a valid point in approximately 4 / π ≈ 1.27 attempts.

1class Solution {2    private double radius;3    private double x_center;4    private double y_center;5 6    public Solution(double radius, double x_center, double y_center) {7        this.radius = radius;8        this.x_center = x_center;9        this.y_center = y_center;10    }11 12    public double[] randPoint() {13        while (true) {14            // Generate random offsets from the center in the range [-radius, radius]15            double x_offset = (Math.random() * 2 - 1) * radius;16            double y_offset = (Math.random() * 2 - 1) * radius;17 18            // Check if the point is inside the circle using squared distance19            if (x_offset * x_offset + y_offset * y_offset <= radius * radius) {20                return new double[]{x_center + x_offset, y_center + y_offset};21            }22        }23    }24}

Complexity

Time

O(1) on average. The number of iterations is determined by a geometric distribution with a success probability of `π/4`. The expected number of iterations is constant (`4/π ≈ 1.27`).

Space

O(1) - We only store the initial parameters of the circle.

Trade-offs

Pros

Conceptually very simple and easy to implement.
Computationally efficient on average, as it avoids expensive functions like sqrt, sin, and cos, relying only on basic arithmetic.
Easily generalizable to other complex shapes for which a bounding box can be found.

Cons

The runtime is not deterministic. While it's O(1) on average, in a rare worst-case scenario, it could take many iterations to find a point inside the circle.

Solutions

Solution

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem