From: Colin Bartlett Date: 2010-06-23T08:25:58+09:00 Subject: Re: [QUIZ] Random Points within a Circle (#234) --001636c5c2093e9cd30489a6be72 Content-Type: text/plain; charset=ISO-8859-1 (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 wrote: > On 6/21/10, Dave Howell 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 --001636c5c2093e9cd30489a6be72--