449,438 Members | 1,610 Online Need help? Post your question and get tips & solutions from a community of 449,438 IT Pros & Developers. It's quick & easy.

# Random numbers within a sphere?

 P: n/a Hello everyone, I was wondering if someone could help me with an issue I have in C++. I want to select random points within the volume of a sphere. I know how to get random numbers using srand() and rand(), but have no idea how to do that within a more complicated geometry. Any help would be greatly appreciated.. Regards Stavros Jul 23 '05 #1
24 Replies

 P: n/a Stavros Christoforou wrote: Hello everyone, I was wondering if someone could help me with an issue I have in C++. I want to select random points within the volume of a sphere. I know how to get random numbers using srand() and rand(), but have no idea how to do that within a more complicated geometry. Any help would be greatly appreciated.. You could represent any point of the sphere in spherical coordinates: a radius and two angles. A coordinate is a uniform variable (using rand()) in its [min,max] interval. Jul 23 '05 #2

 P: n/a Stavros Christoforou wrote: I was wondering if someone could help me with an issue I have in C++. I want to select random points within the volume of a sphere. I know how to get random numbers using srand() and rand(), but have no idea how to do that within a more complicated geometry. Any help would be greatly appreciated.. Select a random radius (between 0 and the sphere radius), a randon azimuth (0 through 2*Pi) and a random elevation (-Pi/2 through Pi/2) and then convert the three values from spherical coordinates into Cartesian (if that's your desired result). And please don't post off-topic questions here. Your question has nothing to do with C++ language and ought to be posted in comp.graphics.algorithms or comp.programming. V Jul 23 '05 #3

 P: n/a Fabio Rossi wrote: Stavros Christoforou wrote: Hello everyone, I was wondering if someone could help me with an issue I have in C++. I want to select random points within the volume of a sphere. I know how to get random numbers using srand() and rand(), but have no idea how to do that within a more complicated geometry. Any help would be greatly appreciated.. You could represent any point of the sphere in spherical coordinates: a radius and two angles. A coordinate is a uniform variable (using rand()) in its [min,max] interval. Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. The fix is to bound the sphere with a cube, tangent on all faces, and find random points in the cube by finding random xyz points, each >= -r and < r, where r is the radius of the sphere. Then filter out all points laying outside the sphere, by comparing x^2 + y^2 + z^2 to r^2. -- Phlip http://industrialxp.org/community/bi...UserInterfaces Jul 23 '05 #4

 P: n/a Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. How so? If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. The fix is to bound the sphere with a cube, tangent on all faces, and find random points in the cube by finding random xyz points, each >= -r and < r, where r is the radius of the sphere. Then filter out all points laying outside the sphere, by comparing x^2 + y^2 + z^2 to r^2. That wouldn't be any better and a lot slower as a lot of samples would have to be generated, tested, and discarded. Jul 23 '05 #5

 P: n/a Ron Natalie wrote: Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. How so? If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. The fix is to bound the sphere with a cube, tangent on all faces, and find random points in the cube by finding random xyz points, each >= -r and < r, where r is the radius of the sphere. Then filter out all points laying outside the sphere, by comparing x^2 + y^2 + z^2 to r^2. That wouldn't be any better and a lot slower as a lot of samples would have to be generated, tested, and discarded. "A lot of samples"? The sphere is about half the volume of its circumscribing cube. So, less than half of all samples are going to be discarded. Doesn't seem like "a lot" to me. Of course, everybody has their own definition of "a lot". Is there a better way to produce points evenly distributed in the volume of a sphere? V Jul 23 '05 #6

 P: n/a Ron Natalie wrote: Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. How so? If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. No, the probability of being close to the center is higher than the probability of being around the edges. Jul 23 '05 #7

 P: n/a No, the probability of being close to the center is higher than the probability of being around the edges. May I ask why? Stavros might need evenly distributed numbers. A polar coordinatescheme would bunch numbers up around the center, at least.How so? If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. The density would be selected from a pdf, eg s = - (log ((double) (rand()+ 1.0)/RAND_MAX))/sigmat (just a random function) Therefore my problem focuses more on how to select the points within the sphere, and my idea so far was similar to Philip's. However, I am sure something faster and more "code-correct" exists. Also, sorry if I posted this on the wrong group, but as I am creating the program on C++ I thought that this would be the appropriate place to ask questions. Stavros Jul 23 '05 #8

 P: n/a Stavros Christoforou wrote: No, the probability of being close to the center is higher than the probability of being around the edges. May I ask why? It might be a little hard to explain without graphical aid :) But basically, to be around the center, you need to have a small radius. The angles don't really matter here - as long as the radius is small, then the point will be near the center. To make the point closer to a particular edge, you need a bigger radius *and* the correct angle (or direction, or whatever). So the probability of this happening is less. Hope this helps, -shez- Jul 23 '05 #9

 P: n/a Ron Natalie wrote: Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. How so? The problem is that the mean distance between 2 neighboring points is smaller near the center then it is at the circumference. So the number of points near the center is packed tighter -> the point density (nr of points per partial volume) is higher. Depending on the application this might or might not be acceptable. If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. The fix is to bound the sphere with a cube, tangent on all faces, and find random points in the cube by finding random xyz points, each >= -r and < r, where r is the radius of the sphere. Then filter out all points laying outside the sphere, by comparing x^2 + y^2 + z^2 to r^2. That wouldn't be any better and a lot slower as a lot of samples would have to be generated, tested, and discarded. .... Yes, but it generates a uniform volume sampling of the sphere. Something the radius/angle method doesn't do. -- Karl Heinz Buchegger kb******@gascad.at Jul 23 '05 #10

 P: n/a Shezan Baig wrote: Stavros Christoforou wrote: No, the probability of being close to the center is higher than the probability of being around the edges. May I ask why? It might be a little hard to explain without graphical aid :) But basically, to be around the center, you need to have a small radius. The angles don't really matter here - as long as the radius is small, then the point will be near the center. To make the point closer to a particular edge, you need a bigger radius *and* the correct angle (or direction, or whatever). So the probability of this happening is less. What 'edges' are you talking about? -- Karl Heinz Buchegger kb******@gascad.at Jul 23 '05 #11

 P: n/a Karl Heinz Buchegger wrote: Shezan Baig wrote: Stavros Christoforou wrote: > No, the probability of being close to the center is higher than the > probability of being around the edges. > May I ask why? It might be a little hard to explain without graphical aid :) But basically, to be around the center, you need to have a small radius. The angles don't really matter here - as long as the radius is small, then the point will be near the center. To make the point closer to a particular edge, you need a bigger radius *and* the correct angle (or direction, or whatever). So the probability of this happening is less. What 'edges' are you talking about? -- Karl Heinz Buchegger kb******@gascad.at Sorry, I meant a point near the circumference. Jul 23 '05 #12

 P: n/a Shezan Baig wrote: Karl Heinz Buchegger wrote: Shezan Baig wrote: Stavros Christoforou wrote: > > No, the probability of being close to the center is higher than the > > probability of being around the edges. > > > > May I ask why? > It might be a little hard to explain without graphical aid :) But basically, to be around the center, you need to have a small radius. The angles don't really matter here - as long as the radius is small, then the point will be near the center. To make the point closer to a particular edge, you need a bigger radius *and* the correct angle (or direction, or whatever). So the probability of this happening is less. What 'edges' are you talking about? Sorry, I meant a point near the circumference. In this case your argumentation doesn't apply. If a sampled radius is 80% of the speheres radius, then it will be 20% from the surface, no matter which direction. -- Karl Heinz Buchegger kb******@gascad.at Jul 23 '05 #13

 P: n/a On Tue, 08 Feb 2005 14:18:56 GMT, Phlip wrote: Fabio Rossi wrote: Stavros Christoforou wrote: > Hello everyone, > > I was wondering if someone could help me with an issue I have in C++. I > want to select random points within the volume of a sphere. I know how > to get random numbers using srand() and rand(), but have no idea how to > do that within a more complicated geometry. Any help would be greatly > appreciated.. You could represent any point of the sphere in spherical coordinates: a radius and two angles. A coordinate is a uniform variable (using rand()) in its [min,max] interval. Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. The fix is to bound the sphere with a cube, tangent on all faces, and find random points in the cube by finding random xyz points, each >= -r and < r, where r is the radius of the sphere. Then filter out all points laying outside the sphere, by comparing x^2 + y^2 + z^2 to r^2. That's not likely to be an even distribution since you're discarding samples. The OP need to define what the set of "points" is in the fist place, which would depend on the coordinate system chosen. The OP would also need to define the function f(x, y), where x and y are "points", against which the random distribution is being applied. It could be metric distance between the points or something else entirely. The OP really needs to repost their question in comp.programming where they deal with these kind of questions rather than there where it's a little off topic. -- Joe Seigh http://atomic-ptr-plus.sourceforge.net/ Jul 23 '05 #14

 P: n/a Joseph Seigh wrote: The OP really needs to repost their question in comp.programming where they deal with these kind of questions rather than there where it's a little off topic. I see. Thank you all for your replies, I'll give it a shot there! Stavros Jul 23 '05 #15

 P: n/a Joseph Seigh wrote: That's not likely to be an even distribution since you're discarding samples. It's a very common technique: generate values that are evenly distributed and discard ones that aren't in the desired range. The remaining values are as evenly distributed in the target range as the original ones were in their range. -- Pete Becker Dinkumware, Ltd. (http://www.dinkumware.com) Jul 23 '05 #16

 P: n/a Pete Becker wrote: Joseph Seigh wrote: That's not likely to be an even distribution since you're discarding samples. It's a very common technique: generate values that are evenly distributed and discard ones that aren't in the desired range. The remaining values are as evenly distributed in the target range as the original ones were in their range. For example, if Pete and me post to a newsgroup for a decade, and your filter in all the posts where he backs up one of my wild opinions, the posts will have the same distribution. Except over a much smaller set. ;-) -- Phlip Jul 23 '05 #17

 P: n/a Off the top of my head, I think you'd need to look at the partial deriative of the volume with respect to radius, ie, at a particular distance see what a delta R did to delta V...... but I've got to go to lectures , ( and a bit OT!) Nice probelm tho!! Mike "Stavros Christoforou" wrote in message news:1f***************************@news1.tudelft.n l... No, the probability of being close to the center is higher than the probability of being around the edges. May I ask why?Stavros might need evenly distributed numbers. A polar coordinatescheme would bunch numbers up around the center, at least.How so? If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. The density would be selected from a pdf, eg s = - (log ((double) (rand()+ 1.0)/RAND_MAX))/sigmat (just a random function) Therefore my problem focuses more on how to select the points within the sphere, and my idea so far was similar to Philip's. However, I am sure something faster and more "code-correct" exists. Also, sorry if I posted this on the wrong group, but as I am creating the program on C++ I thought that this would be the appropriate place to ask questions. Stavros Jul 23 '05 #18

 P: n/a Ron Natalie wrote: Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. How so? If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. Instead of random numbers, imagine evenly spaced numbers on a line. Put the line from the center to the rim of a circle. Add a point to the circle's plane for each number on the line. Now rotate the line so it reaches from the center to another point on the rim. Stamp out more points onto the circle. Keep going until you have covered the rim in an even number of steps. Notice you drew N dotted circles, one for each number on the original line. Now notice how the dots near the center are closer together. Arbitrarily plugging evenly spaced pseudorandom numbers into polar coordinates, with no other adjustments, will bunch the numbers up around the center. The fix is to bound the sphere with a cube, tangent on all faces, and find random points in the cube by finding random xyz points, each >= -r and < r, where r is the radius of the sphere. Then filter out all points laying outside the sphere, by comparing x^2 + y^2 + z^2 to r^2. That wouldn't be any better and a lot slower as a lot of samples would have to be generated, tested, and discarded. Only slower by the volume of a cube minus the volume of a tangent sphere. Most points will be inside the sphere. The performance would still only be dominated by the speed of generating pseudo-random numbers, and the speed of comparing their distances. (And note I left the Square Root calculation out of the distance formula.) -- Phlip Jul 23 '05 #19

 P: n/a Ron Natalie wrote: Stavros might need evenly distributed numbers. A polar coordinate scheme would bunch numbers up around the center, at least. How so? If the [0, sphere-radius] random number generator is uniform, so would the density with respect to the center. As always with geometrical probability, what constitutes "even distribution" is not as obvious as it might seem at the first sight. It depends on the choice of metric. That's exactly the essence of the misunderstanding that takes place in this discussion. For an illustration look up "bertrand paradox" (or "bertrand's paradox") on Google, it is directly relevant to the ongoing discussion (see, for example, here http://www.cut-the-knot.org/bertrand.shtml). -- Best regards, Andrey Tarasevich Jul 23 '05 #20

 P: n/a Stavros Christoforou wrote: I was wondering if someone could help me with an issue I have in C++. I want to select random points within the volume of a sphere. I know how to get random numbers using srand() and rand(), but have no idea how to do that within a more complicated geometry. Any help would be greatly appreciated.. ... This is an off-topic question. But anyway, in order to devise a method of generating random numbers within certain "geometrical object" (a 3D sphere, a 2D circle or something else) you have to decide what kind of distribution you would like to obtain. Depending on the application, this might affect your results significantly. What is the primary purpose of that random point generator? Imagine, for example, that your sphere has radius R. And also that there's another sphere inside that first one with the same center and radius R/2. Let's say we want to use Monte Carlo method in order to determine how many times the [Euclidean] volume of the inner sphere is smaller than the volume of the larger sphere. It is simple: we just generate a large number of random points (N points) inside the outer sphere and count the ones that get into the inner sphere (M points). In this case the volume ratio would be M/N. Now, if you generate the points as '(x = rand(), y = rand(), z = rand())' and then filter away ones outside the outer sphere, you'll finally obtain the value of M/N close to 1/8, which is the correct answer. However, if you use the "polar" method described by other posters (two random angles and a random radius), you'll arrive at the value of M/N close to 1/2, which appears to be incorrect. In fact, both answers are correct in their own way. The problem with the second approach is that the metric associated with this method of generating random points is non-Euclidean, and therefore is not what is needed for this task. It is not "incorrect", it is simply incorrectly applied. Surprising effects induced by different choices of metric in geometrical probability play their roles in rather well-known "Bertrand's Paradox" (see http://www.cut-the-knot.org/bertrand.shtml, for example). Once again, the choice of method in general case depends on the requirements of the application. Since you didn't provide any details, it is hard to come up with a concrete advice. -- Best regards, Andrey Tarasevich Jul 23 '05 #21

 P: n/a Andrey Tarasevich wrote: This is an off-topic question. I want to know how to select a random number (or pseudo-random number) that falls between zero and infinity, with a linear probability distribution. But I'm too CS to ask news:sci.math ... ;-) -- Phlip Jul 23 '05 #22

 P: n/a Phlip wrote: Andrey Tarasevich wrote:This is an off-topic question. I want to know how to select a random number (or pseudo-random number) that falls between zero and infinity, with a linear probability distribution. But I'm too CS to ask news:sci.math ... ;-) You could try normalizing the value, then taking a square root, then scaling to the desired interval. Don't quote me on that, though. V Jul 23 '05 #23

 P: n/a On Wed, 8 Feb 2005, Phlip wrote: I want to know how to select a random number (or pseudo-random number) that falls between zero and infinity, with a linear probability distribution. Me too! And if you figure it out, plase let me know how you intend to save your selected number for future reference if, for example, it contains 10^(10^100) digits. Regards, Peter Jansson http://www.jansson.net/ Jul 23 '05 #24

 P: n/a Peter Jansson wrote: Phlip wrote: I want to know how to select a random number (or pseudo-random number) that falls between zero and infinity, with a linear probability distribution. Me too! And if you figure it out, plase let me know how you intend to save your selected number for future reference if, for example, it contains 10^(10^100) digits. Why, I would store it on www.Google.com , of course! -- Phlip Jul 23 '05 #25

### This discussion thread is closed

Replies have been disabled for this discussion. 