Random point within a circle

Solar2D General Questions/Discussion
#21

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)
#22

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

#23

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

#24

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.

#25

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
#26

@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.)

#27

@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.

#28

local randomAngle = math.random(1000)

local circleRadius = 100

object.x = math.cos(randomAngle)*circleRadius

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

#29

Not too difficult if you use the “easy way”:

local function randomPointInCircle(x, y, radius) local randX, randY repeat randX, randY = math.random(-radius, radius), math.random(-radius, radius) until (((-randX) ^ 2) + ((-randY) ^ 2)) ^ 0.5 \<= radius return x + randX, y + randY end

All it does is repeatedly get a random point within a rectangle, then check if the point is under the needed distance from the center of the rectangle.

This is off the top of my head, so if it doesn’t work perfectly, let me know.

EDIT: Whoops, took so long to post that @thomas6 got there before me.

Might want to try both and see which is faster; don’t know if the cosine/sine calls would be slower than a few extra random calls.

  • Caleb
#30

Hehe, Caleb - and now we can battle out which method is more elegant or optimised!

#31

Well, yours is definitely more elegant, but I don’t know about optimized :). Just a second, let me see…

(Also, you need to set circleRadius to random - otherwise, you’ll just get a random point on a circle.)

  • Caleb
#32

Indeed! We’re getting there together :wink:

#33

After extensive tests (50000 iterations of each), I can officially say…

Faster - @thomas6’s (about 1.15 times faster)

Eleganter - @thomas6’s

Slower - mine

Uglier - mine

So, if you want the slow, ugly version, use mine by all means. Otherwise, use @thomas6’s :).

Funny about my algorithm - the history is that it comes from CBEffects, the initial version of which I wrote several years ago, when I was 12, before I’d learned trigonometry. Now I’ve learned trig, but it never occurred to me to use it for that :D.

  • Caleb
#34

Yeehaaaaa!

Thanks Caleb - did you localize the math.random() function as well for maximum speed gain?

I’m a huge trigonometry freak - probably a third of my code is making cool animations with trig.

#35

Yep. All localized. Don’t rub it in :D.

I adore trigonometry as well. I adore geometry. I adore algebra. I adore matrices. I adore anything math-y. Heh.

  • Caleb
#36

tho points generated in that manner won’t be evenly distributed within the circle, if it matters

to compensate:  take sqrt of a unit random, then mult by r * cos/sin(theta)

hth

#37

How so? And which “manner” are you referring to?

  • Caleb
#38

hi Dave,

Good point, although I’m wondering if there shouldn’t be a more elegant way to bias the circleRadius more towards the outer edge of the circle…

#39

And in this respect, Caleb’s method does work nicely!

#40

Oh yes now I see what you mean. What about distribute the random radius along a sine curve towards the full radius somehow? That might make things a bit better.

Good to hear mine’s better in some way!

  • Caleb