Expand description
§QuadTree Crate
This crate provides a dynamic quadtree implementation in Rust designed for
efficient 2D spatial indexing and querying. It supports storing points and rectangles
associated with unique ItemId
s.
§Key Features:
- Dynamic Operations: Insert and remove items dynamically. The tree structure adapts as items are added or removed.
- Spatial Storage: Stores 2D geometric types:
Point
andRect
(axis-aligned bounding boxes). - Querying:
- Find all items whose bounding boxes overlap a given query rectangle (
get_ids_that_overlap
). - Find all points contained within a given query rectangle (
get_points_contained_by
). - Retrieve specific items by their
ItemId
(get_item_by_id
).
- Find all items whose bounding boxes overlap a given query rectangle (
- DBSCAN Clustering: Includes functionality to perform DBSCAN (Density-Based Spatial Clustering of Applications with Noise)
on the items stored in the quadtree (
get_clusters
). - Generic Float Type: Can use
f32
(default) orf64
(with thef64
feature flag) for coordinates.
§Usage Example
use quadtree_f32::{QuadTree, Rect, Point, Item, ItemId};
// Create a new quadtree
let mut quadtree = QuadTree::new();
// Define a bounding box for the first item, which will also set the QuadTree's initial bbox
let bounds = Rect { min_x: 0.0, min_y: 0.0, max_x: 100.0, max_y: 100.0 };
// For the example to work as originally intended with an initial overall bbox,
// we can simulate this by inserting a dummy item or ensuring the first real item
// establishes a sufficiently large area if that's the desired behavior.
// Or, simply insert items and let the bbox grow.
// For this example, let's assume items will define the bounds.
// Create some items
let item1_id = ItemId(1);
let item1_point = Item::Point(Point::new(10.0, 15.0));
let item2_id = ItemId(2);
let item2_rect = Item::Rect(Rect { min_x: 50.0, min_y: 50.0, max_x: 60.0, max_y: 60.0 });
// Insert items into the quadtree
quadtree.insert(item1_id, item1_point);
quadtree.insert(item2_id, item2_rect);
// Query for items overlapping a certain area
let query_area = Rect { min_x: 5.0, min_y: 5.0, max_x: 55.0, max_y: 55.0 };
let overlapping_item_ids = quadtree.get_ids_that_overlap(&query_area);
println!("Items overlapping query area: {:?}", overlapping_item_ids);
// Example: Might print [ItemId(1), ItemId(2)] or just [ItemId(1)] if item2_rect is outside based on exact overlap logic.
// For this example, item1_point (10,15) is inside. item2_rect (50,50)-(60,60) overlaps (5,5)-(55,55) partially.
// Perform DBSCAN clustering
let clusters = quadtree.get_clusters(5.0, 2); // eps = 5.0, min_items_in_cluster = 2
println!("Found {} clusters.", clusters.len());
for (i, cluster) in clusters.iter().enumerate() {
println!("Cluster {}: {:?}", i + 1, cluster);
}
The commented-out sections in the code (// struct QuadTree { ... }
) represent an older,
static version of the quadtree that this dynamic implementation replaces.
Structs§
- ItemId
- Instead of making a generic tree, the quadtree only
keeps items (rects or points) and their associated IDs.
A unique identifier for an item stored in the
QuadTree
. - Point
- Represents a 2D point with
x
andy
coordinates. - Quad
Tree - The main quadtree data structure.
- Rect
- Represents an axis-aligned rectangle (bounding box).
Enums§
- Item
- Represents a geometric item that can be inserted into the
QuadTree
. - Quad
Tree Node
Type Aliases§
- Float
- Type alias for floating point numbers used in geometry.