LCOV - code coverage report
Current view: top level - src/renderer/core/spatial - QuadTree.ts Coverage Total Hit
Test: ComfyUI E2E Coverage Lines: 59.3 % 81 48
Test Date: 2026-11-17 04:17:53

            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              : }
        

Generated by: LCOV version 2.0-1