Skip to content

Commit a770792

Browse files
mbostockmbostock
committed
Add tests for d3.geom.quadtree.
Also remove backwards-compatibility for [x, y] input.
1 parent b957752 commit a770792

4 files changed

Lines changed: 106 additions & 40 deletions

File tree

‎d3.js‎

Lines changed: 5 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2745,12 +2745,6 @@
27452745
if (children[3]) d3_geom_quadtreeVisit(f, children[3], sx, sy, x2, y2);
27462746
}
27472747
}
2748-
function d3_geom_quadtreePoint(p) {
2749-
return {
2750-
x: p[0],
2751-
y: p[1]
2752-
};
2753-
}
27542748
function d3_time_utc() {
27552749
this._ = new Date(arguments.length > 1 ? Date.UTC.apply(this, arguments) : arguments[0]);
27562750
}
@@ -7050,11 +7044,11 @@
70507044
insert(n, p, x1, y1, x2, y2);
70517045
}
70527046
var p, i = -1, n = points.length;
7053-
if (n && isNaN(points[0].x)) points = points.map(d3_geom_quadtreePoint);
70547047
if (arguments.length < 5) {
70557048
if (arguments.length === 3) {
7056-
y2 = x2 = y1;
7057-
y1 = x1;
7049+
y2 = y1;
7050+
x2 = x1;
7051+
y1 = x1 = 0;
70587052
} else {
70597053
x1 = y1 = Infinity;
70607054
x2 = y2 = -Infinity;
@@ -7065,10 +7059,10 @@
70657059
if (p.x > x2) x2 = p.x;
70667060
if (p.y > y2) y2 = p.y;
70677061
}
7068-
var dx = x2 - x1, dy = y2 - y1;
7069-
if (dx > dy) y2 = y1 + dx; else x2 = x1 + dy;
70707062
}
70717063
}
7064+
var dx = x2 - x1, dy = y2 - y1;
7065+
if (dx > dy) y2 = y1 + dx; else x2 = x1 + dy;
70727066
var root = d3_geom_quadtreeNode();
70737067
root.add = function(p) {
70747068
insert(root, p, x1, y1, x2, y2);

‎d3.min.js‎

Lines changed: 4 additions & 4 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: 9 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,14 @@
1-
// Constructs a new quadtree for the specified array of points. A quadtree is a
2-
// two-dimensional recursive spatial subdivision. This implementation uses
3-
// square partitions, dividing each square into four equally-sized squares. Each
4-
// point exists in a unique node; if multiple points are in the same position,
5-
// some points may be stored on internal nodes rather than leaf nodes. Quadtrees
6-
// can be used to accelerate various spatial operations, such as the Barnes-Hut
7-
// approximation for computing n-body forces, or collision detection.
81
d3.geom.quadtree = function(points, x1, y1, x2, y2) {
92
var p,
103
i = -1,
114
n = points.length;
125

13-
// Type conversion for deprecated API.
14-
if (n && isNaN(points[0].x)) points = points.map(d3_geom_quadtreePoint);
15-
166
// Allow bounds to be specified explicitly.
177
if (arguments.length < 5) {
188
if (arguments.length === 3) {
19-
y2 = x2 = y1;
20-
y1 = x1;
9+
y2 = y1;
10+
x2 = x1;
11+
y1 = x1 = 0;
2112
} else {
2213
x1 = y1 = Infinity;
2314
x2 = y2 = -Infinity;
@@ -30,15 +21,15 @@ d3.geom.quadtree = function(points, x1, y1, x2, y2) {
3021
if (p.x > x2) x2 = p.x;
3122
if (p.y > y2) y2 = p.y;
3223
}
33-
34-
// Squarify the bounds.
35-
var dx = x2 - x1,
36-
dy = y2 - y1;
37-
if (dx > dy) y2 = y1 + dx;
38-
else x2 = x1 + dy;
3924
}
4025
}
4126

27+
// Squarify the bounds.
28+
var dx = x2 - x1,
29+
dy = y2 - y1;
30+
if (dx > dy) y2 = y1 + dx;
31+
else x2 = x1 + dy;
32+
4233
// Recursively inserts the specified point p at the node n or one of its
4334
// descendants. The bounds are defined by [x1, x2] and [y1, y2].
4435
function insert(n, p, x1, y1, x2, y2) {
@@ -120,10 +111,3 @@ function d3_geom_quadtreeVisit(f, node, x1, y1, x2, y2) {
120111
if (children[3]) d3_geom_quadtreeVisit(f, children[3], sx, sy, x2, y2);
121112
}
122113
}
123-
124-
function d3_geom_quadtreePoint(p) {
125-
return {
126-
x: p[0],
127-
y: p[1]
128-
};
129-
}

‎test/geom/quadtree-test.js‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
require("../env");
2+
3+
var vows = require("vows"),
4+
assert = require("assert");
5+
6+
var suite = vows.describe("d3.geom.quadtree");
7+
8+
suite.addBatch({
9+
"can create an empty quadtree": function() {
10+
var q = d3.geom.quadtree([], 8, 10, 56, 47),
11+
n = 0;
12+
q.visit(function(node, x1, y1, x2, y2) {
13+
assert.isNull(node.point);
14+
assert.isUndefined(node[0]);
15+
assert.isUndefined(node[1]);
16+
assert.isUndefined(node[2]);
17+
assert.isUndefined(node[3]);
18+
assert.isTrue(node.leaf);
19+
++n;
20+
});
21+
assert.strictEqual(n, 1, "number of visits");
22+
},
23+
"squarifies the input dimensions": function() {
24+
var ox1 = 8,
25+
oy1 = 10,
26+
ox2 = 56,
27+
oy2 = 47,
28+
q = d3.geom.quadtree([], ox1, oy1, ox2, oy2),
29+
n = 0;
30+
q.visit(function(node, x1, y1, x2, y2) {
31+
assert.strictEqual(x1, ox1);
32+
assert.strictEqual(y1, oy1);
33+
assert.strictEqual(x2, Math.max(ox2 - ox1, oy2 - oy1) + x1);
34+
assert.strictEqual(y2, Math.max(ox2 - ox1, oy2 - oy1) + y1);
35+
++n;
36+
});
37+
assert.strictEqual(n, 1, "number of visits");
38+
},
39+
"with three arguments, x1 and y1 are 0,0": function() {
40+
var dx = 56,
41+
dy = 47,
42+
q = d3.geom.quadtree([], dx, dy),
43+
n = 0;
44+
q.visit(function(node, x1, y1, x2, y2) {
45+
assert.strictEqual(x1, 0);
46+
assert.strictEqual(y1, 0);
47+
assert.strictEqual(x2, Math.max(dx, dy));
48+
assert.strictEqual(y2, Math.max(dx, dy));
49+
++n;
50+
});
51+
assert.strictEqual(n, 1, "number of visits");
52+
},
53+
"visit": {
54+
"uses pre-order traversal": function() {
55+
var a = {x: 100, y: 100},
56+
b = {x: 200, y: 200},
57+
c = {x: 300, y: 300},
58+
q = d3.geom.quadtree([a, b, c], 960, 500),
59+
expected = [
60+
{point: null, x1: 0, y1: 0, x2: 960, y2: 960},
61+
{point: null, x1: 0, y1: 0, x2: 480, y2: 480},
62+
{point: null, x1: 0, y1: 0, x2: 240, y2: 240},
63+
{point: a, x1: 0, y1: 0, x2: 120, y2: 120},
64+
{point: b, x1: 120, y1: 120, x2: 240, y2: 240},
65+
{point: c, x1: 240, y1: 240, x2: 480, y2: 480}
66+
];
67+
q.visit(function(node, x1, y1, x2, y2) {
68+
assert.deepEqual({point: node.point, x1: x1, y1: y1, x2: x2, y2: y2}, expected.shift());
69+
assert.equal(!!node.point, node.leaf);
70+
});
71+
assert.isEmpty(expected);
72+
},
73+
"does not recurse if the callback returns truthy": function() {
74+
var a = {x: 100, y: 100},
75+
b = {x: 700, y: 700},
76+
c = {x: 800, y: 800},
77+
q = d3.geom.quadtree([a, b, c], 960, 500),
78+
n = 0;
79+
q.visit(function(node, x1, y1, x2, y2) {
80+
++n;
81+
return x1 > 0;
82+
});
83+
assert.equal(n, 3);
84+
}
85+
}
86+
});
87+
88+
suite.export(module);

0 commit comments

Comments
 (0)