d3.layout.pack = function() { var hierarchy = d3.layout.hierarchy().sort(d3_layout_packSort), size = [1, 1]; function pack(d, i) { var nodes = hierarchy.call(this, d, i), root = nodes[0]; // Recursively compute the layout. root.x = 0; root.y = 0; d3_layout_packTree(root); // Scale the layout to fit the requested size. var w = size[0], h = size[1], k = 1 / Math.max(2 * root.r / w, 2 * root.r / h); d3_layout_packTransform(root, w / 2, h / 2, k); return nodes; } pack.size = function(x) { if (!arguments.length) return size; size = x; return pack; }; return d3_layout_hierarchyRebind(pack, hierarchy); }; function d3_layout_packSort(a, b) { return a.value - b.value; } function d3_layout_packInsert(a, b) { var c = a._pack_next; a._pack_next = b; b._pack_prev = a; b._pack_next = c; c._pack_prev = b; } function d3_layout_packSplice(a, b) { a._pack_next = b; b._pack_prev = a; } function d3_layout_packIntersects(a, b) { var dx = b.x - a.x, dy = b.y - a.y, dr = a.r + b.r; return (dr * dr - dx * dx - dy * dy) > .001; // within epsilon } function d3_layout_packCircle(nodes) { var xMin = Infinity, xMax = -Infinity, yMin = Infinity, yMax = -Infinity, n = nodes.length, a, b, c, j, k; function bound(node) { xMin = Math.min(node.x - node.r, xMin); xMax = Math.max(node.x + node.r, xMax); yMin = Math.min(node.y - node.r, yMin); yMax = Math.max(node.y + node.r, yMax); } // Create node links. nodes.forEach(d3_layout_packLink); // Create first node. a = nodes[0]; a.x = -a.r; a.y = 0; bound(a); // Create second node. if (n > 1) { b = nodes[1]; b.x = b.r; b.y = 0; bound(b); // Create third node and build chain. if (n > 2) { c = nodes[2]; d3_layout_packPlace(a, b, c); bound(c); d3_layout_packInsert(a, c); a._pack_prev = c; d3_layout_packInsert(c, b); b = a._pack_next; // Now iterate through the rest. for (var i = 3; i < n; i++) { d3_layout_packPlace(a, b, c = nodes[i]); // Search for the closest intersection. var isect = 0, s1 = 1, s2 = 1; for (j = b._pack_next; j !== b; j = j._pack_next, s1++) { if (d3_layout_packIntersects(j, c)) { isect = 1; break; } } if (isect == 1) { for (k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) { if (d3_layout_packIntersects(k, c)) { if (s2 < s1) { isect = -1; j = k; } break; } } } // Update node chain. if (isect == 0) { d3_layout_packInsert(a, c); b = c; bound(c); } else if (isect > 0) { d3_layout_packSplice(a, j); b = j; i--; } else { // isect < 0 d3_layout_packSplice(j, b); a = j; i--; } } } } // Re-center the circles and return the encompassing radius. var cx = (xMin + xMax) / 2, cy = (yMin + yMax) / 2, cr = 0; for (var i = 0; i < n; i++) { var node = nodes[i]; node.x -= cx; node.y -= cy; cr = Math.max(cr, node.r + Math.sqrt(node.x * node.x + node.y * node.y)); } // Remove node links. nodes.forEach(d3_layout_packUnlink); return cr; } function d3_layout_packLink(node) { node._pack_next = node._pack_prev = node; } function d3_layout_packUnlink(node) { delete node._pack_next; delete node._pack_prev; } function d3_layout_packTree(node) { var children = node.children; if (children) { children.forEach(d3_layout_packTree); node.r = d3_layout_packCircle(children); } else { node.r = Math.sqrt(node.value); } } function d3_layout_packTransform(node, x, y, k) { var children = node.children; node.x = (x += k * node.x); node.y = (y += k * node.y); node.r *= k; if (children) { var i = -1, n = children.length; while (++i < n) d3_layout_packTransform(children[i], x, y, k); } } function d3_layout_packPlace(a, b, c) { var da = b.r + c.r, db = a.r + c.r, dx = b.x - a.x, dy = b.y - a.y, dc = Math.sqrt(dx * dx + dy * dy), cos = (db * db + dc * dc - da * da) / (2 * db * dc), theta = Math.acos(cos), x = cos * db, h = Math.sin(theta) * db; dx /= dc; dy /= dc; c.x = a.x + x * dx + h * dy; c.y = a.y + x * dy - h * dx; }