Crate quadtree_f32

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.