Previous: Peano Space-Filling Curve, Up: Space-Filling Curves


7.2.7.6 Sierpinski Curve

(require 'sierpinski)

— Function: make-sierpinski-indexer max-coordinate

Returns a procedure (eg hash-function) of 2 numeric arguments which preserves nearness in its mapping from NxN to N.

max-coordinate is the maximum coordinate (a positive integer) of a population of points. The returned procedures is a function that takes the x and y coordinates of a point, (non-negative integers) and returns an integer corresponding to the relative position of that point along a Sierpinski curve. (You can think of this as computing a (pseudo-) inverse of the Sierpinski spacefilling curve.)

Example use: Make an indexer (hash-function) for integer points lying in square of integer grid points [0,99]x[0,99]:

          (define space-key (make-sierpinski-indexer 100))

Now let's compute the index of some points:

          (space-key 24 78)               ⇒ 9206
          (space-key 23 80)               ⇒ 9172

Note that locations (24, 78) and (23, 80) are near in index and therefore, because the Sierpinski spacefilling curve is continuous, we know they must also be near in the plane. Nearness in the plane does not, however, necessarily correspond to nearness in index, although it tends to be so.

Example applications: