Line data Source code
1 : /**
2 : * QuadTree implementation for spatial indexing of nodes
3 : * Optimized for viewport culling in large node graphs
4 : */
5 : import type { Bounds } from '@comfyorg/shared-frontend-utils/geometry'
6 : import type {
7 : QuadNodeDebugInfo,
8 : SpatialIndexDebugInfo
9 : } from '@/types/spatialIndex'
10 :
11 : interface QuadTreeItem<T> {
12 : id: string
13 : bounds: Bounds
14 : data: T
15 : }
16 :
17 : interface QuadTreeOptions {
18 : maxDepth?: number
19 : maxItemsPerNode?: number
20 : minNodeSize?: number
21 : }
22 :
23 2356 : class QuadNode<T> {
24 : private bounds: Bounds
25 : private depth: number
26 : private maxDepth: number
27 : private maxItems: number
28 : private items: QuadTreeItem<T>[] = []
29 : private children: QuadNode<T>[] | null = null
30 : private divided = false
31 :
32 : constructor(
33 : bounds: Bounds,
34 : depth: number = 0,
35 : maxDepth: number = 5,
36 : maxItems: number = 4
37 : ) {
38 6469 : this.bounds = bounds
39 6469 : this.depth = depth
40 6469 : this.maxDepth = maxDepth
41 6469 : this.maxItems = maxItems
42 : }
43 :
44 : insert(item: QuadTreeItem<T>): boolean {
45 : // Check if item is within bounds
46 46 : if (!this.contains(item.bounds)) {
47 0 : return false
48 : }
49 :
50 : // If we have space and haven't divided, add to this node
51 46 : if (this.items.length < this.maxItems && !this.divided) {
52 46 : this.items.push(item)
53 46 : return true
54 : }
55 :
56 : // If we haven't reached max depth, subdivide
57 46 : if (!this.divided && this.depth < this.maxDepth) {
58 0 : this.subdivide()
59 : }
60 :
61 : // If divided, insert into children
62 46 : if (this.divided && this.children) {
63 0 : for (const child of this.children) {
64 0 : if (child.insert(item)) {
65 0 : return true
66 : }
67 : }
68 : }
69 :
70 : // If we can't subdivide further, add to this node anyway
71 0 : this.items.push(item)
72 0 : return true
73 : }
74 :
75 : remove(item: QuadTreeItem<T>): boolean {
76 21 : const index = this.items.findIndex((i) => i.id === item.id)
77 21 : if (index !== -1) {
78 21 : this.items.splice(index, 1)
79 21 : return true
80 : }
81 :
82 21 : if (this.divided && this.children) {
83 0 : for (const child of this.children) {
84 0 : if (child.remove(item)) {
85 0 : return true
86 : }
87 : }
88 : }
89 :
90 0 : return false
91 : }
92 :
93 : query(
94 : searchBounds: Bounds,
95 : found: QuadTreeItem<T>[] = []
96 : ): QuadTreeItem<T>[] {
97 : // Check if search area intersects with this node
98 549 : if (!this.intersects(searchBounds)) {
99 0 : return found
100 : }
101 :
102 : // Add items in this node that intersect with search bounds
103 549 : for (const item of this.items) {
104 15 : if (this.boundsIntersect(item.bounds, searchBounds)) {
105 2 : found.push(item)
106 : }
107 : }
108 :
109 : // Recursively search children
110 549 : if (this.divided && this.children) {
111 0 : for (const child of this.children) {
112 0 : child.query(searchBounds, found)
113 : }
114 : }
115 :
116 549 : return found
117 : }
118 :
119 : private subdivide() {
120 0 : const { x, y, width, height } = this.bounds
121 0 : const halfWidth = width / 2
122 0 : const halfHeight = height / 2
123 :
124 0 : this.children = [
125 : // Top-left
126 : new QuadNode<T>(
127 : { x, y, width: halfWidth, height: halfHeight },
128 : this.depth + 1,
129 : this.maxDepth,
130 : this.maxItems
131 : ),
132 : // Top-right
133 : new QuadNode<T>(
134 : { x: x + halfWidth, y, width: halfWidth, height: halfHeight },
135 : this.depth + 1,
136 : this.maxDepth,
137 : this.maxItems
138 : ),
139 : // Bottom-left
140 : new QuadNode<T>(
141 : { x, y: y + halfHeight, width: halfWidth, height: halfHeight },
142 : this.depth + 1,
143 : this.maxDepth,
144 : this.maxItems
145 : ),
146 : // Bottom-right
147 : new QuadNode<T>(
148 : {
149 : x: x + halfWidth,
150 : y: y + halfHeight,
151 : width: halfWidth,
152 : height: halfHeight
153 : },
154 : this.depth + 1,
155 : this.maxDepth,
156 : this.maxItems
157 : )
158 : ]
159 :
160 0 : this.divided = true
161 :
162 : // Redistribute existing items to children
163 0 : const itemsToRedistribute = [...this.items]
164 0 : this.items = []
165 :
166 0 : for (const item of itemsToRedistribute) {
167 0 : let inserted = false
168 0 : for (const child of this.children) {
169 0 : if (child.insert(item)) {
170 0 : inserted = true
171 0 : break
172 : }
173 : }
174 : // Keep in parent if it doesn't fit in any child
175 0 : if (!inserted) {
176 0 : this.items.push(item)
177 : }
178 : }
179 : }
180 :
181 : private contains(itemBounds: Bounds): boolean {
182 46 : return (
183 : itemBounds.x >= this.bounds.x &&
184 : itemBounds.y >= this.bounds.y &&
185 : itemBounds.x + itemBounds.width <= this.bounds.x + this.bounds.width &&
186 : itemBounds.y + itemBounds.height <= this.bounds.y + this.bounds.height
187 : )
188 : }
189 :
190 : private intersects(searchBounds: Bounds): boolean {
191 549 : return this.boundsIntersect(this.bounds, searchBounds)
192 : }
193 :
194 : private boundsIntersect(a: Bounds, b: Bounds): boolean {
195 564 : return !(
196 : a.x + a.width < b.x ||
197 : b.x + b.width < a.x ||
198 : a.y + a.height < b.y ||
199 : b.y + b.height < a.y
200 : )
201 : }
202 :
203 : // Debug helper to get tree structure
204 : getDebugInfo(): QuadNodeDebugInfo {
205 0 : return {
206 : bounds: this.bounds,
207 : depth: this.depth,
208 : itemCount: this.items.length,
209 : divided: this.divided,
210 : children: this.children?.map((child) => child.getDebugInfo())
211 : }
212 : }
213 : }
214 :
215 2356 : export class QuadTree<T> {
216 : private root: QuadNode<T>
217 : private itemMap: Map<string, QuadTreeItem<T>> = new Map()
218 : private options: Required<QuadTreeOptions>
219 :
220 : constructor(bounds: Bounds, options: QuadTreeOptions = {}) {
221 4712 : this.options = {
222 : maxDepth: options.maxDepth ?? 5,
223 : maxItemsPerNode: options.maxItemsPerNode ?? 4,
224 : minNodeSize: options.minNodeSize ?? 50
225 : }
226 :
227 4712 : this.root = new QuadNode<T>(
228 : bounds,
229 : 0,
230 : this.options.maxDepth,
231 : this.options.maxItemsPerNode
232 : )
233 : }
234 :
235 : insert(id: string, bounds: Bounds, data: T): boolean {
236 46 : const item: QuadTreeItem<T> = { id, bounds, data }
237 :
238 : // Remove old item if it exists
239 46 : if (this.itemMap.has(id)) {
240 0 : this.remove(id)
241 : }
242 :
243 46 : const success = this.root.insert(item)
244 46 : if (success) {
245 46 : this.itemMap.set(id, item)
246 : }
247 46 : return success
248 : }
249 :
250 : remove(id: string): boolean {
251 21 : const item = this.itemMap.get(id)
252 21 : if (!item) return false
253 :
254 21 : const success = this.root.remove(item)
255 21 : if (success) {
256 21 : this.itemMap.delete(id)
257 : }
258 21 : return success
259 : }
260 :
261 : update(id: string, newBounds: Bounds): boolean {
262 5 : const item = this.itemMap.get(id)
263 5 : if (!item) return false
264 :
265 : // Remove and re-insert with new bounds
266 5 : const data = item.data
267 5 : this.remove(id)
268 5 : return this.insert(id, newBounds, data)
269 : }
270 :
271 : query(searchBounds: Bounds): T[] {
272 : const items = this.root.query(searchBounds)
273 549 : return items.map((item) => item.data)
274 : }
275 :
276 : clear() {
277 1757 : this.root = new QuadNode<T>(
278 : this.root['bounds'],
279 : 0,
280 : this.options.maxDepth,
281 : this.options.maxItemsPerNode
282 : )
283 1757 : this.itemMap.clear()
284 : }
285 :
286 : get size(): number {
287 0 : return this.itemMap.size
288 : }
289 :
290 : getDebugInfo(): SpatialIndexDebugInfo {
291 0 : return {
292 : size: this.size,
293 : tree: this.root.getDebugInfo()
294 : }
295 : }
296 : }
|