quadtree.ts 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
  1. const MAX_OBJECTS = 10;
  2. const MAX_LEVELS = 4;
  3. export type Quads = [Quadtree, Quadtree, Quadtree, Quadtree];
  4. export type Rect = { x: number; y: number; w: number; h: number; [_: string]: any };
  5. /**
  6. * @internal
  7. */
  8. export function pointWithin(px: number, py: number, rlft: number, rtop: number, rrgt: number, rbtm: number) {
  9. return px >= rlft && px <= rrgt && py >= rtop && py <= rbtm;
  10. }
  11. /**
  12. * @internal
  13. *
  14. * Determines if r2 is intersected by r1.
  15. */
  16. export function intersects(r1: Rect, r2: Rect) {
  17. return r1.x <= r2.x + r2.w && r1.x + r1.w >= r2.x && r1.y + r1.h >= r2.y && r1.y <= r2.y + r2.h;
  18. }
  19. /**
  20. * @internal
  21. */
  22. export class Quadtree {
  23. o: Rect[];
  24. q: Quads | null;
  25. constructor(public x: number, public y: number, public w: number, public h: number, public l: number = 0) {
  26. this.o = [];
  27. this.q = null;
  28. }
  29. split() {
  30. let t = this,
  31. x = t.x,
  32. y = t.y,
  33. w = t.w / 2,
  34. h = t.h / 2,
  35. l = t.l + 1;
  36. t.q = [
  37. // top right
  38. new Quadtree(x + w, y, w, h, l),
  39. // top left
  40. new Quadtree(x, y, w, h, l),
  41. // bottom left
  42. new Quadtree(x, y + h, w, h, l),
  43. // bottom right
  44. new Quadtree(x + w, y + h, w, h, l),
  45. ];
  46. }
  47. // invokes callback with index of each overlapping quad
  48. quads(x: number, y: number, w: number, h: number, cb: (q: Quadtree) => void) {
  49. let t = this,
  50. q = t.q!,
  51. hzMid = t.x + t.w / 2,
  52. vtMid = t.y + t.h / 2,
  53. startIsNorth = y < vtMid,
  54. startIsWest = x < hzMid,
  55. endIsEast = x + w > hzMid,
  56. endIsSouth = y + h > vtMid;
  57. // top-right quad
  58. startIsNorth && endIsEast && cb(q[0]);
  59. // top-left quad
  60. startIsWest && startIsNorth && cb(q[1]);
  61. // bottom-left quad
  62. startIsWest && endIsSouth && cb(q[2]);
  63. // bottom-right quad
  64. endIsEast && endIsSouth && cb(q[3]);
  65. }
  66. add(o: Rect) {
  67. let t = this;
  68. if (t.q != null) {
  69. t.quads(o.x, o.y, o.w, o.h, (q) => {
  70. q.add(o);
  71. });
  72. } else {
  73. let os = t.o;
  74. os.push(o);
  75. if (os.length > MAX_OBJECTS && t.l < MAX_LEVELS) {
  76. t.split();
  77. for (let i = 0; i < os.length; i++) {
  78. let oi = os[i];
  79. t.quads(oi.x, oi.y, oi.w, oi.h, (q) => {
  80. q.add(oi);
  81. });
  82. }
  83. t.o.length = 0;
  84. }
  85. }
  86. }
  87. get(x: number, y: number, w: number, h: number, cb: (o: Rect) => void) {
  88. let t = this;
  89. let os = t.o;
  90. for (let i = 0; i < os.length; i++) {
  91. cb(os[i]);
  92. }
  93. if (t.q != null) {
  94. t.quads(x, y, w, h, (q) => {
  95. q.get(x, y, w, h, cb);
  96. });
  97. }
  98. }
  99. clear() {
  100. this.o.length = 0;
  101. this.q = null;
  102. }
  103. }