Crate quadtree_f32

Source
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 ItemIds.

§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 and Rect (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).
  • 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) or f64 (with the f64 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 and y coordinates.
QuadTree
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.
QuadTreeNode

Type Aliases§

Float
Type alias for floating point numbers used in geometry.