Generate Random Point in a Circle

Problem Statement

The problem requires you to design and implement a class named Solution with functionalities to manage and generate random points inside a circle. This circle is defined by a given radius and the coordinates of its center. The class should instantiate using the constructor Solution(double radius, double x_center, double y_center) where:

• radius is the radius of the circle.
• x_center and y_center establish the coordinates of the circle's center.

Another critical function in this class, randPoint(), must generate and return a random point within the bounds of the circle, including its circumference. The function should output the coordinates of this random point as an array [x, y].

This simulates a real-world scenario where random placement of items inside a circular area is needed, ensuring each point lies within the circle's boundary.

Examples

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(); // returns a random point like [-0.02493, -0.38077]
solution.randPoint(); // another random point like [0.82314, 0.38945]
solution.randPoint(); // another random point like [0.36572, 0.17248]

Constraints

• 0 < radius <= 10^8
• -10^7 <= x_center, y_center <= 10^7
• At most 3 * 10^4 calls will be made to randPoint

Approach and Intuition

The task is to select a random point inside a given circle uniformly. This involves understanding both the math of a circle and ensuring uniform randomness:

1. A circle in a plane is defined by its center (x_center, y_center) and radius r. A point (x, y) is inside the circle if (x - x_center)^2 + (y - y_center)^2 <= r^2.

2. Simply generating random x and y within a square around the circle leads to non-uniform distribution, as points cluster near the center.

3. To ensure uniform distribution:

   • Generate a random angle θ from [0, 2π].

   • Generate a random radius r from [0, radius], but use r = sqrt(random()) * radius to correct for area bias.

   • Convert polar coordinates to Cartesian:

     • x = r * cos(θ)
     • y = r * sin(θ)

   • Shift the point by the center coordinates:

     • x += x_center
     • y += y_center

Using this method ensures that the random points are evenly distributed across the entire area of the circle, including the edge. This strategy is mathematically sound and computationally efficient.

Solutions

class RandomPointGenerator {
public:
    double radius, xCenter, yCenter;
    mt19937 rngEngine{random_device{}()};
    uniform_real_distribution<double> distribution{0, 1};
    
    RandomPointGenerator(double r, double x, double y) {
        radius = r, xCenter = x, yCenter = y;
    }
    
    vector<double> generate() {
        double distance = radius * sqrt(distribution(rngEngine));
        double angle = distribution(rngEngine) * (2 * M_PI);
        return {distance * cos(angle) + xCenter, distance * sin(angle) + yCenter};
    }
};