Algorithms

# Generate Uniform Random Points within a Circle

Let’s say we have only access to uniform random number generator which generates random points between 0 and 1 (let’s denote it rand()), and we are asked to generate uniformly random points within a given circle with specified radius (let’s say $R$ for now). The first idea that comes to mind is to utilize the random number generator to get a random angle between 0 and $2\pi$ to set the angular position of the point and utilize another instance of the random number generator to get a random distance of the point from the origin of the circle. However, once this strategy is followed, it will be observed that the distribution will have more density around the origin and less as the distance from the origin increases as can be seen in the following figure:

This is due to the fact that as the distance from the origin increases then the area covered by the circular segments increases for fixed discretization size along the radius. In a sense, using uniform random distribution to select the distance from the origin gives same probability to each distance and as a result circular segments away from the origin statistically have same/similar number of points within them but since their area is larger, the density of points gets less. As a result, the points seem to be clustered more densely around the origin compared to the outer circular rings.

Recall that originally we were asked to generate uniform distribution within the circle. To be able to achieve this we need to consider the increasing area of circular segments away from the origin and instead of selecting the distance from a uniform distribution, we need to give more weights (higher probability) as the distance increases. This is to compensate for the increased area and keep the density of points within circular segments statistically same. How can we achieve this? I will try to show it here. First of all let us find the relationship of area of circular rings to the distance from the origin. The area of the circle with radius $d$ is $A=\pi d^2$. Then the area of the circular ring between $d$ and $2d$ becomes $\pi (2d)^2 - \pi d^2$ which makes $3A$. Similarly, for the circular ring between $2d$ and $3d$, the area is $5A$ as can be seen in the following graph.

So, to obtain such a triangular probability distribution we can utilize built-in functions, however, recall that we have only access to uniform random number generator. In this case, we can utilize the random number generator to get a random number to mimic the CDF value of a random distance. In other words, for the CDF distribution above, we obtain a random point on the y-axis of CDF which is always between 0 and 1 and then map it to the distance from the origin ($r$) on the x-axis. This can be easily achieved as we know the analytical formula of the CDF function whose inverse can be written as $r = R \sqrt{CDF} = R \sqrt{rand()}$. If we utilize this, then the distribution will look like as follows:

Once compared with the previous distribution, the uniformity of these distribution is evident. Here is another instance for both cases:

Here is the Python code to replicate the results:


import random
import math
import numpy as np
import random
import matplotlib.pyplot as plt

def PlotDistributions(**kwargs):

def PlotDist(xpoints, ypoints, rad, xc, yc, figNo=1, stitle='', color='b', marker='.', subtitleinfo=''):

plt.figure(figNo)
plt.plot(xpoints, ypoints, color+marker)
plt.grid('on')

x_circle = [xc + rad*math.cos(i) for i in np.arange(0, math.pi*2, 0.01)]
y_circle = [yc + rad*math.sin(i) for i in np.arange(0, math.pi*2, 0.01)]
plt.plot(x_circle, y_circle, '-k')

str_title = '\n'.join([stitle, subtitleinfo])

plt.title(str_title)
plt.axis('square')
return

colors = ['b', 'r']
markers = ['.', '.']
for i, key in enumerate(kwargs):
(xpoints, ypoints, rad, xc, yc), subtitleinfo = kwargs[key]
PlotDist(xpoints, ypoints, rad, xc, yc, i, key, colors[i], markers[i], subtitleinfo)

plt.show()

return

def ReplicateNTimes(func, rad, xc, yc, Ntrials=1000):

xpoints, ypoints =  [], []
for i in range(Ntrials):
xp, yp = func(rad, xc, yc)
xpoints.append(xp)
ypoints.append(yp)

dist = (xpoints, ypoints, rad, xc, yc)
return dist

def NonUniformRandomPointInCircle(inputRadius=1, xcenter=0, ycenter=0) -&gt; float:

r = inputRadius * random.random()
theta = 2* math.pi * random.random()

return xcenter + r*math.cos(theta), ycenter + r*math.sin(theta)

def UniformRandomPointInCircle(inputRadius=1, xcenter=0, ycenter=0) -&gt; float:

r = inputRadius * math.sqrt(random.random())
theta = 2* math.pi * random.random()

return xcenter + r*math.cos(theta), ycenter + r*math.sin(theta)

def main():

N = 1000
radius, xc, yc = 1, 0, 0
dist1 = ReplicateNTimes(UniformRandomPointInCircle, radius, xc, yc, Ntrials=N)
dist2 = ReplicateNTimes(NonUniformRandomPointInCircle, radius, xc, yc, Ntrials=N)

PlotDistributions(Uniform=(dist1, 'Using sqrt(rand())'), NonUniform=(dist2, 'Using rand()'))

if __name__ == '__main__':
main()<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>


Additional references:

• Originally saw the question here
• I got the original idea here and wanted to put more details on how the pdf and cdf’s are calculated.
Advertisements