Debian Codegraph @

lib/srfi/194/sphere.scm

raw
1 ;;;
2 ;;; Grafted from srfi-194 reference implementation
3 ;;; Original code by Arvydas Silankas
4 ;;;
5
6 (define-module srfi.194.sphere
7 (use scheme.vector)
8 (use srfi.194)
9 (export make-sphere-generator
10 make-ellipsoid-generator
11 make-ball-generator)
12 )
13 (select-module srfi.194.sphere)
14
15 ;
16 ; sphere.scm
17 ; Uniform distributions on a sphere, and a ball.
18 ; Submitted for inclusion in srfi-194
19 ;
20 ; Algorithm based on BoxMeuller as described in
21 ; http://extremelearning.com.au/how-to-generate-uniformly-random-points-on-n-spheres-and-n-balls/
22 ;
23
24 ; make-sphere-generator N - return a generator of points uniformly
25 ; distributed on an N-dimensional sphere.
26 ; This implements the BoxMeuller algorithm, that is, of normalizing
27 ; N+1 Gaussian random variables.
28 (define (make-sphere-generator arg)
29 (cond
30 ((integer? arg) (make-ellipsoid-generator* (make-vector (+ 1 arg) 1.0)))
31 (else (error "expected argument to be an integer dimension"))))
32
33 (define (make-ellipsoid-generator arg)
34 (cond
35 ((vector? arg) (make-ellipsoid-generator* arg))
36 (else (error "expected argument to be a vector of axis lengths"))))
37
38 ; -----------------------------------------------
39 ; Generator of points uniformly distributed on an N-dimensional ellipsoid.
40 ;
41 ; The `axes` should be a vector of floats, specifying the axes of the
42 ; ellipsoid. The algorithm used is an accept/reject sampling algo,
43 ; wherein the acceptance rate is proportional to the measure of a
44 ; surface element on the ellipsoid. The measure is straight-forward to
45 ; arrive at, and the 3D case is described by `mercio` in detail at
46 ; https://math.stackexchange.com/questions/973101/how-to-generate-points-uniformly-distributed-on-the-surface-of-an-ellipsoid
47 ;
48 ; Note that sampling means that performance goes as
49 ; O(B/A x C/A x D/A x ...) where `A` is the shorest axis,
50 ; and `B`, `C`, `D`, ... are the other axes. Maximum performance
51 ; achieved on spheres.
52 ;
53 (define (make-ellipsoid-generator* axes)
54
55 ; A vector of normal gaussian generators
56 (define gaussg-vec
57 (make-vector (vector-length axes) (make-normal-generator 0 1)))
58
59 ; Banach l2-norm of a vector
60 (define (l2-norm VEC)
61 (sqrt (vector-fold
62 (lambda (sum x) (+ sum (* x x)))
63 0
64 VEC)))
65
66 ; Generate one point on a sphere
67 (define (sph)
68 ; Sample a point
69 (define point
70 (vector-map (lambda (gaussg) (gaussg)) gaussg-vec))
71 ; Project it to the unit sphere (make it unit length)
72 (define norm (/ 1.0 (l2-norm point)))
73 (vector-map (lambda (x) (* x norm)) point))
74
75 ; Distance from origin to the surface of the
76 ; ellipsoid along direction RAY.
77 (define (ellipsoid-dist RAY)
78 (sqrt (vector-fold
79 (lambda (sum x a) (+ sum (/ (* x x) (* a a))))
80 0 RAY axes)))
81
82 ; Find the shortest axis.
83 (define minor
84 (vector-fold
85 (lambda (mino l) (if (< l mino) l mino))
86 1e308 axes))
87
88 ; Uniform generator [0,1)
89 (define uni (make-random-real-generator 0.0 1.0))
90
91 ; Return #t if the POINT can be kept; else must resample.
92 (define (keep POINT)
93 (< (uni) (* minor (ellipsoid-dist POINT))))
94
95 ; Sample until a good point is found. The returned sample is a
96 ; vector of unit length (we already normed up above).
97 (define (sample)
98 (define vect (sph))
99 (if (keep vect) vect (sample)))
100
101 (lambda ()
102 ; Find a good point, and rescale to ellipsoid.
103 (vector-map
104 (lambda (x a) (* x a)) (sample) axes))
105 )
106
107 ; -----------------------------------------------
108 ; make-ball-generator N - return a generator of points uniformly
109 ; distributed inside an N-dimensional ball.
110 ; This implements the Harman-Lacko-Voelker Dropped Coordinate method.
111 (define (make-ball-generator arg)
112 (define dim-sizes
113 (cond
114 ((integer? arg) (make-vector (+ 2 arg) 1.0))
115 ((vector? arg) (vector-append arg (vector 1.0 1.0)))
116 (else (error "expected argument to either be a number (dimension), or vector (axis length for the dimensions)"))))
117 (define N (- (vector-length dim-sizes) 2))
118 (define sphereg (make-sphere-generator (+ N 2)))
119 ; Create a vector of N+2 values, and drop the last two.
120 ; (The sphere already added one, so we only add one more)
121 (lambda ()
122 (vector-map
123 (lambda (el dim-size _) (* el dim-size))
124 (sphereg)
125 dim-sizes
126 (make-vector N #f))))