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.

     8 d3.geom.quadtree = function(points, x1, y1, x2, y2) {

     9   var p,

    10       i = -1,

    11       n = points.length;

    12 

    13   // Type conversion for deprecated API.

    14   if (n && isNaN(points[0].x)) points = points.map(d3_geom_quadtreePoint);

    15 

    16   // Allow bounds to be specified explicitly.

    17   if (arguments.length < 5) {

    18     if (arguments.length === 3) {

    19       y2 = x2 = y1;

    20       y1 = x1;

    21     } else {

    22       x1 = y1 = Infinity;

    23       x2 = y2 = -Infinity;

    24 

    25       // Compute bounds.

    26       while (++i < n) {

    27         p = points[i];

    28         if (p.x < x1) x1 = p.x;

    29         if (p.y < y1) y1 = p.y;

    30         if (p.x > x2) x2 = p.x;

    31         if (p.y > y2) y2 = p.y;

    32       }

    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;

    39     }

    40   }

    41 

    42   // Recursively inserts the specified point p at the node n or one of its

    43   // descendants. The bounds are defined by [x1, x2] and [y1, y2].

    44   function insert(n, p, x1, y1, x2, y2) {

    45     if (isNaN(p.x) || isNaN(p.y)) return; // ignore invalid points

    46     if (n.leaf) {

    47       var v = n.point;

    48       if (v) {

    49         // If the point at this leaf node is at the same position as the new

    50         // point we are adding, we leave the point associated with the

    51         // internal node while adding the new point to a child node. This

    52         // avoids infinite recursion.

    53         if ((Math.abs(v.x - p.x) + Math.abs(v.y - p.y)) < .01) {

    54           insertChild(n, p, x1, y1, x2, y2);

    55         } else {

    56           n.point = null;

    57           insertChild(n, v, x1, y1, x2, y2);

    58           insertChild(n, p, x1, y1, x2, y2);

    59         }

    60       } else {

    61         n.point = p;

    62       }

    63     } else {

    64       insertChild(n, p, x1, y1, x2, y2);

    65     }

    66   }

    67 

    68   // Recursively inserts the specified point p into a descendant of node n. The

    69   // bounds are defined by [x1, x2] and [y1, y2].

    70   function insertChild(n, p, x1, y1, x2, y2) {

    71     // Compute the split point, and the quadrant in which to insert p.

    72     var sx = (x1 + x2) * .5,

    73         sy = (y1 + y2) * .5,

    74         right = p.x >= sx,

    75         bottom = p.y >= sy,

    76         i = (bottom << 1) + right;

    77 

    78     // Recursively insert into the child node.

    79     n.leaf = false;

    80     n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode());

    81 

    82     // Update the bounds as we recurse.

    83     if (right) x1 = sx; else x2 = sx;

    84     if (bottom) y1 = sy; else y2 = sy;

    85     insert(n, p, x1, y1, x2, y2);

    86   }

    87 

    88   // Create the root node.

    89   var root = d3_geom_quadtreeNode();

    90 

    91   root.add = function(p) {

    92     insert(root, p, x1, y1, x2, y2);

    93   };

    94 

    95   root.visit = function(f) {

    96     d3_geom_quadtreeVisit(f, root, x1, y1, x2, y2);

    97   };

    98 

    99   // Insert all points.

   100   points.forEach(root.add);

   101   return root;

   102 };

   103 

   104 function d3_geom_quadtreeNode() {

   105   return {

   106     leaf: true,

   107     nodes: [],

   108     point: null

   109   };

   110 }

   111 

   112 function d3_geom_quadtreeVisit(f, node, x1, y1, x2, y2) {

   113   if (!f(node, x1, y1, x2, y2)) {

   114     var sx = (x1 + x2) * .5,

   115         sy = (y1 + y2) * .5,

   116         children = node.nodes;

   117     if (children[0]) d3_geom_quadtreeVisit(f, children[0], x1, y1, sx, sy);

   118     if (children[1]) d3_geom_quadtreeVisit(f, children[1], sx, y1, x2, sy);

   119     if (children[2]) d3_geom_quadtreeVisit(f, children[2], x1, sy, sx, y2);

   120     if (children[3]) d3_geom_quadtreeVisit(f, children[3], sx, sy, x2, y2);

   121   }

   122 }

   123 

   124 function d3_geom_quadtreePoint(p) {

   125   return {

   126     x: p[0],

   127     y: p[1]

   128   };

   129 }