February 21, 2005

Picking points

My biggest problem with this blog is that every time I write something, I want to extend it into a long, rambling essay. I'll try to keep it a little shorter today.

We've all figured out how to pick a random point on the edge of a circle: pick an angle from [0, 2π), then use trig and the radius of the circle to figure out the x and y coordinates.

Contrary to what you might think, picking a point inside the circle at random is harder than just using a random radius. Similarly, it is not easy to pick a point from the surface of a sphere, nor from inside a sphere. MathWorld has good explanations of the problem and the solution for disk point picking and sphere point picking. Combining the two answers to solve the problem of picking a point inside a sphere (aka ball point picking) is an exercise I shall leave to the reader.

The common algorithm for picking points in a sphere is to pick points in the cube around the sphere, then eliminate those points that are too distant from the center. This discards just under half of the points generated, but may still be more efficient than the exact method due to its use of expensive functions. If I weren't trying to keep this short, I would now figure out which one is more efficient and present my results.


Post a Comment

<< Home