;"sierpinski.scm" Hash function for 2d data which preserves nearness.
;From: jjb@isye.gatech.edu (John Bartholdi)
;
; This code is in the public domain.
;Date: Fri, 6 May 94 13:22:34 -0500
;@
(define MAKE-SIERPINSKI-INDEXER
(lambda (max-coordinate)
(lambda (x y)
(if (not (and (<= 0 x max-coordinate)
(<= 0 y max-coordinate)))
(slib:error 'sierpinski-index
"Coordinate exceeds specified maximum.")
;
; The following two mutually recursive procedures
; correspond to to partitioning successive triangles
; into two sub-triangles, adjusting the index according
; to which sub-triangle (x,y) lies in, then rescaling
; and possibly rotating to continue the recursive
; decomposition:
;
(letrec ((loopA
(lambda (resolution x y index)
(cond ((zero? resolution) index)
(else
(let ((finer-index (+ index index)))
(if (> (+ x y) max-coordinate)
;
; In the upper sub-triangle:
(loopB resolution
(- max-coordinate y)
x
(+ 1 finer-index))
;
; In the lower sub-triangle:
(loopB resolution
x
y
finer-index)))))))
(loopB
(lambda (resolution x y index)
(let ((new-x (+ x x))
(new-y (+ y y))
(finer-index (+ index index)))
(if (> new-y max-coordinate)
;
; In the upper sub-triangle:
(loopA (quotient resolution 2)
(- new-y max-coordinate)
(- max-coordinate new-x)
(+ finer-index 1))
;
; In the lower sub-triangle:
(loopA (quotient resolution 2)
new-x
new-y
finer-index))))))
(if (<= x y)
;
; Point in NW triangle of initial square:
(loopA max-coordinate
x
y
0)
;
; Else point in SE triangle of initial square
; so translate point and increase index:
(loopA max-coordinate
(- max-coordinate x)
(- max-coordinate y) 1)))))))