This project is part of the @thi.ng/umbrella monorepo.
Z-order curve / Morton encoding, decoding & range extraction for arbitrary dimensions.
References:
- Z-order-curve
- Decoding Morton Codes
- Morton encoding/decoding through bit interleaving
- github.com/JaneliaSciComp/Morton.jl
- Z-Order Indexing for Multifaceted Queries in Amazon DynamoDB
STABLE - used in production
Search or submit any issues for this package
- @thi.ng/grid-iterators - 2D grid iterators w/ multiple orderings
- @thi.ng/geom-accel - n-D spatial indexing data structures with a shared ES6 Map/Set-like API
yarn add @thi.ng/mortonES module import:
<script type="module" src="https://cdn.skypack.dev/@thi.ng/morton"></script>For Node.js REPL:
# with flag only for < v16
node --experimental-repl-await
> const morton = await import("@thi.ng/morton");
Package sizes (gzipped, pre-treeshake): ESM: 2.07 KB
The ZCurve class provides nD encoding/decoding and Z index range
extraction (for a given nD bounding box). The maximum per-component
value range is 32 bits (unsigned!).
Note: All Z indices are encoded as ES
BigInt
and therefore only available in environments where BigInts are already
supported. No polyfill is provided!
TypeScript projects using this class should set their compile target (in
tsconfig.json) to "ESNext" to enable BigInt support.
// create new Z-curve for 3D positions and 16bit value range
const z = new ZCurve(3, 16);
z.encode([60000, 30000, 20000]);
// 67807501328384n
z.decode(67807501328384n);
// [ 60000, 30000, 20000 ]
// optimized z-index iteration for given bounding box (min, max)
[...z.range([2, 2, 0], [3, 6, 1])]
// [
// 24n, 25n, 26n, 27n, 28n,
// 29n, 30n, 31n, 136n, 137n,
// 138n, 139n, 140n, 141n, 142n,
// 143n, 152n, 153n, 156n, 157n
// ]
// or as coordinates
[...z.range([2, 2, 0], [3, 6, 1])].map((i) => z.decode(i));
// [
// [ 2, 2, 0 ], [ 3, 2, 0 ],
// [ 2, 3, 0 ], [ 3, 3, 0 ],
// [ 2, 2, 1 ], [ 3, 2, 1 ],
// [ 2, 3, 1 ], [ 3, 3, 1 ],
// [ 2, 4, 0 ], [ 3, 4, 0 ],
// [ 2, 5, 0 ], [ 3, 5, 0 ],
// [ 2, 4, 1 ], [ 3, 4, 1 ],
// [ 2, 5, 1 ], [ 3, 5, 1 ],
// [ 2, 6, 0 ], [ 3, 6, 0 ],
// [ 2, 6, 1 ], [ 3, 6, 1 ]
// ]import * as m from "@thi.ng/morton";
// unsigned 16 bit coords only
m.mux2(23, 42);
// 2461
m.demux2(2461)
// [ 23, 42 ]
// encoded normalized coords (see source for opts)
m.muxScaled2(0.25, 0.75)
// 2594876074
m.demuxScaled2(m.muxScaled2(0.25, 0.75))
// [ 0.2500038147554742, 0.7499961852445258 ]Karsten Schmidt
If this project contributes to an academic publication, please cite it as:
@misc{thing-morton,
title = "@thi.ng/morton",
author = "Karsten Schmidt",
note = "https://thi.ng/morton",
year = 2015
}© 2015 - 2021 Karsten Schmidt // Apache Software License 2.0