random points generation on a sphere
johnnykao
1. Random points generation evenly on a sphere
2. Random points generation near a point on a sphere (This means
I want some random points near a fixed point, these random points
should generated by the fixed point)
Did anyone would give me some information(algorithm is more welcome)
about this subject.
Thanks a lot!!
Dave Seaman
Here are four methods for generating uniformly distributed points on a unit
sphere:
(1) The normal-deviate method. Choose x, y, and z, each
normally distributed with mean 0 and variance 1. (Actually, the
variance does not matter, provided it remains fixed.) Normalize
the result to obtain a uniform density on the unit sphere.
This method also generalizes nicely to n dimensions. It works
because the vector chosen (before normalization) has a density
that depends only on the distance from the origin. The method is
mentioned in Knuth, _The Art of Computer Programming_, vol. 2,
3rd. ed., section 3.4.1.E.6.
(2) The hypercube rejection method. Choose x, y, and z, uniformly
distributed on [-1,1]. Compute s = x^2 + y^2 + z^2. If s > 1,
reject the triplet and start over. Once you have an acceptable
vector, normalize it to obtain a point on the unit sphere.
This method also generalizes to n dimensions, but as the dimension
increases the probability of rejection becomes high and many random
numbers are wasted.
(3) The trig method. This method works only in 3-space, but it is
very fast. It depends on the slightly counterintuitive fact (see
proof below) that each of the three coordinates of a uniformly
distributed point on S^2 is uniformly distributed on [-1,1] (but
the three are not independent, obviously). Therefore, it
suffices to choose one axis (Z, say) and generate a uniformly
distributed value on that axis. This constrains the chosen point
to lie on a circle parallel to the X-Y plane, and the obvious
trig method may be used to obtain the remaining coordinates.
(a) Choose z uniformly distributed in [-1,1].
(b) Choose t uniformly distributed on [0, 2*pi).
(c) Let r = sqrt(1-z^2).
(d) Let x = r * cos(t).
(e) Let y = r * sin(t).
(4) A variation of method (3) that doesn't use trig may be found in
Knuth, _loc. cit._. The method is equivalent to the following:
(a) Choose u and v uniformly distributed on [-1,1].
(b) Let s = u^2 + v^2.
(c) If s > 1, return to step (a).
(d) Let a = 2 * sqrt(1-s).
(e) The desired point is (a*u, a*v, 2*s-1).
This method uses two-dimensional rejection, which gives a higher
probability of acceptance compared to algorithm (2) in three
dimensions. I group this with the trig method because both
depend on the fact that the projection on any axis is uniformly
distributed on [-1,1], and therefore both methods are limited to
use on S^2.
The IMSL subroutine RNNOA/DRNNOA may be used to generate normally
distributed values for method (1). There is also an IMSL subroutine
RNSPH/DRNSPH that solves the problem directly by using method (4) in the
3-D case and a variation of this in 4-D. In higher dimensions, the
subroutine uses method (1). In my tests on IBM RS/6000, Sun SPARC 5, and
Apple Macintosh 604e, G3, and G4 platforms, all using the IMSL routines,
I have found method (3) to be the fastest for the 3-D case.
--------------------------------------------------------------------
Here is a proof of correctness for the fact that the z-coordinate is
uniformly distributed. The proof also works for the x- and y-
coordinates, but note that this works only in 3-space.
The area of a surface of revolution in 3-space is given by
A = 2 * pi * int_a^b f(x) * sqrt(1 + [f'(x}]^2) dx
Consider a zone of a sphere of radius R. Since we are integrating in the
z direction, we have
f(z) = sqrt(R^2 - z^2)
f'(z) = -z / sqrt(R^2-z^2)
1 + [f'(z)]^2 = r^2 / (R^2-z^2)
A = 2 * pi * int_a^b sqrt(R^2-z^2) * R/sqrt(R^2-z^2) dz
= 2 * pi * R int_a^b dz
= 2 * pi * R * (b-a)
= 2 * pi * R * h,
where h = b-a is the vertical height of the zone. Notice how the
integrand reduces to a constant. The density is therefore uniform.
--------------------------------------------------------------------
If you want to generate a random point near the South Pole, you can adapt
method (3) by replacing the interval [-1,1] in step (a) by an interval
[-1,h] where h is the sin of the desired maximum latitude.
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
The Last Danish Pastry
news:b34bvv$nof$1...@mozo.cc.purdue.edu...
>[snip]
> Here is a proof of correctness for the fact that the z-coordinate is
> uniformly distributed. The proof also works for the x- and y-
> coordinates, but note that this works only in 3-space.
>
> The area of a surface of revolution in 3-space is given by
>
> A = 2 * pi * int_a^b f(x) * sqrt(1 + [f'(x}]^2) dx
>
> Consider a zone of a sphere of radius R. Since we are integrating in the
> z direction, we have
>
> f(z) = sqrt(R^2 - z^2)
> f'(z) = -z / sqrt(R^2-z^2)
>
> 1 + [f'(z)]^2 = r^2 / (R^2-z^2)
>
> A = 2 * pi * int_a^b sqrt(R^2-z^2) * R/sqrt(R^2-z^2) dz
>
> = 2 * pi * R int_a^b dz
>
> = 2 * pi * R * (b-a)
>
> = 2 * pi * R * h,
>
> where h = b-a is the vertical height of the zone. Notice how the
> integrand reduces to a constant. The density is therefore uniform.
>[snip]
As Dave probably knows, the above theorem is known as Archimedes' Hatbox.
See the first article at
http://westview.tdsb.on.ca/Mathematics/reference.topics.html
for some words by John Conway on the subject.
--
Clive Tooth
http://www.clivetooth.dk