Coding experts, a little help here

[Eeezee]

I've been thinking about this question for a long time. I've looked in my intro C and Java books, but I still haven't found an answer.

Let's say you want to move a particle in 3 dimensions by some unit distance. In other words, we're just dealing with a sphere of movement. Immediately I thought of generating a random number between 0 and 1 and multiplying that by some values

1) For theta, random * pi
2) For phi, random * 2pi

Where theta is from pole to pole and phi is from 0 to 2pi. However, this technique does not work. If you repeat it several times, you artificially obtain a lot of movement toward the poles. The distribution is uneven somehow. Instead, this is a solution.

1) For costheta, 2*random - 1
2) For sintheta, sintheta = sqrt(1-(costheta)^2)
3) For phi, random * 2pi

This generates an even 3d distribution, resulting in random 3d motion whereas the first idea did not. Can anyone figure out why this is?

 

[jiggahertz]

Trig functions are non-linear. The argument to these functions will be uniformly distributed, but the result will not.

 

[Savij]

Originally posted by: Eeezee
I've been thinking about this question for a long time. I've looked in my intro C and Java books, but I still haven't found an answer.

Let's say you want to move a particle in 3 dimensions by some unit distance. In other words, we're just dealing with a sphere of movement. Immediately I thought of generating a random number between 0 and 1 and multiplying that by some values

1) For theta, random * pi
2) For phi, random * 2pi

Where theta is from pole to pole and phi is from 0 to 2pi. However, this technique does not work. If you repeat it several times, you artificially obtain a lot of movement toward the poles. The distribution is uneven somehow. Instead, this is a solution.

1) For costheta, 2*random - 1
2) For sintheta, sintheta = sqrt(1-(costheta)^2)
3) For phi, random * 2pi

This generates an even 3d distribution, resulting in random 3d motion whereas the first idea did not. Can anyone figure out why this is?

Random isn't as random as you think it is.

 

[Eeezee]

Originally posted by: jiggahertz
Trig functions are non-linear. The argument to these functions will be uniformly distributed, but the result will not.

I don't understand this. Why wouldn't the result be evenly distributed?

 

[sciencewhiz]

Originally posted by: Eeezee

Originally posted by: jiggahertz
Trig functions are non-linear. The argument to these functions will be uniformly distributed, but the result will not.

I don't understand this. Why wouldn't the result be evenly distributed?

You're really asking a math question and not a software question.

You'd get the same result if you used an even distribution, for example 0 to 1 in .001 increments.


Here's a related question, For how many values of theta will cos(theta) be equal to 0. How many values of 2*random - 1 will the answer be 0? They aren't the same.

 

[jiggahertz]

Originally posted by: sciencewhiz

Originally posted by: Eeezee

Originally posted by: jiggahertz
Trig functions are non-linear. The argument to these functions will be uniformly distributed, but the result will not.

I don't understand this. Why wouldn't the result be evenly distributed?

You're really asking a math question and not a software question.

You'd get the same result if you used an even distribution, for example 0 to 1 in .001 increments.


Here's a related question, For how many values of theta will cos(theta) be equal to 0. How many values of 2*random - 1 will the answer be 0? They aren't the same.

Yeah, I guess the function doesn't need to be linear, but must be a bijection.

 

[LintMan]

Maybe I'm full of it, but as I see it:
I don't see why trig nonlinearities should factor into this at all. You're essentially picking the equivalent of a random elevation and random azimuth, or random latitude and random longitude, for that matter.

Latitude and longitude numbers are linear north to south and east to west, if you randomly pick a bunch them using an even distibution, they shouldn't bunch up at the poles. If you consider the radius of the earth as unit distance, what you are picking is equivalent. The trig only comes in when you convert the angles to x,y,z coordinates, but your direction is already fixed (ie: the random selection was already done and is the pure determinant of the direction you're moving), so the polar to cartesian conversion is just a straight conversion.

To simplify if further: what if you were randomly moving unit distance in just a 2D plane? It's pretty clear that picking random direction angles rand*0-2pi shouldn't bunch you up in any one direction. Why should 3D be any different?

So why doesn't it work for you? Perhaps a coding error?
- You're using 2 randoms to generate theta and phi, right? (Your post makes it sound like you might be using just one, but I assume you know better than that)
- How does your theta and phi line up with your x,y,z. (ie: does phi sweep the x-y plane?) It might help to specify that. Perhaps theta should run +pi/2 to -pi/2 instead of 0-pi?
- Are you sure your polar conversion to cartesian is 100% correct?
- Is your random function really generating just the [0-1] range? Many rand functions generate an int you must convert by dividing by maxrand (or maxrand+1 if you want [0-1) range).
- Are you using a stinky random number generator? Some only generate a 16-bit random value - that's not that many choices, especially if you're making millions of draws. I was programming a random map gererator using my old version of Visual C++ once and the results were ... not so random. I discovered the VC++ library had a crappy 16-bit rand function, so I googled up a nice powerful random library (Mersenne Twister), incorporated that into my program, and the results were dramatically better.

 

[TuxDave]

Please copy and paste your code. And perhaps a picture of the walk. Also did you make sure that the program isn't confusing radians and degrees?

 

[CTho9305]

Originally posted by: LintMan
Maybe I'm full of it, but as I see it:
I don't see why trig nonlinearities should factor into this at all.

Picking phi & theta is like picking a lattitude and longitude. Take a globe and put a dot on every lattitude-longitude crossing. Note how they're more dense (more crossings per square mile) near the poles. Intuitively, it's because as you move north, the longitudinal lines get closer together. To understand why, look at a plot of sin(x). Imagine picking 1000 random x values between 0 and pi - you'll find the resulting y values are denser near 0 and near pi. I put together a web page which does exactly that: try this (won't work in Internet Explorer, should work in almost anything else as long as it's modern).