Hello Guest

Randomly generating points within a sphere

  • 26 Replies
  • 32193 Views
Randomly generating points within a sphere
« on: March 24, 2005, 18:50:13 »
Ok, my math just isn't so great (I think I'm gonna go buy a book)...

I'm trying to generate x number of random points, all within a sphere. Big problem though, I can't seem to figure out the math.  :?

I know the radius of the sphere, and it's origin (let's just say it's 0,0,0 for simplicity's sake). I've tried several methods, but I always end up with the points being distributed too far within the sphere, or going outside of it.  Anyone know the math for this? It would be greatly appreciated.
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

*

Offline WiESi

  • **
  • 70
Randomly generating points within a sphere
« Reply #1 on: March 24, 2005, 18:55:38 »
« Last Edit: April 19, 2011, 13:01:17 by WiESi »

Randomly generating points within a sphere
« Reply #2 on: March 24, 2005, 18:59:24 »
Where does the Z coordinate factor into this? Is it x^2 + y^2 + z^2 = r^2 ?
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

Randomly generating points within a sphere
« Reply #3 on: March 24, 2005, 19:04:51 »
Of course, now that I'm thinking about it, I'm not even sure how to code it up using the sphere equation...

I tried generating random vectors for dx, dy, and dz, but I wasn't sure how to plug them into the radius to find the point x,y,z. Any ideas? The vector method seems easier to code... I think.  :?
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

Randomly generating points within a sphere
« Reply #4 on: March 24, 2005, 19:07:28 »
An alternative method:
1 radom radius r (0 to sphere radius)
2 random longitude l (0 to 2*PI)
3 random latitude h (0 to PI) Edit: should be -PI/2 to PI/2

(x,y,z)=(r*cos(l)*cos(h), r*sin(h), r*sin(l)*cos(h))

More math instead of using the previous method and only randomizing x, y, z and discarding those outside the sphere but math is fun :wink:

Anders

Edit:
Trial and error method like this:
do {
dx=random()*2*R-R;
dy=random()*2*R-R;
dz=random()*2*R-R;
while(dx*dx+dy*dy+dz*dz>R*R);
position.set(xorigin+dx, yorigin+dy,zorigin+dz);

Randomly generating points within a sphere
« Reply #5 on: March 24, 2005, 19:21:04 »
Thanks Anders... It's working really well. I get an interesting plotting of points (they like gravitating more towards the center and axis of the sphere), but I think I can work with it.  :D

Edit: Oh, and one more thing for those trying it, I had to make the random "h" =  (Math.random()*Math.PI*2) - Math.PI), in order to get values below the top half of the sphere as well.
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

Randomly generating points within a sphere
« Reply #6 on: March 24, 2005, 19:30:27 »
Ah, sorry, should have been r*cos(h) for the y coord to work with 0 to PI.
Edit: and then x and y should use sin (h)

Yes that would be an effect that they seems to be "gravitating" towards the middle since the sphere is smaller there and r is lineary randomized.
this should not happend with the discard method that WEiSi suggested
 
Anders

Randomly generating points within a sphere
« Reply #7 on: March 24, 2005, 20:30:37 »
I'm still curious about the vector method... my vector math is really weak, but I seem to remember, if you have a dx, dy, and dz, and a radius (or random number from 0 to radius), you can generate a point. I'm just not sure who to properly calculate the vector/average the vector for that.
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

Randomly generating points within a sphere
« Reply #8 on: March 24, 2005, 22:37:07 »
Well, I got ahold of a physics professor friend of mine... he shot down the vector method.

Instead he gave me this method (I converted it to code):

float r = (float)Math.random()*(sphereradius);
float phi = (float)(Math.random()*Math.PI);
float theta = (float)(Math.random()*Math.PI*2f);
float tempsetX = (float)(r * Math.cos(theta) * Math.sin(phi));
float tempsetY = (float)(r * Math.sin(theta) * Math.sin(phi));
float tempsetZ = (float)(r * Math.cos(phi));
pointlocation = new Vector3f(tempsetX,tempsetY,tempsetZ);

Basically, using spherical points and converting to cartesian. It's very similar to Anders' method.
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

*

Offline tomb

  • ***
  • 148
Randomly generating points within a sphere
« Reply #9 on: March 25, 2005, 01:16:55 »
That is way to complex. I would go with WEiSis method. Generate randomers inside the sphere bounding box. Discard points outisde sphere.
if dx, dy, dz is distance from center of the sphere to the test point, then the is inside if:

boolean isInsideSphere = ((dx*dx + dy*dy + dz*dz) < (r*r));

Easy, fast and no mucking around with trig functions.

Randomly generating points within a sphere
« Reply #10 on: March 25, 2005, 07:41:02 »
Your helpful physics professor and I suggest the same method. The difference is only a matter of what axis you call x, y, and z. (And the mistake I made in sin(h) writing 0 to PI instead of -PI/2 to PI/2 :oops: )
(Not very surpricing since I´m a physics teatcher...) :)

I agree with tomb that for just generating random points it´s probably easier to do the trial and error method.

Anders

Randomly generating points within a sphere
« Reply #11 on: March 25, 2005, 15:04:09 »
I guess my problem is wanting to actually understand the math better (does that make me crazy?). Unfortunately, my physics professor friend informed me that he didn't learn a lot of the sphere mathematics until he was a senior in his major.  :?  I guess that doesn't bode well for someone who graduated in English.  :P
=-=-=-=-=-======-=-=-=-=-=-
http://www.tommytwisters.com

*

Offline tomb

  • ***
  • 148
Randomly generating points within a sphere
« Reply #12 on: March 25, 2005, 15:36:25 »
In this case the math is very easy. It's been a while since I learned it in school, but I think it is call phytagoras (no idee how it is spelled, but it's the greak guy how discovered it). When you got a triangle with one angle that is 90 deg, then the distance of the longest side is the square root of the sum of the square shortest side. Ok, I know my description sucks, and I might just be rambeling, but this must be basic highschool math that everyone learns, right?

Randomly generating points within a sphere
« Reply #13 on: March 25, 2005, 18:02:15 »
Correct!
Draw a circle at the origin of a x,y coordinate system. Draw a line from the origin to a point on the circle and then straight down to the x-axis. You then got a right-angled triangle. Then x^2+y^2=r^2 (Pythagoras theorem) for all points on the circle.
For a sphere you then imagines a paper standing in the z-direction and going through the origin and a point of your original circle. You will find that  you have to use pythagoras theorem twice (first on the xy-surface and then for the radius) and you end up with x^2+y^2+z^2=r^2

cos and sin is slightly more advanced but the reason physicist in general don´t read a lot of spherical trigonometry is that they dont need it not that it complicated. The only physicists who reads a lot about spheres are astronomers, you can all guess why   :D

Anders

Randomly generating points within a sphere
« Reply #14 on: March 25, 2005, 22:51:11 »
I actually did this last weekend, using vectors. The steps were as follows:

1:generate point a point within a range much higher than your actual sphere radius, store that point in a vector.

2: normalize the vector

3: multiply the individual components of the normalized vector by the (+/-)radius of the sphere.

4: repeat for the number of points you want your sphere to be made up of.


that will put all the points on the edge of a sphere though, not sure if thats what you want. It would be easy to change it so they filled the sphere though. In step 3 where you multiply by the radius of the sphere, instead multiply by a random number between zero and the radius.