# xikka

A collection of things I have made and things I find interesting.

## Round in circles

Thursday, 15th November 2018 ◆ Something unexpected in grand omelette (6)

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 {
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!