Generate a random point within a circle (uniformly)

Generate a random point within a circle (uniformly)

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 ... 2?), 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/R²)r and how he derives the final solution.

---

Regarding rejection sampling: I could generate a random point within the RR square over and over again until I get one within the circle. This approach has the obvious draw-back that it doesn't provide a guarantee for termination (even though it is highly unlikely that it goes on for long).

Answer by recursive for Generate a random point within a circle (uniformly)

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.

Answer by Chris A. for Generate a random point within a circle (uniformly)

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.

Answer by Benjamin Bannier for Generate a random point within a circle (uniformly)

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.

Answer by Aryabhatta for Generate a random point within a circle (uniformly)

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.

Answer by ascanio for Generate a random point within a circle (uniformly)

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 2R-sided square and then select the points (x,y) such that x^2+y^2<=R^2.

Answer by Marino imi for Generate a random point within a circle (uniformly)

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 < matrix.GetLength(0); y++) {          for (int x = 0; x < matrix.GetLength(1); x++)          {              double distance = (center - new Vector(x, y)).Length;              if (distance < radius) {                  matrix[x, y] = r.NextDouble() > 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 < matrix.GetLength(0); y++)      {          for (int x = 0; x < 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);  }  

Answer by sigfpe for Generate a random point within a circle (uniformly)

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>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 > 1, 2 - u, u];    {r Cos[t], r Sin[t]}  ]    ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]  

Answer by btilly for Generate a random point within a circle (uniformly)

Here is a fast and simple solution.

Pick two random numbers in the range (0, 1), namely a and b. If b < 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.

Answer by arsaKasra for Generate a random point within a circle (uniformly)

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< r< r1 + dr, theta1< theta< 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.

Answer by xytor for Generate a random point within a circle (uniformly)

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;  

Answer by krishnab for Generate a random point within a circle (uniformly)

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

Answer by user502248 for Generate a random point within a circle (uniformly)

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.

Answer by selalerer for Generate a random point within a circle (uniformly)

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 < MATRIX_SIZE ; ++x)    {      for (int y = 0 ; y < MATRIX_SIZE ; ++y)      {        if (x * x + y * y < 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 < MATRIX_SIZE ; ++x)    {      for (int y = 0 ; y < MATRIX_SIZE ; ++y)      {        if (x * x + y * y < RADIUS * RADIUS)         {          loopUpTable[numberOfOnBits].x = x;          loopUpTable[numberOfOnBits].y = y;            ++numberOfOnBits;        } // if      } // for    } // for  } // ()    Point choose()  {    int randomIndex = randomInt(numberOfBits);      return loopUpTable[randomIndex];  } // ()  

Answer by Libor for Generate a random point within a circle (uniformly)

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

Answer by cheesefest for Generate a random point within a circle (uniformly)

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.

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72