space_partitioning/quadtree/
quadtree_element.rs

1use crate::quadtree::{free_list, AABB};
2
3/// Alias for all traits required for an element ID.
4pub trait ElementIdType: Default + std::cmp::Eq + std::hash::Hash + Copy {}
5
6/// Helper implementation to automatically derive the [`ElementIdType`] trait
7impl<T> ElementIdType for T where T: Default + std::cmp::Eq + std::hash::Hash + Copy {}
8
9/// Represents an element in the QuadTree.
10#[derive(Debug, PartialEq, Eq, Default, Copy, Clone)]
11pub struct QuadTreeElement<ElementId = u32>
12where
13    ElementId: ElementIdType,
14{
15    /// The axis-aligned bounding box of the element.
16    pub rect: AABB,
17    /// Stores the ID for the element (can be used to refer to external data).
18    pub id: ElementId,
19}
20
21impl<ElementId> QuadTreeElement<ElementId>
22where
23    ElementId: ElementIdType,
24{
25    pub fn new(id: ElementId, rect: AABB) -> Self {
26        Self { id, rect }
27    }
28}
29
30/// Represents an element node in the quadtree.
31///
32/// # Remarks
33/// An element (`QuadTreeElement`) is only inserted once to the quadtree no matter how many
34/// cells it occupies. However, for each cell it occupies, an "element node" (`QuadTreeElementNode`)
35/// is inserted which indexes that element.
36#[derive(Debug, PartialEq, Eq, Default, Copy, Clone)]
37pub(crate) struct QuadTreeElementNode {
38    /// Points to the next element in the leaf node. A value of `free_list::SENTINEL`
39    /// indicates the end of the list.
40    pub next: free_list::IndexType,
41    /// Stores the element index.
42    pub element_idx: free_list::IndexType,
43}
space_partitioning/quadtree/quadtree_element.rs

space_partitioning/quadtree/
quadtree_element.rs
