Generting Random Points on the Surface of a Sphere

2015-10-02

This is really more of an (attempted) explanation than an essay. But it is long and I did write it.

I did sort of invent the algorithm myself, but only because I didn't think of looking for one someone else did. Lots of other people invented it first. Here is an attempt at explaining it. If I explain it badly, I am sorry. I am only good at explaining when I can watch people's reactions so I know what they understand. Be warned, most computer algorithms are math at bottom, and this one is no exception.

The code is in C++ using fixed-pipeline (i.e. simple) OpenGL for graphics. This is the simplest way to program graphics I know. It is still much harder than using an image editor or special graphics software, of course, so I don't recommend it for beginners. The University thinks this is 3rd-year stuff. It doesn't actually need anything from 2nd year, but maybe just the programming experience helps.

The circle is basically a hollow ball. There a 100,000 points on the surface (some overlap) and just draw 1 pixel for each of them. The colours are just the points in space. The ball is in 3D, so we have X, Y, and Z for a point instead of just X and Y like on graphs. Conveniently, we also need 3 numbers (red, green, and blue) for a colour. So I just used X as red, Y as green, and Z as blue. Now my ball has pretty colours.

The tricky point is putting the points on the surface of the sphere. Just getting them somewhere on the surface is easy (e.g. put them all at the same place). However, I want them spaced out equally.

To do this, I break the problem into 2 parts. If we think of our sphere as like the Earth, the two parts are figuring out our longitude and latitude. As it turns out, longitude is easy. We just pick a random number between 0 and 360 degrees and go that far around. At the end. For now, we will just remember our longitude until we need it.

As for latitude, I used to have a complex formula involving numerous trigonometric functions (e.g. sine). However, I recently discovered that I don't need most of that. Instead, I can just pick a vertical position at random and use that. I don't mean a latitude angle like 45 degrees north; just pick how far up or down the image it should be. For reasons explained below, we use -1 as the bottom, 0 as the middle, and +1 as the top. It turns out that latitudes just make straight lines across the picture, and that there are supposed to be the same number of dots on each line (still counting overlapping ones).

This was actually such a surprise that I wrote this program to make sure it worked. It seemed so odd that I didn't need the latitude, but I guess I don't.

Next, we need to find out how wide (in the picture) our sphere is at the latitude we picked. We do this by imagining a triangle our our circle (yes, I know it used to be a sphere, but its too hard to draw on spheres). One triangle corner is at the circle center. Another is on the edge. The third has a right angle and is wherever it needs to be above or below the circle center so that it lines up with the edge corner and we get a proper triangle. Our latitude is the height (a) of this triangle. The triangle width (b) is how far sideways we want out point, and what we are trying to find. The hypotenuse (c) is the size of the sphere (it goes from the middle to the edge).

We can find b with the Pythagorean formula (a^2 + b^2 = c^2). To simplify things, I decide that my sphere is exactly 1 whatever-its-measured-in in size, so c always 1. c^2 is also always 1, because 1^2 = 1. If we remember from above, our point height (a) is already in the same units: 0 in the middle and 1 at the edge. The bottom edge is -1, but it's the same idea. If we substitute this in our equation, it becomes (latitude^2 + b^2 = 1^2). Solving the equation gives us b = sqrt(1 - latitude^2).

So now we know how far up and down our point is and how far sideways. Sadly, we are not done yet. If we use the formula we have so far, we just get a semicircle. This is because we had to flatten out our sphere to make the triangle work.

The good news it that turning a semi-circle into a sphere is easy. All we need to do is spin it along its flat side (we hold the two corners) and it will look like a sphere again. Here is where we need the longitude number from the beginning. Overall, we need X, Y, and Z coordinates. Z is just up and down, but we still need X and Y. Luckily there are standard formulas for moving a point around a circle (longitude). They are X = cos(angle) * radius and Y = sin(angle) * radius. In our case, the angle is our longitude. The radius is just the size of the circle, and we already said that that is always 1. Multiplying by 1 does nothing (I like 1), so we can just ignore it. Out formulas are now X = cos(longitude) and Y = sin(longitude).

So we now have our X, Y, and Z numbers. To actually draw the point, we need to do 2 things. First, we give OpenGL our three numbers and say that they are a colour (red, green, blue). Second, we give it the same three numbers agian, only this time we say they are the position of the point. Then OpenGL and the graphics card take care of actually drawing the point on the screen. We don't have to worry about how.

Finally, we tell the computer to do the whole thing 100,000 times. A modern computer can do that in a fraction of a second, so we don't have to wait too long. I also tried a million points, but it was too slow. When the computer has drawn all the points, I take a screenshot of the image, crop it, and post it to Facebook. And we're finally done.

Here is the actual C++ code for calculating the point. I changed the variable names to match my explanation. 
{
	double longitude = randomNumberFrom0to1() * TWO_PI;
	double z = randomNumberFromMinus1toPlus1();
	double radius_at_latitude = sqrt(1.0 - z * z);
	double x = radius_at_latitude * cos(longitude);
	double y = radius_at_latitude * sin(longitude);
}


Back to essays page
Back to home page