Random Points within a Circle (#234)

Ruby
1

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q.:

  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 Q. 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 T. 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 Q. succeed!

Have fun!

2

Hi !

On 19 June 2010 20:05, Daniel M. [email protected] wrote:

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 Q. succeed!

Have fun!

-Daniel

So here is my solution in a hundred lines, with an ImageMagick
visualisation:

I had an intuition doing some Math.sqrt about the distance, and it
revealed to be exact :slight_smile:

Enjoy,
Benoit D.

3

It’s not as advanced as Daloze’s solution, and it definitely can
(should?)
be enhanced, but my solution is available at
A solution for Ruby quiz #234 - Random Points within a Circle · GitHub.
Any feedback is welcomed.

In a nutshell, Point.random implements a random algorithm that
basically repositions the head of an initial null vector v until it
falls
within a circle of the given radius that is centered around the origin.
It
then translates a copy of that head to the correct position with respect
to
the given center.

BTW, this is the first time I participate in the Ruby Q… I’m looking
forward to future quizzes :slight_smile:

Regards,
Yaser S.

4

On 6/19/10, Daniel M. [email protected] wrote:

The quiz this week
is to generate random points uniformly distributed within a circle of
a given radius and position.

def random_point_in_a_circle(x,y,r)
angle=rand2Math::PI
r*=rand
x+=rMath.sin(angle)
y+=rMath.cos(angle)

return x,y
end

7 lines, 5 minutes, 0 tests or visualizations. Super-easy.

5

On Jun 21, 2010, at 15:45 , Caleb C. wrote:

return x,y
end

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.

6

On Mon, Jun 21, 2010 at 7:12 PM, Dave H.
[email protected] wrote:

y+=r*Math.cos(angle)

return x,y
end

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 whipped up a quick little visualization:

def random_point_in_a_circle(x,y,r)
angle=rand2Math::PI
r*=rand
x+=rMath.sin(angle)
y+=rMath.cos(angle)

return x,y
end

require ‘java’
JFrame = javax.swing.JFrame
JPanel = javax.swing.JPanel

frame = JFrame.new(“Random Points within a Circle”)
frame.default_close_operation = JFrame::EXIT_ON_CLOSE
frame.set_size(400, 400)
frame.show

class RPwiaC < JPanel
def paintComponent(graphics)
super(graphics)

10000.times do
  x,y = random_point_in_a_circle(200,200,150)
  graphics.draw_line(x-1,y-1,x+1,y+1)
  graphics.draw_line(x-1,y+1,x+1,y-1)
end

end
end

panel = RPwiaC.new
frame.add(panel)
panel.repaint
panel.revalidate

7

On 6/21/10, Dave H. [email protected] wrote:

On Jun 21, 2010, at 15:45 , Caleb C. 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.

8

On Mon, Jun 21, 2010 at 9:12 PM, [email protected] wrote:

r*=rand
I whipped up a quick little visualization:
Quick hack to animate the above method side by side with an alternate
method:

require ‘java’
JFrame = javax.swing.JFrame
JPanel = javax.swing.JPanel

frame = JFrame.new(“Random Points within a Circle”)
frame.default_close_operation = JFrame::EXIT_ON_CLOSE
frame.set_size(700, 400)
frame.show

class RPwiaC < JPanel
def initialize times, *procs
super()

@times = times
@procs = procs

end

def paintComponent(graphics)
super(graphics)

@times.times do
  @procs.each_with_index do |proc, i|
    x,y = proc.call(200 + (300 * i),200,150)
    graphics.draw_line(x-1,y-1,x+1,y+1)
    graphics.draw_line(x-1,y+1,x+1,y-1)
  end
end

end
end

panel = RPwiaC.new(
5000,
lambda{|x,y,r|
angle=rand2Math::PI
r*=rand
x+=rMath.sin(angle)
y+=rMath.cos(angle)
return x,y
},
lambda{|x,y,r|
loop {
a = x + rand(2r) - r
b = y + rand(2r) - r
d = Math.sqrt((x - a) ** 2 + (y - b) ** 2)
return a,b if d < r
}
}
)

frame.add(panel)
panel.revalidate

loop { panel.repaint }

9

On 22 June 2010 00:30, Yaser S. [email protected] wrote:

It’s not as advanced as Daloze’s solution, and it definitely can (should?)
be enhanced, but my solution is available at A solution for Ruby quiz #234 - Random Points within a Circle · GitHub.
Any feedback is welcomed.

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).
A quick tip a friend showed me: Math.sqrt(a2 + b2) => 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”

On 22 June 2010 01:12, Dave H. [email protected]
wrote:

r*=rand
x+=rMath.sin(angle)
y+=rMath.cos(angle)

return x,y
end

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.

That was also my initial thought, and I think for most of us.

Caleb:

I guess this is why Benoit had that sqrt in there. I don’t quite get
why it’s necessary.

Indeed, please look at my solution and remove the “sqrt”, and you will
see most of the points will be in the center .
The output will look like:
min: 1, moy, 1.13, max: 122 # This is way too much
max Point: (-2.0,4.0) # which is the center

The image would then look like a point in the center.
I ‘felt’ it would result in that because the points near the center
will be much closer to each other, as it will be as much points at any
distance.

Brabuhr’s visualization is even way better to see it (especially the
animated one) !

And finally, why the sqrt? I just felt like I should have as many
points in each area, and the area of a circle is ðr^2, so let’s reduce
this r^2 and becomes r. (Also I wanted the random distance to be
likely further from the center, and as rand returns between 0 and 1,
we have to do ^(1/2) and not ^2.

  • Benoit
10

On 6/22/10, [email protected] [email protected] wrote:

Found an explanation:
Uniform random points in a circle using polar coordinates – anderswallin.net

Thanks. It took me a while, but it’s making sense now.

11

2010/6/22 Benoit D. [email protected]:

The image would then look like a point in the center.
I ‘felt’ it would result in that because the points near the center
will be much closer to each other, as it will be as much points at any
distance.

And finally, why the sqrt? I just felt like I should have as many
points in each area, and the area of a circle is ðr^2, so let’s reduce
this r^2 and becomes r. (Also I wanted the random distance to be
likely further from the center, and as rand returns between 0 and 1,
we have to do ^(1/2) and not ^2.

Found an explanation:
http://www.anderswallin.net/2009/05/uniform-random-points-in-a-circle-using-polar-coordinates/

12

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)@rrand_sign
run = rand(0)@rrand_sign
#validate that point lies within circle, about 20% fail
if Math.sqrt(run2+rise2)<@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

13

On 6/22/10, Colin B. [email protected] wrote:

(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 H. 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.

14

(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 C. [email protected]
wrote:

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 - r2 ) = pi * 2re + pi * e2
So, if I treat e as an infinitesimal and neglect the e2 (and hope that
no
real mathematicians are looking, or claim I’m using
Abraham Robinson’s Abraham Robinson - Wikipedia
Non-Standard Analysis
Nonstandard analysis - Wikipedia
and hope that nobody asks me any awkward questions about how that really
works)
the area of the annulus is (approximately) pi * 2re.
(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 H.
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

15

On Sun, 20 Jun 2010 03:05:58 +0900
Daniel M. [email protected] wrote:

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 Q. 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+2rand, -1+2rand]
end while Math.sqrt(x2+y2).abs > 1
yield xradius, yradius
end
end

Solution B: Random angle and distance

def mk_points_b(radius, n_points)
n_points.times do
angle = rand2Math::PI
r = Math.sqrt(rand)
yield rMath.sin(angle) * radius , rMath.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

16

2010/6/22 Benoit D. [email protected]

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” :stuck_out_tongue:

A quick tip a friend showed me: Math.sqrt(a2 + b2) => 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 B.
[email protected]wrote:

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 @ A solution for Ruby quiz #234 - Random Points within a Circle · GitHub. Thank you all
for
your valuable feedback!

Regards,
Yaser

17

Here’s a quick solution visualized using Rubygame¹:

http://www.pastie.org/1018079

I’m sorry about the lack of comments (the code should
be mostly self-explanatory, if not just ask.)

–
Lars H.

[1] http://rubygame.org/

18

I had an intuition doing some Math.sqrt about the distance, and it
revealed to be exact :slight_smile:

I bet you didn’t do that right from the start, before seeing the
first results? At least I didn’t. :slight_smile:

19

On 24 June 2010 21:24, Yaser S. [email protected] wrote:

[…] although I have to admit that
talking about generating random vectors sounds “cooler” :stuck_out_tongue:
Yes, and a Point + Point is not as meaningful

Because I’m not using Vectors anymore, Point + Point now performs
the equivalent 2D translation. Also, Point.distance_to now uses Math.hypot.

Cool, but I believe your implementation of Point#+ is somehow bad,
because it returns @y.
So you probably want to return self if you accept the Point objects to
be mutable,
or create a new Point, which is a bit safer, but creates a new object
(in both cases you could definitely get rid of this awful “return p” :slight_smile:
)

Also, @@origin should not be modified, and then should be a constant,
and be #freeze if you want Point to be mutable.

On 25 June 2010 03:05, Lars H. [email protected] wrote:

I had an intuition doing some Math.sqrt about the distance, and it
revealed to be exact :slight_smile:

I bet you didn’t do that right from the start, before seeing the
first results? At least I didn’t. :slight_smile:

Lars H.

I thought while writing it (without sqrt) that it was going wrong, and
the next day I thought to sqrt.
The night is a good adviser :slight_smile:

B.D.

20

On Fri, Jun 25, 2010 at 1:57 PM, Benoit D. [email protected]
wrote:

Cool, but I believe your implementation of Point#+ is somehow bad,
because it returns @y.
So you probably want to return self if you accept the Point objects to
be mutable,
or create a new Point, which is a bit safer, but creates a new object
(in both cases you could definitely get rid of this awful “return p” :slight_smile: )

The awful “return p” is now gone :wink:
I want Point objects to be mutable, so Point#+ returns self
after modifying the x and y coordinates.

Also, @@origin should not be modified, and then should be a constant,
and be #freeze if you want Point to be mutable.

Good point. The origin is now a “frozen” class constant.