Generating random points in a ring

Recently I was working on a game where enemies were spawned somewhere in a ring around the player. The inner radius was set so that they always spawned offscreen and the outer radius was set so that enemies were never too far away. After we zoomed the camera out we had to increase these radii and suddenly the game was noticably hitching whenever it tried to spawn enemies. The culprit was a bit of code that looked something like this:

do
{
    spawnPos = RandomPointInCircle(outerRadius);
}
while (PointIsInCircle(spawnPos, innerRadius));

I wrote this bit of code and I'm glad I was the one to fix it as it reminded me of two interesting lessons I learnt with a good friend of mine while at university, one of which I then evidently forgot. She wrote an excellent in-depth article about our little discoveries. Back then we weren't dealing with such exotic geometry as a ring, merely a circle. The obvious way to do this is to pick a random length between 0 and the radius then a random angle, like so:

Vector2 RandomPointInCircle(float radius)
{
    float r = RandomRange(0.0f, radius);
    float theta = RandomRange(0.0f, 2.0f * PI);
    return new Vector2(r * cos(theta), r * sin(theta));
}

​The first interesting thing we found was that the obvious way to pick a random point in a circle does not give an even distribution. The problem with this approach is that points are just as likely to be near the centre as near the edge, but in a circle half of the area is in the outer third. See Rachel's article for more detail, including illustrations of the distribution this approach gives you.

Having encountered this problem the next simplest approach is to keep generating points in the square encompassing the circle until you find one that is also in the circle:

Vector2 RandomPointInCircle(float radius)
{
    Vector2 point = new Vector2(0.0f, 0.0f);
    do
    {
        point.x = RandomRange(-radius, radius);
        point.y = RandomRange(-radius, radius);
    }
    while (!PointIsInCircle(point, radius));
    return point;
}

This approach is known as rejection sampling and the second interesting thing we found was that rejection sampling is a terrible idea if you want consistently performant code. The problem with this approach is that you have no idea how many attempts it will take to find a point in the circle - it might take 1 or 1,000,000. This is the lesson I forgot. (For the right way to generate points in a circle see Rachel's article.)

My initial idea for generating points in a ring was the obvious one: keep generating points in the outer circle until you find one that isn't in the inner circle. This is a rejection sampling approach and in fact it's quite an egregious one. Consider the ratio between the area of the inner circle and the area of the outer circle. If the inner circle is comparatively small then it becomes fairly likely that you will find a point outside of it in good time. But if the inner circle takes up a large proportion of the outer circle, i.e. if the ring is thin, it becomes more and more likely that a random point will be rejected.

This explains why increasing the size of our enemy spawn ring caused noticable performance hitches; both radii were increased by the same amount, meaning that as a ratio the inner circle now occupied a much larger proportion of the outer circle. That little do-while loop was regularly taking upwards of 600,000 attempts to find a point that was inside the outer circle but outside the inner one. Worse than that is that it was variable: sometimes it would only take a few thousand attempts (only), one particularly unlucky time it took over 11,000,000 attempts.

The solution for even distribution of points in a circle was to pick a random angle then a random weighted radius which takes into account the mathematics of circles. The solution for generating points in a ring follows a similar approach, as detailed here.

Vector2 RandomPointInRing(float minRadius, float maxRadius)
{
    // Avoids rejection sampling! http://stackoverflow.com/a/9048443
    float theta = RandomRange(0.0f, 2.0f * PI);
    float w = RandomRange(0.0f, 1.0f);
    float r = sqrt( (1.0f - w) * minRadius * minRadius + w * maxRadius * maxRadius );
    return new Vector2(r * cos(theta), r * sin(theta));
}