Solution: Generate Random Point in a Circle

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #478 (Medium): Generate Random Point in a Circle

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.

Note:

• input and output values are in floating-point.
• radius and x-y position of the center of the circle is passed into the class constructor.
• a point on the circumference of the circle is considered to be in the circle.
• randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.

Examples:

Example 1:
Input:	["Solution","randPoint","randPoint","randPoint"] [[1,0,0],[],[],[]]
Output:	[null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
Explanation:	The input is two lists: the subroutines called and their arguments. Solution's constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Example 2:
Input:	["Solution","randPoint","randPoint","randPoint"] [[10,5,-7.5],[],[],[]]
Output:	[null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

The easiest way to get a random point in a circle is to use polar notation. With polar notation, you can define any point in the circle with the polar angle (ang) and the length of the hypotenuse (hyp).

For both, we can apply a random number generator to give us a value in a usable range. The polar angle will be in the range [0, 2 * pi] and the hypotenuse will be in the range [0, radius].

Things can get tricky when we're finding a random value for the hypotenuse, however, because if we evenly favor the entire allowable range, the points will tend to be more densely packed towards the center of the circle.

Take, for example, a circle with a radius of 1. If we divide the radius in half, the area in which the points with a hypotenuse in the smaller half ([0, 0.5]) will be scattered is a circle of radius 0.5 whose area is defined as pi * (0.5)^2, or 0.25 * pi. The area in which the points with a hypotenuse in the larger half ([0.5, 1]) will be scattered is the remaining difference of the larger circle, defined as pi * 1^2 - 0.25 * pi, or 0.75 * pi.

So even though the two halves are even, the area described by rotating the two halves around the center are drastically different. In order to allow for an even distribution, then, we need to take the square root of the random number before multiplying it by the radius to get our hypotenuse, so that we can exponentially favor values farther from the center.

Once we have our values for ang and hyp, we can simply use sine and cosine to obtain values for the opposite (opp) and adjacent (adj) legs of our right triangle, which will equal the amount we need to add to/subtract from the x and y coordinates of our center point (XC, YC).

Implementation:

The code for all four languages is almost identical.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

class Solution {    constructor(radius, x_center, y_center) {        this.RAD = radius        this.XC = x_center        this.YC = y_center    }    randPoint() {        let ang = Math.random() * 2 * Math.PI,            hyp = Math.sqrt(Math.random()) * this.RAD,            adj = Math.cos(ang) * hyp,            opp = Math.sin(ang) * hyp        return [this.XC + adj, this.YC + opp]    }};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:    def __init__(self, radius: float, x_center: float, y_center: float):        self.RAD = radius        self.XC = x_center        self.YC = y_center    def randPoint(self) -> List[float]:        ang = random.uniform(0, 1) * 2 * math.pi        hyp = sqrt(random.uniform(0, 1)) * self.RAD        adj = cos(ang) * hyp        opp = sin(ang) * hyp        return [self.XC + adj, self.YC + opp]

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {    double RAD, XC, YC;    public Solution(double radius, double x_center, double y_center) {        RAD = radius;        XC = x_center;        YC = y_center;    }    public double[] randPoint() {        double ang = Math.random() * 2 * Math.PI,            hyp = Math.sqrt(Math.random()) * RAD,            adj = Math.cos(ang) * hyp,            opp = Math.sin(ang) * hyp;        return new double[]{XC + adj, YC + opp};    }}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {public:    double RAD, XC, YC;    Solution(double radius, double x_center, double y_center) {        RAD = radius;        XC = x_center;        YC = y_center;    }       vector<double> randPoint() {        double ang = (double)rand() / RAND_MAX * 2 * M_PI,            hyp = sqrt((double)rand() / RAND_MAX) * RAD,            adj = cos(ang) * hyp,            opp = sin(ang) * hyp;        return vector<double>{XC + adj, YC + opp};    }};