This post explores the problem of uniformly sampling points within a disk and reveals why a naive approach using polar coordinates leads to a concentration of points near the center. The author demonstrates that while generating a random angle and a random radius seems correct, it produces a non-uniform distribution due to the varying area of concentric rings within the disk. The solution presented involves generating a random angle and a radius proportional to the square root of a random number between 0 and 1. This adjustment accounts for the increasing area at larger radii, resulting in a truly uniform distribution of sampled points across the disk. The post includes clear visualizations and mathematical justifications to illustrate the problem and the effectiveness of the corrected sampling method.
The blog post "Non-random uniform disk sampling" by Victor Poughon explores the common problem of generating uniformly distributed random points within a unit disk and identifies a subtle but significant flaw in a naive approach. This naive method, which involves generating random polar coordinates (a radius r and an angle θ) independently, leads to a non-uniform distribution with a higher concentration of points near the center of the disk. The author explains that while selecting the angle θ uniformly from 0 to 2π is correct, the issue arises from choosing the radius r uniformly from 0 to 1. This uniform selection of r results in a disproportionate number of points being generated in the smaller inner circles of the disk, violating the desired uniform distribution across the entire disk's area.
The post then derives the correct distribution for the radius r by considering the relationship between the area and the radius of concentric circles within the disk. Since the area of a circle is proportional to the square of its radius (Area = πr²), the author demonstrates that the radius r should not be selected uniformly but should instead be proportional to the square root of a uniformly distributed variable between 0 and 1. This ensures that equal areas within the disk have an equal probability of containing a randomly generated point, achieving the desired uniform distribution.
The post provides a clear mathematical justification for this correction and presents the final corrected algorithm: choose a uniform random angle θ between 0 and 2π, choose a uniform random value a between 0 and 1, and calculate the radius r as the square root of a. The resulting point with polar coordinates (r, θ) will then be uniformly distributed within the unit disk. The author emphasizes the importance of this correction for applications requiring truly uniform distributions within a disk, such as Monte Carlo simulations or computer graphics. He further illustrates the difference between the incorrect and correct methods with visual examples showing the clustering of points towards the center when using the naive approach versus the even distribution achieved with the corrected square root method. The post concludes by offering Python code implementations of both the incorrect and correct algorithms, allowing readers to easily visualize and experiment with the different sampling methods.
Summary of Comments ( 23 )
https://news.ycombinator.com/item?id=42843252
HN users discuss various aspects of uniformly sampling points within a disk. Several commenters point out the flaws in the naive
sqrt(random())approach, correctly identifying its tendency to cluster points towards the center. They offer alternative solutions, including the accepted approach of sampling an angle and radius separately, as well as using rejection sampling. One commenter explores generating points within a square and rejecting those outside the circle, questioning its efficiency compared to other methods. Another details the importance of this problem in ray tracing and game development. The discussion also delves into the mathematical underpinnings, with commenters explaining the need for the square root on the radius to achieve uniformity and the relationship to the area element in polar coordinates. The practicality and performance of different methods are a recurring theme, including comparisons to pre-calculated lookup tables.The Hacker News post titled "Non-random uniform disk sampling," linking to an article explaining various methods for sampling points within a disk, generated a moderate amount of discussion. Several commenters focused on the practical implications and efficiency of different approaches.
One compelling thread discussed the surprising inefficiency of the naive rejection sampling method (generating random points in a square and rejecting those outside the circle) in higher dimensions. Commenters pointed out how the acceptance rate drastically decreases as dimensionality increases, making it computationally expensive. This spurred further discussion about more sophisticated methods like inverse transform sampling, which offer better performance, especially in higher dimensions.
Another key discussion revolved around the use cases for disk sampling. Commenters brought up applications in computer graphics, simulations (e.g., distributing points on a sphere), and procedural generation. This highlighted the practical relevance of the topic and the importance of choosing an efficient sampling method depending on the specific application.
One commenter offered a concise and insightful explanation of why simply generating a random angle and radius doesn't lead to uniform distribution, emphasizing the need for a square root correction to the radius. This helped clarify a common misconception and underscored the mathematical nuance involved in generating uniformly distributed samples.
There was also a brief exchange about alternative approaches like using pre-calculated lookup tables for generating random points, which could be advantageous in performance-critical scenarios.
Overall, the comments section provides a valuable extension to the original article by exploring the practical considerations of different disk sampling methods, highlighting their strengths and weaknesses, and connecting the concepts to real-world applications. The discussion emphasizes the importance of efficiency, particularly in higher dimensions, and clarifies common misconceptions about seemingly straightforward approaches.