Generate a random point within a circle (uniformly)

Question

I need to generate a uniformly random point within a circle of radius R.

I realize that by just picking a uniformly random angle in the interval [0 ... 2π), and uniformly random radius in the interval (0 ... R) I would end up with more points towards the center, since for two given radii, the points in the smaller radius will be closer to each other than for the points in the larger radius.

I found a blog entry on this over here but I don't understand his reasoning. I suppose it is correct, but I would really like to understand from where he gets (2/R²)×r and how he derives the final solution.

---

Update: 7 years after posting this question I still hadn't received a satisfactory answer on the actual question regarding the math behind the square root algorithm. So I spent a day writing an answer myself. Link to my answer.

Answer 1

How to generate a random point within a circle of radius R:

r = R * sqrt(random())
theta = random() * 2 * PI

(Assuming random() gives a value between 0 and 1 uniformly)

If you want to convert this to Cartesian coordinates, you can do

x = centerX + r * cos(theta)
y = centerY + r * sin(theta)

Why sqrt(random())?

Let's look at the math that leads up to sqrt(random()). Assume for simplicity that we're working with the unit circle, i.e. R = 1.

The average distance between points should be the same regardless of how far from the center we look. This means for example, that looking on the perimeter of a circle with circumference 2 we should find twice as many points as the number of points on the perimeter of a circle with circumference 1.

                

Since the circumference of a circle (2πr) grows linearly with r, it follows that the number of random points should grow linearly with r. In other words, the desired probability density function (PDF) grows linearly. Since a PDF should have an area equal to 1 and the maximum radius is 1, we have

                

So we know how the desired density of our random values should look like. Now: How do we generate such a random value when all we have is a uniform random value between 0 and 1?

We use a trick called inverse transform sampling

1. From the PDF, create the cumulative distribution function (CDF)
2. Mirror this along y = x
3. Apply the resulting function to a uniform value between 0 and 1.

Sounds complicated? Let me insert a blockquote with a little side track that conveys the intuition:

Suppose we want to generate a random point with the following distribution:

                

That is

• 1/5 of the points uniformly between 1 and 2, and
• 4/5 of the points uniformly between 2 and 3.

The CDF is, as the name suggests, the cumulative version of the PDF. Intuitively: While PDF(x) describes the number of random values at x, CDF(x) describes the number of random values less than x.

In this case the CDF would look like:

                

To see how this is useful, imagine that we shoot bullets from left to right at uniformly distributed heights. As the bullets hit the line, they drop down to the ground:

                

See how the density of the bullets on the ground correspond to our desired distribution! We're almost there!

The problem is that for this function, the y axis is the output and the x axis is the input. We can only "shoot bullets from the ground straight up"! We need the inverse function!

This is why we mirror the whole thing; x becomes y and y becomes x:

                

We call this CDF^-1. To get values according to the desired distribution, we use CDF^-1(random()).

…so, back to generating random radius values where our PDF equals 2x.

Step 1: Create the CDF:

Since we're working with reals, the CDF is expressed as the integral of the PDF.

CDF(x) = ∫ 2x = x²

Step 2: Mirror the CDF along y = x:

Mathematically this boils down to swapping x and y and solving for y:

CDF:     y = x²
Swap:   x = y²
Solve:   y = √x
CDF^-1:  y = √x

Step 3: Apply the resulting function to a uniform value between 0 and 1

CDF^-1(random()) = √random()

Which is what we set out to derive :-)