478. Generate Random Point in a Circle

MediumGeometryMathRejection SamplingRandomized
Leetcode Link

Problem Description

Given a circle defined by its radius and the (x_center, y_center) coordinates of its center, the task is to create a function randPoint that can generate a random point within the boundaries of this circle. A valid random point could lie anywhere from the center of the circle to the circumference, with each potential point inside the circle having an equal chance of being selected.

Intuition

The intuitive approach to randomly generating a point within a circle involves two steps - finding a random distance from the center within the range [0, radius] and finding a random angle to pair with this distance.

Here's a breakdown of the solution approach:

  1. Generate a random radius: This should be between 0 and the radius of the circle. But we can't simply pick a uniform random number directly between these two because we're working in two dimensions. If we did that, there would be a higher concentration of points near the circumference than near the center β€” which wouldn't be uniformly random. To get a uniform distribution, we take the square root of a random number between 0 and the square of the radius. In a 2D space, the area of a circle increases with the square of the radius, so this method ensures a uniform distribution of points by their area.

  2. Generate a random angle: Angles in a circle range from 0 to 2Ο€ radians, representing 0 to 360 degrees. Each point within the circle corresponds to an angle from the center. By choosing a random angle from this range, we can cover all possible directions uniformly.

  3. Calculate the coordinates: With the random length and angle, calculate the x and y coordinates of the random point. We use the random radius (length) to determine how far from the center the point is, and the random angle (degree) to determine the direction. Using the formulas x = centerX + length * cos(degree) and y = centerY + length * sin(degree), we can find the position of the random point in a Cartesian coordinate system where centerX and centerY are the coordinates of the center of the circle.

These steps ensure a uniformly random distribution of generated points within the circle.

Solution Approach

The implementation of the Solution class in Python takes advantage of the math module for mathematical functions such as math.sqrt for square root and math.cos and math.sin for cosine and sine functions. It also uses random.uniform to generate a floating-point number within a range. Here is a walk-through of the solution.

  1. Class Initialization: The __init__ method initializes the instance of the class with the radius, x_center, and y_center.

    1class Solution:
    2    def __init__(self, radius: float, x_center: float, y_center: float):
    3        self.radius = radius
    4        self.x_center = x_center
    5        self.y_center = y_center

    This is simple setup code that stores the inputs to be used in the randPoint method.

  2. Random Point Generation:

    The randPoint method is where the random point within the circle is generated.

    a. Generate a random length from the circle's center by using the square root method described in the intuition section to ensure a uniform distribution.

    1 ```python
    2 length = math.sqrt(random.uniform(0, self.radius**2))
    3 ```
    4
    5 `random.uniform(0, self.radius**2)` picks a number uniformly between `0` and the square of the `radius`, and then `math.sqrt` calculates its square root to get a length that has a uniform distribution within the circle when paired with a random angle.

    b. Generate a random angle in radians. Any angle for a full rotation around a circle is between 0 and 2Ο€. This is represented by the following line of code:

    1 ```python
    2 degree = random.uniform(0, 1) * 2 * math.pi
    3 ```
    4
    5 `random.uniform(0, 1)` generates a number between `0` and `1`, multiplying this by `2 * math.pi` scales it to the range of `[0, 2Ο€]`.

    c. Compute the x and y coordinates based on the random length and degree. The cosine and sine functions translate the random length and direction into Cartesian coordinates:

    1 ```python
    2 x = self.x_center + length * math.cos(degree)
    3 y = self.y_center + length * math.sin(degree)
    4 ```
    5
    6 Here, `length * math.cos(degree)` finds the horizontal distance from the center, and `length * math.sin(degree)` finds the vertical distance from the center. When these are added to `self.x_center` and `self.y_center` respectively, the resulting `(x, y)` is the coordinate of the random point within the circle.

    d. Return a list containing the x and y coordinates of the random point:

    1 ```python
    2 return [x, y]
    3 ```

    This method can be called multiple times to generate different points within the circle each time it is called.

All of these steps come together to form the randPoint method of the Solution class which fulfills the problem requirement of generating a random and uniformly distributed point within a given circle.

πŸ’ͺ
Level Up Your
Algo Skills

Example Walkthrough

Let's say we're given a circle with a radius of 5 units and a center at coordinates (2, 3). We want to use the Solution class to generate a random point within this circle.

First, we initialize the Solution class with our circle's parameters:

1my_circle = Solution(5, 2, 3)

To generate a random point within the circle defined by my_circle, we'll walk through the randPoint method inside the Solution class.

  1. Generate a random radius (length):
1length = math.sqrt(random.uniform(0, my_circle.radius**2))

Imagine the random.uniform function returns 16 after being called with parameters 0 and 25 (since 5 squared is 25). So math.sqrt(16) is calculated, resulting in 4 units. This is our random radius, which is uniformly distributed within the circle.

  1. Generate a random angle (degree):
1degree = random.uniform(0, 1) * 2 * math.pi

Here, random.uniform returns approximately 0.5, and when this is multiplied by 2 * math.pi (approximately 6.283), we get roughly 3.142, which is equivalent to 180 degrees in radians. So, our random angle is essentially pointing to the left (west) direction if we imagine the center of the circle corresponding to a compass.

  1. Calculate the coordinates (x, y):
1x = my_circle.x_center + length * math.cos(degree)
2y = my_circle.y_center + length * math.sin(degree)

With length = 4 and degree β‰ˆ 3.142, the computations will approximate to:

  • math.cos(3.142) β‰ˆ -1 and math.sin(3.142) β‰ˆ 0.
  • So, x β‰ˆ my_circle.x_center + 4 * (-1) β†’ x β‰ˆ 2 - 4 β†’ x β‰ˆ -2.
  • y β‰ˆ my_circle.y_center + 4 * 0 β†’ y β‰ˆ 3.

Thus, the random point's coordinates are approximately (-2, 3).

  1. Return the coordinates:
1return [x, y]

The final result will be a coordinate list [-2, 3], which is a random point generated inside our circle of radius 5 with a center at (2, 3).

This example shows how each call to randPoint() would generate a different random point, uniformly distributed within the circle defined by the radius and center provided to the Solution class during initialization.

Python Solution

1import math
2import random
3from typing import List
4
5class Solution:
6    def __init__(self, radius: float, x_center: float, y_center: float):
7        # Initialize the Solution object with the center coordinates and radius of the circle.
8        self.radius = radius
9        self.x_center = x_center
10        self.y_center = y_center
11
12    def rand_point(self) -> List[float]:
13        # Generate a random length within the range [0, radius] with uniform distribution.
14        # The length is sqrt(R^2 * U) where R is the radius and U is a uniform random number [0,1)
15        length = math.sqrt(random.uniform(0, self.radius**2))
16      
17        # Generate a random angle between 0 and 2Ο€ for uniform distribution along the circumference.
18        degree = random.uniform(0, 1) * 2 * math.pi
19      
20        # Calculate the x and y coordinates using the length and angle, relative to the center.
21        x = self.x_center + length * math.cos(degree)  # Horizontal offset from center.
22        y = self.y_center + length * math.sin(degree)  # Vertical offset from center.
23      
24        # Return the random point as a list of its x and y coordinates.
25        return [x, y]
26
27# Note: The method name is preserved as 'rand_point' in compliance with the instruction not to modify method names.
28# However, typically in Python, method names would also follow the snake_case convention.
29

Java Solution

1import java.util.Random;
2
3public class Solution {
4    private double radius;
5    private double xCenter;
6    private double yCenter;
7    private Random random;
8
9    public Solution(double radius, double xCenter, double yCenter) {
10        // Initialize the Solution object with the center coordinates and radius of the circle.
11        this.radius = radius;
12        this.xCenter = xCenter;
13        this.yCenter = yCenter;
14        this.random = new Random(); // Initialize the random instance for generating random numbers.
15    }
16
17    public double[] randPoint() {
18        // Generate a random length within the range [0, radius] with uniform distribution.
19        // The length is sqrt(radius^2 * U) where U is a uniform random number in [0, 1).
20        double length = Math.sqrt(this.radius * this.radius * random.nextDouble());
21      
22        // Generate a random angle between 0 and 2Ο€ for uniform distribution along the circumference.
23        double angle = random.nextDouble() * 2 * Math.PI;
24      
25        // Calculate the x and y coordinates using the length and angle, relative to the center.
26        double x = this.xCenter + length * Math.cos(angle); // Horizontal offset from the center.
27        double y = this.yCenter + length * Math.sin(angle); // Vertical offset from the center.
28      
29        // Return the random point as an array of its x and y coordinates.
30        return new double[]{x, y};
31    }
32}
33

C++ Solution

1#include <cmath>
2#include <vector>
3#include <random>
4
5class Solution {
6private:
7    double radius;
8    double x_center;
9    double y_center;
10    std::default_random_engine generator;
11    std::uniform_real_distribution<double> distribution;
12
13public:
14    Solution(double radius, double x_center, double y_center) 
15        : radius(radius), x_center(x_center), y_center(y_center), distribution(0.0, 1.0) {
16        // Initialize the Solution object with the center coordinates and radius of the circle.
17    }
18
19    std::vector<double> rand_point() {
20        // Generate a random length within the range [0, radius] with uniform distribution.
21        // The length is sqrt(R^2 * U) where R is the radius and U is a uniform random number [0,1)
22        double length = std::sqrt(distribution(generator) * (radius * radius));
23      
24        // Generate a random angle between 0 and 2Ο€ for uniform distribution along the circumference.
25        double angle = distribution(generator) * 2 * M_PI;
26      
27        // Calculate the x and y coordinates using the length and angle, relative to the center.
28        double x = x_center + length * std::cos(angle); // Horizontal offset from center.
29        double y = y_center + length * std::sin(angle); // Vertical offset from center.
30      
31        // Return the random point as a vector of its x and y coordinates.
32        return {x, y};
33    }
34};
35
36// Usage example
37int main() {
38    Solution solution(10.0, 5.0, 5.0); 
39    std::vector<double> point = solution.rand_point();
40    // Now `point` contains the random coordinates
41}
42

Typescript Solution

1import * as math from "mathjs";
2
3// Define the circle's properties globally
4let radius: number;
5let x_center: number;
6let y_center: number;
7
8// Function to initialize the global variables with the center coordinates and radius of the circle
9function initCircle(newRadius: number, newX_center: number, newY_center: number): void {
10    radius = newRadius;
11    x_center = newX_center;
12    y_center = newY_center;
13}
14
15// Function to generate a random point within the circle
16function randPoint(): number[] {
17    // Generate a random length within the range [0, radius] with uniform distribution
18    // The length is the square root of (radius squared multiplied by a uniform random number [0, 1))
19    const length: number = Math.sqrt(Math.random() * (radius ** 2));
20
21    // Generate a random angle between 0 and 2Ο€ for uniform distribution along the circumference
22    const angle: number = Math.random() * 2 * Math.PI;
23
24    // Calculate the x and y coordinates using the length and angle, relative to the center
25    const x: number = x_center + length * Math.cos(angle); // Horizontal offset from center
26    const y: number = y_center + length * Math.sin(angle); // Vertical offset from center
27  
28    // Return the random point as an array of its x and y coordinates
29    return [x, y];
30}
31
32// Note: Although we have removed the class definition and included the methods globally,
33// in a typical TypeScript environment, we would still use a class or module to encapsulate these functions.
34// Additionally, 'import * as math from "mathjs";' is used instead of the default 'import math',
35// as TypeScript does not natively have a math module.
36

Time and Space Complexity

Time Complexity

The given code involves calculating a random point within a circle. The randPoint method contains a constant number of operations regardless of the input size:

  • random.uniform(0, self.radius**2) computes a uniform random value between 0 and the square of the radius, which takes constant time O(1).
  • Taking the square root with math.sqrt() is also a constant time operation O(1).
  • random.uniform(0, 1) * 2 * math.pi computes a random angle, which is again constant time O(1).
  • The sine and cosine functions are computed once per call to randPoint, both of which take constant time O(1).
  • Multiplying the length and angle calculations to get the x and y coordinates are basic arithmetic operations with constant time O(1).

Since all the operations are executed a constant number of times, the time complexity of the randPoint method is O(1).

Space Complexity

As for space complexity:

  • The Solution class holds three variables: self.radius, self.x_center, and self.y_center. This space usage does not scale with the number of times randPoint is called, and they are only stored once when the class instance is created.
  • Temporary variables used in randPoint for length, degree, x, and y are re-created on each call and do not accumulate. Thus, the space required for these variables is constant.

Given that no additional space is used that scales with the size of the input or the number of operations, the space complexity of the randPoint method is O(1).

😈
Become an
Algo Monster

Got a question?Β Ask the Teaching AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

←
↑TA πŸ‘¨β€πŸ«