1 /** 2 * Constructs a new, empty circle-packing layout. Layouts are not typically 3 * constructed directly; instead, they are added to an existing panel via 4 * {@link pv.Mark#add}. 5 * 6 * @class Implements a hierarchical layout using circle-packing. The meaning of 7 * the exported mark prototypes changes slightly in the space-filling 8 * implementation:<ul> 9 * 10 * <li><tt>node</tt> - for rendering nodes; typically a {@link pv.Dot}. 11 * 12 * <p><li><tt>link</tt> - unsupported; undefined. Links are encoded implicitly 13 * in the arrangement of the space-filling nodes. 14 * 15 * <p><li><tt>label</tt> - for rendering node labels; typically a 16 * {@link pv.Label}. 17 * 18 * </ul>The pack layout support dynamic sizing for leaf nodes, if a 19 * {@link #size} psuedo-property is specified. The default size function returns 20 * 1, causing all leaf nodes to be sized equally, and all internal nodes to be 21 * sized by the number of leaf nodes they have as descendants. 22 * 23 * <p>The size function can be used in conjunction with the order property, 24 * which allows the nodes to the sorted by the computed size. Note: for sorting 25 * based on other data attributes, simply use the default <tt>null</tt> for the 26 * order property, and sort the nodes beforehand using the {@link pv.Dom} 27 * operator. 28 * 29 * <p>For more details on how to use this layout, see 30 * {@link pv.Layout.Hierarchy}. 31 * 32 * @extends pv.Layout.Hierarchy 33 * @see <a href="http://portal.acm.org/citation.cfm?id=1124772.1124851" 34 * >"Visualization of large hierarchical data by circle packing"</a> by W. Wang, 35 * H. Wang, G. Dai, and H. Wang, ACM CHI 2006. 36 */ 37 pv.Layout.Pack = function() { 38 pv.Layout.Hierarchy.call(this); 39 40 this.node 41 .radius(function(n) { return n.radius; }) 42 .strokeStyle("rgb(31, 119, 180)") 43 .fillStyle("rgba(31, 119, 180, .25)"); 44 45 this.label 46 .textAlign("center"); 47 48 /* Hide unsupported link. */ 49 delete this.link; 50 }; 51 52 pv.Layout.Pack.prototype = pv.extend(pv.Layout.Hierarchy) 53 .property("spacing", Number) 54 .property("order", String); // ascending, descending, reverse, null 55 56 /** 57 * Default properties for circle-packing layouts. The default spacing parameter 58 * is 1 and the default order is "ascending". 59 * 60 * @type pv.Layout.Pack 61 */ 62 pv.Layout.Pack.prototype.defaults = new pv.Layout.Pack() 63 .extend(pv.Layout.Hierarchy.prototype.defaults) 64 .spacing(1) 65 .order("ascending"); 66 67 /** 68 * The spacing parameter; defaults to 1, which provides a little bit of padding 69 * between sibling nodes and the enclosing circle. Larger values increase the 70 * spacing, by making the sibling nodes smaller; a value of zero makes the leaf 71 * nodes as large as possible, with no padding on enclosing circles. 72 * 73 * @type number 74 * @name pv.Layout.Pack.prototype.spacing 75 */ 76 77 /** 78 * The sibling node order. The default order is <tt>null</tt>, which means to 79 * use the sibling order specified by the nodes property as-is. A value of 80 * "ascending" will sort siblings in ascending order of size, while "descending" 81 * will do the reverse. For sorting based on data attributes other than size, 82 * use the default <tt>null</tt> for the order property, and sort the nodes 83 * beforehand using the {@link pv.Dom} operator. 84 * 85 * @see pv.Dom.Node#sort 86 * @type string 87 * @name pv.Layout.Pack.prototype.order 88 */ 89 90 /** @private The default size function. */ 91 pv.Layout.Pack.prototype.$radius = function() { return 1; }; 92 93 // TODO is it possible for spacing to operate in pixel space? 94 // Right now it appears to be multiples of the smallest radius. 95 96 /** 97 * Specifies the sizing function. By default, a sizing function is disabled and 98 * all nodes are given constant size. The sizing function is invoked for each 99 * leaf node in the tree (passed to the constructor). 100 * 101 * <p>For example, if the tree data structure represents a file system, with 102 * files as leaf nodes, and each file has a <tt>bytes</tt> attribute, you can 103 * specify a size function as: 104 * 105 * <pre> .size(function(d) d.bytes)</pre> 106 * 107 * As with other properties, a size function may specify additional arguments to 108 * access the data associated with the layout and any enclosing panels. 109 * 110 * @param {function} f the new sizing function. 111 * @returns {pv.Layout.Pack} this. 112 */ 113 pv.Layout.Pack.prototype.size = function(f) { 114 this.$radius = typeof f == "function" 115 ? function() { return Math.sqrt(f.apply(this, arguments)); } 116 : (f = Math.sqrt(f), function() { return f; }); 117 return this; 118 }; 119 120 /** @private */ 121 pv.Layout.Pack.prototype.buildImplied = function(s) { 122 if (pv.Layout.Hierarchy.prototype.buildImplied.call(this, s)) return; 123 124 var that = this, 125 nodes = s.nodes, 126 root = nodes[0]; 127 128 /** @private Compute the radii of the leaf nodes. */ 129 function radii(nodes) { 130 var stack = pv.Mark.stack; 131 stack.unshift(null); 132 for (var i = 0, n = nodes.length; i < n; i++) { 133 var c = nodes[i]; 134 if (!c.firstChild) { 135 c.radius = that.$radius.apply(that, (stack[0] = c, stack)); 136 } 137 } 138 stack.shift(); 139 } 140 141 /** @private */ 142 function packTree(n) { 143 var nodes = []; 144 for (var c = n.firstChild; c; c = c.nextSibling) { 145 if (c.firstChild) c.radius = packTree(c); 146 c.n = c.p = c; 147 nodes.push(c); 148 } 149 150 /* Sort. */ 151 switch (s.order) { 152 case "ascending": { 153 nodes.sort(function(a, b) { return a.radius - b.radius; }); 154 break; 155 } 156 case "descending": { 157 nodes.sort(function(a, b) { return b.radius - a.radius; }); 158 break; 159 } 160 case "reverse": nodes.reverse(); break; 161 } 162 163 return packCircle(nodes); 164 } 165 166 /** @private */ 167 function packCircle(nodes) { 168 var xMin = Infinity, 169 xMax = -Infinity, 170 yMin = Infinity, 171 yMax = -Infinity, 172 a, b, c, j, k; 173 174 /** @private */ 175 function bound(n) { 176 xMin = Math.min(n.x - n.radius, xMin); 177 xMax = Math.max(n.x + n.radius, xMax); 178 yMin = Math.min(n.y - n.radius, yMin); 179 yMax = Math.max(n.y + n.radius, yMax); 180 } 181 182 /** @private */ 183 function insert(a, b) { 184 var c = a.n; 185 a.n = b; 186 b.p = a; 187 b.n = c; 188 c.p = b; 189 } 190 191 /** @private */ 192 function splice(a, b) { 193 a.n = b; 194 b.p = a; 195 } 196 197 /** @private */ 198 function intersects(a, b) { 199 var dx = b.x - a.x, 200 dy = b.y - a.y, 201 dr = a.radius + b.radius; 202 return (dr * dr - dx * dx - dy * dy) > .001; // within epsilon 203 } 204 205 /* Create first node. */ 206 a = nodes[0]; 207 a.x = -a.radius; 208 a.y = 0; 209 bound(a); 210 211 /* Create second node. */ 212 if (nodes.length > 1) { 213 b = nodes[1]; 214 b.x = b.radius; 215 b.y = 0; 216 bound(b); 217 218 /* Create third node and build chain. */ 219 if (nodes.length > 2) { 220 c = nodes[2]; 221 place(a, b, c); 222 bound(c); 223 insert(a, c); 224 a.p = c; 225 insert(c, b); 226 b = a.n; 227 228 /* Now iterate through the rest. */ 229 for (var i = 3; i < nodes.length; i++) { 230 place(a, b, c = nodes[i]); 231 232 /* Search for the closest intersection. */ 233 var isect = 0, s1 = 1, s2 = 1; 234 for (j = b.n; j != b; j = j.n, s1++) { 235 if (intersects(j, c)) { 236 isect = 1; 237 break; 238 } 239 } 240 if (isect == 1) { 241 for (k = a.p; k != j.p; k = k.p, s2++) { 242 if (intersects(k, c)) { 243 if (s2 < s1) { 244 isect = -1; 245 j = k; 246 } 247 break; 248 } 249 } 250 } 251 252 /* Update node chain. */ 253 if (isect == 0) { 254 insert(a, c); 255 b = c; 256 bound(c); 257 } else if (isect > 0) { 258 splice(a, j); 259 b = j; 260 i--; 261 } else if (isect < 0) { 262 splice(j, b); 263 a = j; 264 i--; 265 } 266 } 267 } 268 } 269 270 /* Re-center the circles and return the encompassing radius. */ 271 var cx = (xMin + xMax) / 2, 272 cy = (yMin + yMax) / 2, 273 cr = 0; 274 for (var i = 0; i < nodes.length; i++) { 275 var n = nodes[i]; 276 n.x -= cx; 277 n.y -= cy; 278 cr = Math.max(cr, n.radius + Math.sqrt(n.x * n.x + n.y * n.y)); 279 } 280 return cr + s.spacing; 281 } 282 283 /** @private */ 284 function place(a, b, c) { 285 var da = b.radius + c.radius, 286 db = a.radius + c.radius, 287 dx = b.x - a.x, 288 dy = b.y - a.y, 289 dc = Math.sqrt(dx * dx + dy * dy), 290 cos = (db * db + dc * dc - da * da) / (2 * db * dc), 291 theta = Math.acos(cos), 292 x = cos * db, 293 h = Math.sin(theta) * db; 294 dx /= dc; 295 dy /= dc; 296 c.x = a.x + x * dx + h * dy; 297 c.y = a.y + x * dy - h * dx; 298 } 299 300 /** @private */ 301 function transform(n, x, y, k) { 302 for (var c = n.firstChild; c; c = c.nextSibling) { 303 c.x += n.x; 304 c.y += n.y; 305 transform(c, x, y, k); 306 } 307 n.x = x + k * n.x; 308 n.y = y + k * n.y; 309 n.radius *= k; 310 } 311 312 radii(nodes); 313 314 /* Recursively compute the layout. */ 315 root.x = 0; 316 root.y = 0; 317 root.radius = packTree(root); 318 319 var w = this.width(), 320 h = this.height(), 321 k = 1 / Math.max(2 * root.radius / w, 2 * root.radius / h); 322 transform(root, w / 2, h / 2, k); 323 }; 324