#interval-tree #overlap #volume #overlapping #creation #lookup #k-dimensional

kd_interval_tree

Implements a K-dimensional interval tree, for fast interval-overlap lookup. Binary-tree based implementation, i.e. O(log(n)) lookups.

2 releases

0.1.1 Feb 16, 2023
0.1.0 Feb 16, 2023

#1559 in Data structures

MIT license

22KB
453 lines

K-dimensional Interval Tree

This crates implements a K-dimensional interval tree, based on a binary search (with the same complexity w.r.t operations).

Features

  • Creation of the tree from a Vec
  • Overlap / inclusion test
  • Overlapping intervals retrieval
  • Overlapping volume computation

~~ That's all folks ~~

TODOs

  1. Support insertion!
  2. ... and deletion, mutation in general
  3. Make API safer: how to get the desired behavior for the dynamic case?) -> without using more than one trait...
  4. Make API safer: add different overload when "borrowing" is desired, or exact same type is expected.
  5. Real benchmarks...

Dependencies

~150KB