ZBush

A very fast spatial index for 2D points based on a Z-Order space filling curve and BIGMIN search space pruning.

Installation

We publish this project as the package zbush on NPM

``npm install zbush`

`Usage`

`ts const index = new ZBush();

for (const {x, y} of items) { index.add(x, y); }

index.finish();

const foundIds = index.range(minX, minY, maxX, maxY);`

Note: at the moment the x and y coordinates of points added must be of non-negative integral type and fit into 32-bit, i.e. in [0, 2^32-1]. We might relax this constraint in the future.

`How It Works`

We sort 2d points along a Z-order space-filling curve and use an optimization ("BIGMIN") to skip over irrelevant data when walking the curve.

| Z-curve with query bounding box | Z-curve with BIGMIN skipping | |-|-| | ![](./1.jpg) | ![](./2.jpg) |

If you are interested in a high-level overview check out my blog post. The ideas implemented here originated as experiments in tinygraph.org but really go back to the 80s.

For experiments, context, implementation details, and ideas for further improvements - https://github.com/tinygraph/tinygraph/issues/22 - https://github.com/tinygraph/tinygraph/pull/68 - https://github.com/tinygraph/tinygraph/issues/71 - https://github.com/tinygraph/tinygraph/issues/70 - https://github.com/tinygraph/tinygraph/blob/main/tinygraph/tinygraph-zorder.c - https://github.com/tinygraph/tinygraph/blob/main/tinygraph/tinygraph-index.c

Note: The core ideas implemented here are very flexible and allow e.g. to index more dimensions than two, indexing more shapes and not just points, have a fast WebAssembly version, and more. If you come across limitations or have use-cases not covered here, please do open an issue and let us know.

`Similar`

Similar projects for point indices using R-Tree or KD-Tree data structures - https://github.com/mourner/rbush - https://github.com/mourner/kdbush - https://github.com/mourner/flatbush

`Release`

Checklist - [ ] Bump version inpackage.json- [ ] Tag the releasegit tag vx.y.z -a- [ ] Push the taggit push origin vx.y.z`

There is a GitHub Action publishing to the zbush package on NPM with provenance attestation.

License

Distributed under the MIT License (MIT).

Usage

ts
const index = new ZBush();

for (const {x, y} of items) {
  index.add(x, y);
}

index.finish();

const foundIds = index.range(minX, minY, maxX, maxY);

Note: at the moment the x and y coordinates of points added must be of non-negative integral type and fit into 32-bit, i.e. in

[0, 2^32-1]

.
We might relax this constraint in the future.

How It Works

We sort 2d points along a Z-order space-filling curve and use an optimization ("BIGMIN") to skip over irrelevant data when walking the curve.

| Z-curve with query bounding box | Z-curve with BIGMIN skipping |
|-|-|
| ![](./1.jpg) | ![](./2.jpg) |

If you are interested in a high-level overview check out my blog post.
The ideas implemented here originated as experiments in tinygraph.org but really go back to the 80s.

For experiments, context, implementation details, and ideas for further improvements
- https://github.com/tinygraph/tinygraph/issues/22
- https://github.com/tinygraph/tinygraph/pull/68
- https://github.com/tinygraph/tinygraph/issues/71
- https://github.com/tinygraph/tinygraph/issues/70
- https://github.com/tinygraph/tinygraph/blob/main/tinygraph/tinygraph-zorder.c
- https://github.com/tinygraph/tinygraph/blob/main/tinygraph/tinygraph-index.c

Note: The core ideas implemented here are very flexible and allow e.g. to index more dimensions than two, indexing more shapes and not just points, have a fast WebAssembly version, and more.
If you come across limitations or have use-cases not covered here, please do open an issue and let us know.