Crate space

space intends to define the necessary abstractions and implementations for working with spatial data.

Uses of spatial data structures:

• Point clouds
• k-NN (finding nearest neighborn in N-dimensional space)
• Collision detection
• N-body simulations

This crate will not be 1.0 until it has removed all dependencies on nightly features and const generics are available in stable to allow the abstraction over N-dimensional trees.

Modules

bitmask	Encoding/decoding of Morton Z-curve indices using precomputed bitmasks.
bmi2	Encoding/decoding of Morton Z-curve indices using BMI2 pdep/pext instructions.
lut	Encoding/decoding of Morton Z-curve indices using a look-up table.

Structs

LeveledRegion	This defines a region from [-2n, 2n).
LinearOctree	A linear hashed octree. This has constant time lookup for a given region or morton code.
MortonHash	This is not to be used with anything other than a morton code, as it depends on its unique structure. It is safe to use it with other data, but it wont perform well at all and may eat tons of memory. Use at your own risk.
MortonRegion	Defines a region by dividing finite space into a z-order curve of level and uses the upper bits of morton.
MortonRegionIterator	An Iterator over a MortonRegion that uses a closure to limit the exploration space.
MortonWrapper	This wraps a morton to convey special external trait implementations to it that are specific to mortons.
NullFolder	Null folder that only produces only tuples.
PointerOctree	An octree that uses pointers for internal nodes.

Traits

Folder	Implement this trait to perform a tree fold across the octree.
Morton	Also known as a Z-order encoding, this partitions a bounded space into finite, but localized, linear boxes. This morton code is always encoding 3 dimensional data.

Functions

decode_2d	Decodes an interleaved Morton index for a Z-Curve into two-dimensional coordinates.
decode_3d_high_bits	Decodes the high-bits of b into the coordinates x and y.
decode_3d	Decodes an interleaved Morton index for a Z-Curve into three-dimensional coordinates.
encode_2d	Encode coordinates x and y into an interleaved Morton index for a z-Curve.
encode_3d_high_bits	Encodes the high-bits of x and y into the Morton index v.
encode_3d	Encode coordinates x, y, and z into an interleaved Morton index for a z-Curve.
invalidate_region_cache	Invalidates pieces of a cache when something is changed at this particular morton.
morton_cache	Create a MortonCache.
morton_levels	Generates regions over every level of this morton from the first octant (level 1) to the least significant level (level M::dim_bits()). This does not include the root region (level 0).
morton_map	Create a MortonMap.
morton_set	Create a MortonSet.
region_cache	Create a MortonRegionCache.
region_map	Create a MortonRegionMap.
region_map_difference	Visits the values representing the difference, i.e. the keys that are in primary but not in secondary.
region_set	Create a MortonRegionSet.

Type Definitions

MortonBuildHasher	The BuildHasher for MortonHash.
MortonCache	Use this to map voxels in z-order to arbitrary objects. This uses a custom hasher that is optimized for z-order data locality. This also uses an LRU cache under the hood so memory can be preserved.
MortonMap	Use this to map voxels in z-order to arbitrary objects. This uses a custom hasher that is optimized for z-order data locality.
MortonRegionCache	Use this to map regions defined by a z-order curve on a particular level to arbitrary objects. This uses a custom hasher that is optimized for z-order data locality. This also uses an LRU cache under the hood so memory can be preserved.
MortonRegionMap	Use this to map regions defined by a z-order curve on a particular level to arbitrary objects. This uses a custom hasher that is optimized for z-order data locality.
MortonRegionSet	Use this to have a set of regions defined by a z-order curve on a particular level. This will not exclude subset regions. This uses a custom hasher that is optimized for z-order data locality.
MortonSet	Use this to keep a set of voxels in z-order. This uses a custom hasher that is optimized for z-order data locality.