cvkg_spatial/quadtree.rs
1//! # CVKG Agentic Development Guidelines (v1.2)
2//!
3//! All AI agents contributing to this crate MUST follow ALL seven rules:
4//!
5//! ── Karpathy Guidelines (1–4) ────────────────────────────────────────────
6//! 1. THINK FIRST -- State assumptions. Surface ambiguity. Push back on complexity.
7//! 2. STAY SIMPLE -- Minimum code. No speculative features. No unasked-for abstractions.
8//! 3. BE SURGICAL -- Touch only what's required. Own your orphans. Don't improve neighbors.
9//! 4. VERIFY GOALS -- Turn tasks into checkable criteria. Loop until they pass. Never commit broken.
10//!
11//! ── CVKG Extended Protocols (5–7) ────────────────────────────────────────
12//! 5. TRIPLE-PASS -- Read the target, its surrounding context, and its full call graph
13//! at least THREE TIMES before making any edit or revision.
14//! 6. COMMENT ALL -- Every major pub fn, unsafe block, and non-trivial algorithm in
15//! every .rs/.ts/.h/.wgsl file MUST have a descriptive doc comment.
16//! Comments describe WHY and WHAT CONTRACT, not HOW mechanically.
17//! 7. MONITOR LOOPS -- Check every tool call / command for progress every 30 seconds.
18//! After 3 consecutive identical failures, stop, write BLOCKED.md,
19//! and move to unblocked work. Never silently accept a broken state.
20//!
21//! Sources:
22// Karpathy: https://github.com/multica-ai/andrej-karpathy-skills
23// CVKG Extended: Section 2 of the CVKG Design Specification
24
25//! QuadTree spatial partitioning structure.
26//!
27//! # Why this exists
28//! A QuadTree recursively subdivides a 2D region into four quadrants when a node
29//! exceeds a capacity threshold. This enables O(log n) broad-phase collision checks
30//! and dirty-rect merge queries instead of O(n²) brute-force comparisons.
31//!
32//! This was previously duplicated in `cvkg-scene`. Moving it here makes it available
33//! to Physics, Flow, and Layout without import cycles.
34
35use cvkg_core::Rect;
36
37/// An axis-aligned 2D spatial partitioning tree.
38///
39/// # Contract
40/// - Insertions that fall entirely outside `bounds` are silently dropped.
41/// - `retrieve` returns ALL rects in leaf nodes that overlap the query rect;
42/// callers must perform their own exact AABB test on the returned set.
43/// - Maximum recursion depth is capped at `max_depth` (default 5) to bound
44/// memory usage even with degenerate inputs (all rects at one point).
45pub struct Quadtree {
46 bounds: Rect,
47 rects: Vec<Rect>,
48 children: Option<Box<[Quadtree; 4]>>,
49 max_rects: usize,
50 max_depth: usize,
51 depth: usize,
52}
53
54impl Quadtree {
55 /// Create a new root QuadTree node covering the given bounds.
56 ///
57 /// Default capacity per leaf is 10 rects, maximum depth is 5 levels.
58 pub fn new(bounds: Rect) -> Self {
59 Self {
60 bounds,
61 rects: Vec::new(),
62 children: None,
63 max_rects: 10,
64 max_depth: 5,
65 depth: 0,
66 }
67 }
68
69 /// Internal constructor for child nodes with an inherited depth counter.
70 fn new_with_depth(bounds: Rect, depth: usize) -> Self {
71 Self {
72 bounds,
73 rects: Vec::new(),
74 children: None,
75 max_rects: 10,
76 max_depth: 5,
77 depth,
78 }
79 }
80
81 /// Insert a rect into the tree.
82 ///
83 /// The rect is dropped if it does not intersect this node's bounds.
84 /// If this is an interior node (already subdivided), the rect is
85 /// propagated to all overlapping children. Otherwise it is stored
86 /// in this leaf; if the leaf is now over capacity and below max depth,
87 /// the node is subdivided and existing rects redistributed.
88 pub fn insert(&mut self, rect: Rect) {
89 if !self.intersects(self.bounds, rect) {
90 return;
91 }
92
93 if let Some(ref mut children) = self.children {
94 for child in children.iter_mut() {
95 child.insert(rect);
96 }
97 return;
98 }
99
100 self.rects.push(rect);
101
102 if self.rects.len() > self.max_rects && self.depth < self.max_depth {
103 self.subdivide();
104 }
105 }
106
107 /// Split this leaf into four equal quadrants and redistribute stored rects.
108 ///
109 /// After subdivision, this node becomes interior — its `rects` vec is drained
110 /// into the children. The subdivision is skipped if `depth >= max_depth`.
111 fn subdivide(&mut self) {
112 let hw = self.bounds.width / 2.0;
113 let hh = self.bounds.height / 2.0;
114 let x = self.bounds.x;
115 let y = self.bounds.y;
116 let d = self.depth + 1;
117
118 let mut children = Box::new([
119 Quadtree::new_with_depth(
120 Rect {
121 x,
122 y,
123 width: hw,
124 height: hh,
125 },
126 d,
127 ),
128 Quadtree::new_with_depth(
129 Rect {
130 x: x + hw,
131 y,
132 width: hw,
133 height: hh,
134 },
135 d,
136 ),
137 Quadtree::new_with_depth(
138 Rect {
139 x,
140 y: y + hh,
141 width: hw,
142 height: hh,
143 },
144 d,
145 ),
146 Quadtree::new_with_depth(
147 Rect {
148 x: x + hw,
149 y: y + hh,
150 width: hw,
151 height: hh,
152 },
153 d,
154 ),
155 ]);
156
157 for rect in self.rects.drain(..) {
158 for child in children.iter_mut() {
159 child.insert(rect);
160 }
161 }
162
163 self.children = Some(children);
164 }
165
166 /// Returns true if rect `a` and rect `b` overlap (strict interior intersection).
167 fn intersects(&self, a: Rect, b: Rect) -> bool {
168 a.x < b.x + b.width && a.x + a.width > b.x && a.y < b.y + b.height && a.y + a.height > b.y
169 }
170
171 /// Collect all candidate rects that may overlap `rect` into `out`.
172 ///
173 /// This is a broad-phase query: returned rects are candidates from overlapping
174 /// leaf nodes. Callers MUST perform their own exact intersection test on results.
175 /// The `out` vec is appended to — it is never cleared.
176 pub fn retrieve(&self, rect: Rect, out: &mut Vec<Rect>) {
177 if !self.intersects(self.bounds, rect) {
178 return;
179 }
180
181 if let Some(ref children) = self.children {
182 for child in children.iter() {
183 child.retrieve(rect, out);
184 }
185 } else {
186 for r in &self.rects {
187 out.push(*r);
188 }
189 }
190 }
191}
192
193#[cfg(test)]
194mod tests {
195 use super::*;
196 use cvkg_core::Rect;
197
198 fn rect(x: f32, y: f32, w: f32, h: f32) -> Rect {
199 Rect {
200 x,
201 y,
202 width: w,
203 height: h,
204 }
205 }
206
207 #[test]
208 fn test_insert_and_retrieve_basic() {
209 let bounds = rect(0.0, 0.0, 100.0, 100.0);
210 let mut qt = Quadtree::new(bounds);
211
212 qt.insert(rect(10.0, 10.0, 20.0, 20.0));
213 qt.insert(rect(60.0, 60.0, 20.0, 20.0));
214
215 // Query that overlaps first rect
216 let mut out = Vec::new();
217 qt.retrieve(rect(5.0, 5.0, 30.0, 30.0), &mut out);
218 assert!(!out.is_empty(), "Should find at least one candidate");
219 }
220
221 #[test]
222 fn test_out_of_bounds_insert_is_dropped() {
223 let bounds = rect(0.0, 0.0, 100.0, 100.0);
224 let mut qt = Quadtree::new(bounds);
225
226 // Entirely outside bounds
227 qt.insert(rect(200.0, 200.0, 10.0, 10.0));
228
229 let mut out = Vec::new();
230 qt.retrieve(rect(0.0, 0.0, 100.0, 100.0), &mut out);
231 assert!(out.is_empty(), "Out-of-bounds rect should be dropped");
232 }
233
234 #[test]
235 fn test_subdivide_triggers_under_load() {
236 let bounds = rect(0.0, 0.0, 1000.0, 1000.0);
237 let mut qt = Quadtree::new(bounds);
238
239 // Insert 15 rects spread across bounds to trigger subdivision (threshold = 10)
240 for i in 0..15_u32 {
241 let offset = (i * 60) as f32;
242 qt.insert(rect(offset % 900.0, offset % 900.0, 30.0, 30.0));
243 }
244
245 // After subdivision, retrieval must still work
246 let mut out = Vec::new();
247 qt.retrieve(rect(0.0, 0.0, 1000.0, 1000.0), &mut out);
248 assert!(!out.is_empty(), "Should retrieve rects after subdivision");
249 }
250}