algoadvance

You are given a circle represented as (x_center, y_center, radius). Implement a class Solution with two methods:

  1. __init__(self, radius: float, x_center: float, y_center: float): This initializes the class with the circle’s radius and center.
  2. randPoint(self) -> List[float]: This method returns a random point inside the circle. Each point must be uniformly distributed inside the circle.

Here’s the problem from LeetCode 478. Generate Random Point in a Circle:

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        pass

    def randPoint(self) -> List[float]:
        pass

Clarifying Questions

  1. Uniform Distribution: Should the points be uniformly distributed inside the circle? (Assumption: Yes, they should be covered uniformly.)
  2. Precision of Points: Is there any specific precision required for the floating points? (Assumption: Standard floating-point precision should be fine.)
  3. Bounding Box Usage: Can we use a bounding box and rejection sampling to generate points within the circle? (Assumption: Yes, this can be a valid strategy.)

Strategy

To ensure the points are uniformly distributed inside the circle, we should follow these steps:

  1. Random Radius and Angle:
    • Generate a random radius r using the square root of a uniformly generated random number. This ensures uniform distribution over the area.
    • Generate a random angle theta between 0 and 2*pi.
  2. Conversion to Cartesian Coordinates:
    • Convert the polar coordinates (r, theta) to Cartesian coordinates using the formulas:
      • x = x_center + r * cos(theta)
      • y = y_center + r * sin(theta)
  3. Implementation Details:
    • Use Python’s random module to generate random numbers.
    • Ensure that the points are calculated accurately within the desired range.

Code

Here’s the implementation based on the discussed strategy:

import random
import math
from typing import List

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]:
        # Generate a random radius with sqrt scaling to ensure uniform distribution over the area
        r = self.radius * math.sqrt(random.random())
        # Generate a random angle
        theta = random.uniform(0, 2 * math.pi)
        # Convert polar coordinates to Cartesian coordinates
        x = self.x_center + r * math.cos(theta)
        y = self.y_center + r * math.sin(theta)
        return [x, y]

Time Complexity

This solution efficiently ensures uniformly distributed random points inside a given circle.

Try our interview co-pilot at AlgoAdvance.com