(data)
| 4510 | return quadtree(points); |
| 4511 | } |
| 4512 | function quadtree(data) { |
| 4513 | var d, fx = d3_functor(x), fy = d3_functor(y), xs, ys, i, n, x1_, y1_, x2_, y2_; |
| 4514 | if (x1 != null) { |
| 4515 | x1_ = x1, y1_ = y1, x2_ = x2, y2_ = y2; |
| 4516 | } else { |
| 4517 | x2_ = y2_ = -(x1_ = y1_ = Infinity); |
| 4518 | xs = [], ys = []; |
| 4519 | n = data.length; |
| 4520 | if (compat) for (i = 0; i < n; ++i) { |
| 4521 | d = data[i]; |
| 4522 | if (d.x < x1_) x1_ = d.x; |
| 4523 | if (d.y < y1_) y1_ = d.y; |
| 4524 | if (d.x > x2_) x2_ = d.x; |
| 4525 | if (d.y > y2_) y2_ = d.y; |
| 4526 | xs.push(d.x); |
| 4527 | ys.push(d.y); |
| 4528 | } else for (i = 0; i < n; ++i) { |
| 4529 | var x_ = +fx(d = data[i], i), y_ = +fy(d, i); |
| 4530 | if (x_ < x1_) x1_ = x_; |
| 4531 | if (y_ < y1_) y1_ = y_; |
| 4532 | if (x_ > x2_) x2_ = x_; |
| 4533 | if (y_ > y2_) y2_ = y_; |
| 4534 | xs.push(x_); |
| 4535 | ys.push(y_); |
| 4536 | } |
| 4537 | } |
| 4538 | var dx = x2_ - x1_, dy = y2_ - y1_; |
| 4539 | if (dx > dy) y2_ = y1_ + dx; else x2_ = x1_ + dy; |
| 4540 | function insert(n, d, x, y, x1, y1, x2, y2) { |
| 4541 | if (isNaN(x) || isNaN(y)) return; |
| 4542 | if (n.leaf) { |
| 4543 | var nx = n.x, ny = n.y; |
| 4544 | if (nx != null) { |
| 4545 | if (Math.abs(nx - x) + Math.abs(ny - y) < .01) { |
| 4546 | insertChild(n, d, x, y, x1, y1, x2, y2); |
| 4547 | } else { |
| 4548 | var nPoint = n.point; |
| 4549 | n.x = n.y = n.point = null; |
| 4550 | insertChild(n, nPoint, nx, ny, x1, y1, x2, y2); |
| 4551 | insertChild(n, d, x, y, x1, y1, x2, y2); |
| 4552 | } |
| 4553 | } else { |
| 4554 | n.x = x, n.y = y, n.point = d; |
| 4555 | } |
| 4556 | } else { |
| 4557 | insertChild(n, d, x, y, x1, y1, x2, y2); |
| 4558 | } |
| 4559 | } |
| 4560 | function insertChild(n, d, x, y, x1, y1, x2, y2) { |
| 4561 | var sx = (x1 + x2) * .5, sy = (y1 + y2) * .5, right = x >= sx, bottom = y >= sy, i = (bottom << 1) + right; |
| 4562 | n.leaf = false; |
| 4563 | n = n.nodes[i] || (n.nodes[i] = d3_geom_quadtreeNode()); |
| 4564 | if (right) x1 = sx; else x2 = sx; |
| 4565 | if (bottom) y1 = sy; else y2 = sy; |
| 4566 | insert(n, d, x, y, x1, y1, x2, y2); |
| 4567 | } |
| 4568 | var root = d3_geom_quadtreeNode(); |
| 4569 | root.add = function(d) { |
no test coverage detected