Expand description
§Kiddo
A high-performance, flexible, ergonomic k-d tree library.
Possibly the fastest k-d tree library in the world? See for yourself.
Kiddo provides:
- A standard floating-point k-d tree, exposed as
kiddo::KdTree
, for when you may need to add or remove points to the tree after the initial construction / deserialization - An
ImmutableKdTree
with performance and space advantages over the standard k-d tree, for situations where the tree does not need to be modified after creation - integer / fixed point support via the
fixed
crate; f16
support via thehalf
crate;- instant zero-copy deserialization and serialisation via
Rkyv
(Serde
still available).
Kiddo is ideal for superfast spatial / geospatial lookups and nearest-neighbour / KNN queries for low-ish numbers of dimensions, where you want to ask questions such as:
- Find the nearest_n item(s) to a query point, ordered by distance;
- Find all items within a specified radius of a query point;
- Find the “best” n item(s) within a specified distance of a query point, for some definition of “best”, For example, “give me the 5 largest settlements within 50km of a given point, ordered by descending population”, or “the 5 brightest stars within a degree of a point on the sky, ordered by brightest first”.
§Installation
Add kiddo
to Cargo.toml
[dependencies]
kiddo = "5.2.0"
§Usage
use kiddo::KdTree;
use kiddo::SquaredEuclidean;
use kiddo::NearestNeighbour;
let entries = vec![
[0f64, 0f64],
[1f64, 1f64],
[2f64, 2f64],
[3f64, 3f64]
];
// use the kiddo::KdTree type to get up and running quickly with default settings
let mut kdtree: KdTree<_, 2> = (&entries).into();
// How many items are in tree?
assert_eq!(kdtree.size(), 4);
// find the nearest item to [0f64, 0f64].
// returns a tuple of (dist, index)
assert_eq!(
kdtree.nearest_one::<SquaredEuclidean>(&[0f64, 0f64]),
NearestNeighbour { distance: 0f64, item: 0 }
);
// find the nearest 3 items to [0f64, 0f64], and collect into a `Vec`
assert_eq!(
kdtree.nearest_n::<SquaredEuclidean>(&[0f64, 0f64], 3),
vec![NearestNeighbour { distance: 0f64, item: 0 }, NearestNeighbour { distance: 2f64, item: 1 }, NearestNeighbour { distance: 8f64, item: 2 }]
);
See the examples documentation for some more in-depth examples.
§Optional Features
The Kiddo crate exposes the following features. Any labelled as (NIGHTLY) are not available on stable
Rust as they require some unstable features. You’ll need to build with nightly
in order to user them.
- serde - serialization / deserialization via
Serde
- rkyv - zero-copy serialization / deserialization via
Rkyv
version 0.7.x - rkyv_08 - zero-copy serialization / deserialization via
Rkyv
version 0.8.x simd
(NIGHTLY) - enables some handwritten SIMD and pre-fetch intrinsics code withinImmutableKdTree
that may improve performance (currently only on nearest_one withf64
)fixed
- enables usage ofkiddo::fixed::KdTree
for use with thefixed
library’s fixed-point number types
NOTE: Support for rkyv 0.7 is now deprecated and will be removed in Kiddo v6.
Re-exports§
pub use float::distance::Manhattan;
pub use float::distance::SquaredEuclidean;
Modules§
- fixed
- Fixed point k-d tree, for use when the co-ordinates of the points being stored in the tree
are fixed point or integers.
u8
,u16
,u32
, andu64
based fixed-point / integers are supported via the Fixed crate, egFixedU16<U14>
for a 16-bit fixed point number with 14 bits after the decimal point. - float
- Floating point k-d tree, for use when the co-ordinates of the points being stored in the tree
are floats.
f64
orf32
are the types that are supported for use as co-ordinates, orf16
when used with thehalf
crate - immutable
- Immutable k-d trees (faster and smaller, but cannot be modified after construction).
- traits
- Definitions and implementations for some traits that are common between the
float
,immutable
andfixed
modules
Structs§
- Best
Neighbour - Represents an entry in the results of a “best” query, with
distance
being the distance of this particular item from the query point, anditem
being the stored item index that was found as part of the query. - Nearest
Neighbour - Represents an entry in the results of a nearest neighbour query, with
distance
being the distance of this particular item from the query point, anditem
being the stored item index that was found as part of the query. - Within
Unsorted Iter - Iterator object returned by within_unsorted_iter
Type Aliases§
- Immutable
KdTree - An immutable floating-point k-d tree with default parameters.
- KdTree
- A floating-point k-d tree with default parameters.