This content originally appeared on DEV Community and was authored by seanpgallivan
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
randPointwhich 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.
randPointreturns 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};
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-03-17T09:40:32+00:00) Solution: Generate Random Point in a Circle. Retrieved from https://www.scien.cx/2021/03/17/solution-generate-random-point-in-a-circle/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.