Skip to content

Commit ccfbb06

Browse files
jasondaviesjasondavies
committed
Add circle-packing layout.
Based on the Protovis layout. I've kept the convention of using `size` for the width/height and `separation` for the spacing. The Protovis layout had a `size` property but this was used to compute the radius. I've left this out as I've assumed it's straightforward enough to pass in the appropriate `radius` function instead. Likewise, I think the existing hierarchy `sort` property can handle situations that `order` was intended for in the Protovis version.
1 parent 9f71e4e commit ccfbb06

9 files changed

Lines changed: 797 additions & 1 deletion

File tree

‎Makefile‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -105,6 +105,7 @@ d3.layout.js: \
105105
src/layout/pie.js \
106106
src/layout/stack.js \
107107
src/layout/hierarchy.js \
108+
src/layout/pack.js \
108109
src/layout/tree.js \
109110
src/layout/treemap.js \
110111
src/end.js

‎d3.layout.js‎

Lines changed: 222 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -739,6 +739,228 @@ function d3_layout_hierarchyValue(d) {
739739
function d3_layout_hierarchySort(a, b) {
740740
return b.value - a.value;
741741
}
742+
d3.layout.pack = function() {
743+
var hierarchy = d3.layout.hierarchy(),
744+
separation = 1, // spacing
745+
size = [1, 1];
746+
radius = d3_layout_packRadius;
747+
748+
function pack(d, i) {
749+
var nodes = hierarchy.call(this, d, i),
750+
root = nodes[0];
751+
752+
d3_layout_packRadii(nodes, radius);
753+
754+
/* Recursively compute the layout. */
755+
root.x = 0;
756+
root.y = 0;
757+
root.radius = d3_layout_packTree(root, separation);
758+
759+
var w = size[0],
760+
h = size[1],
761+
k = 1 / Math.max(2 * root.radius / w, 2 * root.radius / h);
762+
d3_layout_packTransform(root, w / 2, h / 2, k);
763+
return nodes;
764+
}
765+
766+
pack.sort = d3.rebind(pack, hierarchy.sort);
767+
pack.children = d3.rebind(pack, hierarchy.children);
768+
pack.value = d3.rebind(pack, hierarchy.value);
769+
770+
pack.separation = function(x) {
771+
if (!arguments.length) return separation;
772+
separation = x;
773+
return pack;
774+
};
775+
776+
pack.size = function(x) {
777+
if (!arguments.length) return size;
778+
size = x;
779+
return pack;
780+
};
781+
782+
pack.radius = function(x) {
783+
if (!arguments.length) return radius;
784+
radius = x;
785+
return pack;
786+
};
787+
788+
return pack;
789+
};
790+
791+
function d3_layout_packRadius(d) {
792+
return d.radius;
793+
}
794+
795+
function d3_layout_packCircle(nodes, spacing) {
796+
var xMin = Infinity,
797+
xMax = -Infinity,
798+
yMin = Infinity,
799+
yMax = -Infinity,
800+
a, b, c, j, k;
801+
802+
function bound(n) {
803+
xMin = Math.min(n.x - n.radius, xMin);
804+
xMax = Math.max(n.x + n.radius, xMax);
805+
yMin = Math.min(n.y - n.radius, yMin);
806+
yMax = Math.max(n.y + n.radius, yMax);
807+
}
808+
809+
function insert(a, b) {
810+
var c = a.n;
811+
a.n = b;
812+
b.p = a;
813+
b.n = c;
814+
c.p = b;
815+
}
816+
817+
function splice(a, b) {
818+
a.n = b;
819+
b.p = a;
820+
}
821+
822+
function intersects(a, b) {
823+
var dx = b.x - a.x,
824+
dy = b.y - a.y,
825+
dr = a.radius + b.radius;
826+
return (dr * dr - dx * dx - dy * dy) > .001; // within epsilon
827+
}
828+
829+
/* Create first node. */
830+
a = nodes[0];
831+
a.x = -a.radius;
832+
a.y = 0;
833+
bound(a);
834+
835+
/* Create second node. */
836+
if (nodes.length > 1) {
837+
b = nodes[1];
838+
b.x = b.radius;
839+
b.y = 0;
840+
bound(b);
841+
842+
/* Create third node and build chain. */
843+
if (nodes.length > 2) {
844+
c = nodes[2];
845+
d3_layout_packPlace(a, b, c);
846+
bound(c);
847+
insert(a, c);
848+
a.p = c;
849+
insert(c, b);
850+
b = a.n;
851+
852+
/* Now iterate through the rest. */
853+
for (var i = 3; i < nodes.length; i++) {
854+
d3_layout_packPlace(a, b, c = nodes[i]);
855+
856+
/* Search for the closest intersection. */
857+
var isect = 0, s1 = 1, s2 = 1;
858+
for (j = b.n; j != b; j = j.n, s1++) {
859+
if (intersects(j, c)) {
860+
isect = 1;
861+
break;
862+
}
863+
}
864+
if (isect == 1) {
865+
for (k = a.p; k != j.p; k = k.p, s2++) {
866+
if (intersects(k, c)) {
867+
if (s2 < s1) {
868+
isect = -1;
869+
j = k;
870+
}
871+
break;
872+
}
873+
}
874+
}
875+
876+
/* Update node chain. */
877+
if (isect == 0) {
878+
insert(a, c);
879+
b = c;
880+
bound(c);
881+
} else if (isect > 0) {
882+
splice(a, j);
883+
b = j;
884+
i--;
885+
} else if (isect < 0) {
886+
splice(j, b);
887+
a = j;
888+
i--;
889+
}
890+
}
891+
}
892+
}
893+
894+
/* Re-center the circles and return the encompassing radius. */
895+
var cx = (xMin + xMax) / 2,
896+
cy = (yMin + yMax) / 2,
897+
cr = 0;
898+
for (var i = 0; i < nodes.length; i++) {
899+
var n = nodes[i];
900+
n.x -= cx;
901+
n.y -= cy;
902+
cr = Math.max(cr, n.radius + Math.sqrt(n.x * n.x + n.y * n.y));
903+
}
904+
return cr + spacing;
905+
}
906+
907+
function d3_layout_packTree(n, spacing) {
908+
var nodes = [],
909+
children = n.children;
910+
if (children) {
911+
for (var i = 0, l = children.length; i < l; i++) {
912+
var c = children[i];
913+
if (c.children) c.radius = d3_layout_packTree(c, spacing);
914+
c.n = c.p = c;
915+
nodes.push(c);
916+
}
917+
}
918+
return d3_layout_packCircle(nodes, spacing);
919+
}
920+
921+
function d3_layout_packTransform(n, x, y, k) {
922+
var children = n.children;
923+
if (children) {
924+
for (var i = 0, l = children.length; i < l; i++) {
925+
var c = children[i];
926+
c.x += n.x;
927+
c.y += n.y;
928+
d3_layout_packTransform(c, x, y, k);
929+
}
930+
}
931+
n.x = x + k * n.x;
932+
n.y = y + k * n.y;
933+
n.radius *= k;
934+
}
935+
936+
function d3_layout_packPlace(a, b, c) {
937+
var da = b.radius + c.radius,
938+
db = a.radius + c.radius,
939+
dx = b.x - a.x,
940+
dy = b.y - a.y,
941+
dc = Math.sqrt(dx * dx + dy * dy),
942+
cos = (db * db + dc * dc - da * da) / (2 * db * dc),
943+
theta = Math.acos(cos),
944+
x = cos * db,
945+
h = Math.sin(theta) * db;
946+
dx /= dc;
947+
dy /= dc;
948+
c.x = a.x + x * dx + h * dy;
949+
c.y = a.y + x * dy - h * dx;
950+
}
951+
952+
// Computes the radii of the leaf nodes.
953+
// TODO (from Protovis version):
954+
// Is it possible for spacing to operate in pixel space?
955+
// Right now it appears to be multiples of the smallest radius.
956+
function d3_layout_packRadii(nodes, radius) {
957+
for (var i = 0, n = nodes.length; i < n; i++) {
958+
var c = nodes[i];
959+
if (!c.children) {
960+
c.radius = radius.call(this, c, i);
961+
}
962+
}
963+
}
742964
// Node-link tree diagram using the Reingold-Tilford "tidy" algorithm
743965
d3.layout.tree = function() {
744966
var hierarchy = d3.layout.hierarchy(),

‎d3.layout.min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎examples/index.html‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@
2828
<li><a href="moire/moire.html">moire</a></li>
2929
<li><a href="partition/partition-icicle.html">partition-icicle</a></li>
3030
<li><a href="partition/partition-sunburst.html">partition-sunburst</a></li>
31+
<li><a href="pack/pack.html">pack</a></li>
3132
<li><a href="pie/pie.html">pie</a></li>
3233
<li><a href="pie/pie-transition.html">pie-transition</a></li>
3334
<li><a href="quadtree/quadtree.html">quadtree</a></li>

0 commit comments

Comments
 (0)