Retreiving a random point in a circle

Function GetRandomPointInCircle GetRandomPointInCircle: function GetRandomPointInCircle takers real centerX, real centerY, real radius returns location local real degree = GetRandomReal(0, 360) local real range = GetRandomReal(0, radius) local real x = centerX + range * Cos(degree * bj_DEGTORAD) local real y = centerY + range * Sin(degree, * bj_dEGTORAD) return Location(x, y) endfunction

I'm curious as to the overall accuracy of this. Theoretically, getting a random angle and then a random radius should return a truly random point within a circle. Lately it has come to my attention that for some reason, this tends to hug the center of the circle instead of being truly random.

Could somebody please expand on this idea because if I need to get a random point from a circle, I want to make damned sure that its random. The effect just isn't the same if its not.



Here is the accurate version of the function, for those who need it:

Function GetRandomPointInCircle GetRandomPointInCircle: function GetRandomPointInCircle takers real centerX, real centerY, real radius returns location local real degree = GetRandomReal(0, 360) local real range = SquareRoot(GetRandomReal(0.0, 1.0)) * radius local real x = centerX + range * Cos(degree * bj_DEGTORAD) local real y = centerY + range * Sin(degree, * bj_dEGTORAD) return Location(x, y) endfunction

Consider a disk of radius two. Let's look at a strip with inner radius one, outer radius 1.1, and another strip between 2 and 2.1. The former has area roughly 2*pi*0.1 and the latter has area roughly 2*pi*2*0.1. If you chose between these two with equal probability, you would hit a given point on the inner ring twice as often as a given point in the outer, as there are twice as many points to choose from in the outer ring.

Now let me say that I think leaving this bias in is good for most applications. But if you must have equi-area probabilities,

That really clarified it for me, I hadn't thought about that. Your example was a little difficult to follow, so I'm still uncertain as to the math behind it, but it makes sense that the method in my previous post would be inaccurate.

I know I'm slightly retarded, so if its not too much trouble I would really appreciate a more clear example of your disk analogy. Regardless, thanks.

P.S.

I have altered my first post to contain the proper function, so that if anybody happens to venture onto this thread looking for the proper and accurate function, it will be right there.

What Pipedream was trying to say is the inner circle is smaller, therefore has lesser points to choose from, while the outer radius is bigger and has more points to choose from. By randomly picking numbers, you would get points inside the inner radius more often.

Why? If you were to choose a card inside a box that contained 5 cards, containing card number 1, 2, 3, 4 and 5 and another card in another box that contains 10 cards, from cards 1 - 10. You would have a much higher chance of getting a card from 1-5 in the first box than in the second box since there are less cards.

I'm saying that PipeDream's post made me understand that there are more points in the outer circle, therefore making it less probable to get further from the center, but what I don't get is the math behind it.

This is the part that I don't really get. I'm guessing you do 0 to 1 because that is like 0% of the radius to 100% of the radius, but why the square root?

Math Reasoning:
see http://en.wikipedia.org/wiki/Cumulat...ution_function
The probability of choosing a point up to x away from the center in a circle of radius r is the area of a circle with radius x divided by the area of our circle with radius r.

So our cumulative distribution function is:
C = pi*x^2/pi*r^2 = (x/r)^2

Now, given the cumulative probability function of something you want, you can take the output uniform probability function (what a computer gives you) and give an answer. It's easy: you just solve for x! (note: not actually easy sometimes)
C = (x/r)^2
x/r = squareroot(C)
x = r*squareroot(C)
which is exactly what you're doing now

In general you need multivariable calculus to measure the point density, so I recommend giving up on understanding why until you've studied that.

To get a truly random point, what you could technically do is make a square region encompassing your circle (if the circle has a radius of 500, your region would have points 500,500 500,-500 -500,-500 -500, 500) And then set a location variable to a random point in this region. Now, from here, you would say if that point is farther than 500 from the center of the region (thus syaing it has to be within 500 from the center) then you would try again to get a different point. (I would put the point choosing functions in a seperate trigger, then you can just re-execute the trigger over and over until it gets an acceptable point).
That may be a bit hard to understand, so ill trigger it out if you dont get it.

Thats a really un-reliable method since you could try 1000s of times and reject them all.

And now the lame-man's version of the random circle thing.

Okay, the original method was to pick a random angle and a random radius. Lets say, we have a circle of radius 100. Now, the random value picks a radius of 10. Now, no matter what angle is picked, the points will never exceed a distance of 20 between them.

Now, if you were to pick a radius of 100 (the max) the distance between points can vary up to 200 away. So, if the radius is smaller, you have a higher probability of picking the same point or close to. The farther you go out, the farther the points are.

Now, to counter this, we have to make the inside harder to pick, while the outside easier. This is done by simply taking the square root of a random real between 0 and 1 and then multiply it by the radius. Because the square root of 0.9 is roughly 0.9486 and the square root of 0.1 is roughly 0.3162, it exponentially pushes the random points to the outside of the circle, evening the spread.

Sampling is a great method. You can easily calculate the expected number of rejections, and it's not obviously not 1000s. For more general shapes and distributions it's also the only method, so it deserves mention. However since we have an analytical solution with an efficient implementation it is unnecessary.
There's a huge body of work on rapidly picking random points from a distribution, so check out scholar.google.com or your local library, as it's an old enough topic to appear in textbooks.

I got another method:
first u random the x axis from -radius to +radius, and then with the known circle radius you can find ymax and ymin using pythagoras, then just random between ymin and ymax to get random point in y axis.
And now as u have the randomed x and y, just add them to the x,y center point of the circle.

Same problem as polar coordinates, but even worse as it loses rotation symmetry. The center strip has many more points than a strip on the ends.

um no... i will make an example tomorrow and show u tat my method works.

No, he is right. You're method will favor the ~outside of the circle. You're picking a random x, which is essentially a random vertical line through the circle, then a random point on that line. The lines near the sides aren't as tall so the points contained in them are chosen more often than points on the tall lines.

ure right... i just couldnt understand pipe's language :P