- 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 NUMBER
s 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 NUMBER
s. 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 NUMBER
s 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 NUMBER
s 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 NUMBER
s. 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))