Generate a random point within a circle uniformly

Question

I need to generate a uniformly random point within a circle of radius R   I realize that by just picking a uniformly random angle in the interval  0     2p   and uniformly random radius in the interval  0     R  I would end up with more points towards the center  since for two given radii  the points in the smaller radius will be closer to each other than for the points in the larger radius   I found a blog entry on this over here but I don t understand his reasoning  I suppose it is correct  but I would really like to understand from where he gets  2 R2  times r and how he derives the final solution     Update  7 years after posting this question I still hadn t received a satisfactory answer on the actual question regarding the math behind the square root algorithm  So I spent a day writing an answer myself  Link to my answer

User · Answer

Let    radius  and  f  azimuth  be two random variables corresponding to polar coordinates of an arbitrary point inside the circle  If the points are uniformly distributed then what is the disribution function of   and f   For any r  0  lt  r  lt  R the probability of radius coordinate   to be less then r is  P    lt  r    P point is within a circle of radius r    S1   S0   r R 2  Where S1 and S0 are the areas of circle of radius r and R respectively  So the CDF can be given as             0          if r lt  0   CDF      r R   2   if 0  lt  r  lt   R           1          if r  gt  R   And PDF   PDF   d dr CDF    2    r R  2   0  lt  r  lt   R     Note that for R 1 random variable sqrt X  where X is uniform on  0  1  has this exact CDF  because P sqrt X   lt  y    P x  lt  y  2    y  2 for 0  lt  y  lt   1     The distribution of f is obviously uniform from 0 to 2 p  Now you can create random polar coordinates and convert them to Cartesian using trigonometric equations   x       cos f  y       sin f    Can t resist to post python code for R 1    from matplotlib import pyplot as plt import numpy as np  rho   np sqrt np random uniform 0  1  5000   phi   np random uniform 0  2 np pi  5000   x   rho   np cos phi  y   rho   np sin phi   plt scatter x  y  s   4    You will get

User · Answer

Here is a fast and simple solution   Pick two random numbers in the range  0  1   namely a and b   If b  lt  a  swap them   Your point is  b R cos 2 pi a b   b R sin 2 pi a b     You can think about this solution as follows   If you took the circle  cut it  then straightened it out  you d get a right-angled triangle   Scale that triangle down  and you d have a triangle from  0  0  to  1  0  to  1  1  and back again to  0  0    All of these transformations change the density uniformly   What you ve done is uniformly picked a random point in the triangle and reversed the process to get a point in the circle

User · Answer

How to generate a random point within a circle of radius R   r   R   sqrt random    theta   random     2   PI    Assuming random   gives a value between 0 and 1 uniformly   If you want to convert this to Cartesian coordinates  you can do  x   centerX   r   cos theta  y   centerY   r   sin theta      Why sqrt random      Let s look at the math that leads up to sqrt random     Assume for simplicity that we re working with the unit circle  i e  R   1   The average distance between points should be the same regardless of how far from the center we look  This means for example  that looking on the perimeter of a circle with circumference 2 we should find twice as many points as the number of points on the perimeter of a circle with circumference 1     nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp     Since the circumference of a circle  2 pi r  grows linearly with r  it follows that the number of random points should grow linearly with r  In other words  the desired probability density function  PDF  grows linearly  Since a PDF should have an area equal to 1 and the maximum radius is 1  we have    nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp   So we know how the desired density of our random values should look like  Now  How do we generate such a random value when all we have is a uniform random value between 0 and 1   We use a trick called inverse transform sampling   From the PDF  create the cumulative distribution function  CDF  Mirror this along y   x Apply the resulting function to a uniform value between 0 and 1    Sounds complicated  Let me insert a blockquote with a little side track that conveys the intuition      Suppose we want to generate a random point with the following distribution        nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp       That is         1 5 of the points uniformly between 1 and 2  and   4 5 of the points uniformly between 2 and 3          The CDF is  as the name suggests  the cumulative version of the PDF  Intuitively  While PDF x  describes the number of random values at x  CDF x  describes the number of random values less than x       In this case the CDF would look like        nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp       To see how this is useful  imagine that we shoot bullets from left to right at uniformly distributed heights  As the bullets hit the line  they drop down to the ground        nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp       See how the density of the bullets on the ground correspond to our desired distribution  We re almost there       The problem is that for this function  the y axis is the output and the x axis is the input  We can only  shoot bullets from the ground straight up   We need the inverse function       This is why we mirror the whole thing  x becomes y and y becomes x        nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp  nbsp       We call this CDF-1  To get values according to the desired distribution  we use CDF-1 random        hellip so  back to generating random radius values where our PDF equals 2x   Step 1  Create the CDF  Since we re working with reals  the CDF is expressed as the integral of the PDF   CDF x      2x   x2  Step 2  Mirror the CDF along y   x    Mathematically this boils down to swapping x and y and solving for y   CDF  nbsp  nbsp  nbsp  nbsp  nbsp y   x2 Swap  nbsp  nbsp  nbsp x   y2 Solve  nbsp  nbsp  nbsp y    radic x CDF-1  nbsp  nbsp y    radic x  Step 3  Apply the resulting function to a uniform value between 0 and 1  CDF-1 random       radic random    Which is what we set out to derive  -

User · Answer

1  Choose a random X between -1 and 1   var X Number   Math random     2 - 1    2  Using the circle formula  calculate the maximum and minimum values of Y given that X and a radius of 1   var YMin Number   -Math sqrt 1 - X   X   var YMax Number   Math sqrt 1 - X   X     3  Choose a random Y between those extremes   var Y Number   Math random      YMax - YMin    YMin    4  Incorporate your location and radius values in the final value   var finalX Number   X   radius   pos x  var finalY Number   Y   radois   pos y

User · Answer

Solution in Java and the distribution example  2000 points    public void getRandomPointInCircle         double t   2   Math PI   Math random        double r   Math sqrt Math random         double x   r   Math cos t       double y   r   Math sin t       System out println x       System out println y         based on previus solution https   stackoverflow com a 5838055 5224246 from  sigfpe

User · Answer

The area element in a circle is dA rdr dphi  That extra factor r destroyed your idea to randomly choose a r and phi  While phi is distributed flat  r is not  but flat in 1 r  i e  you are more likely to hit the boundary than  the bull s eye     So to generate points evenly distributed over the circle pick phi from a flat distribution and r from a 1 r distribution   Alternatively use the Monte Carlo method proposed by Mehrdad   EDIT  To pick a random r flat in 1 r you could pick a random x from the interval  1 R  infinity  and calculate r 1 x  r is then distributed flat in 1 r   To calculate a random phi pick a random x from the interval  0  1  and calculate phi 2 pi x

User · Answer

Let s approach this like Archimedes would have   How can we generate a point uniformly in a triangle ABC  where  AB   BC   Let s make this easier by extending to a parallelogram ABCD  It s easy to generate points uniformly in ABCD  We uniformly pick a random point X on AB and Y on BC and choose Z such that XBYZ is a parallelogram  To get a uniformly chosen point in the original triangle we just fold any points that appear in ADC back down to ABC along AC   Now consider a circle  In the limit we can think of it as infinitely many isoceles triangles ABC with B at the origin and A and C on the circumference vanishingly close to each other  We can pick one of these triangles simply by picking an angle theta  So we now need to generate a distance from the center by picking a point in the sliver ABC  Again  extend to ABCD  where D is now twice the radius from the circle center   Picking a random point in ABCD is easy using the above method  Pick a random point on AB  Uniformly pick a random point on BC  Ie  pick a pair of random numbers x and y uniformly on  0 R  giving distances from the center  Our triangle is a thin sliver so AB and BC are essentially parallel  So the point Z is simply a distance x y from the origin  If x y R we fold back down   Here s the complete algorithm for R 1  I hope you agree it s pretty simple  It uses trig  but you can give a guarantee on how long it ll take  and how many random   calls it needs  unlike rejection sampling   t   2 pi random   u   random   random   r   if u gt 1 then 2-u else u  r cos t   r sin t     Here it is in Mathematica   f      Block  u  t  r     u   Random     Random      t   Random   2 Pi    r   If u  gt  1  2 - u  u      r Cos t   r Sin t      ListPlot Table f     10000    AspectRatio - gt  Automatic

User · Answer

Note the point density in proportional to inverse square of the radius  hence instead of picking r from  0  r max   pick from  0  r max 2   then compute your coordinates as   x   sqrt r    cos angle  y   sqrt r    sin angle    This will give you uniform point distribution on a disk   http   mathworld wolfram com DiskPointPicking html

User · Answer

I used once this method  This may be totally unoptimized  ie it uses an array of point so its unusable for big circles  but gives random distribution enough  You could skip the creation of the matrix and draw directly if you wish to  The method is to randomize all points in a rectangle that fall inside the circle   bool    getMatrix System Drawing Rectangle r        bool    matrix   new bool r Width  r Height       return matrix     void fillMatrix ref bool    matrix  Vector center        double radius   center X      Random r   new Random        for  int y   0  y  lt  matrix GetLength 0   y              for  int x   0  x  lt  matrix GetLength 1   x                          double distance    center - new Vector x  y   Length              if  distance  lt  radius                    matrix x  y    r NextDouble    gt  0 5                                    private void drawMatrix Vector centerPoint  double radius  bool    matrix        var g   this CreateGraphics         Bitmap pixel   new Bitmap 1 1       pixel SetPixel 0  0  Color Black        for  int y   0  y  lt  matrix GetLength 0   y                  for  int x   0  x  lt  matrix GetLength 1   x                          if  matrix x  y                     g DrawImage pixel  new PointF  float  centerPoint X - radius   x    float  centerPoint Y - radius   y                                        g Dispose       private void button1 Click object sender  EventArgs e        System Drawing Rectangle r   new System Drawing Rectangle 100 100 200 200       double radius   r Width   2      Vector center   new Vector r Left   radius  r Top   radius       Vector normalizedCenter   new Vector radius  radius       bool    matrix   getMatrix r       fillMatrix ref matrix  normalizedCenter       drawMatrix center  radius  matrix

User · Answer

You can also use your intuition   The area of a circle is pi r 2  For r 1  This give us an area of pi  Let us assume that we have some kind of function fthat would uniformly distrubute N 10 points inside a circle  The ratio here is 10   pi  Now we double the area and the number of points  For r 2 and N 20  This gives an area of 4pi and the ratio is now 20 4pi or 10 2pi  The ratio will get smaller and smaller the bigger the radius is  because its growth is quadratic and the N scales linearly   To fix this we can just say  x   r 2 sqrt x    r   If you would generate a vector in polar coordinates like this  length   random 0 1    angle   random 0 2pi      More points would land around the center   length   sqrt random 0 1     angle   random 0 2pi      length is not uniformly distributed anymore  but the vector will now be uniformly distributed

User · Answer

It really depends on what you mean by  uniformly random   This is a subtle point and you can read more about it on the wiki page here  http   en wikipedia org wiki Bertrand paradox  28probability 29  where the same problem  giving different interpretations to  uniformly random  gives different answers   Depending on how you choose the points  the distribution could vary  even though they are uniformly random in some sense   It seems like the blog entry is trying to make it uniformly random in the following sense  If you take a sub-circle of the circle  with the same center  then the probability that the point falls in that region is proportional to the area of the region  That  I believe  is attempting to follow the now standard interpretation of  uniformly random  for 2D regions with areas defined on them  probability of a point falling in any region  with area well defined  is proportional to the area of that region

User · Answer

There is a linear relationship between the radius and the number of points  near  that radius  so he needs to use a radius distribution that is also makes the number of data points near a radius r proportional to r

User · Answer

A programmer solution    Create a bit map  a matrix of boolean values   It can be as large as you want  Draw a circle in that bit map  Create a lookup table of the circle s points  Choose a random index in this lookup table    const int RADIUS   64  const int MATRIX SIZE   RADIUS   2   bool matrix MATRIX SIZE  MATRIX SIZE     0    struct Point   int x  int y      Point lookupTable MATRIX SIZE   MATRIX SIZE    void init       int numberOfOnBits   0     for  int x   0   x  lt  MATRIX SIZE     x          for  int y   0   y  lt  MATRIX SIZE     y              if  x   x   y   y  lt  RADIUS   RADIUS                   matrix x  y    true           loopUpTable numberOfOnBits  x   x          loopUpTable numberOfOnBits  y   y             numberOfOnBits              if          for        for          Point choose       int randomIndex   randomInt numberOfBits      return loopUpTable randomIndex             The bitmap is only necessary for the explanation of the logic  This is the code without the bitmap   const int RADIUS   64  const int MATRIX SIZE   RADIUS   2   struct Point   int x  int y      Point lookupTable MATRIX SIZE   MATRIX SIZE    void init       int numberOfOnBits   0     for  int x   0   x  lt  MATRIX SIZE     x          for  int y   0   y  lt  MATRIX SIZE     y              if  x   x   y   y  lt  RADIUS   RADIUS                   loopUpTable numberOfOnBits  x   x          loopUpTable numberOfOnBits  y   y             numberOfOnBits             if          for        for          Point choose       int randomIndex   randomInt numberOfBits      return loopUpTable randomIndex

User · Answer

I don t know if this question is still open for a new solution with all the answer already given  but I happened to have faced exactly the same question myself  I tried to  reason  with myself for a solution  and I found one  It might be the same thing as some have already suggested here  but anyway here it is    in order for two elements of the circle s surface to be equal  assuming equal dr s  we must have dtheta1 dtheta2   r2 r1  Writing expression of the probability for that element as P r  theta    P  r1 lt  r lt  r1   dr  theta1 lt  theta lt  theta   dtheta1    f r theta  dr dtheta1  and setting the two probabilities  for r1 and r2  equal  we arrive to  assuming r and theta are independent  f r1  r1   f r2  r2   constant  which gives f r    c r  And the rest  determining the constant c follows from the condition on f r  being a PDF

User · Answer

I think that in this case using polar coordinates is a way of complicate the problem  it would be much easier if you pick random points into a square with sides of length 2R and then select the points  x y  such that x 2 y 2 lt  R 2

User · Answer

Think about it this way   If you have a rectangle where one axis is radius and one is angle  and you take the points inside this rectangle that are near radius 0   These will all fall very close to the origin  that is close together on the circle    However  the points near radius R  these will all fall near the edge of the circle  that is  far apart from each other      This might give you some idea of why you are getting this behavior   The factor that s derived on that link tells you how much corresponding area in the rectangle needs to be adjusted to not depend on the radius once it s mapped to the circle   Edit  So what he writes in the link you share is   That   s easy enough to do by calculating the inverse of the cumulative distribution  and we get for r     The basic premise is here that you can create a variable with a desired distribution from a uniform by mapping the uniform by the inverse function of the cumulative distribution function of the desired probability density function   Why   Just take it for granted for now  but this is a fact   Here s my somehwat intuitive explanation of the math   The density function f r  with respect to r has to be proportional to r itself   Understanding this fact is part of any basic calculus books   See sections on polar area elements   Some other posters have mentioned this    So we ll call it f r    C r    This turns out to be most of the work   Now  since f r  should be a probability density  you can easily see that by integrating f r  over the interval  0 R  you get that C   2 R 2  this is an exercise for the reader      Thus  f r    2 r R 2  OK  so that s how you get the formula in the link     Then  the final part is going from the uniform random variable u in  0 1  you must map by the inverse function of the cumulative distribution function from this desired density f r    To understand why this is the case you need to find an advanced probability text like Papoulis probably  or derive it yourself    Integrating f r  you get  F r    r 2 R 2  To find the inverse function of this you set u   r 2 R 2 and then solve for r  which gives you   r   R   sqrt u   This totally makes sense intuitively too  u   0 should map to r   0   Also  u   1 shoudl map to r   R   Also  it goes by the square root function  which makes sense and matches the link

User · Answer

Here is my Python code to generate num random points from a circle of radius rad   import matplotlib pyplot as plt import numpy as np rad   10 num   1000  t   np random uniform 0 0  2 0 np pi  num  r   rad   np sqrt np random uniform 0 0  1 0  num   x   r   np cos t  y   r   np sin t   plt plot x  y   ro   ms 1  plt axis  -15  15  -15  15   plt show

User · Answer

Such a fun problem  The rationale of the probability of a point being chosen lowering as distance from the axis origin increases is explained multiple times above  We account for that by taking the root of U 0 1   Here s a general solution for a positive r in Python 3   import numpy import math import matplotlib pyplot as plt  def sq point in circle r               Generate a random point in an r radius circle      centered around the start of the axis              t   2 math pi numpy random uniform       R    numpy random uniform 0 1     0 5    r      return R math cos t   R math sin t    R   200   Radius N   1000   Samples  points   numpy array  sq point in circle R  for i in range N    plt scatter points    0   points   1

User · Answer

First we generate a cdf x  which is  The probability that a point is less than distance x from the centre of the circle  Assume the circle has a radius of R   obviously if x is zero then cdf 0    0  obviously if x is R then the cdf R    1  obviously if x   r then the cdf r     Pi r 2   Pi R 2   This is because each  small area  on the circle has the same probability of being picked  So the probability is proportionally to the area in question  And the area given a distance x from the centre of the circle is Pi r 2  so  cdf x    x 2 R 2  because the Pi cancel each other out  we have   cdf x  x 2 R 2 where x goes from 0 to R  So we solve for x  R 2 cdf x    x 2  x   R Sqrt  cdf x      We can now replace cdf with a random number from 0 to 1  x   R Sqrt  RandomReal  0 1       Finally  r   R Sqrt   RandomReal  0 1      theta   360 deg   RandomReal  0 1     r theta    we get the polar coordinates      0 601168 R  311 915 deg

User · Answer

The reason why the naive solution doesn t work is that it gives a higher probability density to the points closer to the circle center  In other words the circle that has radius r 2 has probability r 2 of getting a point selected in it  but it has area  number of points  pi r 2 4   Therefore we want a radius probability density to have the following property    The probability of choosing a radius smaller or equal to a given r has to be proportional to the area of the circle with radius r   because we want to have a uniform distribution on the points and larger areas mean more points   In other words we want the probability of choosing a radius between  0 r  to be equal to its share of the overall area of the circle  The total circle area is pi R 2  and the area of the circle with radius r is pi r 2  Thus we would like the probability of choosing a radius between  0 r  to be  pi r 2   pi R 2    r 2 R 2   Now comes the math    The probability of choosing a radius between  0 r  is the integral of p r  dr from 0 to r  that s just because we add all the probabilities of the smaller radii   Thus we want integral p r dr    r 2 R 2  We can clearly see that R 2 is a constant  so all we need to do is figure out which p r   when integrated would give us something like r 2  The answer is clearly r   constant  integral r   constant dr    r 2 2   constant  This has to be equal to r 2 R 2  therefore constant   2 R 2  Thus you have the probability distribution p r    r   2 R 2  Note  Another more intuitive way to think about the problem  is to imagine that you are trying to give each circle of radius r a probability density equal to the proportion of the number of points it has on its circumference  Thus a circle which has radius r will have 2   pi   r  points  on its circumference  The total number of points is pi   R 2  Thus you should give the circle r a probability equal to  2   pi   r     pi   R 2    2   r R 2  This is much easier to understand and more intuitive  but it s not quite as mathematically sound

User · Answer

I am still not sure about the exact   2 R2   r  but what is apparent is the number of points required to be distributed in given unit  dr  i e  increase in r will be proportional to r2 and not r    check this way   number of points at some angle theta and between r  0 1r to 0 2r  i e  fraction of the r and number of points between  r  0 6r to 0 7r  would be equal if you use standard generation  since the difference is only 0 1r between two intervals   but since area covered between points  0 6r to 0 7r  will be much larger than area covered between 0 1r to 0 2r  the equal number of points will be sparsely spaced in larger area  this I assume you already know  So the function to generate the random points must not be linear but quadratic   since number of points required to be distributed in given unit  dr  i e  increase in r will be proportional to r2 and not r   so in this case it will be inverse of quadratic  since the delta we have  0 1r  in both intervals must be square of some function so it can act as seed value for linear generation of points  since afterwords  this seed is used linearly in sin and cos function   so we know  dr must be quadratic value and to make this seed quadratic  we need to originate this values from square root of r not r itself  I hope this makes it little more clear

[math] Generate a random point within a circle (uniformly)

Examples related to math

Examples related to random

Examples related to geometry

Examples related to probability