[−][src]Crate quadtree_rs
A point/region Quadtree with support for overlapping regions.
Quick Start
use quadtree_rs::{area::AreaBuilder, point::Point, Quadtree}; // Instantiate a new quadtree which associates String values with u64 coordinates. let mut qt = Quadtree::<u64, String>::new(/*depth=*/4); // A depth of four means a square with width (and height) 2^4. assert_eq!(qt.width(), 16); // Associate the value "foo" with a rectangle of size 2x1, anchored at (0, 0). let region_a = AreaBuilder::default() .anchor(Point {x: 0, y: 0}) .dimensions((2, 1)) .build().unwrap(); qt.insert(region_a, "foo".to_string()); // Query over a region of size 2x2, anchored at (1, 0). let region_b = AreaBuilder::default() .anchor(Point {x: 1, y: 0}) .dimensions((2, 2)) .build().unwrap(); let mut query = qt.query(region_b); // The query region (region_b) intersects the region "foo" is associated with (region_a), so the query iterator returns "foo" by reference. assert_eq!(query.next().unwrap().value_ref(), "foo");
Implementation
use quadtree_rs::{area::AreaBuilder, point::Point, Quadtree}; let mut qt = Quadtree::<u8, char>::new(2); // In a quadtree, every region is (lazily) subdivided into subqudrants. // Associating a value with a point, which is represented by a region with dimensions 1x1, means traversing the full height of the quadtree. qt.insert_pt(Point {x: 0, y: 0}, 'a'); // (0,0)->4x4 +---+---+---+---+ // (0,0)->2x2 | a | | | // (0,0)->1x1 ['a'] +---+ + + // | | | // +---+---+---+---+ // | | | // + + + // | | | // +---+---+---+---+ // Often inserting a large region requires traversing only as far down as necessary to fully cover that region. let region_b = AreaBuilder::default() .anchor(Point {x: 0, y: 0}) .dimensions((2, 2)) .build().unwrap(); qt.insert(region_b, 'b'); // (0,0)->4x4 +---+---+---+---+ // (0,0)->2x2 ['b'] | a | | | // (0,0)->1x1 ['a'] +---+ + + // | b | | // +---+---+---+---+ // | | | // + + + // | | | // +---+---+---+---+ // If a region cannot be represented by one node in the tree, a handle type is inserted in multiple places. let region_c = AreaBuilder::default() .anchor(Point {x: 0, y: 0}) .dimensions((3, 3)) .build().unwrap(); qt.insert(region_c, 'c'); // (0,0)->4x4 +---+---+---+---+ // (0,0)->2x2 ['b', 'c'] | a | | c | | // (0,0)->1x1 ['a'] +---+ +---+---+ // (0,2)->2x2 | b,c | c | | // (0,2)->1x1 ['c'] +---+---+---+---+ // (1,2)->1x1 ['c'] | c | c | c | | // (2,0)->2x2 +---+---+---+---+ // (2,0)->1x1 ['c'] | | | | | // (2,1)->1x1 ['c'] +---+---+---+---+ // (2,2)->2x2 // (2,2)->1x1 ['c']
Duplicating the storage handle allows for fast lookup and insertion at the cost of slow
deletion. quadtree_rs
is well-suited for scenarios with low churn but frequent read access.
Usage
For further usage details, see the documentations for the Quadtree
struct.
Modules
area | A rectangular region in the tree. |
entry | A view into a single entry in the Quadtree. |
iter | |
point | A point region in the tree. |
Structs
Quadtree | A data structure for storing and accessing data in 2d space. |