Random Points within a Circle (#234)
in [Ruby]
|
Prev: Ruby Basic
Next: Ruby Basic
From: timr on 22 Jun 2010 17:20 This is actually a pretty interesting puzzle. Correct solutions should have points that are distributed as a hump Gaussian-like curve when histogram plotted over the y rand and x range. My first solution had a humped-histogram over the X ranges but was evenly distributed over the Y ranges. Back to the drawing board. The algorithm I ended up using makes points distributed over the Y and X range, but only keeps them if they are within the circle. Used R to plot. Code below: class Circle attr_reader :r,:x,:y def initialize(r,x,y) @r = r @y = y @x = x end #get random x and y from within circle space def internal_rand #to randomly select rise run values rise = rand(0)*@r*rand_sign run = rand(0)*@r*rand_sign #validate that point lies within circle, about 20% fail if Math.sqrt(run**2+rise**2)<@r [@x+run,@y+rise] else internal_rand end end private def rand_sign rand(2) == 0? -1 : 1 end end #test c1 = Circle.new(4,10,10) xs = []; ys = [] 1000.times do point = c1.internal_rand xs << point.first ys << point.last end plotted in R using: x = c(pasted in xs from ruby output) y = c(pasted in ys from ruby output) plot(x,y) library(plotrix) draw.circle(10,10,4) #evenly distribute points within circle hist(x, breaks=20) #Gaussian histogram bar distribution hist(y, breaks=20) #Gaussian histogram bar distribution On Jun 19, 11:05 am, Daniel Moore <yahi...(a)gmail.com> wrote: > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- > > The three rules of Ruby Quiz: > > 1. Please do not post any solutions or spoiler discussion for this > quiz until 48 hours have elapsed from the time this message was > sent. > > 2. Support Ruby Quiz by submitting ideas and responses > as often as you can. > > 3. Enjoy! > > Suggestion: A [QUIZ] in the subject of emails about the problem > helps everyone on Ruby Talk follow the discussion. Please reply to > the original quiz message, if you can. > > - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - > > RSS Feed:http://rubyquiz.strd6.com/quizzes.rss > > Suggestions?:http://rubyquiz.strd6.com/suggestions > > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- > > ## Random Points within a Circle (#234) > > Greetings Rubyists, > > Generating random numbers is a useful feature and Ruby provides us > with `Kernel.rand` to generate numbers uniformly distributed between > zero and one. If we want to generate random numbers with other > distributions, then we'll need to do a little work. The quiz this week > is to generate random points uniformly distributed within a circle of > a given radius and position. > > This quiz is relatively simple, great if you are new to Ruby or > strapped for time. Remember, it is contributions from people like > *you* that make Ruby Quiz succeed! > > Have fun! > > -- > -Danielhttp://rubyquiz.strd6.com
From: Colin Bartlett on 22 Jun 2010 19:25 [Note: parts of this message were removed to make it a legal post.] (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 <vikkous(a)gmail.com> wrote: > On 6/21/10, Dave Howell <groups.2009a(a)grandfenwick.net> 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
From: Caleb Clausen on 22 Jun 2010 21:56 On 6/22/10, Colin Bartlett <colinb2r(a)googlemail.com> wrote: > 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. That was beautiful! The best explanation yet. Thank you. I keep wondering the use of sqrt will cause weird float rounding errors; that is will there be valid [float, float] pairs which are in the circle but can never be be found by an algorithm that includes Math.sqrt(rand)? Maybe someone with a better grip on the math has an answer to this.
From: Martin Boese on 23 Jun 2010 01:47 On Sun, 20 Jun 2010 03:05:58 +0900 Daniel Moore <yahivin(a)gmail.com> wrote: > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- > > ## Random Points within a Circle (#234) > > Greetings Rubyists, > > Generating random numbers is a useful feature and Ruby provides us > with `Kernel.rand` to generate numbers uniformly distributed between > zero and one. If we want to generate random numbers with other > distributions, then we'll need to do a little work. The quiz this week > is to generate random points uniformly distributed within a circle of > a given radius and position. > > This quiz is relatively simple, great if you are new to Ruby or > strapped for time. Remember, it is contributions from people like > *you* that make Ruby Quiz succeed! > > Have fun! Inspired by the other solutions here are two possible algorithms with a little benchmark and Tk visualization (call like ruby circlepoints.rb [n_points=5000] [a || b]). Martin -------------------- # Solution A: Randomly select a point in a square and retry if out of # the circle def mk_points_a(radius, n_points) n_points.times do begin x, y = [-1+2*rand, -1+2*rand] end while Math.sqrt(x**2+y**2).abs > 1 yield x*radius, y*radius end end # Solution B: Random angle and distance def mk_points_b(radius, n_points) n_points.times do angle = rand*2*Math::PI r = Math.sqrt(rand) yield r*Math.sin(angle) * radius , r*Math.cos(angle) * radius end end require 'tk' require 'benchmark' canvas = TkCanvas.new radius = 100 n_points = (ARGV[0] || 5000).to_i # select an algorithm method = ARGV.include?('b') ? :mk_points_b : :mk_points_a bench = Benchmark.measure do send(method, radius, n_points) do |x,y| TkcLine.new(canvas, radius + x, radius + y, radius + x + 1, radius + y + 1, 'fill' => 'black') end end puts "Using: #{method}" puts bench.to_s canvas.pack Tk.mainloop
From: Yaser Sulaiman on 24 Jun 2010 14:24
[Note: parts of this message were removed to make it a legal post.] 2010/6/22 Benoit Daloze <eregontp(a)gmail.com> > I would say it is a good try, and the distinction Vector/Point is > interesting, while being a problem with DRY (you repeat the > calculation of the distance). > Thanks. I don't know how did I miss it, but it kinda suddenly hit me: I can use Point.distance_to instead of Vector.length. After this realization, I decided to drop the Vector class altogether - although I have to admit that talking about generating random vectors sounds "cooler" :P A quick tip a friend showed me: Math.sqrt(a**2 + b**2) => Math.hypot(a, b) > In the end, you manually add the offset to x and y. As you have > Vector/Point, the Point+Vector should be defined and then the 4 last > lines would be: "center + v" > Because I'm not using Vectors anymore, Point + Point now performs the equivalent 2D translation. Also, Point.distance_to now uses Math.hypot. On Wed, Jun 23, 2010 at 2:25 AM, Colin Bartlett <colinb2r(a)googlemail.com>wrote: > 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. > I have modified the comments in the code to better reflect the used approach, which you have elaborate on here quite nicely. (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.) > v.length > 0 was necessary because of the way I was using the until loop (after initializing v to a null vector, v.length is 0 and the second test, v.length < radius, evaluates to true). Anyways, I'm now using the begin-end-until loop with a single test. Regarding using < vs. <=, I think it depends on whether points on the circumference (perimeter) of the circle are considered to be "within" the circle or not. Check the updated code @ http://gist.github.com/447554. Thank you all for your valuable feedback! Regards, Yaser |