- Browsable repository: https://github.com/nklein/grid-generators
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:
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:
: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:
To generate all of the grid points in DIMENSIONS-dimensional space with integer number of steps in the cardinal directions, use the generator:
&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:
: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:
: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:
These parameters relate directly to their namesakes in the GRID-GENERATORS package. So, for example, you could:
(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:
&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:
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:
&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:
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))