Code Implementation

import random
import math

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) -> [float, float]:
        while True:
            x = random.uniform(-self.radius, self.radius)
            y = random.uniform(-self.radius, self.radius)
            if x * x + y * y <= self.radius * self.radius:
                return [self.x_center + x, self.y_center + y]
      

class Solution {
    double radius, x_center, y_center;
public:
    Solution(double radius, double x_center, double y_center) {
        this->radius = radius;
        this->x_center = x_center;
        this->y_center = y_center;
    }
    
    vector<double> randPoint() {
        while (true) {
            double x = (double)rand() / RAND_MAX * 2 * radius - radius;
            double y = (double)rand() / RAND_MAX * 2 * radius - radius;
            if (x * x + y * y <= radius * radius) {
                return {x_center + x, y_center + y};
            }
        }
    }
};
      

import java.util.Random;

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() {
        while (true) {
            double x = rand.nextDouble() * 2 * radius - radius;
            double y = rand.nextDouble() * 2 * radius - radius;
            if (x * x + y * y <= radius * radius) {
                return new double[]{x_center + x, y_center + y};
            }
        }
    }
}
      

var Solution = function(radius, x_center, y_center) {
    this.radius = radius;
    this.x_center = x_center;
    this.y_center = y_center;
};

Solution.prototype.randPoint = function() {
    while (true) {
        let x = Math.random() * 2 * this.radius - this.radius;
        let y = Math.random() * 2 * this.radius - this.radius;
        if (x * x + y * y <= this.radius * this.radius) {
            return [this.x_center + x, this.y_center + y];
        }
    }
};
      

Problem Description

Given a circle with a given radius and center at coordinates (x_center, y_center), implement a class that can generate a random point uniformly distributed inside the circle. Each time the randPoint() method is called, it should return a random point [x, y] such that the point lies inside or on the boundary of the circle. The distribution of points must be uniform, meaning every point within the circle is equally likely to be chosen.

• Input: radius, x_center, y_center
• Function: randPoint() returns a random [x, y] within the circle
• Constraints: Points must be truly random and uniformly distributed inside the entire area of the circle

Thought Process

At first glance, the problem seems straightforward: just pick random x and y values within the circle's bounding box. However, this approach does not guarantee that the points are inside the circle, nor does it ensure a uniform distribution.

The main challenge is to ensure that points are evenly spread across the entire area of the circle, not just within the bounding square. If we simply pick random x and y in the square, many of the points will fall outside the circle, and discarding them can be inefficient. Moreover, using naive polar coordinates may lead to clustering near the center if not handled properly.

The key insight is to use rejection sampling or to generate points using polar coordinates with a correction for uniform area distribution.

Solution Approach

There are two common approaches to solve this problem:

• Rejection Sampling:
  • Randomly select x and y within the bounding square of the circle (from -radius to radius).
  • If the point (x, y) is inside the circle (i.e., x^2 + y^2 <= radius^2), return it. Otherwise, repeat.
  • This approach is simple and ensures uniformity but may discard some points (those outside the circle).
• Polar Coordinates with Area Correction:
  • Randomly pick an angle theta between 0 and 2π.
  • Randomly pick a radius r such that the probability is proportional to r (to ensure uniform area coverage). This is done by r = radius * sqrt(random()).
  • Compute x = x_center + r * cos(theta) and y = y_center + r * sin(theta).
  • This approach is efficient and always produces a valid point.

In the code provided, we use the Rejection Sampling method because it's straightforward and easy to implement in any language.

1. In the constructor, store the radius and the center coordinates.
2. In randPoint(), loop until a random point within the bounding square falls inside the circle.
3. Return the valid point, shifted by the circle's center.

This method guarantees uniform distribution and is simple to code.

Example Walkthrough

Let's walk through an example where radius = 2, x_center = 1, y_center = 1.

1. The bounding square is from x = -2 to 2 and y = -2 to 2.
2. Suppose we randomly pick x = 1.3, y = -0.7.
3. Check if this point is inside the circle: x^2 + y^2 = 1.3^2 + (-0.7)^2 = 1.69 + 0.49 = 2.18. Since 2.18 <= 4 (because radius^2 = 4), the point is inside.
4. Return the point shifted by the center: x_center + x = 1 + 1.3 = 2.3, y_center + y = 1 + (-0.7) = 0.3.
5. If the point was outside the circle, the process would repeat until a valid point is found.

This process ensures that every call to randPoint() returns a point inside the circle, uniformly distributed.

Time and Space Complexity

• Brute-force (Rejection Sampling):
  • Time Complexity: On average, the ratio of the area of the circle to the area of the square is π/4 (~78.5%). So, on average, each point is generated in about 1.27 tries. Thus, the expected time per call is O(1).
  • Space Complexity: O(1) since we only store the circle's parameters.
• Optimized (Polar Coordinates):
  • Time Complexity: O(1) per point, since no points are discarded.
  • Space Complexity: O(1).

Both approaches are very efficient, but the polar coordinates method is slightly more optimal in terms of number of iterations.

Summary

Generating a random point uniformly inside a circle requires more than just picking random x and y values. By using rejection sampling or polar coordinates with area correction, we ensure that every point within the circle is equally likely to be chosen. The provided solution uses rejection sampling for its simplicity and clarity, but the polar coordinate method is also a great alternative. Both approaches are efficient and guarantee a uniform distribution of points inside the circle.