Crate insides

A compact, high performance space filling curve library for Rust.

This library provides an abstract interface to generalise interactions with space filling curves as well as a morton curve implementation and supporting manipulation methods.

We currently only support Morton Encoding, but the interface will support a Hilbert implementation - and we have plans to include it soon.

Morton Encoding

Morton encoding, also known as a Z-order curve, is a space filling algorithm which maps a multidimensional set of coordinates to one dimension, achieved by interleaving the bit sequence of each coordinate value.

Whilst other encoding methods may exhibit better spatial locality (such as the Hilbert curve), the Morton curve offers excellent CPU performance, since most behaviours can be reduced to a simple set of bitwise operations - making it an ideal choice for applications such and quad trees and octrees.

Examples

use insides::*;
 
// Create a 3D morton location using u16 coordinate indices
// At the moment, we have to specify the number of dimensions twice, sorry!
// (this will change with improvements to Rust const generics)
let location = Morton::<Expand<u16, 3>, 3>::from_coords([1, 2, 3]);
 
assert_eq!(location.index(), 0b110101);
assert_eq!(location.coords(), [1, 2, 3]);

Re-exports

pub use crate::morton::Morton;

Modules

morton

Morton curve implementation

Enums

QueryDirection

Direction to search within an axis when making queries

Traits

CurveCoord

Trait wrapper for coordinates

CurveIndex

Trait wrapper for indices

Neighbours

Provides methods for retrieving adacent locations

Siblings

Provides methods for retrieving adacent locations within a cluster

SpaceFillingCurve

Provides conversion to and from coordinates