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