module import extend from "@yomguithereal/helpers/extend" ; import { PlainObject } from "../types" ; /**
 * Constants.
 *
 * Note that since we are representing a static 4-ary tree, the indices of the
 * quadrants are the following:
 *   - TOP_LEFT:     4i + b
 *   - TOP_RIGHT:    4i + 2b
 *   - BOTTOM_LEFT:  4i + 3b
 *   - BOTTOM_RIGHT: 4i + 4b
 */ const BLOCKS = 4 , MAX_LEVEL = 5 ; const OUTSIDE_BLOCK = "outside" ; const X_OFFSET = 0 , Y_OFFSET = 1 , WIDTH_OFFSET = 2 , HEIGHT_OFFSET = 3 ; const TOP_LEFT = 1 , TOP_RIGHT = 2 , BOTTOM_LEFT = 3 , BOTTOM_RIGHT = 4 ; let hasWarnedTooMuchOutside = false ; export interface Boundaries { x : number ; y : number ; width : number ; height : number ; } export interface Rectangle { x1 : number ; y1 : number ; x2 : number ; y2 : number ; height : number ; } export interface Vector { x : number ; y : number ; } /**
 * Geometry helpers.
 */ param { Rectangle } rect return { boolean } export function isRectangleAligned ( rect ) { return rect . x1 === rect . x2 || rect . y1 === rect . y2 ; } param { Rectangle } rect return { Rectangle } export function getCircumscribedAlignedRectangle ( rect ) { const width = Math . sqrt ( Math . pow ( rect . x2 - rect . x1 , 2 ) + Math . pow ( rect . y2 - rect . y1 , 2 ) ) ; const heightVector = { x : ( ( rect . y1 - rect . y2 ) * rect . height ) / width , y : ( ( rect . x2 - rect . x1 ) * rect . height ) / width , } ; const tl = { x : rect . x1 , y : rect . y1 } ; const tr = { x : rect . x2 , y : rect . y2 } ; const bl = { x : rect . x1 + heightVector . x , y : rect . y1 + heightVector . y , } ; const br = { x : rect . x2 + heightVector . x , y : rect . y2 + heightVector . y , } ; const xL = Math . min ( tl . x , tr . x , bl . x , br . x ) ; const xR = Math . max ( tl . x , tr . x , bl . x , br . x ) ; const yT = Math . min ( tl . y , tr . y , bl . y , br . y ) ; const yB = Math . max ( tl . y , tr . y , bl . y , br . y ) ; return { x1 : xL , y1 : yT , x2 : xR , y2 : yT , height : yB - yT , } ; } param x1 param y1 param w param qx param qy param qw param qh export function squareCollidesWithQuad ( x1 , y1 , w , qx , qy , qw , qh ) { return x1 < qx + qw && x1 + w > qx && y1 < qy + qh && y1 + w > qy ; } export function rectangleCollidesWithQuad ( x1 , y1 , w , h , qx , qy , qw , qh ) { return x1 < qx + qw && x1 + w > qx && y1 < qy + qh && y1 + h > qy ; } function pointIsInQuad ( x , y , qx , qy , qw , qh ) { const xmp = qx + qw / 2 , ymp = qy + qh / 2 , top = y < ymp , left = x < xmp ; return top ? ( left ? TOP_LEFT : TOP_RIGHT ) : left ? BOTTOM_LEFT : BOTTOM_RIGHT ; } /**
 * Helper functions that are not bound to the class so an external user
 * cannot mess with them.
 */ function buildQuadrants ( maxLevel , data ) { const stack = [ 0 , 0 ] ; while ( stack . length ) { const level = stack . pop ( ) as number , block = stack . pop ( ) as number ; const topLeftBlock = 4 * block + BLOCKS , topRightBlock = 4 * block + 2 * BLOCKS , bottomLeftBlock = 4 * block + 3 * BLOCKS , bottomRightBlock = 4 * block + 4 * BLOCKS ; const x = data [ block + X_OFFSET ] , y = data [ block + Y_OFFSET ] , width = data [ block + WIDTH_OFFSET ] , height = data [ block + HEIGHT_OFFSET ] , hw = width / 2 , hh = height / 2 ; data [ topLeftBlock + X_OFFSET ] = x ; data [ topLeftBlock + Y_OFFSET ] = y ; data [ topLeftBlock + WIDTH_OFFSET ] = hw ; data [ topLeftBlock + HEIGHT_OFFSET ] = hh ; data [ topRightBlock + X_OFFSET ] = x + hw ; data [ topRightBlock + Y_OFFSET ] = y ; data [ topRightBlock + WIDTH_OFFSET ] = hw ; data [ topRightBlock + HEIGHT_OFFSET ] = hh ; data [ bottomLeftBlock + X_OFFSET ] = x ; data [ bottomLeftBlock + Y_OFFSET ] = y + hh ; data [ bottomLeftBlock + WIDTH_OFFSET ] = hw ; data [ bottomLeftBlock + HEIGHT_OFFSET ] = hh ; data [ bottomRightBlock + X_OFFSET ] = x + hw ; data [ bottomRightBlock + Y_OFFSET ] = y + hh ; data [ bottomRightBlock + WIDTH_OFFSET ] = hw ; data [ bottomRightBlock + HEIGHT_OFFSET ] = hh ; if ( level < maxLevel - 1 ) { stack . push ( bottomRightBlock , level + 1 ) ; stack . push ( bottomLeftBlock , level + 1 ) ; stack . push ( topRightBlock , level + 1 ) ; stack . push ( topLeftBlock , level + 1 ) ; } } } function insertNode ( maxLevel , data , containers , key , x , y , size ) { const x1 = x - size , y1 = y - size , w = size * 2 ; let level = 0 , block = 0 ; while ( true ) { if ( level >= maxLevel ) { containers [ block ] = containers [ block ] || [ ] ; containers [ block ] . push ( key ) ; return ; } const topLeftBlock = 4 * block + BLOCKS , topRightBlock = 4 * block + 2 * BLOCKS , bottomLeftBlock = 4 * block + 3 * BLOCKS , bottomRightBlock = 4 * block + 4 * BLOCKS ; const collidingWithTopLeft = squareCollidesWithQuad ( x1 , y1 , w , data [ topLeftBlock + X_OFFSET ] , data [ topLeftBlock + Y_OFFSET ] , data [ topLeftBlock + WIDTH_OFFSET ] , data [ topLeftBlock + HEIGHT_OFFSET ] ) ; const collidingWithTopRight = squareCollidesWithQuad ( x1 , y1 , w , data [ topRightBlock + X_OFFSET ] , data [ topRightBlock + Y_OFFSET ] , data [ topRightBlock + WIDTH_OFFSET ] , data [ topRightBlock + HEIGHT_OFFSET ] ) ; const collidingWithBottomLeft = squareCollidesWithQuad ( x1 , y1 , w , data [ bottomLeftBlock + X_OFFSET ] , data [ bottomLeftBlock + Y_OFFSET ] , data [ bottomLeftBlock + WIDTH_OFFSET ] , data [ bottomLeftBlock + HEIGHT_OFFSET ] ) ; const collidingWithBottomRight = squareCollidesWithQuad ( x1 , y1 , w , data [ bottomRightBlock + X_OFFSET ] , data [ bottomRightBlock + Y_OFFSET ] , data [ bottomRightBlock + WIDTH_OFFSET ] , data [ bottomRightBlock + HEIGHT_OFFSET ] ) ; const collisions = [ collidingWithTopLeft , collidingWithTopRight , collidingWithBottomLeft , collidingWithBottomRight , ] . reduce ( ( acc , current ) => { if ( current ) return acc + 1 ; else return acc ; } , 0 ) ; if ( collisions === 0 && level === 0 ) { containers [ OUTSIDE_BLOCK ] . push ( key ) ; if ( ! hasWarnedTooMuchOutside && containers [ OUTSIDE_BLOCK ] . length >= 5 ) { hasWarnedTooMuchOutside = true ; console . warn ( "sigma/quadtree.insertNode: At least 5 nodes are outside the global quadtree zone. " + "You might have a problem with the normalization function or the custom bounding box." ) ; } return ; } if ( collisions === 0 ) throw new Error ( `sigma/quadtree.insertNode: no collision (level: ${ level }, key: ${ key }, x: ${ x }, y: ${ y }, size: ${ size }).` ) ; if ( collisions === 3 ) throw new Error ( `sigma/quadtree.insertNode: 3 impossible collisions (level: ${ level }, key: ${ key }, x: ${ x }, y: ${ y }, size: ${ size }).` ) ; if ( collisions > 1 ) { containers [ block ] = containers [ block ] || [ ] ; containers [ block ] . push ( key ) ; return ; } else { level ++ ; } if ( collidingWithTopLeft ) block = topLeftBlock ; if ( collidingWithTopRight ) block = topRightBlock ; if ( collidingWithBottomLeft ) block = bottomLeftBlock ; if ( collidingWithBottomRight ) block = bottomRightBlock ; } } function getNodesInAxisAlignedRectangleArea ( maxLevel , data , containers , x1 , y1 , w , h ) { const stack = [ 0 , 0 ] ; const collectedNodes = [ ] ; let container ; while ( stack . length ) { const level = stack . pop ( ) as number , block = stack . pop ( ) as number ; container = containers [ block ] ; if ( container ) extend ( collectedNodes , container ) ; if ( level >= maxLevel ) continue ; const topLeftBlock = 4 * block + BLOCKS , topRightBlock = 4 * block + 2 * BLOCKS , bottomLeftBlock = 4 * block + 3 * BLOCKS , bottomRightBlock = 4 * block + 4 * BLOCKS ; const collidingWithTopLeft = rectangleCollidesWithQuad ( x1 , y1 , w , h , data [ topLeftBlock + X_OFFSET ] , data [ topLeftBlock + Y_OFFSET ] , data [ topLeftBlock + WIDTH_OFFSET ] , data [ topLeftBlock + HEIGHT_OFFSET ] ) ; const collidingWithTopRight = rectangleCollidesWithQuad ( x1 , y1 , w , h , data [ topRightBlock + X_OFFSET ] , data [ topRightBlock + Y_OFFSET ] , data [ topRightBlock + WIDTH_OFFSET ] , data [ topRightBlock + HEIGHT_OFFSET ] ) ; const collidingWithBottomLeft = rectangleCollidesWithQuad ( x1 , y1 , w , h , data [ bottomLeftBlock + X_OFFSET ] , data [ bottomLeftBlock + Y_OFFSET ] , data [ bottomLeftBlock + WIDTH_OFFSET ] , data [ bottomLeftBlock + HEIGHT_OFFSET ] ) ; const collidingWithBottomRight = rectangleCollidesWithQuad ( x1 , y1 , w , h , data [ bottomRightBlock + X_OFFSET ] , data [ bottomRightBlock + Y_OFFSET ] , data [ bottomRightBlock + WIDTH_OFFSET ] , data [ bottomRightBlock + HEIGHT_OFFSET ] ) ; if ( collidingWithTopLeft ) stack . push ( topLeftBlock , level + 1 ) ; if ( collidingWithTopRight ) stack . push ( topRightBlock , level + 1 ) ; if ( collidingWithBottomLeft ) stack . push ( bottomLeftBlock , level + 1 ) ; if ( collidingWithBottomRight ) stack . push ( bottomRightBlock , level + 1 ) ; } return collectedNodes ; } constructor param { object } boundaries export default class QuadTree { data : Float32Array ; containers : PlainObject < string [ ] > = { [ OUTSIDE_BLOCK ] : [ ] } ; cache : string [ ] | null = null ; lastRectangle : Rectangle | null = null ; constructor ( params = { } ) { const L = Math . pow ( 4 , MAX_LEVEL ) ; this . data = new Float32Array ( BLOCKS * ( ( 4 * L - 1 ) / 3 ) ) ; if ( params . boundaries ) this . resize ( params . boundaries ) ; else this . resize ( { x : 0 , y : 0 , width : 1 , height : 1 , } ) ; } add ( key , x , y , size ) { insertNode ( MAX_LEVEL , this . data , this . containers , key , x , y , size ) ; return this ; } resize ( boundaries ) { this . clear ( ) ; this . data [ X_OFFSET ] = boundaries . x ; this . data [ Y_OFFSET ] = boundaries . y ; this . data [ WIDTH_OFFSET ] = boundaries . width ; this . data [ HEIGHT_OFFSET ] = boundaries . height ; buildQuadrants ( MAX_LEVEL , this . data ) ; } clear ( ) { this . containers = { [ OUTSIDE_BLOCK ] : [ ] } ; return this ; } point ( x , y ) { const nodes = this . containers [ OUTSIDE_BLOCK ] ; let block = 0 , level = 0 ; do { if ( this . containers [ block ] ) nodes . push ( ... this . containers [ block ] ) ; const quad = pointIsInQuad ( x , y , this . data [ block + X_OFFSET ] , this . data [ block + Y_OFFSET ] , this . data [ block + WIDTH_OFFSET ] , this . data [ block + HEIGHT_OFFSET ] ) ; block = 4 * block + quad * BLOCKS ; level ++ ; } while ( level <= MAX_LEVEL ) ; return nodes ; } rectangle ( x1 , y1 , x2 , y2 , height ) { const lr = this . lastRectangle ; if ( lr && x1 === lr . x1 && x2 === lr . x2 && y1 === lr . y1 && y2 === lr . y2 && height === lr . height ) { return this . cache as string [ ] ; } this . lastRectangle = { x1 , y1 , x2 , y2 , height , } ; if ( ! isRectangleAligned ( this . lastRectangle ) ) this . lastRectangle = getCircumscribedAlignedRectangle ( this . lastRectangle ) ; this . cache = getNodesInAxisAlignedRectangleArea ( MAX_LEVEL , this . data , this . containers , x1 , y1 , Math . abs ( x1 - x2 ) || Math . abs ( y1 - y2 ) , height ) ; this . cache . push ( ... this . containers [ OUTSIDE_BLOCK ] ) ; return this . cache ; } }