Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
d3-quadtree
Advanced tools
d3-quadtree - npm Package Compare versions
Comparing version 1.0.1 to 1.0.2
@@ -1,2 +0,2 @@ | ||
| // https://d3js.org/d3-quadtree/ Version 1.0.1. Copyright 2016 Mike Bostock. | ||
| // https://d3js.org/d3-quadtree/ Version 1.0.2. Copyright 2016 Mike Bostock. | ||
| (function (global, factory) { | ||
@@ -6,431 +6,431 @@ typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) : | ||
| (factory((global.d3 = global.d3 || {}))); | ||
| }(this, function (exports) { 'use strict'; | ||
| }(this, (function (exports) { 'use strict'; | ||
| function tree_add(d) { | ||
| var x = +this._x.call(null, d), | ||
| y = +this._y.call(null, d); | ||
| return add(this.cover(x, y), x, y, d); | ||
| } | ||
| var tree_add = function(d) { | ||
| var x = +this._x.call(null, d), | ||
| y = +this._y.call(null, d); | ||
| return add(this.cover(x, y), x, y, d); | ||
| }; | ||
| function add(tree, x, y, d) { | ||
| if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points | ||
| function add(tree, x, y, d) { | ||
| if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points | ||
| var parent, | ||
| node = tree._root, | ||
| leaf = {data: d}, | ||
| x0 = tree._x0, | ||
| y0 = tree._y0, | ||
| x1 = tree._x1, | ||
| y1 = tree._y1, | ||
| xm, | ||
| ym, | ||
| xp, | ||
| yp, | ||
| right, | ||
| bottom, | ||
| i, | ||
| j; | ||
| var parent, | ||
| node = tree._root, | ||
| leaf = {data: d}, | ||
| x0 = tree._x0, | ||
| y0 = tree._y0, | ||
| x1 = tree._x1, | ||
| y1 = tree._y1, | ||
| xm, | ||
| ym, | ||
| xp, | ||
| yp, | ||
| right, | ||
| bottom, | ||
| i, | ||
| j; | ||
| // If the tree is empty, initialize the root as a leaf. | ||
| if (!node) return tree._root = leaf, tree; | ||
| // If the tree is empty, initialize the root as a leaf. | ||
| if (!node) return tree._root = leaf, tree; | ||
| // Find the existing leaf for the new point, or add it. | ||
| while (node.length) { | ||
| if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; | ||
| if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; | ||
| if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree; | ||
| } | ||
| // Find the existing leaf for the new point, or add it. | ||
| while (node.length) { | ||
| if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; | ||
| if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; | ||
| if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree; | ||
| } | ||
| // Is the new point is exactly coincident with the existing point? | ||
| xp = +tree._x.call(null, node.data); | ||
| yp = +tree._y.call(null, node.data); | ||
| if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree; | ||
| // Is the new point is exactly coincident with the existing point? | ||
| xp = +tree._x.call(null, node.data); | ||
| yp = +tree._y.call(null, node.data); | ||
| if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree; | ||
| // Otherwise, split the leaf node until the old and new point are separated. | ||
| do { | ||
| parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4); | ||
| if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; | ||
| if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; | ||
| } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm))); | ||
| return parent[j] = node, parent[i] = leaf, tree; | ||
| // Otherwise, split the leaf node until the old and new point are separated. | ||
| do { | ||
| parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4); | ||
| if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; | ||
| if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; | ||
| } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm))); | ||
| return parent[j] = node, parent[i] = leaf, tree; | ||
| } | ||
| function addAll(data) { | ||
| var d, i, n = data.length, | ||
| x, | ||
| y, | ||
| xz = new Array(n), | ||
| yz = new Array(n), | ||
| x0 = Infinity, | ||
| y0 = Infinity, | ||
| x1 = -Infinity, | ||
| y1 = -Infinity; | ||
| // Compute the points and their extent. | ||
| for (i = 0; i < n; ++i) { | ||
| if (isNaN(x = +this._x.call(null, d = data[i])) || isNaN(y = +this._y.call(null, d))) continue; | ||
| xz[i] = x; | ||
| yz[i] = y; | ||
| if (x < x0) x0 = x; | ||
| if (x > x1) x1 = x; | ||
| if (y < y0) y0 = y; | ||
| if (y > y1) y1 = y; | ||
| } | ||
| function addAll(data) { | ||
| var d, i, n = data.length, | ||
| x, | ||
| y, | ||
| xz = new Array(n), | ||
| yz = new Array(n), | ||
| x0 = Infinity, | ||
| y0 = Infinity, | ||
| x1 = -Infinity, | ||
| y1 = -Infinity; | ||
| // If there were no (valid) points, inherit the existing extent. | ||
| if (x1 < x0) x0 = this._x0, x1 = this._x1; | ||
| if (y1 < y0) y0 = this._y0, y1 = this._y1; | ||
| // Compute the points and their extent. | ||
| for (i = 0; i < n; ++i) { | ||
| if (isNaN(x = +this._x.call(null, d = data[i])) || isNaN(y = +this._y.call(null, d))) continue; | ||
| xz[i] = x; | ||
| yz[i] = y; | ||
| if (x < x0) x0 = x; | ||
| if (x > x1) x1 = x; | ||
| if (y < y0) y0 = y; | ||
| if (y > y1) y1 = y; | ||
| } | ||
| // Expand the tree to cover the new points. | ||
| this.cover(x0, y0).cover(x1, y1); | ||
| // If there were no (valid) points, inherit the existing extent. | ||
| if (x1 < x0) x0 = this._x0, x1 = this._x1; | ||
| if (y1 < y0) y0 = this._y0, y1 = this._y1; | ||
| // Add the new points. | ||
| for (i = 0; i < n; ++i) { | ||
| add(this, xz[i], yz[i], data[i]); | ||
| } | ||
| // Expand the tree to cover the new points. | ||
| this.cover(x0, y0).cover(x1, y1); | ||
| return this; | ||
| } | ||
| // Add the new points. | ||
| for (i = 0; i < n; ++i) { | ||
| add(this, xz[i], yz[i], data[i]); | ||
| } | ||
| var tree_cover = function(x, y) { | ||
| if (isNaN(x = +x) || isNaN(y = +y)) return this; // ignore invalid points | ||
| return this; | ||
| var x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1 = this._x1, | ||
| y1 = this._y1; | ||
| // If the quadtree has no extent, initialize them. | ||
| // Integer extent are necessary so that if we later double the extent, | ||
| // the existing quadrant boundaries don’t change due to floating point error! | ||
| if (isNaN(x0)) { | ||
| x1 = (x0 = Math.floor(x)) + 1; | ||
| y1 = (y0 = Math.floor(y)) + 1; | ||
| } | ||
| function tree_cover(x, y) { | ||
| if (isNaN(x = +x) || isNaN(y = +y)) return this; // ignore invalid points | ||
| // Otherwise, double repeatedly to cover. | ||
| else if (x0 > x || x > x1 || y0 > y || y > y1) { | ||
| var z = x1 - x0, | ||
| node = this._root, | ||
| parent, | ||
| i; | ||
| var x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1 = this._x1, | ||
| y1 = this._y1; | ||
| // If the quadtree has no extent, initialize them. | ||
| // Integer extent are necessary so that if we later double the extent, | ||
| // the existing quadrant boundaries don’t change due to floating point error! | ||
| if (isNaN(x0)) { | ||
| x1 = (x0 = Math.floor(x)) + 1; | ||
| y1 = (y0 = Math.floor(y)) + 1; | ||
| switch (i = (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) { | ||
| case 0: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x1 = x0 + z, y1 = y0 + z, x > x1 || y > y1); | ||
| break; | ||
| } | ||
| case 1: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x0 = x1 - z, y1 = y0 + z, x0 > x || y > y1); | ||
| break; | ||
| } | ||
| case 2: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x1 = x0 + z, y0 = y1 - z, x > x1 || y0 > y); | ||
| break; | ||
| } | ||
| case 3: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x0 = x1 - z, y0 = y1 - z, x0 > x || y0 > y); | ||
| break; | ||
| } | ||
| } | ||
| // Otherwise, double repeatedly to cover. | ||
| else if (x0 > x || x > x1 || y0 > y || y > y1) { | ||
| var z = x1 - x0, | ||
| node = this._root, | ||
| parent, | ||
| i; | ||
| if (this._root && this._root.length) this._root = node; | ||
| } | ||
| switch (i = (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) { | ||
| case 0: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x1 = x0 + z, y1 = y0 + z, x > x1 || y > y1); | ||
| break; | ||
| } | ||
| case 1: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x0 = x1 - z, y1 = y0 + z, x0 > x || y > y1); | ||
| break; | ||
| } | ||
| case 2: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x1 = x0 + z, y0 = y1 - z, x > x1 || y0 > y); | ||
| break; | ||
| } | ||
| case 3: { | ||
| do parent = new Array(4), parent[i] = node, node = parent; | ||
| while (z *= 2, x0 = x1 - z, y0 = y1 - z, x0 > x || y0 > y); | ||
| break; | ||
| } | ||
| } | ||
| // If the quadtree covers the point already, just return. | ||
| else return this; | ||
| if (this._root && this._root.length) this._root = node; | ||
| } | ||
| this._x0 = x0; | ||
| this._y0 = y0; | ||
| this._x1 = x1; | ||
| this._y1 = y1; | ||
| return this; | ||
| }; | ||
| // If the quadtree covers the point already, just return. | ||
| else return this; | ||
| var tree_data = function() { | ||
| var data = []; | ||
| this.visit(function(node) { | ||
| if (!node.length) do data.push(node.data); while (node = node.next) | ||
| }); | ||
| return data; | ||
| }; | ||
| this._x0 = x0; | ||
| this._y0 = y0; | ||
| this._x1 = x1; | ||
| this._y1 = y1; | ||
| return this; | ||
| } | ||
| var tree_extent = function(_) { | ||
| return arguments.length | ||
| ? this.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1]) | ||
| : isNaN(this._x0) ? undefined : [[this._x0, this._y0], [this._x1, this._y1]]; | ||
| }; | ||
| function tree_data() { | ||
| var data = []; | ||
| this.visit(function(node) { | ||
| if (!node.length) do data.push(node.data); while (node = node.next) | ||
| }); | ||
| return data; | ||
| } | ||
| var Quad = function(node, x0, y0, x1, y1) { | ||
| this.node = node; | ||
| this.x0 = x0; | ||
| this.y0 = y0; | ||
| this.x1 = x1; | ||
| this.y1 = y1; | ||
| }; | ||
| function tree_extent(_) { | ||
| return arguments.length | ||
| ? this.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1]) | ||
| : isNaN(this._x0) ? undefined : [[this._x0, this._y0], [this._x1, this._y1]]; | ||
| } | ||
| var tree_find = function(x, y, radius) { | ||
| var data, | ||
| x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1, | ||
| y1, | ||
| x2, | ||
| y2, | ||
| x3 = this._x1, | ||
| y3 = this._y1, | ||
| quads = [], | ||
| node = this._root, | ||
| q, | ||
| i; | ||
| function Quad(node, x0, y0, x1, y1) { | ||
| this.node = node; | ||
| this.x0 = x0; | ||
| this.y0 = y0; | ||
| this.x1 = x1; | ||
| this.y1 = y1; | ||
| if (node) quads.push(new Quad(node, x0, y0, x3, y3)); | ||
| if (radius == null) radius = Infinity; | ||
| else { | ||
| x0 = x - radius, y0 = y - radius; | ||
| x3 = x + radius, y3 = y + radius; | ||
| radius *= radius; | ||
| } | ||
| function tree_find(x, y, radius) { | ||
| var data, | ||
| x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1, | ||
| y1, | ||
| x2, | ||
| y2, | ||
| x3 = this._x1, | ||
| y3 = this._y1, | ||
| quads = [], | ||
| node = this._root, | ||
| q, | ||
| i; | ||
| while (q = quads.pop()) { | ||
| if (node) quads.push(new Quad(node, x0, y0, x3, y3)); | ||
| if (radius == null) radius = Infinity; | ||
| else { | ||
| x0 = x - radius, y0 = y - radius; | ||
| x3 = x + radius, y3 = y + radius; | ||
| radius *= radius; | ||
| } | ||
| // Stop searching if this quadrant can’t contain a closer node. | ||
| if (!(node = q.node) | ||
| || (x1 = q.x0) > x3 | ||
| || (y1 = q.y0) > y3 | ||
| || (x2 = q.x1) < x0 | ||
| || (y2 = q.y1) < y0) continue; | ||
| while (q = quads.pop()) { | ||
| // Bisect the current quadrant. | ||
| if (node.length) { | ||
| var xm = (x1 + x2) / 2, | ||
| ym = (y1 + y2) / 2; | ||
| // Stop searching if this quadrant can’t contain a closer node. | ||
| if (!(node = q.node) | ||
| || (x1 = q.x0) > x3 | ||
| || (y1 = q.y0) > y3 | ||
| || (x2 = q.x1) < x0 | ||
| || (y2 = q.y1) < y0) continue; | ||
| quads.push( | ||
| new Quad(node[3], xm, ym, x2, y2), | ||
| new Quad(node[2], x1, ym, xm, y2), | ||
| new Quad(node[1], xm, y1, x2, ym), | ||
| new Quad(node[0], x1, y1, xm, ym) | ||
| ); | ||
| // Bisect the current quadrant. | ||
| if (node.length) { | ||
| var xm = (x1 + x2) / 2, | ||
| ym = (y1 + y2) / 2; | ||
| quads.push( | ||
| new Quad(node[3], xm, ym, x2, y2), | ||
| new Quad(node[2], x1, ym, xm, y2), | ||
| new Quad(node[1], xm, y1, x2, ym), | ||
| new Quad(node[0], x1, y1, xm, ym) | ||
| ); | ||
| // Visit the closest quadrant first. | ||
| if (i = (y >= ym) << 1 | (x >= xm)) { | ||
| q = quads[quads.length - 1]; | ||
| quads[quads.length - 1] = quads[quads.length - 1 - i]; | ||
| quads[quads.length - 1 - i] = q; | ||
| } | ||
| // Visit the closest quadrant first. | ||
| if (i = (y >= ym) << 1 | (x >= xm)) { | ||
| q = quads[quads.length - 1]; | ||
| quads[quads.length - 1] = quads[quads.length - 1 - i]; | ||
| quads[quads.length - 1 - i] = q; | ||
| } | ||
| } | ||
| // Visit this point. (Visiting coincident points isn’t necessary!) | ||
| else { | ||
| var dx = x - +this._x.call(null, node.data), | ||
| dy = y - +this._y.call(null, node.data), | ||
| d2 = dx * dx + dy * dy; | ||
| if (d2 < radius) { | ||
| var d = Math.sqrt(radius = d2); | ||
| x0 = x - d, y0 = y - d; | ||
| x3 = x + d, y3 = y + d; | ||
| data = node.data; | ||
| } | ||
| // Visit this point. (Visiting coincident points isn’t necessary!) | ||
| else { | ||
| var dx = x - +this._x.call(null, node.data), | ||
| dy = y - +this._y.call(null, node.data), | ||
| d2 = dx * dx + dy * dy; | ||
| if (d2 < radius) { | ||
| var d = Math.sqrt(radius = d2); | ||
| x0 = x - d, y0 = y - d; | ||
| x3 = x + d, y3 = y + d; | ||
| data = node.data; | ||
| } | ||
| } | ||
| return data; | ||
| } | ||
| function tree_remove(d) { | ||
| if (isNaN(x = +this._x.call(null, d)) || isNaN(y = +this._y.call(null, d))) return this; // ignore invalid points | ||
| return data; | ||
| }; | ||
| var parent, | ||
| node = this._root, | ||
| retainer, | ||
| previous, | ||
| next, | ||
| x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1 = this._x1, | ||
| y1 = this._y1, | ||
| x, | ||
| y, | ||
| xm, | ||
| ym, | ||
| right, | ||
| bottom, | ||
| i, | ||
| j; | ||
| var tree_remove = function(d) { | ||
| if (isNaN(x = +this._x.call(null, d)) || isNaN(y = +this._y.call(null, d))) return this; // ignore invalid points | ||
| // If the tree is empty, initialize the root as a leaf. | ||
| if (!node) return this; | ||
| var parent, | ||
| node = this._root, | ||
| retainer, | ||
| previous, | ||
| next, | ||
| x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1 = this._x1, | ||
| y1 = this._y1, | ||
| x, | ||
| y, | ||
| xm, | ||
| ym, | ||
| right, | ||
| bottom, | ||
| i, | ||
| j; | ||
| // Find the leaf node for the point. | ||
| // While descending, also retain the deepest parent with a non-removed sibling. | ||
| if (node.length) while (true) { | ||
| if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; | ||
| if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; | ||
| if (!(parent = node, node = node[i = bottom << 1 | right])) return this; | ||
| if (!node.length) break; | ||
| if (parent[(i + 1) & 3] || parent[(i + 2) & 3] || parent[(i + 3) & 3]) retainer = parent, j = i; | ||
| } | ||
| // If the tree is empty, initialize the root as a leaf. | ||
| if (!node) return this; | ||
| // Find the point to remove. | ||
| while (node.data !== d) if (!(previous = node, node = node.next)) return this; | ||
| if (next = node.next) delete node.next; | ||
| // Find the leaf node for the point. | ||
| // While descending, also retain the deepest parent with a non-removed sibling. | ||
| if (node.length) while (true) { | ||
| if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm; | ||
| if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym; | ||
| if (!(parent = node, node = node[i = bottom << 1 | right])) return this; | ||
| if (!node.length) break; | ||
| if (parent[(i + 1) & 3] || parent[(i + 2) & 3] || parent[(i + 3) & 3]) retainer = parent, j = i; | ||
| } | ||
| // If there are multiple coincident points, remove just the point. | ||
| if (previous) return (next ? previous.next = next : delete previous.next), this; | ||
| // Find the point to remove. | ||
| while (node.data !== d) if (!(previous = node, node = node.next)) return this; | ||
| if (next = node.next) delete node.next; | ||
| // If this is the root point, remove it. | ||
| if (!parent) return this._root = next, this; | ||
| // If there are multiple coincident points, remove just the point. | ||
| if (previous) return (next ? previous.next = next : delete previous.next), this; | ||
| // Remove this leaf. | ||
| next ? parent[i] = next : delete parent[i]; | ||
| // If this is the root point, remove it. | ||
| if (!parent) return this._root = next, this; | ||
| // If the parent now contains exactly one leaf, collapse superfluous parents. | ||
| if ((node = parent[0] || parent[1] || parent[2] || parent[3]) | ||
| && node === (parent[3] || parent[2] || parent[1] || parent[0]) | ||
| && !node.length) { | ||
| if (retainer) retainer[j] = node; | ||
| else this._root = node; | ||
| } | ||
| // Remove this leaf. | ||
| next ? parent[i] = next : delete parent[i]; | ||
| return this; | ||
| // If the parent now contains exactly one leaf, collapse superfluous parents. | ||
| if ((node = parent[0] || parent[1] || parent[2] || parent[3]) | ||
| && node === (parent[3] || parent[2] || parent[1] || parent[0]) | ||
| && !node.length) { | ||
| if (retainer) retainer[j] = node; | ||
| else this._root = node; | ||
| } | ||
| function removeAll(data) { | ||
| for (var i = 0, n = data.length; i < n; ++i) this.remove(data[i]); | ||
| return this; | ||
| } | ||
| return this; | ||
| }; | ||
| function tree_root() { | ||
| return this._root; | ||
| } | ||
| function removeAll(data) { | ||
| for (var i = 0, n = data.length; i < n; ++i) this.remove(data[i]); | ||
| return this; | ||
| } | ||
| function tree_size() { | ||
| var size = 0; | ||
| this.visit(function(node) { | ||
| if (!node.length) do ++size; while (node = node.next) | ||
| }); | ||
| return size; | ||
| } | ||
| var tree_root = function() { | ||
| return this._root; | ||
| }; | ||
| function tree_visit(callback) { | ||
| var quads = [], q, node = this._root, child, x0, y0, x1, y1; | ||
| if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1)); | ||
| while (q = quads.pop()) { | ||
| if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) && node.length) { | ||
| var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2; | ||
| if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)); | ||
| if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)); | ||
| if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)); | ||
| if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)); | ||
| } | ||
| var tree_size = function() { | ||
| var size = 0; | ||
| this.visit(function(node) { | ||
| if (!node.length) do ++size; while (node = node.next) | ||
| }); | ||
| return size; | ||
| }; | ||
| var tree_visit = function(callback) { | ||
| var quads = [], q, node = this._root, child, x0, y0, x1, y1; | ||
| if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1)); | ||
| while (q = quads.pop()) { | ||
| if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) && node.length) { | ||
| var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2; | ||
| if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)); | ||
| if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)); | ||
| if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)); | ||
| if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)); | ||
| } | ||
| return this; | ||
| } | ||
| return this; | ||
| }; | ||
| function tree_visitAfter(callback) { | ||
| var quads = [], next = [], q; | ||
| if (this._root) quads.push(new Quad(this._root, this._x0, this._y0, this._x1, this._y1)); | ||
| while (q = quads.pop()) { | ||
| var node = q.node; | ||
| if (node.length) { | ||
| var child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2; | ||
| if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)); | ||
| if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)); | ||
| if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)); | ||
| if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)); | ||
| } | ||
| next.push(q); | ||
| var tree_visitAfter = function(callback) { | ||
| var quads = [], next = [], q; | ||
| if (this._root) quads.push(new Quad(this._root, this._x0, this._y0, this._x1, this._y1)); | ||
| while (q = quads.pop()) { | ||
| var node = q.node; | ||
| if (node.length) { | ||
| var child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2; | ||
| if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym)); | ||
| if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym)); | ||
| if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1)); | ||
| if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1)); | ||
| } | ||
| while (q = next.pop()) { | ||
| callback(q.node, q.x0, q.y0, q.x1, q.y1); | ||
| } | ||
| return this; | ||
| next.push(q); | ||
| } | ||
| function defaultX(d) { | ||
| return d[0]; | ||
| while (q = next.pop()) { | ||
| callback(q.node, q.x0, q.y0, q.x1, q.y1); | ||
| } | ||
| return this; | ||
| }; | ||
| function tree_x(_) { | ||
| return arguments.length ? (this._x = _, this) : this._x; | ||
| } | ||
| function defaultX(d) { | ||
| return d[0]; | ||
| } | ||
| function defaultY(d) { | ||
| return d[1]; | ||
| } | ||
| var tree_x = function(_) { | ||
| return arguments.length ? (this._x = _, this) : this._x; | ||
| }; | ||
| function tree_y(_) { | ||
| return arguments.length ? (this._y = _, this) : this._y; | ||
| } | ||
| function defaultY(d) { | ||
| return d[1]; | ||
| } | ||
| function quadtree(nodes, x, y) { | ||
| var tree = new Quadtree(x == null ? defaultX : x, y == null ? defaultY : y, NaN, NaN, NaN, NaN); | ||
| return nodes == null ? tree : tree.addAll(nodes); | ||
| } | ||
| var tree_y = function(_) { | ||
| return arguments.length ? (this._y = _, this) : this._y; | ||
| }; | ||
| function Quadtree(x, y, x0, y0, x1, y1) { | ||
| this._x = x; | ||
| this._y = y; | ||
| this._x0 = x0; | ||
| this._y0 = y0; | ||
| this._x1 = x1; | ||
| this._y1 = y1; | ||
| this._root = undefined; | ||
| } | ||
| function quadtree(nodes, x, y) { | ||
| var tree = new Quadtree(x == null ? defaultX : x, y == null ? defaultY : y, NaN, NaN, NaN, NaN); | ||
| return nodes == null ? tree : tree.addAll(nodes); | ||
| } | ||
| function leaf_copy(leaf) { | ||
| var copy = {data: leaf.data}, next = copy; | ||
| while (leaf = leaf.next) next = next.next = {data: leaf.data}; | ||
| return copy; | ||
| } | ||
| function Quadtree(x, y, x0, y0, x1, y1) { | ||
| this._x = x; | ||
| this._y = y; | ||
| this._x0 = x0; | ||
| this._y0 = y0; | ||
| this._x1 = x1; | ||
| this._y1 = y1; | ||
| this._root = undefined; | ||
| } | ||
| var treeProto = quadtree.prototype = Quadtree.prototype; | ||
| function leaf_copy(leaf) { | ||
| var copy = {data: leaf.data}, next = copy; | ||
| while (leaf = leaf.next) next = next.next = {data: leaf.data}; | ||
| return copy; | ||
| } | ||
| treeProto.copy = function() { | ||
| var copy = new Quadtree(this._x, this._y, this._x0, this._y0, this._x1, this._y1), | ||
| node = this._root, | ||
| nodes, | ||
| child; | ||
| var treeProto = quadtree.prototype = Quadtree.prototype; | ||
| if (!node) return copy; | ||
| treeProto.copy = function() { | ||
| var copy = new Quadtree(this._x, this._y, this._x0, this._y0, this._x1, this._y1), | ||
| node = this._root, | ||
| nodes, | ||
| child; | ||
| if (!node.length) return copy._root = leaf_copy(node), copy; | ||
| if (!node) return copy; | ||
| nodes = [{source: node, target: copy._root = new Array(4)}]; | ||
| while (node = nodes.pop()) { | ||
| for (var i = 0; i < 4; ++i) { | ||
| if (child = node.source[i]) { | ||
| if (child.length) nodes.push({source: child, target: node.target[i] = new Array(4)}); | ||
| else node.target[i] = leaf_copy(child); | ||
| } | ||
| if (!node.length) return copy._root = leaf_copy(node), copy; | ||
| nodes = [{source: node, target: copy._root = new Array(4)}]; | ||
| while (node = nodes.pop()) { | ||
| for (var i = 0; i < 4; ++i) { | ||
| if (child = node.source[i]) { | ||
| if (child.length) nodes.push({source: child, target: node.target[i] = new Array(4)}); | ||
| else node.target[i] = leaf_copy(child); | ||
| } | ||
| } | ||
| } | ||
| return copy; | ||
| }; | ||
| return copy; | ||
| }; | ||
| treeProto.add = tree_add; | ||
| treeProto.addAll = addAll; | ||
| treeProto.cover = tree_cover; | ||
| treeProto.data = tree_data; | ||
| treeProto.extent = tree_extent; | ||
| treeProto.find = tree_find; | ||
| treeProto.remove = tree_remove; | ||
| treeProto.removeAll = removeAll; | ||
| treeProto.root = tree_root; | ||
| treeProto.size = tree_size; | ||
| treeProto.visit = tree_visit; | ||
| treeProto.visitAfter = tree_visitAfter; | ||
| treeProto.x = tree_x; | ||
| treeProto.y = tree_y; | ||
| treeProto.add = tree_add; | ||
| treeProto.addAll = addAll; | ||
| treeProto.cover = tree_cover; | ||
| treeProto.data = tree_data; | ||
| treeProto.extent = tree_extent; | ||
| treeProto.find = tree_find; | ||
| treeProto.remove = tree_remove; | ||
| treeProto.removeAll = removeAll; | ||
| treeProto.root = tree_root; | ||
| treeProto.size = tree_size; | ||
| treeProto.visit = tree_visit; | ||
| treeProto.visitAfter = tree_visitAfter; | ||
| treeProto.x = tree_x; | ||
| treeProto.y = tree_y; | ||
| exports.quadtree = quadtree; | ||
| exports.quadtree = quadtree; | ||
| Object.defineProperty(exports, '__esModule', { value: true }); | ||
| Object.defineProperty(exports, '__esModule', { value: true }); | ||
| })); | ||
| }))); |
@@ -1,2 +0,2 @@ | ||
| // https://d3js.org/d3-quadtree/ Version 1.0.1. Copyright 2016 Mike Bostock. | ||
| !function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i(t.d3=t.d3||{})}(this,function(t){"use strict";function i(t){var i=+this._x.call(null,t),r=+this._y.call(null,t);return e(this.cover(i,r),i,r,t)}function e(t,i,e,r){if(isNaN(i)||isNaN(e))return t;var n,h,s,o,a,u,l,_,f,y=t._root,x={data:r},c=t._x0,d=t._y0,v=t._x1,p=t._y1;if(!y)return t._root=x,t;for(;y.length;)if((u=i>=(h=(c+v)/2))?c=h:v=h,(l=e>=(s=(d+p)/2))?d=s:p=s,n=y,!(y=y[_=l<<1|u]))return n[_]=x,t;if(o=+t._x.call(null,y.data),a=+t._y.call(null,y.data),i===o&&e===a)return x.next=y,n?n[_]=x:t._root=x,t;do n=n?n[_]=new Array(4):t._root=new Array(4),(u=i>=(h=(c+v)/2))?c=h:v=h,(l=e>=(s=(d+p)/2))?d=s:p=s;while((_=l<<1|u)===(f=(a>=s)<<1|o>=h));return n[f]=y,n[_]=x,t}function r(t){var i,r,n,h,s=t.length,o=new Array(s),a=new Array(s),u=1/0,l=1/0,_=-(1/0),f=-(1/0);for(r=0;r<s;++r)isNaN(n=+this._x.call(null,i=t[r]))||isNaN(h=+this._y.call(null,i))||(o[r]=n,a[r]=h,n<u&&(u=n),n>_&&(_=n),h<l&&(l=h),h>f&&(f=h));for(_<u&&(u=this._x0,_=this._x1),f<l&&(l=this._y0,f=this._y1),this.cover(u,l).cover(_,f),r=0;r<s;++r)e(this,o[r],a[r],t[r]);return this}function n(t,i){if(isNaN(t=+t)||isNaN(i=+i))return this;var e=this._x0,r=this._y0,n=this._x1,h=this._y1;if(isNaN(e))n=(e=Math.floor(t))+1,h=(r=Math.floor(i))+1;else{if(!(e>t||t>n||r>i||i>h))return this;var s,o,a=n-e,u=this._root;switch(o=(i<(r+h)/2)<<1|t<(e+n)/2){case 0:do s=new Array(4),s[o]=u,u=s;while(a*=2,n=e+a,h=r+a,t>n||i>h);break;case 1:do s=new Array(4),s[o]=u,u=s;while(a*=2,e=n-a,h=r+a,e>t||i>h);break;case 2:do s=new Array(4),s[o]=u,u=s;while(a*=2,n=e+a,r=h-a,t>n||r>i);break;case 3:do s=new Array(4),s[o]=u,u=s;while(a*=2,e=n-a,r=h-a,e>t||r>i)}this._root&&this._root.length&&(this._root=u)}return this._x0=e,this._y0=r,this._x1=n,this._y1=h,this}function h(){var t=[];return this.visit(function(i){if(!i.length)do t.push(i.data);while(i=i.next)}),t}function s(t){return arguments.length?this.cover(+t[0][0],+t[0][1]).cover(+t[1][0],+t[1][1]):isNaN(this._x0)?void 0:[[this._x0,this._y0],[this._x1,this._y1]]}function o(t,i,e,r,n){this.node=t,this.x0=i,this.y0=e,this.x1=r,this.y1=n}function a(t,i,e){var r,n,h,s,a,u,l,_=this._x0,f=this._y0,y=this._x1,x=this._y1,c=[],d=this._root;for(d&&c.push(new o(d,_,f,y,x)),null==e?e=1/0:(_=t-e,f=i-e,y=t+e,x=i+e,e*=e);u=c.pop();)if(!(!(d=u.node)||(n=u.x0)>y||(h=u.y0)>x||(s=u.x1)<_||(a=u.y1)<f))if(d.length){var v=(n+s)/2,p=(h+a)/2;c.push(new o(d[3],v,p,s,a),new o(d[2],n,p,v,a),new o(d[1],v,h,s,p),new o(d[0],n,h,v,p)),(l=(i>=p)<<1|t>=v)&&(u=c[c.length-1],c[c.length-1]=c[c.length-1-l],c[c.length-1-l]=u)}else{var w=t-+this._x.call(null,d.data),N=i-+this._y.call(null,d.data),g=w*w+N*N;if(g<e){var A=Math.sqrt(e=g);_=t-A,f=i-A,y=t+A,x=i+A,r=d.data}}return r}function u(t){if(isNaN(h=+this._x.call(null,t))||isNaN(s=+this._y.call(null,t)))return this;var i,e,r,n,h,s,o,a,u,l,_,f,y=this._root,x=this._x0,c=this._y0,d=this._x1,v=this._y1;if(!y)return this;if(y.length)for(;;){if((u=h>=(o=(x+d)/2))?x=o:d=o,(l=s>=(a=(c+v)/2))?c=a:v=a,i=y,!(y=y[_=l<<1|u]))return this;if(!y.length)break;(i[_+1&3]||i[_+2&3]||i[_+3&3])&&(e=i,f=_)}for(;y.data!==t;)if(r=y,!(y=y.next))return this;return(n=y.next)&&delete y.next,r?(n?r.next=n:delete r.next,this):i?(n?i[_]=n:delete i[_],(y=i[0]||i[1]||i[2]||i[3])&&y===(i[3]||i[2]||i[1]||i[0])&&!y.length&&(e?e[f]=y:this._root=y),this):(this._root=n,this)}function l(t){for(var i=0,e=t.length;i<e;++i)this.remove(t[i]);return this}function _(){return this._root}function f(){var t=0;return this.visit(function(i){if(!i.length)do++t;while(i=i.next)}),t}function y(t){var i,e,r,n,h,s,a=[],u=this._root;for(u&&a.push(new o(u,this._x0,this._y0,this._x1,this._y1));i=a.pop();)if(!t(u=i.node,r=i.x0,n=i.y0,h=i.x1,s=i.y1)&&u.length){var l=(r+h)/2,_=(n+s)/2;(e=u[3])&&a.push(new o(e,l,_,h,s)),(e=u[2])&&a.push(new o(e,r,_,l,s)),(e=u[1])&&a.push(new o(e,l,n,h,_)),(e=u[0])&&a.push(new o(e,r,n,l,_))}return this}function x(t){var i,e=[],r=[];for(this._root&&e.push(new o(this._root,this._x0,this._y0,this._x1,this._y1));i=e.pop();){var n=i.node;if(n.length){var h,s=i.x0,a=i.y0,u=i.x1,l=i.y1,_=(s+u)/2,f=(a+l)/2;(h=n[0])&&e.push(new o(h,s,a,_,f)),(h=n[1])&&e.push(new o(h,_,a,u,f)),(h=n[2])&&e.push(new o(h,s,f,_,l)),(h=n[3])&&e.push(new o(h,_,f,u,l))}r.push(i)}for(;i=r.pop();)t(i.node,i.x0,i.y0,i.x1,i.y1);return this}function c(t){return t[0]}function d(t){return arguments.length?(this._x=t,this):this._x}function v(t){return t[1]}function p(t){return arguments.length?(this._y=t,this):this._y}function w(t,i,e){var r=new N(null==i?c:i,null==e?v:e,NaN,NaN,NaN,NaN);return null==t?r:r.addAll(t)}function N(t,i,e,r,n,h){this._x=t,this._y=i,this._x0=e,this._y0=r,this._x1=n,this._y1=h,this._root=void 0}function g(t){for(var i={data:t.data},e=i;t=t.next;)e=e.next={data:t.data};return i}var A=w.prototype=N.prototype;A.copy=function(){var t,i,e=new N(this._x,this._y,this._x0,this._y0,this._x1,this._y1),r=this._root;if(!r)return e;if(!r.length)return e._root=g(r),e;for(t=[{source:r,target:e._root=new Array(4)}];r=t.pop();)for(var n=0;n<4;++n)(i=r.source[n])&&(i.length?t.push({source:i,target:r.target[n]=new Array(4)}):r.target[n]=g(i));return e},A.add=i,A.addAll=r,A.cover=n,A.data=h,A.extent=s,A.find=a,A.remove=u,A.removeAll=l,A.root=_,A.size=f,A.visit=y,A.visitAfter=x,A.x=d,A.y=p,t.quadtree=w,Object.defineProperty(t,"__esModule",{value:!0})}); | ||
| // https://d3js.org/d3-quadtree/ Version 1.0.2. Copyright 2016 Mike Bostock. | ||
| !function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i(t.d3=t.d3||{})}(this,function(t){"use strict";function i(t,i,e,r){if(isNaN(i)||isNaN(e))return t;var n,h,s,o,a,u,l,_,f,y=t._root,x={data:r},c=t._x0,d=t._y0,v=t._x1,p=t._y1;if(!y)return t._root=x,t;for(;y.length;)if((u=i>=(h=(c+v)/2))?c=h:v=h,(l=e>=(s=(d+p)/2))?d=s:p=s,n=y,!(y=y[_=l<<1|u]))return n[_]=x,t;if(o=+t._x.call(null,y.data),a=+t._y.call(null,y.data),i===o&&e===a)return x.next=y,n?n[_]=x:t._root=x,t;do n=n?n[_]=new Array(4):t._root=new Array(4),(u=i>=(h=(c+v)/2))?c=h:v=h,(l=e>=(s=(d+p)/2))?d=s:p=s;while((_=l<<1|u)===(f=(a>=s)<<1|o>=h));return n[f]=y,n[_]=x,t}function e(t){var e,r,n,h,s=t.length,o=new Array(s),a=new Array(s),u=1/0,l=1/0,_=-(1/0),f=-(1/0);for(r=0;r<s;++r)isNaN(n=+this._x.call(null,e=t[r]))||isNaN(h=+this._y.call(null,e))||(o[r]=n,a[r]=h,n<u&&(u=n),n>_&&(_=n),h<l&&(l=h),h>f&&(f=h));for(_<u&&(u=this._x0,_=this._x1),f<l&&(l=this._y0,f=this._y1),this.cover(u,l).cover(_,f),r=0;r<s;++r)i(this,o[r],a[r],t[r]);return this}function r(t){for(var i=0,e=t.length;i<e;++i)this.remove(t[i]);return this}function n(t){return t[0]}function h(t){return t[1]}function s(t,i,e){var r=new o(null==i?n:i,null==e?h:e,NaN,NaN,NaN,NaN);return null==t?r:r.addAll(t)}function o(t,i,e,r,n,h){this._x=t,this._y=i,this._x0=e,this._y0=r,this._x1=n,this._y1=h,this._root=void 0}function a(t){for(var i={data:t.data},e=i;t=t.next;)e=e.next={data:t.data};return i}var u=function(t){var e=+this._x.call(null,t),r=+this._y.call(null,t);return i(this.cover(e,r),e,r,t)},l=function(t,i){if(isNaN(t=+t)||isNaN(i=+i))return this;var e=this._x0,r=this._y0,n=this._x1,h=this._y1;if(isNaN(e))n=(e=Math.floor(t))+1,h=(r=Math.floor(i))+1;else{if(!(e>t||t>n||r>i||i>h))return this;var s,o,a=n-e,u=this._root;switch(o=(i<(r+h)/2)<<1|t<(e+n)/2){case 0:do s=new Array(4),s[o]=u,u=s;while(a*=2,n=e+a,h=r+a,t>n||i>h);break;case 1:do s=new Array(4),s[o]=u,u=s;while(a*=2,e=n-a,h=r+a,e>t||i>h);break;case 2:do s=new Array(4),s[o]=u,u=s;while(a*=2,n=e+a,r=h-a,t>n||r>i);break;case 3:do s=new Array(4),s[o]=u,u=s;while(a*=2,e=n-a,r=h-a,e>t||r>i)}this._root&&this._root.length&&(this._root=u)}return this._x0=e,this._y0=r,this._x1=n,this._y1=h,this},_=function(){var t=[];return this.visit(function(i){if(!i.length)do t.push(i.data);while(i=i.next)}),t},f=function(t){return arguments.length?this.cover(+t[0][0],+t[0][1]).cover(+t[1][0],+t[1][1]):isNaN(this._x0)?void 0:[[this._x0,this._y0],[this._x1,this._y1]]},y=function(t,i,e,r,n){this.node=t,this.x0=i,this.y0=e,this.x1=r,this.y1=n},x=function(t,i,e){var r,n,h,s,o,a,u,l=this._x0,_=this._y0,f=this._x1,x=this._y1,c=[],d=this._root;for(d&&c.push(new y(d,l,_,f,x)),null==e?e=1/0:(l=t-e,_=i-e,f=t+e,x=i+e,e*=e);a=c.pop();)if(!(!(d=a.node)||(n=a.x0)>f||(h=a.y0)>x||(s=a.x1)<l||(o=a.y1)<_))if(d.length){var v=(n+s)/2,p=(h+o)/2;c.push(new y(d[3],v,p,s,o),new y(d[2],n,p,v,o),new y(d[1],v,h,s,p),new y(d[0],n,h,v,p)),(u=(i>=p)<<1|t>=v)&&(a=c[c.length-1],c[c.length-1]=c[c.length-1-u],c[c.length-1-u]=a)}else{var w=t-+this._x.call(null,d.data),N=i-+this._y.call(null,d.data),g=w*w+N*N;if(g<e){var A=Math.sqrt(e=g);l=t-A,_=i-A,f=t+A,x=i+A,r=d.data}}return r},c=function(t){if(isNaN(h=+this._x.call(null,t))||isNaN(s=+this._y.call(null,t)))return this;var i,e,r,n,h,s,o,a,u,l,_,f,y=this._root,x=this._x0,c=this._y0,d=this._x1,v=this._y1;if(!y)return this;if(y.length)for(;;){if((u=h>=(o=(x+d)/2))?x=o:d=o,(l=s>=(a=(c+v)/2))?c=a:v=a,i=y,!(y=y[_=l<<1|u]))return this;if(!y.length)break;(i[_+1&3]||i[_+2&3]||i[_+3&3])&&(e=i,f=_)}for(;y.data!==t;)if(r=y,!(y=y.next))return this;return(n=y.next)&&delete y.next,r?(n?r.next=n:delete r.next,this):i?(n?i[_]=n:delete i[_],(y=i[0]||i[1]||i[2]||i[3])&&y===(i[3]||i[2]||i[1]||i[0])&&!y.length&&(e?e[f]=y:this._root=y),this):(this._root=n,this)},d=function(){return this._root},v=function(){var t=0;return this.visit(function(i){if(!i.length)do++t;while(i=i.next)}),t},p=function(t){var i,e,r,n,h,s,o=[],a=this._root;for(a&&o.push(new y(a,this._x0,this._y0,this._x1,this._y1));i=o.pop();)if(!t(a=i.node,r=i.x0,n=i.y0,h=i.x1,s=i.y1)&&a.length){var u=(r+h)/2,l=(n+s)/2;(e=a[3])&&o.push(new y(e,u,l,h,s)),(e=a[2])&&o.push(new y(e,r,l,u,s)),(e=a[1])&&o.push(new y(e,u,n,h,l)),(e=a[0])&&o.push(new y(e,r,n,u,l))}return this},w=function(t){var i,e=[],r=[];for(this._root&&e.push(new y(this._root,this._x0,this._y0,this._x1,this._y1));i=e.pop();){var n=i.node;if(n.length){var h,s=i.x0,o=i.y0,a=i.x1,u=i.y1,l=(s+a)/2,_=(o+u)/2;(h=n[0])&&e.push(new y(h,s,o,l,_)),(h=n[1])&&e.push(new y(h,l,o,a,_)),(h=n[2])&&e.push(new y(h,s,_,l,u)),(h=n[3])&&e.push(new y(h,l,_,a,u))}r.push(i)}for(;i=r.pop();)t(i.node,i.x0,i.y0,i.x1,i.y1);return this},N=function(t){return arguments.length?(this._x=t,this):this._x},g=function(t){return arguments.length?(this._y=t,this):this._y},A=s.prototype=o.prototype;A.copy=function(){var t,i,e=new o(this._x,this._y,this._x0,this._y0,this._x1,this._y1),r=this._root;if(!r)return e;if(!r.length)return e._root=a(r),e;for(t=[{source:r,target:e._root=new Array(4)}];r=t.pop();)for(var n=0;n<4;++n)(i=r.source[n])&&(i.length?t.push({source:i,target:r.target[n]=new Array(4)}):r.target[n]=a(i));return e},A.add=u,A.addAll=e,A.cover=l,A.data=_,A.extent=f,A.find=x,A.remove=c,A.removeAll=r,A.root=d,A.size=v,A.visit=p,A.visitAfter=w,A.x=N,A.y=g,t.quadtree=s,Object.defineProperty(t,"__esModule",{value:!0})}); |
| { | ||
| "name": "d3-quadtree", | ||
| "version": "1.0.1", | ||
| "version": "1.0.2", | ||
| "description": "Two-dimensional recursive spatial subdivision.", | ||
@@ -31,5 +31,5 @@ "keywords": [ | ||
| "d3-array": "1", | ||
| "eslint": "2", | ||
| "eslint": "3", | ||
| "package-preamble": "0.0", | ||
| "rollup": "0.34", | ||
| "rollup": "0.36", | ||
| "tape": "4", | ||
@@ -36,0 +36,0 @@ "uglify-js": "2" |
@@ -7,6 +7,2 @@ # d3-quadtree | ||
| <a href="http://bl.ocks.org/mbostock/4343214"><img src="http://bl.ocks.org/mbostock/raw/4343214/thumbnail.png" width="202"></a> | ||
| <a href="http://bl.ocks.org/mbostock/6216724"><img src="http://bl.ocks.org/mbostock/raw/6216724/thumbnail.png" width="202"></a> | ||
| <a href="http://bl.ocks.org/mbostock/6224050"><img src="http://bl.ocks.org/mbostock/raw/6224050/thumbnail.png" width="202"></a> | ||
| <a href="http://bl.ocks.org/patricksurry/6478178"><img src="http://bl.ocks.org/patricksurry/raw/6478178/thumbnail.png" width="202"></a> | ||
| <a href="http://bl.ocks.org/llb4ll/8709363"><img src="http://bl.ocks.org/llb4ll/raw/8709363/thumbnail.png" width="202"></a> | ||
@@ -31,2 +27,3 @@ ## Installing | ||
| <a name="quadtree" href="#quadtree">#</a> d3.<b>quadtree</b>([<i>data</i>[, <i>x</i>, <i>y</i>]]) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/quadtree.js#L14 "Source") | ||
@@ -49,3 +46,3 @@ Creates a new, empty quadtree with an empty [extent](#quadtree_extent) and the default [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors. If *data* is specified, [adds](#quadtree_addAll) the specified array of data to the quadtree. This is equivalent to: | ||
| <a name="quadtree_x" href="#quadtree_x">#</a> <i>quadtree</i>.<b>x</b>([<i>x</i>]) | ||
| <a name="quadtree_x" href="#quadtree_x">#</a> <i>quadtree</i>.<b>x</b>([<i>x</i>]) [<>](https://github.com/d3/d3-quadtree/blob/master/src/x.js "Source") | ||
@@ -63,2 +60,3 @@ If *x* is specified, sets the current *x*-coordinate accessor and returns the quadtree. If *x* is not specified, returns the current *x*-accessor, which defaults to: | ||
| <a name="quadtree_y" href="#quadtree_y">#</a> <i>quadtree</i>.<b>y</b>([<i>y</i>]) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/y.js "Source") | ||
@@ -76,2 +74,3 @@ If *y* is specified, sets the current *y*-coordinate accessor and returns the quadtree. If *y* is not specified, returns the current *y*-accessor, which defaults to: | ||
| <a name="quadtree_extent" href="#quadtree_extent">#</a> <i>quadtree</i>.<b>extent</b>([*extent*]) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/extent.js "Source") | ||
@@ -81,2 +80,3 @@ If *extent* is specified, expands the quadtree to [cover](#quadtree_cover) the specified points [[*x0*, *y0*], [*x1*, *y1*]] and returns the quadtree. If *extent* is not specified, returns the quadtree’s current extent [[*x0*, *y0*], [*x1*, *y1*]], where *x0* and *y0* are the inclusive lower bounds and *x1* and *y1* are the inclusive upper bounds, or undefined if the quadtree has no extent. The extent may also be expanded by calling [*quadtree*.cover](#quadtree_cover) or [*quadtree*.add](#quadtree_add). | ||
| <a name="quadtree_cover" href="#quadtree_cover">#</a> <i>quadtree</i>.<b>cover</b>(<i>x</i>, <i>y</i>) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/cover.js "Source") | ||
@@ -86,2 +86,3 @@ Expands the quadtree to cover the specified point ⟨*x*,*y*⟩, and returns the quadtree. If the quadtree’s extent already covers the specified point, this method does nothing. If the quadtree has an extent, the extent is repeatedly doubled to cover the specified point, wrapping the [root](#quadtree_root) [node](#nodes) as necessary; if the quadtree is empty, the extent is initialized to the extent [[⌊*x*⌋, ⌊*y*⌋], [⌈*x*⌉, ⌈*y*⌉]]. (Rounding is necessary such that if the extent is later doubled, the boundaries of existing quadrants do not change due to floating point error.) | ||
| <a name="quadtree_add" href="#quadtree_add">#</a> <i>quadtree</i>.<b>add</b>(<i>datum</i>) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/add.js "Source") | ||
@@ -91,2 +92,3 @@ Adds the specified *datum* to the quadtree, deriving its coordinates ⟨*x*,*y*⟩ using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors, and returns the quadtree. If the new point is outside the current [extent](#quadtree_extent) of the quadtree, the quadtree is automatically expanded to [cover](#quadtree_cover) the new point. | ||
| <a name="quadtree_addAll" href="#quadtree_addAll">#</a> <i>quadtree</i>.<b>addAll</b>(<i>data</i>) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/add.js#L50 "Source") | ||
@@ -104,2 +106,3 @@ Adds the specified array of *data* to the quadtree, deriving each element’s coordinates ⟨*x*,*y*⟩ using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors, and return this quadtree. This is approximately equivalent to calling [*quadtree*.add](#quadtree_add) repeatedly: | ||
| <a name="quadtree_remove" href="#quadtree_remove">#</a> <i>quadtree</i>.<b>remove</b>(<i>datum</i>) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/remove.js "Source") | ||
@@ -109,2 +112,3 @@ Removes the specified *datum* to the quadtree, deriving its coordinates ⟨*x*,*y*⟩ using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors, and returns the quadtree. If the specified *datum* does not exist in this quadtree, this method does nothing. | ||
| <a name="quadtree_removeAll" href="#quadtree_removeAll">#</a> <i>quadtree</i>.<b>removeAll</b>(<i>data</i>) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/remove.js#L59 "Source") | ||
@@ -118,2 +122,3 @@ … | ||
| <a name="quadtree_root" href="#quadtree_root">#</a> <i>quadtree</i>.<b>root</b>() | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/root.js "Source") | ||
@@ -123,2 +128,3 @@ Returns the root [node](#nodes) of the quadtree. | ||
| <a name="quadtree_data" href="#quadtree_data">#</a> <i>quadtree</i>.<b>data</b>() | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/data.js "Source") | ||
@@ -128,2 +134,3 @@ Returns an array of all data in the quadtree. | ||
| <a name="quadtree_size" href="#quadtree_size">#</a> <i>quadtree</i>.<b>size</b>() | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/size.js "Source") | ||
@@ -133,2 +140,3 @@ Returns the total number of data in the quadtree. | ||
| <a name="quadtree_find" href="#quadtree_find">#</a> <i>quadtree</i>.<b>find</b>(<i>x</i>, <i>y</i>[, <i>radius</i>]) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/find.js "Source") | ||
@@ -138,2 +146,3 @@ Returns the datum closest to the position ⟨*x*,*y*⟩ with the given search *radius*. If *radius* is not specified, it defaults to infinity. If there is no datum within the search area, returns undefined. | ||
| <a name="quadtree_visit" href="#quadtree_visit">#</a> <i>quadtree</i>.<b>visit</b>(<i>callback</i>) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/visit.js "Source") | ||
@@ -145,2 +154,3 @@ Visits each [node](#nodes) in the quadtree in pre-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds, and returns the quadtree. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) | ||
| <a name="quadtree_visitAfter" href="#quadtree_visitAfter">#</a> <i>quadtree</i>.<b>visitAfter</b>(<i>callback</i>) | ||
| [<>](https://github.com/d3/d3-quadtree/blob/master/src/visitAfter.js "Source") | ||
@@ -168,5 +178,5 @@ Visits each [node](#nodes) in the quadtree in post-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds, and returns the quadtree. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) Returns *root*. | ||
| ```js | ||
| if (!node.length) do console.log(node.data); while (node = node.next) | ||
| if (!node.length) do console.log(node.data); while (node = node.next); | ||
| ``` | ||
| The point’s *x*- and *y*-coordinates **must not be modified** while the point is in the quadtree. To update a point’s position, [remove](#quadtree_remove) the point and then re-[add](#quadtree_add) it to the quadtree at the new position. Alternatively, you may discard the existing quadtree entirely and create a new one from scratch; this may be more efficient if many of the points have moved. |
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Lines of code
- increased by0.13%
748
- Number of lines in readme file
- increased by6.41%
166
Worsened metrics
- Total package byte prevSize
- decreased by-0.1%
44717
No dependency changes