Depending on circumstances, you might have different requirements and want to optimise for different things:
- You probably want your points to be uniformly (evenly) distributed across the circle. To verify if an algorithm is outputting uniformly-distributed points, we check the average (mean) distance from the centre of the circle to each point. It should be about (2/3 * radius). This is because half the area of a circle is in its outer third, so when the average distance is (2/3 * radius) you know half the points are in the outer third.
- You may want to minimise calls to the random number generator. Why? Because RNGs can be a bit crap. Certainly the C++ standard library's rand() function is. It might be bad for lots of different reasons. It might have a short period, meaning that it begins to repeat itself after a few thousand calls, which might be a big deal to you. Or it might not be very fast, which is unlikely to be impactful, but this stuff can get pretty weird.
- You might want to avoid using the square-root function. There's a discussion on stackoverflow regarding the speed of sqrt, in which someone says that it is "about 4 times slower than addition using -O2, or about 13 times slower without using -O2." Not huge in the fully-optimised case, but still big enough to add up, and you might be working on hardware where the implementation of sqrt is bad.
- You might want to avoid using many calls to trigonometry functions, because these might be bottlenecks in your code. Sure, you can write sin and cos functions that use a lookup table to speed things along, but maybe you don't want to have to stoop to doing all that work in what should be the age of fast processors. Again, as with rand(), these standard-library should-just-god-damn-work utilities aren't perfect.
- You want to avoid branching in performance-critical code. You can factor comparisons out using smart maths, sometimes, but that involves adding in extra code.
The RandomInRange function I use looks like this:
Anyway, let's begin!
Here we take a basic, intuitive approach. We randomly generate an angle. This gives us a line from the centre of the circle to its circumference. The next random number we generate is used to place the point along this line. Then we use trigonometry to determine the coordinates of the point.
I mentioned above that the available surface area of a circle gets larger as you go further and further out from the centre, such that half of its area is in its outer third. What this means is that if you just dump points along lines heading out from the centre, the points you dump further out will have much more space for themselves, and those dumped further in will be much more cramped, as you can see. Here, the average distance of points from the centre is 1/2, and this is precisely the problem.
The next two algorithms attempt to solve this problem by skewing the distribution of points towards the outside of the circle, so as to generate uniformly-distributed points.
This takes the same approach, but instead of generating points in the interval [0, radius] we use the interval [0, radius^2]. Then we square-root the result.
The algorithm achieves an average point distance of 2/3.
This is the technique that Connor showed me that got me thinking about this in the first place. Calling the random function twice and summing the results puts r in the range [0, 2], but if it's greater than 1, the radius of the circle, we 'fold' it back over. For example an r of 1.1 would become 0.9. An r of 1.9 would become 0.1.
The distribution that RandomInRange(0, 1) + RandomInRange(0, 1) gives is weighted towards its centre, that is, 1. Folding this distribution over balances the distribution of points away from the centre of the circle and closer to the edge. You might get a better explanation here.
Generate 2 numbers a and b, ensuring that a is smaller than b. Calculate the ratio a/b. This ratio determines the angle used. b determines how far out along the radius the point is placed. I found the algorithm here.
I came up with this pretty quickly without thinking about it much. It doesn't quite work.
Generate points inside the square of width d and reject the ones that lie outside the circle of diameter d.
Not good. You shouldn't do this because the algorithm will take a random amount of time to complete, which is completely useless in almost every situation.