Grid-Generators October 29th, 2015
Patrick Stein

This package provides functions useful for generating the points in a grid. There are three generator constructors. Each returns a function. Upon successive calls to the returned function, it returns two values: the coordinates of the next point in the grid (or NIL if the grid has been exhausted) and T if a grid point was returned as the first value (or NIL if the grid has been exhausted).

Generating Points In A Cube

To generate points in a cube, use the generator:

(make-grid-generator TO &KEY FROM BY)

Given a list of REAL numbers TO and a list of REAL numbers FROM and a list of real numbers BY (all of length N), return a function that on successive calls will return points on an N-dimensional grid starting at FROM and incrementing by BY.

FROM defaults to all zeros if not specified.

BY defaults to all ones if not specified.

All of the BY numbers must be positive.

All of the FROM numbers must be less than or equal to their corresponding TO numbers.

For example:

(loop :with generator := (make-grid-generator '(2 2) :by '(1 2))
    :for v := (funcall generator)
    :while v
    :collecting v)

=> ((0 0) (1 0) (2 0) (0 2) (1 2) (2 2))

Note: This function makes no guarantees about the order in which the grid points will be covered. It only guarantees that they all will be covered.

Generating Points By Taxicab Distance

The taxicab distance from the origin to some point P is just the sum of the absolute values of its coordinates. This differs from the Euclidean distance. Given a list of coordinates P for the point, you can calculate the taxicab distance from the origin to that point with:

(taxicab-distance P)

To generate all of the grid points in DIMENSIONS-dimensional space with integer number of steps in the cardinal directions, use the generator:

(make-taxicab-generator DIMENSIONS
                        &KEY (MINIMUM-STEPS 0)
                             MAXIMUM-STEPS
                             SCALE
                             OFFSET)

Given a positive integer number of DIMENSIONS, a non-negative integer MINIMUM-STEPS, and a non-negative (or null) MAXIMUM-STEPS, return a generator which, on successive calls, returns the points in a taxicab-annulus with inner-radius MINIMUM-STEPS and outer-radius MAXIMUM-STEPS.

MINIMUM-STEPS must be less than or equal to MAXIMUM-STEPS (if MAXIMUM-STEPS is non-null).

If SCALE is specified, it must be either a list of length DIMENSIONS of NUMBERs or a single NUMBER. The taxicab coordinates will be scaled respectively by these amounts (or all by this amount if it is a single number) before they are returned.

If OFFSET is specified, it must be a list of length DIMENSIONS of NUMBERs. This offset will be added to the taxicab coordinates (after they are scaled and) before they are returned.

If MAXIMUM-STEPS is null, the iteration continues on indefinitely.

For example:

(loop :with generator = (make-taxicab-generator 2
                                                :maximum-steps 2
                                                :scale 2
                                                :offset '(1 0))
    :for v := (funcall generator)
    :while v
    :collecting v)

=> ((1 0)
    (-1 0) (1 -2) (1 2) (3 0)
    (-3 0) (-1 -2) (-1 2) (1 -4) (1 4) (3 -2) (3 2) (5 0))

Note: When the scaling is not specified or is constant, this function guarantees that it will generate all of the points at the minimum steps before moving on to the next greater number of steps, etc. It does not, however, guarantee the order in which it will generate the points at a given number of steps away, just that it will generate all of the points at each number of steps.

Generating Points In An Arbitrary Lattice

Given a list of BASIS-VECTORS (each a list of NUMBERs with all lists the same length), a non-negative integer MINIMUM-STEPS, and a non-negative (or null) MAXIMUM-STEPS, return a generator which, on successive calls, returns points on the scaled lattice centered at the offset with the given basis vectors starting with those points which can be reached with the MINIMUM-STEPS and proceeding through more and more steps until those points at MAXIMUM-STEPS have all been enumerated.

If SCALE is specified, it must be either a list of the same length as the basis vectors of NUMBERs or a single NUMBER. The point’s coordinates will be scaled by this amount before they are returned.

If OFFSET is specified, it must be a list of same length as the basis vectors of NUMBERs. This offset will be added to the coordinates (after they are scaled and) before they are returned.

MINIMUM-STEPS must be less than or equal to MAXIMUM-STEPS (if MAXIMUM-STEPS is non-null).

If MAXIMUM-STEPS is null, the iteration continues on indefinitely.

For example:

(loop :with generator = (make-lattice-generator '((#C(1 0)) (#C(0 1)))
                                                :maximum-steps 1
                                                :scale 2
                                                :offset '(#C(1/2 1/2)))
    :for v := (funcall generator)
    :while v
    :collecting (first v))

=> (#C(1/2 1/2) #C(-3/2 1/2) #C(1/2 -3/2) #C(1/2 5/2) #C(5/2 1/2))

GRID-ITERATE Package

This package provides ITERATE drivers for the generators in the GRID-GENERATORS package.

Iterating Points In A Cube

The iterate clause for generating the points on the grid is:

(ITERATE:FOR var ON-GRID-TO to &optional FROM from BY by)

These parameters relate directly to their namesakes in the GRID-GENERATORS package. So, for example, you could:

(iterate:iterate (iterate:for v on-grid-to '(2 2) by '(1 2))
                 (iterate:collecting v))

=> ((0 0) (1 0) (2 0) (0 2) (1 2) (2 2))

Iterating Points By Taxicab Distance

The iterate clause for generating points by taxicab distance is:

(ITERATE:FOR var BY-TAXICAB-STEPS-IN-DIMENSIONS dimensions
         &optional MINIMUM-STEPS min-steps
                   MAXIMUM-STEPS max-steps
                   WITH-SCALE scale
                   WITH-OFFSET offset)

These parameters relate directly to their namesakes in the GRID-GENERATORS package. So, for example, you could:

(iterate:iterate (iterate:for v by-taxicab-steps-in-dimensions 2
                           maximum-steps 2
                           with-scale 2
                           with-offset '(1 0))
                 (iterate:collect v))

=> ((1 0)
    (-1 0) (1 -2) (1 2) (3 0)
    (-3 0) (-1 -2) (-1 2) (1 -4) (1 4) (3 -2) (3 2) (5 0))

Iterating Points In An Arbitrary Lattice

The iterate clause for generating points in an arbitrary lattice is:

(ITERATE:FOR var BY-LATTICE-STEPS basis-vectors
         &optional MINIMUM-STEPS min-steps
                   MAXIMUM-STEPS max-steps
                   WITH-SCALE scale
                   WITH-OFFSET offset)

These parameters relate directly to their namesakes in the GRID-GENERATORS package. So, for example, you could:

(iterate:iterate (iterate:for v by-lattice-steps '((1 -1) (1 1))
                           maximum-steps 2
                           with-scale 2
                           with-offset '(1 0))
                 (iterate:collect v))

=> ((1 0)
    (-1 2) (-1 -2) (3 2) (3 -2)
    (-3 4) (-3 0) (1 4) (-3 -4) (5 4) (1 -4) (5 0) (5 -4))

Grid-Generators v0.4.20151016 (and List-Types v0.4.20151029) Released October 29th, 2015
Patrick Stein

Two new Common Lisp libraries released: GRID-GENERATORS and LIST-TYPES. GRID-GENERATORS and GRID-ITERATE packages I often find myself wanting to iterate over the points in a rectangular region of a grid in an arbitrary number of dimensions. If my grid is only one-dimensional or two-dimensional then I often just write nested loops to traverse the points […]

Updates In Email

Email:

l