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:

Using uniform rand() distribution to get the distance from the origin.
1000 points are utilized to get this distribution.

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.

Areas of circular rings for segments of length d
Following this, we can deduce that for increasing distance from the radius the area is linearly increasing as illustrated below:
The relationship of circular ring areas to the distance from origin
Since the area and density of points in a circular ring is inversely proportional, the probability distribution of the distance from the origin should be linearly increasing between 0 and R to compensate for the reduction in density (and 0 outside this range). Since the area under the probability distribution function (pdf) should be equal to 1, the pdf function becomes: pdf = \alpha r where \alpha to be found. Since \int_0^{R} \alpha r dr = \alpha r^2/2 = 1, then \alpha = \frac{2}{R^2} which gives us a pdf distribution of pdf(r) = \frac{2}{R^2} r between 0 and R and zero outside. Similarly, cumulative distribution function (CDF) can be found by integrating the pdf and its gives us cdf(r) = \frac{r^2}{R^2} between 0 and R and 0/1 below/after this range.
PDF and CDF of distribution of distance from origin that provides same density of points along different circular rings

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: 

Using square root of the uniform rand()distribution to get the distance from the origin.
1000 points are utilized to get this distribution.


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

Uniform and non-uniform distribution of points within a circle

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) -> 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) -> 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s