(data)
| 4825 | return quadtree(points); |
| 4826 | } |
| 4827 | function quadtree(data) { |
| 4828 | var d, fx = d3_functor(x), fy = d3_functor(y), xs, ys, i, n, x1_, y1_, x2_, y2_; |
| 4829 | if (x1 != null) { |
| 4830 | x1_ = x1, y1_ = y1, x2_ = x2, y2_ = y2; |
| 4831 | } else { |
| 4832 | x2_ = y2_ = -(x1_ = y1_ = Infinity); |
| 4833 | xs = [], ys = []; |
| 4834 | n = data.length; |
| 4835 | if (compat) for (i = 0; i < n; ++i) { |
| 4836 | d = data[i]; |
| 4837 | if (d.x < x1_) x1_ = d.x; |
| 4838 | if (d.y < y1_) y1_ = d.y; |
| 4839 | if (d.x > x2_) x2_ = d.x; |
| 4840 | if (d.y > y2_) y2_ = d.y; |
| 4841 | xs.push(d.x); |
| 4842 | ys.push(d.y); |
| 4843 | } else for (i = 0; i < n; ++i) { |
| 4844 | var x_ = +fx(d = data[i], i), y_ = +fy(d, i); |
| 4845 | if (x_ < x1_) x1_ = x_; |
| 4846 | if (y_ < y1_) y1_ = y_; |
| 4847 | if (x_ > x2_) x2_ = x_; |
| 4848 | if (y_ > y2_) y2_ = y_; |
| 4849 | xs.push(x_); |
| 4850 | ys.push(y_); |
| 4851 | } |
| 4852 | } |
| 4853 | var dx = x2_ - x1_, dy = y2_ - y1_; |
| 4854 | if (dx > dy) y2_ = y1_ + dx; else x2_ = x1_ + dy; |
| 4855 | function insert(n, d, x, y, x1, y1, x2, y2) { |
| 4856 | if (isNaN(x) || isNaN(y)) return; |
| 4857 | if (n.leaf) { |
| 4858 | var nx = n.x, ny = n.y; |
| 4859 | if (nx != null) { |
| 4860 | if (Math.abs(nx - x) + Math.abs(ny - y) < .01) { |
| 4861 | insertChild(n, d, x, y, x1, y1, x2, y2); |
| 4862 | } else { |
| 4863 | var nPoint = n.point; |
| 4864 | n.x = n.y = n.point = null; |
| 4865 | insertChild(n, nPoint, nx, ny, x1, y1, x2, y2); |
| 4866 | insertChild(n, d, x, y, x1, y1, x2, y2); |
| 4867 | } |
| 4868 | } else { |
| 4869 | n.x = x, n.y = y, n.point = d; |
| 4870 | } |
| 4871 | } else { |
| 4872 | insertChild(n, d, x, y, x1, y1, x2, y2); |
| 4873 | } |
| 4874 | } |
| 4875 | function insertChild(n, d, x, y, x1, y1, x2, y2) { |
| 4876 | var sx = (x1 + x2) * .5, sy = (y1 + y2) * .5, right = x >= sx, bottom = y >= sy, i = (bottom << 1) + right; |
| 4877 | n.leaf = false; |
| 4878 | n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode()); |
| 4879 | if (right) x1 = sx; else x2 = sx; |
| 4880 | if (bottom) y1 = sy; else y2 = sy; |
| 4881 | insert(n, d, x, y, x1, y1, x2, y2); |
| 4882 | } |
| 4883 | var root = d3_geom_quadtreeNode(); |
| 4884 | root.add = function(d) { |
no test coverage detected