How to sample a circle uniformly in 2D-CCS?

Question Description

Assume that we have a unit circle with R=1 and centered at the origin point. We need to generate some sample points inside the circle uniformly. The points should distribute uniformly inside the circle area in 2D-CCS, that is, the expectation per area of the number of sample points is the same inside the circle.

Note: 2D-CCS, 2-dimension Cartesian coordinate system.

Naive Solutions

Sample with Filter

Consider the bounding box of the unit circle, or the 2×2 square centered at the origin point, like the graph below.

A unit circle with a square around it

Assume we have two independent random variables P,Q uniformly distributed in [0,1]. Sampling the 2×2 square just need a simple tranformation as below:

{x=2P−1,y=2Q−1.

The transformation just scales each variable by 2 times, and moves the value interval center to 0.

But sampling the square is not sampling the circle, some sample points may be out of the circle. Given the square area is 2×2=4, and the circle area is π×12=π, there are (1−π4) of all sample points expected to be out of the circle, or the failure probability of the sampling is (1−π4).

The idea of the failure probability leads us to a different concept – expected random count for an output. This is easy to solve as the reciprocal of the area ratio, or 4π≈1.27. That means in average, we need 127 random results for 100 valid sample points, implying the poor efficiency of this method.

Polar Coordinates

How about mapping a square area to a circle area? This idea leads us to polar coodinate system, which uses (ρ,θ) to present a point in a plane. In PCS, a unit circle can be described as an equation ρ=1,θ∈[0,2π], as the graph below.

A circle in PCS

Same as above, we get 2 random variables P,Q, then scale Q to [0,2π], finally transform the polar coordinates to Cartesian coordinates.

{x=Pcos⁡(2πQ),y=Psin⁡(2πQ).

Random points generated by the method above[1]

Let’s have a try on this method, and get the distribution graph above. Points seem closer around the center than far from the center. Why?

In this method, we independently sample ρ and θ, that is, for every value of ρ, we are expected to have the same number of points distributed uniformly in θ value. But for smaller ρ, the circle perimeter, 2πρ, becomes smaller too. Smaller perimeter, same amount of points, closer the points seem to be.

Wise in Probabilities[2]

First, it’s OK to sample θ value uniformly in [0,2π], for the circle is centrosymmetric. All we need to do is to adjust the point distribution in sampling ρ value. But how?

Consider this, if we have 2 ρ values ρ1,ρ2, then the circle perimeters are 2πρ1 and 2πρ2. Points must be evenly distributed in this area, so the ratio of amount of points is the ratio of perimeter, that is ρ1ρ2. This leads to the idea of Probability Density Function, or PDF. If we let the PDF of points defined with ρ values is f(ρ), then the fact above indicates f(ρ) is a linear function.

f(0)=0 is the next things we know about the PDF, for ρ=0 presents a point. Then we assume f(ρ)=kρ and try to solve k. PDF must be normalized, or integrated to be 1. So

∫01f(ξ)dξ=∫01kξdξ=k2=1.

Obviously k=2, and f(ρ)=2ρ.

Let X be the random variable with a PDF of f(x)=2x. The question is, we have another random variable Y uniformly distributed in [0,1], try to find a function G(x) making G(Y) has the same distribution as X. This is a question about probability.

We can use Probability Distribution Function, another PDF, to solve this. This PDF is the integral of the PDF above, that is, P{X≤x}=∫0xf(x)dx=x2. The same distribution means the same PDF, so P{G(Y)≤x}=P{X≤x}=x2, or P{Y≤G−1(x)}=x2. We also know that P{Y≤y}=y, then G−1(x)=x2 and G(x)=x.

Back to the question, we have 2 variables P,Q, then let another variable P′=P, then do the transformation like

{x=P′cos⁡(2πQ),y=P′sin⁡(2πQ).={x=Pcos⁡(2πQ),y=Psin⁡(2πQ).

Problem solved.

Random generated by the method with a P in it[1]

Look at the sample points, how beautiful!

References