We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Generate Random Point in a Circle

Number: 915

Difficulty: Medium

Paid? No

Companies: Ultraleap

Problem Description

Design a Solution class that, given a circle defined by its radius and center, provides a method randPoint() which generates a uniformly random point within the circle. Points on the circle's circumference are considered inside.

Key Insights

  • The uniform distribution is achieved by careful sampling in polar coordinates.
  • Directly choosing a random radius uniformly does not yield a uniform distribution in the circle. Instead, generate the square root of a uniformly distributed value.
  • Compute the coordinates using: x = x_center + r * cos(theta), y = y_center + r * sin(theta).

Space and Time Complexity

Time Complexity: O(1) per call to randPoint() Space Complexity: O(1)

Solution

The solution leverages polar coordinates to ensure uniform randomness within the circle. The key steps are:

  1. Generate a random angle theta between 0 and 2π.
  2. Generate a random number between 0 and 1, take its square root, and multiply by the circle's radius to obtain the random distance (r). This ensures that the probability distribution is uniform over the circle.
  3. Convert the polar coordinates (r, theta) to Cartesian coordinates using cosine and sine functions.
  4. Offset the computed coordinates by the center of the circle (x_center, y_center).

This approach guarantees both uniform distribution and an efficient O(1) solution per point generation.

Code Solutions

import math
import random

class Solution:
    def __init__(self, radius: float, x_center: float, y_center: float):
        # Initialize the circle's radius and center coordinates.
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center
    
    def randPoint(self):
        # Generate a random angle between 0 and 2π.
        theta = random.uniform(0, 2 * math.pi)
        # Generate a random distance from center by taking square root of uniformly sampled number.
        r = self.radius * math.sqrt(random.uniform(0, 1))
        # Compute new x and y coordinates.
        x = self.x_center + r * math.cos(theta)
        y = self.y_center + r * math.sin(theta)
        return [x, y]
← Back to All Questions