sunil.page

Round in circles

Note: this is a follow-on post from follow your dart.

In making games, I often want to randomly place objects inside a circle. I have always done this one of two ways, but I feel unsatisfied with both.

Method 1: Randomly pick a point in the surrounding square, and reject points which are not in the circle.

function tick() {
    do {
        x = random( -radius, radius )
        y = random( -radius, radius )
        d = sqrt( x*x + y*y )
    } while (d > radius)
    drawDot( x, y )
}

This generates an even spread of points. However, I don't like the fact that you are not guaranteed to find a valid point on each iteration. In this example, dots which took more than one iteration to draw appear in red.

Method 2: Uniformly pick an angle and a distance.

function tick() {
    theta = random( 0, 2 * PI )
    d = random( 0, radius )
    drawDot( sin( theta ) * d, cos( theta ) * d )
}

This generates an uneven spread of points: there is a higher density of points near the centre. However, I like that each iteration will definitely pick a valid point.

I wanted to find the elusive method 3 which generates an even spread of points, but which is also guaranteed to generate a point every time. Using method 2 as the starting point, I will stick with a uniform distribution for the angle. I just need to find the how to correctly generate the distance from the centre.

Thinking about such a distribution is what instigated a previous blog post: follow your dart. From that, I know the c.d.f. of the distribution: \(F_D(d) = \frac{d^2}{r^2}\). That gives us:

$$ \begin{aligned} \Theta &\sim \text{Uniform}(0, 2\pi) \\ D &\sim F_D \end{aligned} $$

In programming, rand()-esque functions are usually only uniform. I need a way, therefore, to use the uniform distribution to generate samples of \(F_D\). Let us define a new random variable \(X\) which is the inverse of our target distribution applied to the uniform distribution: \(X = F_D^{-1}(U)\). It has c.d.f. \(F_X\).

$$ \begin{aligned} F_X(x) &= \mathbb{P}(X \le x) \\ &= \mathbb{P}(F_D^{-1}(U) \le x) \\ &= \mathbb{P}(U \le F_D(x)) \end{aligned} $$

For the last step, we apply \(F_D(\cdot)\) to both sides of the probability. This is acceptable since it's an increasing function (a property of the c.d.f.).

Finally, we look at the c.d.f. of the uniform distribution, it's just \(\mathbb{P}(U \le u) = u\). This means we have:

$$ \begin{aligned} F_X(x) &= \mathbb{P}(U \le F_D(x)) \\ &= F_D(x) \end{aligned} $$

Which is exactly the distribution we want to simulate. That is the distribution of \(X\) is exactly the same as that of \(D\). Generating \(X\) is easy, we apply \(F_D^{-1}\) to samples of the uniform distribution.

$$ \begin{aligned} F_D(d) &= \frac{d^2}{r^2} \\ r^2 F_D(d) &= d^2 \\ \sqrt{r^2 F_D(d)} &= d \\ d &= \sqrt{r^2 F_D(d)} \\ F_D^{-1}(d) &= r\sqrt{d} \end{aligned} $$

Which means to generate \(D\), we simply use the square root of the uniform distribution and multiply by the radius. That's pretty elegant!

Let's put this into practice:

function tick() {
    theta = random( 0, 2 * PI )
    d = radius * sqrt ( random( 0, 1 ) )
    drawDot( sin( theta ) * d, cos( theta ) * d )
}

This is certainly a success. Since the sqaure root is notoriously expensive, I'd be curious if it's actually any quicker than method 1 on average. Either way, I much prefer this method and I will be using it at every opportunity!