| 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)))) |