1 | /*
|
2 | * Copyright (C) 1998-2021 by Northwoods Software Corporation. All Rights Reserved.
|
3 | */
|
4 | import * as go from '../release/go-module.js';
|
5 | /**
|
6 | * @hidden @internal
|
7 | */
|
8 | class QuadNode {
|
9 | constructor(bounds, parent, level) {
|
10 | this.objects = [];
|
11 | this.treeObjects = [];
|
12 | this.totalObjects = 0; // total in this node + in all children (recursively)
|
13 | this.nodes = [null, null, null, null];
|
14 | this.bounds = bounds;
|
15 | this.parent = parent;
|
16 | this.level = level;
|
17 | }
|
18 | split() {
|
19 | const w2 = this.bounds.width / 2;
|
20 | const h2 = this.bounds.height / 2;
|
21 | const x = this.bounds.x;
|
22 | const y = this.bounds.y;
|
23 | this.nodes[0] = new QuadNode(new go.Rect(x + w2, y, w2, h2), this, this.level + 1);
|
24 | this.nodes[1] = new QuadNode(new go.Rect(x, y, w2, h2), this, this.level + 1);
|
25 | this.nodes[2] = new QuadNode(new go.Rect(x, y + h2, w2, h2), this, this.level + 1);
|
26 | this.nodes[3] = new QuadNode(new go.Rect(x + w2, y + h2, w2, h2), this, this.level + 1);
|
27 | }
|
28 | clear() {
|
29 | this.treeObjects = [];
|
30 | this.objects = [];
|
31 | this.totalObjects = 0;
|
32 | for (let i = 0; i < this.nodes.length; i++) {
|
33 | const n = this.nodes[i];
|
34 | if (n !== null) {
|
35 | n.clear();
|
36 | this.nodes[i] = null;
|
37 | }
|
38 | }
|
39 | }
|
40 | }
|
41 | /**
|
42 | * @internal @hidden
|
43 | * Object to be contained by the {@link Quadtree} class. This object needs
|
44 | * to have rectangular bounds (described by an {@link Rect} object), as well
|
45 | * as something (of any type) associated with it.
|
46 | */
|
47 | class QuadObj {
|
48 | constructor(bounds, obj) {
|
49 | this.bounds = bounds;
|
50 | this.obj = obj;
|
51 | }
|
52 | }
|
53 | /**
|
54 | * Implementation of the quadtree data structure using the {@link Rect} class.
|
55 | * Each Quadtree has defined bounds found at {@link #bounds}, an array
|
56 | * of member rectangles, and an array of child nodes
|
57 | * (Quadtrees themselves). If the Quadtree has no
|
58 | * children, the nodes array will have four nulls. To construct a Quadtree, you
|
59 | * can call its constructor with no arguments. Then, to insert a rectangle, call
|
60 | * {@link #add}. This tree supports adding points (rectangles with 0
|
61 | * width and height), segments (rectangles with either 0 width or 0 height), and
|
62 | * rectangles with nonzero widths and heights.
|
63 | *
|
64 | * Quadtrees can be used to calculate intersections extremely quickly between a
|
65 | * given rectangle and all of the rectangles in the quadtree. Use of this data
|
66 | * structure prevents having to do precise intersection calculations for every
|
67 | * rectangle in the tree. To calculate all of the rectangular intersections for
|
68 | * a given rectangle, use {@link #intersecting}.
|
69 | *
|
70 | * Other common operations are detailed below.
|
71 | * @category Layout Extension
|
72 | */
|
73 | export class Quadtree {
|
74 | /**
|
75 | * In most cases, simply calling this constructor with no arguments will produce the desired behaviour.
|
76 | * @constructor
|
77 | * @param {number=} nodeCapacity The node capacity of this quadtree. This is the number of objects a node can contain before it splits. Defaults to 1.
|
78 | * @param {number=} maxLevel The maximum depth the Quadtree will allow before it will no longer split. Defaults to Infinity (no maximum depth).
|
79 | * @param {Rect=} bounds The bounding box surrounding the entire Quadtree. If the bounds are unset or a node is inserted outside of the bounds, the tree will automatically grow.
|
80 | */
|
81 | constructor(nodeCapacity, maxLevel, bounds) {
|
82 | /** @hidden @internal */ this._nodeCapacity = 1;
|
83 | /** @hidden @internal */ this._maxLevels = Infinity;
|
84 | /** @hidden @internal */ this._treeObjectMap = new go.Map();
|
85 | // we can avoid unnecessary work when adding objects if there are no objects with 0 width or height.
|
86 | // Note that after being set to true, these flags are not ever set again to false, even if all objects
|
87 | // with zero width/height are removed (assumption was made that this should almost never matter)
|
88 | /** @hidden @internal */ this._hasZeroWidthObject = false;
|
89 | /** @hidden @internal */ this._hasZeroHeightObject = false;
|
90 | if (nodeCapacity) {
|
91 | this._nodeCapacity = nodeCapacity;
|
92 | }
|
93 | if (maxLevel) {
|
94 | this._maxLevels = maxLevel;
|
95 | }
|
96 | if (bounds === undefined) {
|
97 | bounds = new go.Rect();
|
98 | }
|
99 | this._root = new QuadNode(bounds, null, 0);
|
100 | }
|
101 | /**
|
102 | * Gets the node capacity of this quadtree. This is the number of objects a node can contain before it splits.
|
103 | */
|
104 | get nodeCapacity() { return this._nodeCapacity; }
|
105 | /**
|
106 | * Gets the maximum depth the Quadtree will allow before it will no longer split..
|
107 | */
|
108 | get maxLevels() { return this._maxLevels; }
|
109 | /**
|
110 | * Gets the boundaries of the node. All nodes should be square.
|
111 | */
|
112 | get bounds() { return this._root.bounds; }
|
113 | /**
|
114 | * Gets the root node of the tree
|
115 | */
|
116 | get root() { return this._root; }
|
117 | /**
|
118 | * Clears the Quadtree, removing all objects and children nodes. Keeps the current bounds of the root node.
|
119 | * @this {Quadtree}
|
120 | * @return {void}
|
121 | */
|
122 | clear() {
|
123 | this._root.clear();
|
124 | this._treeObjectMap.clear();
|
125 | }
|
126 | /**
|
127 | * @hidden @internal
|
128 | * Returns a list of possible quadrants that the given rect could be in
|
129 | * @this {Quadtree}
|
130 | * @param {Rect} rect the rectangle to test
|
131 | * @return {Array<number>}
|
132 | */
|
133 | _getQuadrants(rect, node) {
|
134 | const quadrants = [];
|
135 | const horizontalMidpoint = node.bounds.x + (node.bounds.width / 2);
|
136 | const verticalMidpoint = node.bounds.y + (node.bounds.height / 2);
|
137 | const topQuadrant = rect.y <= verticalMidpoint;
|
138 | const bottomQuadrant = rect.y + rect.height >= verticalMidpoint;
|
139 | if (rect.x <= horizontalMidpoint) {
|
140 | if (topQuadrant) {
|
141 | quadrants.push(1);
|
142 | }
|
143 | if (bottomQuadrant) {
|
144 | quadrants.push(2);
|
145 | }
|
146 | }
|
147 | if (rect.x + rect.width >= horizontalMidpoint) {
|
148 | if (topQuadrant) {
|
149 | quadrants.push(0);
|
150 | }
|
151 | if (bottomQuadrant) {
|
152 | quadrants.push(3);
|
153 | }
|
154 | }
|
155 | return quadrants;
|
156 | }
|
157 | /**
|
158 | * @hidden @internal
|
159 | * Determine which node the rect belongs to. -1 means rect
|
160 | * cannot completely fit within a child node and is part of
|
161 | * the parent node. This function avoids some additional
|
162 | * calculations by assuming that the rect is contained entirely
|
163 | * within the parent node's bounds.
|
164 | * @this {Quadtree}
|
165 | * @param {Rect} rect the rect to test
|
166 | * @return {number}
|
167 | */
|
168 | _getIndex(rect, node) {
|
169 | let index = -1;
|
170 | if (node.bounds === undefined) { // the quadtree is empty
|
171 | return index;
|
172 | }
|
173 | const horizontalMidpoint = node.bounds.x + (node.bounds.width / 2);
|
174 | const verticalMidpoint = node.bounds.y + (node.bounds.height / 2);
|
175 | const topQuadrant = rect.y <= verticalMidpoint && rect.y + rect.height <= verticalMidpoint;
|
176 | const bottomQuadrant = rect.y >= verticalMidpoint;
|
177 | if (rect.x + rect.width <= horizontalMidpoint) {
|
178 | if (topQuadrant) {
|
179 | index = 1;
|
180 | }
|
181 | else if (bottomQuadrant) {
|
182 | index = 2;
|
183 | }
|
184 | }
|
185 | else if (rect.x >= horizontalMidpoint) {
|
186 | if (topQuadrant) {
|
187 | index = 0;
|
188 | }
|
189 | else if (bottomQuadrant) {
|
190 | index = 3;
|
191 | }
|
192 | }
|
193 | return index;
|
194 | }
|
195 | /**
|
196 | * Insert the object into the quadtree. If the node
|
197 | * exceeds the capacity, it will split and add all
|
198 | * objects to their corresponding nodes. If the object is
|
199 | * outside the bounds of the tree's root node, the tree
|
200 | * will grow to accomodate it. Possibly restructures the
|
201 | * tree if a more efficient configuration can be found with
|
202 | * the new dimensions. Bounds can be given either as a
|
203 | * single {@link Rect} or as any combination of arguments
|
204 | * which is valid for the {@link Rect} constructor.
|
205 | * @this {Quadtree}
|
206 | * @param {T} obj the object to insert
|
207 | * @param {Rect|Point|number} x The Rect bounds of the object, or top-left Point, or x value.
|
208 | * @param {Point|Size|number} y Bottom-right Point or Size or y value.
|
209 | * @param {number} w Width to be used if x,y are specified;
|
210 | * must be non-negative.
|
211 | * @param {number} h Height to be used if x,y are specified;
|
212 | * @return {void}
|
213 | */
|
214 | add(obj, x, y, w, h) {
|
215 | let bounds;
|
216 | if (!(obj instanceof QuadObj) && (x === undefined || x === null)) {
|
217 | throw new Error('Invalid bounds for added object');
|
218 | }
|
219 | if (x instanceof go.Rect) {
|
220 | bounds = x.copy();
|
221 | }
|
222 | else {
|
223 | bounds = new go.Rect(x, y, w, h);
|
224 | }
|
225 | let treeObj;
|
226 | if (obj instanceof QuadObj) {
|
227 | treeObj = obj;
|
228 | obj = treeObj.obj;
|
229 | bounds = treeObj.bounds;
|
230 | }
|
231 | else {
|
232 | treeObj = new QuadObj(bounds, obj);
|
233 | }
|
234 | if (isNaN(bounds.x) || bounds.x === Infinity ||
|
235 | isNaN(bounds.y) || bounds.y === Infinity ||
|
236 | isNaN(bounds.width) || bounds.width === Infinity ||
|
237 | isNaN(bounds.height) || bounds.height === Infinity) {
|
238 | throw new Error('Invalid rectangle, contains NaN or Infinity properties');
|
239 | }
|
240 | this._hasZeroWidthObject = this._hasZeroWidthObject || bounds.width === 0;
|
241 | this._hasZeroHeightObject = this._hasZeroHeightObject || bounds.height === 0;
|
242 | // initialize bounds of tree as the max width or height of the first object added
|
243 | if (this._root.bounds.width === 0 || this._root.bounds.height === 0) {
|
244 | const len = Math.max(bounds.width, bounds.height);
|
245 | this._root.bounds = new go.Rect(bounds.x, bounds.y, len, len);
|
246 | }
|
247 | // fixes quadtree having a width and height of 0 if the first object added is a point
|
248 | // this will only be called after a second object is added, the new width/height is the maximum distance between them
|
249 | if (this._root.bounds !== undefined && (this._root.bounds.width === 0 || this._root.bounds.height === 0)) {
|
250 | const len = Math.max(Math.abs(bounds.x - this._root.bounds.x), Math.abs(bounds.y - this._root.bounds.y));
|
251 | this._root.bounds = new go.Rect(Math.min(this._root.bounds.x, bounds.x), Math.min(this._root.bounds.y, bounds.y), len, len);
|
252 | }
|
253 | // map the object to its corresponding QuadObj (so that the bounds of this object can be retrieved later)
|
254 | this._treeObjectMap.add(obj, treeObj);
|
255 | // grow as many times as necessary to fit the new object
|
256 | while (!this._root.bounds.containsRect(bounds)) {
|
257 | const old = this._root;
|
258 | this.walk(n => n.level++, old);
|
259 | const intersectsTopBound = bounds.y < this._root.bounds.y;
|
260 | const intersectsBottomBound = bounds.y + bounds.height > this._root.bounds.y + this._root.bounds.height;
|
261 | const intersectsRightBound = bounds.x + bounds.width > this._root.bounds.x + this._root.bounds.width;
|
262 | const intersectsLeftBound = bounds.x < this._root.bounds.x;
|
263 | if ((intersectsTopBound && intersectsRightBound) || (intersectsTopBound && !intersectsLeftBound)) {
|
264 | /* _______
|
265 | * | 1 | 0 |
|
266 | * |___|___|
|
267 | * |old| 3 |
|
268 | * |___|___|
|
269 | */
|
270 | const newBounds = new go.Rect(this._root.bounds.x, this._root.bounds.y - this._root.bounds.height, this._root.bounds.width * 2, this._root.bounds.height * 2);
|
271 | this._root = new QuadNode(newBounds, null, 0);
|
272 | this._root.split();
|
273 | this._root.nodes[2] = old;
|
274 | this._root.totalObjects = old.totalObjects;
|
275 | old.parent = this._root;
|
276 | this._restructure(old);
|
277 | this._restructureLevels(old);
|
278 | if (this._hasZeroHeightObject) {
|
279 | this._fixTopObjectPlacement(old);
|
280 | }
|
281 | }
|
282 | else if (intersectsTopBound && intersectsLeftBound) {
|
283 | /* _______
|
284 | * | 1 | 0 |
|
285 | * |___|___|
|
286 | * | 2 |old|
|
287 | * |___|___|
|
288 | */
|
289 | const newBounds = new go.Rect(this._root.bounds.x - this._root.bounds.width, this._root.bounds.y - this._root.bounds.height, this._root.bounds.width * 2, this._root.bounds.height * 2);
|
290 | this._root = new QuadNode(newBounds, null, 0);
|
291 | this._root.split();
|
292 | this._root.nodes[3] = old;
|
293 | this._root.totalObjects = old.totalObjects;
|
294 | old.parent = this._root;
|
295 | this._restructure(old);
|
296 | this._restructureLevels(old);
|
297 | if (this._hasZeroWidthObject) {
|
298 | this._fixLeftObjectPlacement(old);
|
299 | }
|
300 | if (this._hasZeroHeightObject) {
|
301 | this._fixTopObjectPlacement(old);
|
302 | }
|
303 | }
|
304 | else if ((intersectsBottomBound && intersectsRightBound) || ((intersectsRightBound || intersectsBottomBound) && !intersectsLeftBound)) {
|
305 | /* _______
|
306 | * |old| 0 |
|
307 | * |___|___|
|
308 | * | 2 | 3 |
|
309 | * |___|___|
|
310 | */
|
311 | const newBounds = new go.Rect(this._root.bounds.x, this._root.bounds.y, this._root.bounds.width * 2, this._root.bounds.height * 2);
|
312 | this._root = new QuadNode(newBounds, null, 0);
|
313 | this._root.split();
|
314 | this._root.nodes[1] = old;
|
315 | this._root.totalObjects = old.totalObjects;
|
316 | old.parent = this._root;
|
317 | this._restructure(old);
|
318 | this._restructureLevels(old);
|
319 | }
|
320 | else if ((intersectsBottomBound && intersectsLeftBound) || intersectsLeftBound) {
|
321 | /* _______
|
322 | * | 1 |old|
|
323 | * |___|___|
|
324 | * | 2 | 3 |
|
325 | * |___|___|
|
326 | */
|
327 | const newBounds = new go.Rect(this._root.bounds.x - this._root.bounds.width, this._root.bounds.y, this._root.bounds.width * 2, this._root.bounds.height * 2);
|
328 | this._root = new QuadNode(newBounds, null, 0);
|
329 | this._root.split();
|
330 | this._root.nodes[0] = old;
|
331 | this._root.totalObjects = old.totalObjects;
|
332 | old.parent = this._root;
|
333 | this._restructure(old);
|
334 | this._restructureLevels(old);
|
335 | if (this._hasZeroWidthObject) {
|
336 | this._fixLeftObjectPlacement(old);
|
337 | }
|
338 | }
|
339 | }
|
340 | // add the object to the tree
|
341 | this._addHelper(this._root, treeObj);
|
342 | }
|
343 | /**
|
344 | * @hidden @internal
|
345 | * Helper function to recursively perform the add operation
|
346 | * on the tree.
|
347 | * @this {Quadtree}
|
348 | * @param {QuadNode<T>} root the current node being operated on
|
349 | * @param {QuadObj<T>} treeObj the object being added
|
350 | * @return {void}
|
351 | */
|
352 | _addHelper(root, treeObj) {
|
353 | root.totalObjects++;
|
354 | if (root.nodes[0]) {
|
355 | const index = this._getIndex(treeObj.bounds, root);
|
356 | if (index !== -1) {
|
357 | const selected = root.nodes[index];
|
358 | if (selected !== null) {
|
359 | this._addHelper(selected, treeObj);
|
360 | return;
|
361 | }
|
362 | }
|
363 | }
|
364 | root.treeObjects.push(treeObj);
|
365 | root.objects.push(treeObj.obj);
|
366 | if (root.treeObjects.length > this._nodeCapacity && root.level < this._maxLevels) {
|
367 | if (!root.nodes[0]) {
|
368 | root.split();
|
369 | }
|
370 | let i = 0;
|
371 | while (i < root.treeObjects.length) {
|
372 | const index = this._getIndex(root.treeObjects[i].bounds, root);
|
373 | if (index !== -1 && !(root.treeObjects[i].bounds.width === 0 || root.treeObjects[i].bounds.height === 0)) {
|
374 | root.objects.splice(i, 1);
|
375 | const selected = root.nodes[index];
|
376 | if (selected !== null) {
|
377 | this._addHelper(selected, root.treeObjects.splice(i, 1)[0]);
|
378 | }
|
379 | }
|
380 | else {
|
381 | i++;
|
382 | }
|
383 | }
|
384 | }
|
385 | }
|
386 | /**
|
387 | * @hidden @internal
|
388 | * Recursively moves objects placed on the right side of a vertical border
|
389 | * between two nodes to the left side of the vertical border. This allows
|
390 | * them to be located by {@link #_getIndex}. This function is called
|
391 | * after an {@link #add} call grows the Quadtree, but only if there
|
392 | * are 0 width objects in the tree.
|
393 | * @this {Quadtree}
|
394 | * @param {QuadNode<T>} root the current root node being operated on
|
395 | * @return {void}
|
396 | */
|
397 | _fixLeftObjectPlacement(root) {
|
398 | const nw = root.nodes[1];
|
399 | if (nw !== null) { // if root is split
|
400 | this._fixLeftObjectPlacement(nw); // NW
|
401 | const sw = root.nodes[2];
|
402 | if (sw !== null) {
|
403 | this._fixLeftObjectPlacement(sw); // SW
|
404 | }
|
405 | }
|
406 | const toRemove = [];
|
407 | const toAdd = [];
|
408 | for (let i = 0; i < root.objects.length; i++) {
|
409 | const obj = root.treeObjects[i];
|
410 | if (obj.bounds.width === 0 && obj.bounds.x === root.bounds.x) {
|
411 | toRemove.push(i);
|
412 | toAdd.push(obj);
|
413 | }
|
414 | }
|
415 | this._removeFromOwner(root, toRemove);
|
416 | for (const obj of toAdd) {
|
417 | this.add(obj.obj, obj.bounds);
|
418 | }
|
419 | }
|
420 | /**
|
421 | * @hidden @internal
|
422 | * Recursively moves objects placed on the bottom side of a horizontal border
|
423 | * between two nodes to the top side of the vertical border. This allows
|
424 | * them to be located by {@link #_getIndex}. This function is called
|
425 | * after an {@link #add} call grows the Quadtree, but only if there
|
426 | * are 0 height objects in the tree.
|
427 | * @this {Quadtree}
|
428 | * @param {QuadNode<T>} root the current root node being operated on
|
429 | * @return {void}
|
430 | */
|
431 | _fixTopObjectPlacement(root) {
|
432 | const ne = root.nodes[0];
|
433 | if (ne !== null) { // if root is split
|
434 | this._fixTopObjectPlacement(ne); // NE
|
435 | const nw = root.nodes[1];
|
436 | if (nw !== null) {
|
437 | this._fixTopObjectPlacement(nw); // NW
|
438 | }
|
439 | }
|
440 | const toRemove = [];
|
441 | const toAdd = [];
|
442 | for (let i = 0; i < root.objects.length; i++) {
|
443 | const obj = root.treeObjects[i];
|
444 | if (obj.bounds.height === 0 && obj.bounds.y === root.bounds.y) {
|
445 | toRemove.push(i);
|
446 | toAdd.push(obj);
|
447 | }
|
448 | }
|
449 | this._removeFromOwner(root, toRemove);
|
450 | for (const obj of toAdd) {
|
451 | this.add(obj);
|
452 | }
|
453 | }
|
454 | /**
|
455 | * @hidden @internal
|
456 | * Moves all objects from a leaf node to its parent and unsplits.
|
457 | * Used after growing the tree when level>max level.
|
458 | * @this {Quadtree}
|
459 | * @param {QuadNode<T>} node the leaf node to restructure
|
460 | * @return {void}
|
461 | */
|
462 | _restructureLevels(node) {
|
463 | if (node && this._maxLevels < Infinity && node.nodes[0] !== null) {
|
464 | if (node.level >= this._maxLevels) {
|
465 | for (let i = 0; i < node.nodes.length; i++) {
|
466 | const selected = node.nodes[i];
|
467 | if (selected !== null) {
|
468 | node.objects.push.apply(node.objects, selected.objects);
|
469 | node.treeObjects.push.apply(node.treeObjects, selected.treeObjects);
|
470 | selected.clear();
|
471 | node.nodes[i] = null;
|
472 | }
|
473 | }
|
474 | }
|
475 | else {
|
476 | for (let i = 0; i < node.nodes.length; i++) {
|
477 | const selected = node.nodes[i];
|
478 | if (selected !== null) {
|
479 | this._restructureLevels(selected);
|
480 | }
|
481 | }
|
482 | }
|
483 | }
|
484 | }
|
485 | /**
|
486 | * Return the node that contains the given object.
|
487 | * @this {Quadtree}
|
488 | * @param {T} obj the object to find
|
489 | * @return {QuadNode<T>} the node containing the given object, null if the object is not found
|
490 | */
|
491 | find(obj) {
|
492 | const treeObj = this._treeObjectMap.get(obj);
|
493 | if (treeObj) {
|
494 | return this._findHelper(this._root, treeObj);
|
495 | }
|
496 | return null;
|
497 | }
|
498 | _findHelper(root, treeObj) {
|
499 | for (const object of root.treeObjects) {
|
500 | if (object === treeObj) {
|
501 | return root;
|
502 | }
|
503 | }
|
504 | const index = this._getIndex(treeObj.bounds, root);
|
505 | const selected = index === -1 ? null : root.nodes[index];
|
506 | if (selected !== null) {
|
507 | const result = this._findHelper(selected, treeObj);
|
508 | if (result) {
|
509 | return result;
|
510 | }
|
511 | }
|
512 | return null;
|
513 | }
|
514 | /**
|
515 | * Convenience method, calls {@link #find} and returns a boolean
|
516 | * indicating whether or not the tree contains the given object
|
517 | * @this {Quadtree}
|
518 | * @param {T} obj the object to check for
|
519 | * @return {boolean} whether or not the given object is present in the tree
|
520 | */
|
521 | has(obj) {
|
522 | return !!this.find(obj);
|
523 | }
|
524 | /**
|
525 | * Checks if any of the objects in the tree have the given boundaries
|
526 | * @this {Quadtree}
|
527 | * @param {Rect} bounds the rectangle to check for
|
528 | * @return {Rect} the actual bounds object stored in the tree
|
529 | */
|
530 | findBounds(bounds) {
|
531 | if (bounds) {
|
532 | return this._findBoundsHelper(this._root, bounds);
|
533 | }
|
534 | return null;
|
535 | }
|
536 | _findBoundsHelper(root, bounds) {
|
537 | for (const object of root.treeObjects) {
|
538 | if (bounds.equalsApprox(object.bounds)) {
|
539 | return bounds;
|
540 | }
|
541 | }
|
542 | const index = this._getIndex(bounds, root);
|
543 | const selected = index === -1 ? null : root.nodes[index];
|
544 | if (selected !== null) {
|
545 | return this._findBoundsHelper(selected, bounds);
|
546 | }
|
547 | return null;
|
548 | }
|
549 | /**
|
550 | * Remove the given object from the tree, restructuring to
|
551 | * get rid of empty nodes that are unneeded.
|
552 | * @this {Quadtree}
|
553 | * @param {T} obj the object to remove
|
554 | * @return {boolean} whether or not the deletion was successful. False when the object is not in the tree.
|
555 | */
|
556 | remove(obj) {
|
557 | const treeObj = this._treeObjectMap.get(obj);
|
558 | if (treeObj) {
|
559 | const owner = this._findHelper(this._root, treeObj);
|
560 | if (owner) {
|
561 | owner.treeObjects.splice(owner.treeObjects.indexOf(treeObj), 1);
|
562 | owner.objects.splice(owner.objects.indexOf(obj), 1);
|
563 | owner.totalObjects--;
|
564 | this._treeObjectMap.remove(obj);
|
565 | let parent = owner.parent;
|
566 | while (parent) {
|
567 | parent.totalObjects--;
|
568 | parent = parent.parent;
|
569 | }
|
570 | if (owner.nodes[0] && owner.totalObjects <= this._nodeCapacity) {
|
571 | this._addChildObjectsToNode(owner, owner);
|
572 | for (let i = 0; i < owner.nodes.length; i++) {
|
573 | const selected = owner.nodes[i];
|
574 | if (selected !== null) {
|
575 | selected.clear();
|
576 | }
|
577 | owner.nodes[i] = null;
|
578 | }
|
579 | }
|
580 | this._restructure(owner);
|
581 | return true;
|
582 | }
|
583 | }
|
584 | return false;
|
585 | }
|
586 | /**
|
587 | * Removes multiple objects at the given indices from the given owner. Similar
|
588 | * to the normal remove function, but much faster when the owner and indices are
|
589 | * already known.
|
590 | * @this {Quadtree}
|
591 | * @param {QuadNode<T>} owner the node to remove objects from
|
592 | * @param {Array<number>} indexes the indices to remove. Should be given in ascending order.
|
593 | */
|
594 | _removeFromOwner(owner, indexes) {
|
595 | if (indexes.length === 0) {
|
596 | return;
|
597 | }
|
598 | for (let i = indexes.length - 1; i >= 0; i--) {
|
599 | this._treeObjectMap.remove(owner.objects[indexes[i]]);
|
600 | owner.treeObjects.splice(indexes[i], 1);
|
601 | owner.objects.splice(indexes[i], 1);
|
602 | }
|
603 | owner.totalObjects -= indexes.length;
|
604 | let parent = owner.parent;
|
605 | while (parent) {
|
606 | parent.totalObjects -= indexes.length;
|
607 | parent = parent.parent;
|
608 | }
|
609 | if (owner.nodes[0] && owner.totalObjects <= this._nodeCapacity) {
|
610 | this._addChildObjectsToNode(owner, owner);
|
611 | for (let i = 0; i < owner.nodes.length; i++) {
|
612 | const selected = owner.nodes[i];
|
613 | if (selected !== null) {
|
614 | selected.clear();
|
615 | }
|
616 | owner.nodes[i] = null;
|
617 | }
|
618 | }
|
619 | this._restructure(owner);
|
620 | }
|
621 | /**
|
622 | * @hidden @internal
|
623 | * Recursively adds all objects from children of the given
|
624 | * root tree to the given owner tree
|
625 | * Used internally by {@link #remove}
|
626 | * @this {Quadtree}
|
627 | * @param {Quadtree} owner the tree to add objects to
|
628 | * @return {void}
|
629 | */
|
630 | _addChildObjectsToNode(owner, root) {
|
631 | for (const node of root.nodes) {
|
632 | if (node) {
|
633 | owner.treeObjects.push.apply(owner.treeObjects, node.treeObjects);
|
634 | owner.objects.push.apply(owner.objects, node.objects);
|
635 | this._addChildObjectsToNode(owner, node);
|
636 | }
|
637 | }
|
638 | }
|
639 | /**
|
640 | * @hidden @internal
|
641 | * Recursively combines parent nodes that should be split, all the way
|
642 | * up the tree. Starts from the given node.
|
643 | * @this {Quadtree}
|
644 | * @return {void}
|
645 | */
|
646 | _restructure(root) {
|
647 | const parent = root.parent;
|
648 | if (parent) {
|
649 | // if none of the child nodes have any objects, the parent should not be split
|
650 | let childrenHaveNoObjects = true;
|
651 | for (const node of parent.nodes) {
|
652 | if (node !== null && node.totalObjects > 0) {
|
653 | childrenHaveNoObjects = false;
|
654 | break;
|
655 | }
|
656 | }
|
657 | // unsplit children and move nodes to parent
|
658 | if (parent.totalObjects <= this._nodeCapacity || childrenHaveNoObjects) {
|
659 | for (let i = 0; i < parent.nodes.length; i++) {
|
660 | const selected = parent.nodes[i];
|
661 | if (selected !== null) {
|
662 | parent.objects.push.apply(parent.objects, selected.objects);
|
663 | parent.treeObjects.push.apply(parent.treeObjects, selected.treeObjects);
|
664 | selected.clear();
|
665 | parent.nodes[i] = null;
|
666 | }
|
667 | }
|
668 | this._restructure(parent);
|
669 | }
|
670 | }
|
671 | }
|
672 | /**
|
673 | * Can be called as either (obj, x, y) or (obj, point). Translate
|
674 | * the given object to given x and y coordinates or to a given {@link Point}.
|
675 | * @this {Quadtree}
|
676 | * @param {T} obj the object to move
|
677 | * @param {number|Point} x the x coordinate or Point to move the object to
|
678 | * @param {number} y the y coordinate to move the object to
|
679 | * @return {boolean} whether or not the move was successful. False if the object was not in the tree.
|
680 | */
|
681 | move(obj, x, y) {
|
682 | const treeObj = this._treeObjectMap.get(obj);
|
683 | if (treeObj && this.remove(obj)) {
|
684 | if (x instanceof go.Point) {
|
685 | treeObj.bounds.x = x.x;
|
686 | treeObj.bounds.y = x.y;
|
687 | }
|
688 | else if (y !== undefined) {
|
689 | treeObj.bounds.x = x;
|
690 | treeObj.bounds.y = y;
|
691 | }
|
692 | else {
|
693 | throw new Error('Please provide the position as either a Point or two numbers');
|
694 | }
|
695 | this.add(treeObj);
|
696 | return true;
|
697 | }
|
698 | return false;
|
699 | }
|
700 | /**
|
701 | * Can be called as either (obj, width, height) or (obj, size). Resize
|
702 | * the given object to given width and height or to a given {@link Size}.
|
703 | * @this {Quadtree}
|
704 | * @param {T} obj the object to resize
|
705 | * @param {number|Size} width the width or Size to resize the object to
|
706 | * @param {number} height the height to resize the object to
|
707 | * @return {boolean} whether or not the resize was successful. False if the object was not in the tree.
|
708 | */
|
709 | resize(obj, width, height) {
|
710 | const treeObj = this._treeObjectMap.get(obj);
|
711 | if (treeObj && this.remove(obj)) {
|
712 | if (width instanceof go.Size) {
|
713 | treeObj.bounds.width = width.width;
|
714 | treeObj.bounds.height = width.height;
|
715 | }
|
716 | else if (height !== undefined) {
|
717 | treeObj.bounds.width = width;
|
718 | treeObj.bounds.height = height;
|
719 | }
|
720 | else {
|
721 | throw new Error('Please provide the size as either a Size or two numbers');
|
722 | }
|
723 | this.add(treeObj);
|
724 | return true;
|
725 | }
|
726 | return false;
|
727 | }
|
728 | /**
|
729 | * Updates the given object to have the bounds given, provided as either a
|
730 | * {@link Rect} or x, y, width, and height.
|
731 | * @this {Quadtree}
|
732 | * @param obj the object to change the bounds of
|
733 | * @param x the x-coordinate or Rect to set the object to
|
734 | * @param y the y-coordinate to set the object to, unnecessary if a Rect was given
|
735 | * @param width the width to set the object to, unnecessary if a Rect was given
|
736 | * @param height the height to set the object to, unnecessary if a Rect was given
|
737 | */
|
738 | setTo(obj, x, y, width, height) {
|
739 | const treeObj = this._treeObjectMap.get(obj);
|
740 | if (treeObj && this.remove(obj)) {
|
741 | if (x instanceof go.Rect) {
|
742 | treeObj.bounds.set(x);
|
743 | }
|
744 | else if (y !== undefined && width !== undefined && height !== undefined) {
|
745 | treeObj.bounds.setTo(x, y, width, height);
|
746 | }
|
747 | else {
|
748 | throw new Error('Please provide new bounds as either a Rect or combination of four numbers (x, y, width, height)');
|
749 | }
|
750 | this.add(treeObj);
|
751 | return true;
|
752 | }
|
753 | return false;
|
754 | }
|
755 | /**
|
756 | * Return all objects that intersect (wholly or partially) with
|
757 | * the given {@link Rect} or {@link Point}. Touching edges and
|
758 | * objects overlapping by 1e-7 or less (to account for floating
|
759 | * point error) are both not considered intersections.
|
760 | * @this {Quadtree}
|
761 | * @param {Rect|Point} rect the Rect or Point to check intersections for. If a point is given, a Rect with size (0, 0) is created for intersection calculations.
|
762 | * @return {Array<T>} array containing all intersecting objects
|
763 | */
|
764 | intersecting(rect) {
|
765 | if (rect instanceof go.Point) {
|
766 | rect = new go.Rect(rect.x, rect.y, 0, 0);
|
767 | }
|
768 | const returnObjects = [];
|
769 | this._intersectingHelper(rect, this._root, returnObjects);
|
770 | return returnObjects;
|
771 | }
|
772 | _intersectingHelper(rect, root, returnObjects) {
|
773 | const index = this._getIndex(rect, root);
|
774 | const selected = index === -1 ? null : root.nodes[index];
|
775 | if (selected !== null) {
|
776 | this._intersectingHelper(rect, selected, returnObjects);
|
777 | }
|
778 | else if (root.nodes[0] !== null) {
|
779 | const quadrants = this._getQuadrants(rect, root);
|
780 | for (const quadrant of quadrants) {
|
781 | const node = root.nodes[quadrant];
|
782 | if (node !== null) {
|
783 | this._intersectingHelper(rect, node, returnObjects);
|
784 | }
|
785 | }
|
786 | }
|
787 | for (const obj of root.treeObjects) {
|
788 | if (Quadtree._rectsIntersect(obj.bounds, rect)) {
|
789 | returnObjects.push(obj.obj);
|
790 | }
|
791 | }
|
792 | }
|
793 | /**
|
794 | * @hidden @internal
|
795 | * Similar as {@link Rect.intersectsRect}, but doesn't count edges as intersections.
|
796 | * Also accounts for floating error (by returning false more often) up to an error of 1e-7.
|
797 | * Used by {@link #intersecting}.
|
798 | * @this {Quadtree}
|
799 | * @param {Rect} r1 first rectangle
|
800 | * @param {Rect} r2 second rectangle
|
801 | * @return {boolean} whether or not the two rectangles intersect
|
802 | */
|
803 | static _rectsIntersect(r1, r2) {
|
804 | return !(r2.left + 1e-7 >= r1.right || r2.right - 1e-7 <= r1.left || r2.top + 1e-7 >= r1.bottom || r2.bottom - 1e-7 <= r1.top);
|
805 | }
|
806 | /**
|
807 | * Return all objects that fully contain the given {@link Rect} or {@link Point}.
|
808 | * @this {Quadtree}
|
809 | * @param {Rect|Point} rect the Rect or Point to check containing for. If a point is given, a Rect with size (0, 0) is created for containment calculations.
|
810 | * @return {Array<T>} array containing all containing objects
|
811 | */
|
812 | containing(rect) {
|
813 | if (rect instanceof go.Point) {
|
814 | rect = new go.Rect(rect.x, rect.y, 0, 0);
|
815 | }
|
816 | const returnObjects = [];
|
817 | this._containingHelper(rect, this._root, returnObjects);
|
818 | return returnObjects;
|
819 | }
|
820 | _containingHelper(rect, root, returnObjects) {
|
821 | const index = this._getIndex(rect, root);
|
822 | const selected = index === -1 ? null : root.nodes[index];
|
823 | if (selected !== null) {
|
824 | this._containingHelper(rect, selected, returnObjects);
|
825 | }
|
826 | else if (root.nodes[0]) {
|
827 | const quadrants = this._getQuadrants(rect, root);
|
828 | for (const quadrant of quadrants) {
|
829 | const node = root.nodes[quadrant];
|
830 | if (node !== null) {
|
831 | this._containingHelper(rect, node, returnObjects);
|
832 | }
|
833 | }
|
834 | }
|
835 | for (const obj of root.treeObjects) {
|
836 | if (obj.bounds.containsRect(rect)) {
|
837 | returnObjects.push(obj.obj);
|
838 | }
|
839 | }
|
840 | }
|
841 | /**
|
842 | * Returns the square of the distance from the centers of the given objects
|
843 | * @this {Quadtree}
|
844 | * @param {T} obj1
|
845 | * @param {T} obj2
|
846 | * @return {number} square of the distance between the centers of obj1 and obj2
|
847 | */
|
848 | distanceSquared(obj1, obj2) {
|
849 | const owner1 = this.find(obj1);
|
850 | const owner2 = this.find(obj2);
|
851 | if (owner1 !== null && owner2 !== null) {
|
852 | const treeObj1 = this._treeObjectMap.get(obj1);
|
853 | const treeObj2 = this._treeObjectMap.get(obj2);
|
854 | if (treeObj1 !== null && treeObj2 !== null) {
|
855 | return treeObj1.bounds.center.distanceSquaredPoint(treeObj2.bounds.center);
|
856 | }
|
857 | }
|
858 | return -1;
|
859 | }
|
860 | /**
|
861 | * Recursively traverses the tree (depth first) and executes the
|
862 | * given callback on each node.
|
863 | * @this {Quadtree}
|
864 | * @param {function} callback the callback to execute on each node. Takes the form of (n: Quadtree) => void
|
865 | * @param {boolean} root whether or not to execute the callback on the root node as well. Defaults to true
|
866 | * @return {void}
|
867 | */
|
868 | walk(callback, node = this._root, root = true) {
|
869 | if (root) {
|
870 | root = false;
|
871 | callback(node);
|
872 | }
|
873 | for (const n of node.nodes) {
|
874 | if (n) {
|
875 | callback(n);
|
876 | this.walk(callback, n, root);
|
877 | }
|
878 | }
|
879 | }
|
880 | /**
|
881 | * Visits every object stored in the tree (depth first)
|
882 | * @this {Quadtree}
|
883 | * @param {function} callback the callback to execute on each object.
|
884 | * @return {void}
|
885 | */
|
886 | forEach(callback) {
|
887 | this.walk((n) => {
|
888 | for (const obj of n.objects) {
|
889 | callback(obj);
|
890 | }
|
891 | });
|
892 | }
|
893 | /**
|
894 | * Finds the most furthest object in each direction stored in the tree.
|
895 | * Bounds are tested using the center x and y coordinate.
|
896 | * @this {Quadtree}
|
897 | * @return {Array<T>} maximum and minimum objects in the tree, in the format [min x, max x, min y, max y].
|
898 | */
|
899 | findExtremeObjects() {
|
900 | const [extremes0, extremes1, extremes2, extremes3] = this._findExtremeObjectsHelper();
|
901 | return [
|
902 | extremes0 !== null ? extremes0.obj : null,
|
903 | extremes1 !== null ? extremes1.obj : null,
|
904 | extremes2 !== null ? extremes2.obj : null,
|
905 | extremes3 !== null ? extremes3.obj : null
|
906 | ];
|
907 | }
|
908 | /**
|
909 | * @hidden @internal
|
910 | * Recursive helper function for {@link #findExtremeObjects}
|
911 | * @this {Quadtree}
|
912 | * @param {QuadNode<T>} root the current root node being searched
|
913 | * @return {Array<QuadObj<T>>} maximum and minimum objects in the tree, in the format [min x, max x, min y, max y].
|
914 | */
|
915 | _findExtremeObjectsHelper(root = this._root) {
|
916 | let minX = null;
|
917 | let maxX = null;
|
918 | let minY = null;
|
919 | let maxY = null;
|
920 | if (root.nodes[0]) { // if root is split
|
921 | for (const node of root.nodes) {
|
922 | if (node !== null) {
|
923 | const [extremes0, extremes1, extremes2, extremes3] = this._findExtremeObjectsHelper(node);
|
924 | if (minX == null || (extremes0 !== null && extremes0.bounds.centerX < minX.bounds.centerX)) {
|
925 | minX = extremes0;
|
926 | }
|
927 | if (maxX === null || (extremes1 !== null && extremes1.bounds.centerX > maxX.bounds.centerX)) {
|
928 | maxX = extremes1;
|
929 | }
|
930 | if (minY === null || (extremes2 !== null && extremes2.bounds.centerY < minY.bounds.centerY)) {
|
931 | minY = extremes2;
|
932 | }
|
933 | if (maxY === null || (extremes3 !== null && extremes3.bounds.centerY > maxY.bounds.centerY)) {
|
934 | maxY = extremes3;
|
935 | }
|
936 | }
|
937 | }
|
938 | }
|
939 | for (const obj of root.treeObjects) {
|
940 | if (!minX || obj.bounds.centerX < minX.bounds.centerX) {
|
941 | minX = obj;
|
942 | }
|
943 | if (!maxX || obj.bounds.centerX > maxX.bounds.centerX) {
|
944 | maxX = obj;
|
945 | }
|
946 | if (!minY || obj.bounds.centerY < minY.bounds.centerY) {
|
947 | minY = obj;
|
948 | }
|
949 | if (!maxY || obj.bounds.centerY > maxY.bounds.centerY) {
|
950 | maxY = obj;
|
951 | }
|
952 | }
|
953 | return [minX, maxX, minY, maxY];
|
954 | }
|
955 | }
|