# xikka

A collection of the things I have made. Some of them useful, most of them not.

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

remokna-nn ◆ Sunday, 13th January 2019 at 21:20

<a href=http://remokna-nn.ru&gt;?????? ???? ???</a>

prooknann ◆ Sunday, 13th January 2019 at 14:27

<a href=http://prooknann.ru/Moskitnye-setki-alyuminiy.html&gt;???????? ?????</a>

SEOhok ◆ Monday, 31st December 2018 at 16:55

seorussian.ru - ???????????? ??????

http://www.seorussian.ru - ????????? ?????

http://www.seorussian.ru/Izgotovlenie-saytov.html - ???????????? ????? ? ??????