Skip to content

Commit f8da7ce

Browse files
jasondaviesjasondavies
committed
Simplify quadtree.find and add test.
1 parent 2a7f582 commit f8da7ce

4 files changed

Lines changed: 43 additions & 26 deletions

File tree

‎d3.js‎

Lines changed: 11 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -5519,11 +5519,11 @@
55195519
}
55205520
}
55215521
function insertChild(n, d, x, y, x1, y1, x2, y2) {
5522-
var sx = (x1 + x2) * .5, sy = (y1 + y2) * .5, right = x >= sx, bottom = y >= sy, i = (bottom << 1) + right;
5522+
var xm = (x1 + x2) * .5, ym = (y1 + y2) * .5, right = x >= xm, below = y >= ym, i = below << 1 | right;
55235523
n.leaf = false;
55245524
n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode());
5525-
if (right) x1 = sx; else x2 = sx;
5526-
if (bottom) y1 = sy; else y2 = sy;
5525+
if (right) x1 = xm; else x2 = xm;
5526+
if (below) y1 = ym; else y2 = ym;
55275527
insert(n, d, x, y, x1, y1, x2, y2);
55285528
}
55295529
var root = d3_geom_quadtreeNode();
@@ -5603,11 +5603,14 @@
56035603
closestPoint = point;
56045604
}
56055605
}
5606-
var children = node.nodes, xm = (x1 + x2) * .5, ym = (y1 + y2) * .5, right = x > xm, below = y > ym;
5607-
if (node = children[below << 1 | right]) find(node, right ? xm : x1, below ? ym : y1, right ? x2 : xm, below ? y2 : ym);
5608-
if (node = children[below << 1 | !right]) find(node, right ? x1 : xm, below ? ym : y1, right ? xm : x2, below ? y2 : ym);
5609-
if (node = children[!below << 1 | right]) find(node, right ? xm : x1, below ? y1 : ym, right ? x2 : xm, below ? ym : y2);
5610-
if (node = children[!below << 1 | !right]) find(node, right ? x1 : xm, below ? y1 : ym, right ? xm : x2, below ? ym : y2);
5606+
var children = node.nodes, xm = (x1 + x2) * .5, ym = (y1 + y2) * .5, right = x >= xm, below = y >= ym;
5607+
var i = below << 1 | right, cx0, cy0, cx1, cy1, node;
5608+
for (var j = i + 4; i < j; ++i) {
5609+
if (!(node = children[i & 3])) continue;
5610+
if (i & 1) cx0 = xm, cx1 = x2; else cx0 = x1, cx1 = xm;
5611+
if (i & 2) cy0 = ym, cy1 = y2; else cy0 = y1, cy1 = ym;
5612+
find(node, cx0, cy0, cx1, cy1);
5613+
}
56115614
})(root, x0, y0, x3, y3);
56125615
return closestPoint;
56135616
}

‎d3.min.js‎

Lines changed: 3 additions & 3 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/geom/quadtree.js‎

Lines changed: 18 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -98,19 +98,19 @@ d3.geom.quadtree = function(points, x1, y1, x2, y2) {
9898
// n. The bounds are defined by [x1, x2] and [y1, y2].
9999
function insertChild(n, d, x, y, x1, y1, x2, y2) {
100100
// Compute the split point, and the quadrant in which to insert p.
101-
var sx = (x1 + x2) * .5,
102-
sy = (y1 + y2) * .5,
103-
right = x >= sx,
104-
bottom = y >= sy,
105-
i = (bottom << 1) + right;
101+
var xm = (x1 + x2) * .5,
102+
ym = (y1 + y2) * .5,
103+
right = x >= xm,
104+
below = y >= ym,
105+
i = below << 1 | right;
106106

107107
// Recursively insert into the child node.
108108
n.leaf = false;
109109
n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode());
110110

111111
// Update the bounds as we recurse.
112-
if (right) x1 = sx; else x2 = sx;
113-
if (bottom) y1 = sy; else y2 = sy;
112+
if (right) x1 = xm; else x2 = xm;
113+
if (below) y1 = ym; else y2 = ym;
114114
insert(n, d, x, y, x1, y1, x2, y2);
115115
}
116116

@@ -225,15 +225,19 @@ function d3_geom_quadtreeFind(root, x, y, x0, y0, x3, y3) {
225225
var children = node.nodes,
226226
xm = (x1 + x2) * .5,
227227
ym = (y1 + y2) * .5,
228-
right = x > xm,
229-
below = y > ym;
228+
right = x >= xm,
229+
below = y >= ym;
230230

231231
// visit closest cell first
232-
// TODO would be nice to reducing branching here!
233-
if (node = children[below << 1 | right]) find(node, right ? xm : x1, below ? ym : y1, right ? x2 : xm, below ? y2 : ym);
234-
if (node = children[below << 1 | !right]) find(node, right ? x1 : xm, below ? ym : y1, right ? xm : x2, below ? y2 : ym);
235-
if (node = children[!below << 1 | right]) find(node, right ? xm : x1, below ? y1 : ym, right ? x2 : xm, below ? ym : y2);
236-
if (node = children[!below << 1 | !right]) find(node, right ? x1 : xm, below ? y1 : ym, right ? xm : x2, below ? ym : y2);
232+
var i = below << 1 | right,
233+
cx0, cy0, cx1, cy1,
234+
node;
235+
for (var j = i + 4; i < j; ++i) {
236+
if (!(node = children[i & 3])) continue;
237+
if (i & 1) cx0 = xm, cx1 = x2; else cx0 = x1, cx1 = xm;
238+
if (i & 2) cy0 = ym, cy1 = y2; else cy0 = y1, cy1 = ym;
239+
find(node, cx0, cy0, cx1, cy1);
240+
}
237241
})(root, x0, y0, x3, y3);
238242

239243
return closestPoint;

‎test/geom/quadtree-test.js‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
var vows = require("vows"),
22
load = require("../load"),
3-
assert = require("../assert");
3+
assert = require("../assert"),
4+
_ = require("../../");
45

56
var suite = vows.describe("d3.geom.quadtree");
67

@@ -37,6 +38,15 @@ suite.addBatch({
3738
++n;
3839
});
3940
assert.strictEqual(n, 1, "number of visits");
41+
},
42+
"find locates the closest point to a given point": function(q) {
43+
var dx = 17, dy = 17,
44+
points = _.range(dx * dy).map(function(i) { return [i % dx, i / dx | 0]; });
45+
q = q(points);
46+
assert.deepEqual(q.find(.1, .1), [0, 0]);
47+
assert.deepEqual(q.find(7.5, 7.5), [7, 7]);
48+
assert.deepEqual(q.find(.1, 15.9), [0, 16]);
49+
assert.deepEqual(q.find(15.9, 15.9), [16, 16]);
4050
}
4151
},
4252
"the quadtree applied directly": {

0 commit comments

Comments
 (0)