Random point within a circle

Solar2D General Questions/Discussion
#41

Hey Caleb,

A random radius between 1 and 36000 divided by 100 doesn’t help - and don’t you mean random angle? I think Dave is referring to the fact that using a linear distribution from center of the circle to outer edge, will mean that the points will be more densely populated near the center.

By the way, my math.random(1000) is, of course, just a crude and simple method. For perfect solutions I would need to get one full revolution in there, but I just went for something that probably works for the needs here.

#42

Yep. Duh. I realized that right when I posted it. And yes, I meant angle. I was thinking of the angle as being better distributed that way, because it wouldn’t skip as many points nearer the edge of the circle. But that wouldn’t solve the problem anyhow.

I need to back out of this conversation before I say something really stupid :).

  • Caleb
#43

Whew! On testing, you do actually get a little better distribution with that, so it wasn’t all that dumb after all. But it doesn’t solve the problem.

At least I’m justified in my thinking :).

EDIT: https://www.dropbox.com/s/118ql8o7m8iiol6/distribution.gif?dl=0

  • Caleb
#44

I’m thinking - but it’s just a intuitive guess - that I can fix my method by biasing the circleRadius like this:

local circleRadius = 100

local rooted = math.random(math.sqrt(circleRadius))

local correctedDistance = rooted * rooted

object.x = math.cos(randomAngle)correctedDistance

object.y = math.sin(randomAngle)*correctedDistance

Then again, this will introduces a loss of precision in defining the radius. Oh well. Close enough!

#45

almost, but squaring a square root just gives you back the original number (and its distribution) minus a “quantizing” effect from loss of precision (from calling math.random(N) instead of math.random()*N).  this is the sort of form you’d want for an even distribution (assuming that’s what you want):

local function pointInCircle(x,y,r)   r = math.sqrt(math.random())\*r   local theta = math.random()\*2\*math.pi   return { x=x+r\*math.cos(theta), y=y+r\*math.sin(theta) } end

hth

#46

Awesome response as usual.  I was expecting one maybe two replies at most.
Will have a play around with the different suggestions and work out which works best for what I need.
Many many thanks!

#47

In some boids implementations, you’ll start with a given direction, add a little offset to it, and then snap that back onto the circumference to get the new (unit vector) direction. This will give you a reasonably “nearby” direction without much effort.

The same idea might give you a reasonable generator, although maybe it would mostly get stuck near the border. In any case, something like (tested just a little):

local x, y = 0, 0 local Scale = 10 -- tune if necessary function RandomPointInCircle (radius) x, y = x + (2 \* math.random() - 1) \* Scale, y + (2 \* math.random() - 1) \* Scale local r = math.sqrt(x^2, y^2) if r \> radius then local scale = radius / r scale = scale \* (.8 + math.random() \* .2) -- Maybe this would avoid getting "stuck" x, y = x \* scale, y \* scale end return x, y end local circle = display.newCircle(0, 0, 15) local params = { time = 100 } timer.performWithDelay(150, function() local x, y = RandomPointInCircle(250) params.x, params.y = display.contentCenterX + x, display.contentCenterY + y transition.to(circle, params) end, 0)
#48

Thank you gentlemen! This was an awesome thread :slight_smile:

#49

I agree.  It’s just a shame I don’t really understand 99% of it  :smiley:

#50

No shame at all - you only need to understand enough to use it. Trust me, it’s the same for everyone, just at different levels.

#51

Indeed quite an awesome thread.

Cinders and ashes! The “corrected” version of @thomas6’s approach (the last comment by @davebollinger) is still faster than mine. I was going to test them both (now that @thomas6’s has more math function calls), then come yell Ha! and pull out the time data, but it still ended up being faster by about 1.09 times. A bit slower than the original one, but not very much so.

Whatever the case, anyone who doesn’t see the beauty in a circle with evenly distributed randomized points in it is just crazy.

https://www.dropbox.com/s/gggzsfxjrmsvhi8/distribution_final.gif?dl=0

(I managed to catch it at a time when the first one took a longer time, but that’s not the norm… unfortunately!)

  • Caleb
#52

@Caleb P

Slightly off-topic for this thread, but if you “see the beauty … with evenly distributed randomized points” (say, for particle distributions), the “boundary sampling” routine mentioned in this paper doesn’t look too hard to port: code (assuming the relaxation steps afterward aren’t strictly necessary, anyway). I keep meaning to get around to it myself, but so far never have.

(It’s kind of a weird paper, since the authors spend ten pages developing a different technique, then at the end sort of go “Or you could do this” and show boundary sampling.)

#53

@Caleb P
Actually I like you approach (I don’t think it’s uglier @thomas6’s approach :slight_smile: ), and it seems could be faster, here my changes:

[lua]

local math_sqrt = math.sqrt
local math_random = math.random
local math_pi2 = math.pi * 2
local math_cos = math.cos
local math_sin = math.sin

local radius = 500
local radius2 = radius * radius

local count = 2000000
local x, y, r, theta

local time = system.getTimer ()
for i = 1, count do
    r = math_sqrt (math_random()) * radius
    theta = math_random () * math_pi2
    x = r * math_cos (theta)
    y = r * math_sin (theta)
    – too many circles
    – display.newCircle (x + display.contentCenterX, y + display.contentCenterY, 1)
end

local time2 = system.getTimer()

for i = 1, count do
    repeat
        x = math_random (-radius, radius)
        y = math_random (-radius, radius)
    until x * x + y * y <= radius2 – << this is the optimization
    – too many circles
    – display.newCircle (x + display.contentCenterX, y + display.contentCenterY, 1)
end

local time3 = system.getTimer()

print ((time2 - time) / (time3 - time2), time3 - time2, time2 - time)

[/lua]

On my tests, your approach is faster about 1.3 times than @thomas6’s approach.
Thanks for thread.