Given the radius and the position of the center of a circle, implement the function randPoint which generates a uniform random point inside the circle.
Implement the Solution class:
Solution(double radius, double x_center, double y_center) initializes the object with the radius of the circle radius and the position of the center (x_center, y_center).randPoint() returns a random point inside the circle. A point on the circumference of the circle is considered to be in the circle. The answer is returned as an array [x, y].
Example 1:
Input ["Solution", "randPoint", "randPoint", "randPoint"] [[1.0, 0.0, 0.0], [], [], []] Output [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]] Explanation Solution solution = new Solution(1.0, 0.0, 0.0); solution.randPoint(); // return [-0.02493, -0.38077] solution.randPoint(); // return [0.82314, 0.38945] solution.randPoint(); // return [0.36572, 0.17248]
Constraints:
0 < radius <= 108-107 <= x_center, y_center <= 1073 * 104 calls will be made to randPoint.Rejection sampling is a technique used to generate samples from a distribution by generating samples from a proposal distribution and then rejecting some of the samples. In the context of this problem, you can generate random points in a square that circumscribes the circle and then only accept those points that lie inside the circle.
This solution uses a square of side double the radius centered at the (x_center, y_center) to generate random points. If the point lies within the circle (determined by the condition x^2 + y^2 <= radius^2), it is returned, otherwise the process is repeated.
C++
Time Complexity: O(1) on average. Space Complexity: O(1) as no extra space is used.
Instead of generating points in a square and rejecting those outside the circle, we can directly generate points within the circle using polar coordinates. By randomly selecting an angle and a distance from the center, and then converting these polar coordinates to Cartesian coordinates, we can efficiently generate a uniform random point within the circle.
This Java solution utilizes polar coordinates to generate a point by first determining a random angle and a random radial distance (scaled correctly) within the circle. The radial distance is the square root of a random number between 0 and 1 multiplied by the circle's radius to ensure uniform distribution.
JavaScript
Time Complexity: O(1). Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Rejection Sampling | Time Complexity: |
| Polar Coordinates | Time Complexity: |
The BEST Way to Find a Random Point in a Circle | #SoME1 #3b1b • nubDotDev • 469,801 views views
Watch 9 more video solutions →Practice Generate Random Point in a Circle with our built-in code editor and test cases.
Practice on FleetCode