Generating a Random Point within a Circle

Date: 04/02/2007 at 17:41:13
From: PC
Subject: Random point within a circle.

Given a circle C with center (xc, yc) and radius R, find a random 
point within the circle.  What's the best possible way to do that in
terms of computation?

Date: 04/03/2007 at 08:57:09
From: Doctor George
Subject: Re: Random point within a circle.

Hi PC,

Thanks for writing to Doctor Math.

I assume that you are looking for the points to be uniformly
distributed in the circle.

One method is to pick random points in a square in which the circle is
circumscribed.  Then reject those points that are not also in the circle.

Another method is to select a random pair of values (M, theta) where M
is the magnitude of the vector from the center to a random point and
theta is the angle by which the vector is rotated.  The random points
then have the following form.

  x = xc + M cos(theta)
  y = yc + M sin(theta)

The distribution of theta is uniform on the interval [0, 2pi].  The
distribution of M has a ramp shape on the interval [0, R].  It is a
good exercise to prove that M has this distribution.

To compute random values of M you can use the inverse of its
cumulative distribution.  Another technique is to generate a pair of
values (r1, r2) that are uniform on the interval [0, R] and let M =
max(r1, r2).  This proof is also a good exercise.

I prefer the second method, and I typically generate values of M using
the (r1, r2) pairs.

Does that make sense?  Write again if you need more help.

- Doctor George, The Math Forum
  http://mathforum.org/dr.math/