!@thi.ng/grid-iterators

!npm downloads

> [!NOTE]
> This is one of 214 standalone projects, maintained as part
> of the @thi.ng/umbrella monorepo
> and anti-framework.
>
> 🚀 Please help me to work full-time on these projects by sponsoring me on
> GitHub. Thank you! ❤️

- About
- Columns
- Diagonal (45 degrees)
- Diagonal with configurable slope
- Hilbert curve
- Interleave columns
- Interleave rows
- Random
- Rows
- Outward spiral
- Z-curve
- Zigzag columns
- Zigzag diagonal
- Zigzag rows
- Mirror symmetries & arbitrary coordinate transformations
- Flood filling
- Shape iterators
- Status
- Related packages
- Installation
- Dependencies
- Usage examples
- API
- Authors
- License

About

2D grid and shape iterators w/ multiple orderings.

Provides the altogether 25 following orderings (excluding symmetries) to
generate grid coordinates, including iterators for shape rasterization, drawing,
clipping, filling, processing in general:

$3

!anim

Source

Also see the filtered version
columnEnds2d(),
which only includes the end points of each column.

$3

!anim

Source

Also see the filtered version
diagonalEnds2d(),
which only includes the end points of the diagonals.

$3

!anim
!anim

Source

$3

!anim

Source

$3

!anim

Source

Supports custom strides... example uses step = 4

$3

!anim

Source

Supports custom strides... example uses step = 4

$3

!anim

Source

Supports custom PRNG implementations via IRandom interface defined in
@thi.ng/random

$3

!anim

Source

Also see the filtered version
rowEnds2d(),
which only includes the end points of each row.

$3

!anim

Source

$3

!anim

Source

$3

!anim

Source

$3

!anim

Source

$3

!anim

Source

Some functions have been ported from Christopher
Kulla's Java-based Sunflow
renderer.

For more basic 2D/3D grid iteration, also see range2d() & range3d()
in
@thi.ng/transducers.

$3

All of the above mentioned grid iterators support point (grid coordinate)
transformations to create variations of their base orderings. The package
provides the flipX, flipY and flipXY preset transforms to mirror one or
both axes, but custom transforms can be easily implemented via the same
underlying mechanism. These transforms can be specified via the tx option
passed to the iterators (see code example further below).

$3

The floodFill() iterator can be used to iterate arbitrary 2D grids using an
user-provided predicate function. The function recursively explores (in a
row-major manner) the space in the [0,0]..(width,height) interval, starting at
given x,y and continues as long given predicate function returns a truthy
value. Any eligible 90-degree connected regions will be found and iterated
recursively. The predicate function is used to select eligible grid cells
(e.g. "pixels" of sorts).

``ts
import { floodFill } from "@thi.ng/grid-iterators";

// source "image"
const img = [
"█", " ", " ", " ", "█",
"█", " ", "█", " ", " ",
" ", " ", "█", " ", "█",
" ", "█", "█", " ", " ",
" ", " ", " ", "█", "█",
];

// flood fill iterator from point (1,0)
// only accept " " as source pixel value
// image size is 5x5
const region = floodFill((x, y) => img[x + y * 5] === " ", 1, 0, 5, 5);

// label filled pixels using increasing ASCII values
let ascii = 65; // "A"
for(let [x,y] of region) img[x + y * 5] = String.fromCharCode(ascii++);

// result image showing fill order
img
// [
// "█", "A", "B", "C", "█",
// "█", "I", "█", "D", "E",
// "K", "J", "█", "F", "█",
// "L", "█", "█", "G", "H",
// "M", "N", "O", "█", "█"
// ]
`

$3

Additionally, the following shape iterators are available, all also with
optional clipping:

- circle (Bresenham)
- hline
- vline
- line (Bresenham)

Status

STABLE - used in production

Search or submit any issues for this package

Related packages

- @thi.ng/morton - Z-order curve / Morton encoding, decoding & range extraction for arbitrary dimensions
- @thi.ng/rasterize - Headless 2D shape drawing, filling & rasterization for arbitrary targets/purposes (no canvas required)
- @thi.ng/transducers - Collection of ~170 lightweight, composable transducers, reducers, generators, iterators for functional data transformations

Installation

`bash
yarn add @thi.ng/grid-iterators
`

ESM import:

`ts
import * as gi from "@thi.ng/grid-iterators";
`

Browser ESM import:

`html

`

JSDelivr documentation

For Node.js REPL:

`js
const gi = await import("@thi.ng/grid-iterators");
`

Package sizes (brotli'd, pre-treeshake): ESM: 2.67 KB

Dependencies

- @thi.ng/api
- @thi.ng/arrays
- @thi.ng/binary
- @thi.ng/bitfield
- @thi.ng/errors
- @thi.ng/morton
- @thi.ng/random
- @thi.ng/transducers

Note: @thi.ng/api is in _most_ cases a type-only import (not used at runtime)

Usage examples

Three projects in this repo's
/examples
directory are using this package:

| Screenshot | Description | Live demo | Source |
|:-----------------------------------------------------------------------------------------------------------------------------------|:-------------------------------------------------------|:------------------------------------------------------------------|:-----------------------------------------------------------------------------------------------|
| | Visualization of different grid iterator strategies | Demo | Source |
| | Generating pure CSS image transitions | Demo | Source |
| | Multi-layer vectorization & dithering of bitmap images | Demo | Source |

API

Generated API docs

`ts
import * as gi from "@thi.ng/grid-iterators";

[...gi.zigzagRows2d({ cols: 4, rows: 4 })]

// [
// [ 0, 0 ], [ 1, 0 ], [ 2, 0 ], [ 3, 0 ],
// [ 3, 1 ], [ 2, 1 ], [ 1, 1 ], [ 0, 1 ],
// [ 0, 2 ], [ 1, 2 ], [ 2, 2 ], [ 3, 2 ],
// [ 3, 3 ], [ 2, 3 ], [ 1, 3 ], [ 0, 3 ]
// ]

// with applied horizontal mirroring
// also, if rows is missing, it defaults to same value as cols
[...gi.zigzagRows2d({ cols: 4, tx: gi.flipX })]
// [
// [ 3, 0 ], [ 2, 0 ], [ 1, 0 ], [ 0, 0 ],
// [ 0, 1 ], [ 1, 1 ], [ 2, 1 ], [ 3, 1 ],
// [ 3, 2 ], [ 2, 2 ], [ 1, 2 ], [ 0, 2 ],
// [ 0, 3 ], [ 1, 3 ], [ 2, 3 ], [ 3, 3 ]
// ]
`

Authors

- Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

`bibtex
@misc{thing-grid-iterators,
title = "@thi.ng/grid-iterators",
author = "Karsten Schmidt",
note = "https://thi.ng/grid-iterators",
year = 2019
}
``

License

© 2019 - 2026 Karsten Schmidt // Apache License 2.0