# Generate Random Point in a Circle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/generate-random-point-in-a-circle)
Canonical: https://scaleengineer.com/dsa/problems/generate-random-point-in-a-circle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Algorithms:** [Rejection Sampling](https://scaleengineer.com/algorithms/rejection-sampling)
---
## Problem
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 <= 107`
* At most `3 * 104` calls will be made to `randPoint`.

# Approaches
## Polar Coordinates with Inverse Transform Sampling
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.
**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.
**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.
### Explanation
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:
1. Generate a random angle `angle = Math.random() * 2 * Math.PI`.
2. Generate a random value `u = Math.random()` and calculate the correctly distributed length `len = radius * Math.sqrt(u)`.
3. Calculate the Cartesian offsets: `x_offset = len * Math.cos(angle)` and `y_offset = len * Math.sin(angle)`.
4. 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.

```java
class Solution {
    private double radius;
    private double x_center;
    private double 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;
    }

    public double[] randPoint() {
        double angle = Math.random() * 2 * Math.PI;
        double len = Math.sqrt(Math.random()) * radius;
        double x = x_center + len * Math.cos(angle);
        double y = y_center + len * Math.sin(angle);
        return new double[]{x, y};
    }
}
```
### Algorithm
1. Generate a random angle `angle` uniformly in the range `[0, 2π)`.
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)`.
3. Convert the polar coordinates `(len, angle)` to Cartesian coordinates relative to the origin: `x_offset = len * cos(angle)` and `y_offset = len * sin(angle)`.
4. Translate the point by the circle's center coordinates: `x = x_center + x_offset` and `y = y_center + y_offset`.
5. Return the point `[x, y]`.

## Rejection Sampling
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.
**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.
**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.
### Explanation
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:
1. 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`.
2. 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`.
3. For each generated point `(x_center + dx, y_center + dy)`, we check if it's inside the circle.
4. 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²`.
5. If the condition is met, we have found a valid point, and we return `[x_center + dx, y_center + dy]`.
6. 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.

```java
class Solution {
    private double radius;
    private double x_center;
    private double 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;
    }

    public double[] randPoint() {
        while (true) {
            // Generate random offsets from the center in the range [-radius, radius]
            double x_offset = (Math.random() * 2 - 1) * radius;
            double y_offset = (Math.random() * 2 - 1) * radius;

            // Check if the point is inside the circle using squared distance
            if (x_offset * x_offset + y_offset * y_offset <= radius * radius) {
                return new double[]{x_center + x_offset, y_center + y_offset};
            }
        }
    }
}
```
### Algorithm
1. 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`.
2. Enter a loop that continues until a valid point is found.
3. 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]`.
4. 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²`.
5. If the point is inside the circle, return it and exit the loop.
6. If the point is outside, the loop continues, and a new point is generated.

# Solutions
### Python

```python
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]

```