Keywords: uniform distribution | random point generation | inverse transform sampling | probability density function | circle sampling
Abstract: This paper thoroughly explores the mathematical principles behind generating uniformly distributed random points within a circle, explaining why naive polar coordinate approaches lead to non-uniform distributions and deriving the correct algorithm using square root transformation. Through concepts of probability density functions, cumulative distribution functions, and inverse transform sampling, it systematically presents the theoretical foundation while providing complete code implementation and geometric intuition to help readers fully understand this classical problem's solution.
Problem Background and Intuitive Analysis
In computer graphics, physical simulations, and game development, there is frequent need to generate uniformly distributed random points within a circle. A common mistaken intuition is to sample uniformly in both the radius interval (0, R) and angle interval [0, 2π). However, this approach causes excessive concentration of points near the center because as radius increases, the arc length corresponding to the same angle interval grows linearly while point density remains constant.
Mathematical Modeling and Probability Analysis
Considering the unit circle (R=1) case, to achieve uniform distribution across the entire circular area, we need to ensure that the number of points in any concentric ring is proportional to its area. Since ring area is proportional to radius r (area element is 2πrdr), the probability density of points should grow linearly with radius.
Let random variable r represent the distance from the point to the center, its probability density function (PDF) should satisfy:
f(r) = 2r, 0 ≤ r ≤ 1
This PDF satisfies the normalization condition: ∫01 2rdr = 1. When extending to radius R, the corresponding PDF becomes:
f(r) = 2r/R², 0 ≤ r ≤ R
Inverse Transform Sampling Method
Inverse transform sampling is a general technique for converting uniform distribution to any specified distribution. The core steps include:
- Calculate the cumulative distribution function (CDF) of the target distribution
- Find the inverse function of the CDF
- Substitute uniform random numbers into the inverse function
For our PDF f(r) = 2r, the cumulative distribution function is:
F(r) = ∫0r 2tdt = r²
Finding the inverse function gives:
F⁻¹(u) = √u
Therefore, to generate radius distribution meeting the requirements, we simply compute:
r = R * √random()
Complete Algorithm Implementation
Based on the above derivation, the complete uniform random point generation algorithm is as follows:
function generateUniformPointInCircle(centerX, centerY, radius) {
// Generate uniformly distributed radius
let r = radius * Math.sqrt(Math.random());
// Generate uniformly distributed angle
let theta = 2 * Math.PI * Math.random();
// Convert to Cartesian coordinates
let x = centerX + r * Math.cos(theta);
let y = centerY + r * Math.sin(theta);
return {x, y};
}
Geometric Intuitive Explanation
From a geometric perspective, the square root transformation ensures constant area density of points. Consider two concentric rings with inner radius r₁ and outer radius r₂. Their area ratio is (r₂² - r₁²):(r₁² - 0²). Through square root transformation, we are essentially performing uniform sampling in area space rather than in radius space.
Alternative Method Comparison
Besides the inverse transform sampling method, other techniques exist for generating uniform random points in a circle. One algorithm based on triangle approximation uses the following code:
function alternativeMethod(radius) {
let t = 2 * Math.PI * Math.random();
let u = Math.random() + Math.random();
let r = (u > 1) ? (2 - u) : u;
return {
x: radius * r * Math.cos(t),
y: radius * r * Math.sin(t)
};
}
This method simulates linear distribution through the sum of two uniform random numbers. While computationally efficient, its mathematical principles are less intuitive than the inverse transform sampling method.
Practical Applications and Considerations
In practical programming, attention should be paid to the quality of random number generators. Low-quality random number generators may cause visible patterns or biases in point distribution. Additionally, for high-performance applications, consider precomputing trigonometric function values or using lookup tables to optimize performance.
This algorithm can be widely applied in:
- Initial position distribution in particle systems
- Sampling point generation in Monte Carlo integration
- Random texture generation in computer graphics
- Random event location determination in games
Conclusion
By deeply understanding the mathematical principles of probability density functions, cumulative distribution functions, and inverse transform sampling, we have not only mastered the correct method for generating uniform random points in a circle but, more importantly, established a general framework for solving similar distribution generation problems. The square root transformation ensures truly uniform distribution of points across the circular area, avoiding the center concentration phenomenon caused by simple polar coordinate methods.