cvkg_layout/
spatial.rs

1use cvkg_core::Rect;
2
3/// A node entry stored in the spatial index after layout completes.
4#[derive(Debug, Clone)]
5pub struct LayoutSpatialEntry {
6    /// Stable identity of the view — matches `LayoutView::view_hash()`.
7    pub hash: u64,
8    /// Post-layout bounding rect in the root coordinate space.
9    pub rect: Rect,
10}
11
12/// Axis-aligned 2-D quadtree that indexes laid-out view bounding boxes.
13pub struct LayoutSpatialIndex {
14    root: Option<Box<QuadNode>>,
15    /// Root bounds used when the tree was built — needed for hit queries.
16    bounds: Rect,
17}
18
19const MAX_ITEMS_PER_NODE: usize = 16;
20const MAX_TREE_DEPTH: u32 = 8;
21
22struct QuadNode {
23    bounds: Rect,
24    entries: Vec<LayoutSpatialEntry>,
25    children: Option<Box<[Box<QuadNode>; 4]>>,
26}
27
28impl QuadNode {
29    fn new(bounds: Rect) -> Self {
30        Self {
31            bounds,
32            entries: Vec::new(),
33            children: None,
34        }
35    }
36
37    fn insert(&mut self, entry: LayoutSpatialEntry, depth: u32) {
38        if !self.bounds.intersects(&entry.rect) {
39            return;
40        }
41        if let Some(children) = &mut self.children {
42            for child in children.iter_mut() {
43                if child.bounds.intersects(&entry.rect) {
44                    child.insert(entry.clone(), depth + 1);
45                }
46            }
47            return;
48        }
49        self.entries.push(entry);
50        if self.entries.len() > MAX_ITEMS_PER_NODE && depth < MAX_TREE_DEPTH {
51            self.split(depth);
52        }
53    }
54
55    fn split(&mut self, depth: u32) {
56        let hw = self.bounds.width * 0.5;
57        let hh = self.bounds.height * 0.5;
58        let mx = self.bounds.x + hw;
59        let my = self.bounds.y + hh;
60        let make = |x, y, w, h| Box::new(QuadNode::new(Rect { x, y, width: w, height: h }));
61        let mut children = Box::new([
62            make(self.bounds.x, self.bounds.y, hw, hh), // NW
63            make(mx, self.bounds.y, hw, hh),            // NE
64            make(self.bounds.x, my, hw, hh),            // SW
65            make(mx, my, hw, hh),                       // SE
66        ]);
67        let entries = std::mem::take(&mut self.entries);
68        for e in entries {
69            for child in children.iter_mut() {
70                if child.bounds.intersects(&e.rect) {
71                    child.insert(e.clone(), depth + 1);
72                }
73            }
74        }
75        self.children = Some(children);
76    }
77
78    fn hit_test(&self, point: (f32, f32), out: &mut Vec<LayoutSpatialEntry>) {
79        if !self.bounds.contains(point.0, point.1) {
80            return;
81        }
82        for e in &self.entries {
83            if e.rect.contains(point.0, point.1) {
84                out.push(e.clone());
85            }
86        }
87        if let Some(children) = &self.children {
88            for child in children.iter() {
89                child.hit_test(point, out);
90            }
91        }
92    }
93
94    fn query_region(&self, region: &Rect, out: &mut Vec<LayoutSpatialEntry>) {
95        if !self.bounds.intersects(region) {
96            return;
97        }
98        for e in &self.entries {
99            if e.rect.intersects(region) {
100                out.push(e.clone());
101            }
102        }
103        if let Some(children) = &self.children {
104            for child in children.iter() {
105                child.query_region(region, out);
106            }
107        }
108    }
109}
110
111impl LayoutSpatialIndex {
112    /// Construct an empty index.
113    pub fn new() -> Self {
114        Self { root: None, bounds: Rect::zero() }
115    }
116
117    /// Rebuild the index from a flat list of (hash, rect) pairs produced after a layout pass.
118    pub fn rebuild(&mut self, root_bounds: Rect, entries: impl IntoIterator<Item = LayoutSpatialEntry>) {
119        self.bounds = root_bounds;
120        let mut root = QuadNode::new(root_bounds);
121        for e in entries {
122            if e.rect.width > 0.0 && e.rect.height > 0.0 {
123                root.insert(e, 0);
124            }
125        }
126        self.root = Some(Box::new(root));
127    }
128
129    /// Return all entries whose bounding rect contains `(x, y)`, ordered front-to-back.
130    pub fn hit_test(&self, x: f32, y: f32) -> Vec<LayoutSpatialEntry> {
131        let mut out = Vec::new();
132        if let Some(root) = &self.root {
133            root.hit_test((x, y), &mut out);
134        }
135        out
136    }
137
138    /// Return all entries whose bounding rect overlaps `region`.
139    pub fn query_region(&self, region: &Rect) -> Vec<LayoutSpatialEntry> {
140        let mut out = Vec::new();
141        if let Some(root) = &self.root {
142            root.query_region(region, &mut out);
143        }
144        out
145    }
146}
147
148impl Default for LayoutSpatialIndex {
149    fn default() -> Self {
150        Self::new()
151    }
152}
cvkg_layout/spatial.rs

cvkg_layout/
spatial.rs
