Re: [QUIZ] Random Points within a Circle (#234)

(Apologies for this oldish "re-post": it seems that changing from googlemail
to gmail makes emails not recognised by ruby-talk.)

On Tue, Jun 22, 2010 at 3:41 AM, Caleb Clausen <[e-mail]> wrote:

> On 6/21/10, Dave Howell <[e-mail]> wrote:
> >
> > On Jun 21, 2010, at 15:45 , Caleb Clausen wrote:
> >> 7 lines, 5 minutes, 0 tests or visualizations. Super-easy.
> >
> > And wrong, unfortunately. You're selecting a random angle, and then a
> random
> > distance from the center. This will result in way too many points at the
> > center of the circle.
>
> I guess this is why Benoit had that sqrt in there. I don't quite get
> why it's necessary.
>

> I kinda like Yaser's solution.
>
Yaser's solution is a "Monte Carlo" simulation? My initial reaction was that
Yaser's method might not end up with the correct distribution, but on
further thought it (I think):
1. Generates points uniformly in a square of side r.
2. Redistributes the points uniformly in a square of side 2*r. (I wondered
what the "Flip coin to reflect" bits were doing until I realised that.)
3. Ignores any points outside the circle. Which should leave points
uniformly distributed (by area) inside the circle.
So Yaser's solution does have the correct distribution of points. And shows
that sometimes a way to generate a correct distribution is to use an
incorrect distribution and then ignore some values generated from the
incorrect distribution.
(Strictly speaking, is the test that "v.length > 0" necessary, and should
the other test be "v.length <= radius"? It won't make much difference
though.)

** The rest of this has now been covered by other posts, but the links might
be interesting.

The random angle bit in your method is OK.
For the square root: the area of an annulus radius r to r+e is
    pi * ( (r+e)**2 - r**2 ) = pi * 2*r*e + pi * e**2
So, if I treat e as an infinitesimal and neglect the e**2 (and hope that no
real mathematicians are looking, or claim I'm using
  Abraham Robinson's http://en.wikipedia.org/wiki/Abraham_robinson
  Non-Standard Analysis http://en.wikipedia.org/wiki/Non-standard_analysis
and hope that nobody asks me any awkward questions about how that really
works)
the area of the annulus is (approximately) pi * 2*r*e.
(Think of it as a (very) "bent" rectangle of length pi * 2*r with a "width"
of e.)

If you use a uniform distribution for the radius to the random point then on
average you'll be putting the same number of points in an annulus (a0) of
width e very close to the centre of the circle as in an annulus (a1) of
width e very close to the circumference of the circle. But the annulus (a1)
has a much larger area than the annulus (a0), so the density of points will
be greater in annulus (a0) than annulus (a1). Which is why Dave Howell made
his comment.

So if we want to use a method which selects a random angle and a random
distance from the centre of the circle, for the random distance from the
centre of the circle we need a 0 to 1 distribution which isn't uniform but
which has more weight for higher than lower values in 0 to 1. When I saw
this quiz I thought of using the random angle and distance method, and after
a bit of work guessed that the correct distribution for the distance was
probably to take the square root of random numbers generated from a uniform
0 to 1 distribution. BUT: I couldn't immediately see a way to prove that! So
I didn't post anything! I suspect Benoit can *prove* that taking the square
root gives the correct distribution for the radius!

def uniform_random_point_in_
circle( r, x, y )
  # circle radius r, centre at x, y
  r_to_point = Math.sqrt( Kernel.rand ) * r
  radians_to_point = 2 * Math::PI * Kernel.rand
  return x + r_to_point * Math.cos( radians_to_point ),
         y + r_to_point * Math.sin( radians_to_point )
end