Crate crater

Very Generic Data Structures

Crater provides KD Trees (kdtree::KdTree), minmax heaps (mmheap::MmHeap), and intrusive Fibonacci heaps (fheap::FibHeap) with as much flexibility as possible. For KD Trees, no restrictions are placed on the data besides that points have well defined distance to regions/other points, and regions can be expanded/split. Similarly, minmax heaps accept any comparison function.

To get started quickly, look at cuboid::CuPoint and cuboid::CuRegion and the tests in [cuboid::tests::pointcloud]. This will provide an overview of how to use KD trees with the prebuilt Cartesian points/regions. To associate custom data to points, create structs wrapping cuboid::CuPoint and cuboid::CuRegion which delegate to their KdPoint and KdRegion implementations. To implement KdPoint and KdRegion for arbitrary custom types, continue reading their trait documentation here.

Modules

• cuboid
• fheap
  A fibonacci heap is a type of data structure optimized for use as a priority queue. It is commonly useful in pathfinding algorithms like Dijkstra’s and A*.
• kdtree
• mmheap

Enums

• WalkDecision
  Tree traversal control flow, similar to Rust’s builtin std::ops::ControlFlow enum.

Traits

• KdPoint
  A point in the tree. Types implementing this can contain arbitrary data, to be accessed when the tree is queried by a point + distance, point + count, region, etc. NB: If T: KdPoint, <T as Eq>::eq can be implemented by comparing T::sqdist to T::Distance::zero()
• KdRegion
  A region in the tree, or in space in general. A type implementing this will be tightly coupled to some type implementing KdPoint. For example, the prebuilt cuboid::CuPoint struct represents a point in Cartesian space with Euclidean distance, and the prebuilt cuboid::CuRegion struct represents cuboid regions of space (rectangles in 2D, rectangular prisms in 3D, etc). Regions often represent infinitely many points in space (how many points are in your typical rectangle?). Regions should be able to represent a single point, but the ability to represent an empty region isn’t necessary.

Functions

• get_bounds
  Get the bounding box of a set of points. For cuboid::CuRegion and cuboid::CuPoint, this will be an AABB (Axis Aligned Bounding Box). For general KdRegion, the bounds are not required to be tight