Skip to content

Commit 41c91fd

Browse files
mbostockmbostock
committed
Merge branch 'force'
2 parents ce07649 + 1a6163c commit 41c91fd

9 files changed

Lines changed: 338 additions & 16 deletions

File tree

‎Makefile‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,7 @@ d3.geom.js: \
117117
src/geom/polygon.js \
118118
src/geom/voronoi.js \
119119
src/geom/delaunay.js \
120+
src/geom/quadtree.js \
120121
src/end.js
121122

122123
%.min.js: %.js Makefile

‎d3.geom.js‎

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -672,4 +672,126 @@ d3.geom.delaunay = function(vertices) {
672672

673673
return triangles;
674674
};
675+
/**
676+
* Constructs a new quadtree for the specified array of points. A quadtree is a
677+
* two-dimensional recursive spatial subdivision. This implementation uses
678+
* square partitions, dividing each square into four equally-sized squares. Each
679+
* point exists in a unique node; if multiple points are in the same position,
680+
* some points may be stored on internal nodes rather than leaf nodes. Quadtrees
681+
* can be used to accelerate various spatial operations, such as the Barnes-Hut
682+
* approximation for computing n-body forces, or collision detection.
683+
*
684+
* @param points [[x1, y1], [x2, y2], …]
685+
* @return quadtree root {left: boolean, nodes: […], point: [x, y]}
686+
*/
687+
d3.geom.quadtree = function(points) {
688+
var p,
689+
i = -1,
690+
n = points.length;
691+
692+
/* Compute bounds. */
693+
var x1 = Number.POSITIVE_INFINITY, y1 = x1,
694+
x2 = Number.NEGATIVE_INFINITY, y2 = x2;
695+
while (++i < n) {
696+
p = points[i];
697+
if (p[0] < x1) x1 = p[0];
698+
if (p[1] < y1) y1 = p[1];
699+
if (p[0] > x2) x2 = p[0];
700+
if (p[1] > y2) y2 = p[1];
701+
}
702+
703+
/* Squarify the bounds. */
704+
var dx = x2 - x1,
705+
dy = y2 - y1;
706+
if (dx > dy) y2 = y1 + dx;
707+
else x2 = x1 + dy;
708+
709+
/**
710+
* @ignore Recursively inserts the specified point <i>p</i> at the node
711+
* <i>n</i> or one of its descendants. The bounds are defined by [<i>x1</i>,
712+
* <i>x2</i>] and [<i>y1</i>, <i>y2</i>].
713+
*/
714+
function insert(n, p, x1, y1, x2, y2) {
715+
if (isNaN(p[0]) || isNaN(p[1])) return; // ignore invalid points
716+
if (n.leaf) {
717+
var v = n.point;
718+
if (v) {
719+
/*
720+
* If the point at this leaf node is at the same position as the new
721+
* point we are adding, we leave the point associated with the
722+
* internal node while adding the new point to a child node. This
723+
* avoids infinite recursion.
724+
*/
725+
if ((Math.abs(v[0] - p[0]) + Math.abs(v[1] - p[1])) < .01) {
726+
insertChild(n, p, x1, y1, x2, y2);
727+
} else {
728+
n.point = null;
729+
insertChild(n, v, x1, y1, x2, y2);
730+
insertChild(n, p, x1, y1, x2, y2);
731+
}
732+
} else {
733+
n.point = p;
734+
}
735+
} else {
736+
insertChild(n, p, x1, y1, x2, y2);
737+
}
738+
}
739+
740+
/**
741+
* @ignore Recursively inserts the specified point <i>p</i> into a
742+
* descendant of node <i>n</i>. The bounds are defined by [<i>x1</i>,
743+
* <i>x2</i>] and [<i>y1</i>, <i>y2</i>].
744+
*/
745+
function insertChild(n, p, x1, y1, x2, y2) {
746+
/* Compute the split point, and the quadrant in which to insert p. */
747+
var sx = (x1 + x2) * .5,
748+
sy = (y1 + y2) * .5,
749+
right = p[0] >= sx,
750+
bottom = p[1] >= sy,
751+
i = (bottom << 1) + right;
752+
753+
/* Recursively insert into the child node. */
754+
n.leaf = false;
755+
n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode());
756+
757+
/* Update the bounds as we recurse. */
758+
if (right) x1 = sx; else x2 = sx;
759+
if (bottom) y1 = sy; else y2 = sy;
760+
insert(n, p, x1, y1, x2, y2);
761+
}
762+
763+
/* Create the root node. */
764+
var root = d3_geom_quadtreeNode();
765+
766+
/* Insert all points. */
767+
i = -1;
768+
while (++i < n) insert(root, points[i], x1, y1, x2, y2);
769+
770+
/* Register a visitor function for the root. */
771+
root.visit = function(f) {
772+
d3_geom_quadtreeVisit(f, root, x1, y1, x2, y2);
773+
};
774+
775+
return root;
776+
};
777+
778+
function d3_geom_quadtreeNode() {
779+
return {
780+
leaf: true,
781+
nodes: [],
782+
point: null
783+
};
784+
}
785+
786+
function d3_geom_quadtreeVisit(f, node, x1, y1, x2, y2) {
787+
if (!f(node, x1, y1, x2, y2)) {
788+
var sx = (x1 + x2) * .5,
789+
sy = (y1 + y2) * .5,
790+
children = node.nodes;
791+
if (children[0]) d3_geom_quadtreeVisit(f, children[0], x1, y1, sx, sy);
792+
if (children[1]) d3_geom_quadtreeVisit(f, children[1], sx, y1, x2, sy);
793+
if (children[2]) d3_geom_quadtreeVisit(f, children[2], x1, sy, sx, y2);
794+
if (children[3]) d3_geom_quadtreeVisit(f, children[3], sx, sy, x2, y2);
795+
}
796+
}
675797
})()

‎d3.geom.min.js‎

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

‎d3.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
(function(){d3 = {version: "0.29.2"}; // semver
1+
(function(){d3 = {version: "0.29.3"}; // semver
22
if (!Date.now) Date.now = function() {
33
return +new Date();
44
};

0 commit comments

Comments
 (0)