Daniel@0: // Word cloud layout by Jason Davies, http://www.jasondavies.com/word-cloud/
Daniel@0: // Algorithm due to Jonathan Feinberg, http://static.mrfeinberg.com/bv_ch03.pdf
Daniel@0: (function() {
Daniel@0: 
Daniel@0: if (typeof define === "function" && define.amd) define(["d3"], cloud);
Daniel@0: else cloud(this.d3);
Daniel@0: 
Daniel@0: function cloud(d3) {
Daniel@0:   d3.layout.cloud = function cloud() {
Daniel@0:     var size = [256, 256],
Daniel@0:         text = cloudText,
Daniel@0:         font = cloudFont,
Daniel@0:         fontSize = cloudFontSize,
Daniel@0:         fontStyle = cloudFontNormal,
Daniel@0:         fontWeight = cloudFontNormal,
Daniel@0:         rotate = cloudRotate,
Daniel@0:         padding = cloudPadding,
Daniel@0:         spiral = archimedeanSpiral,
Daniel@0:         words = [],
Daniel@0:         timeInterval = Infinity,
Daniel@0:         event = d3.dispatch("word", "end"),
Daniel@0:         timer = null,
Daniel@0:         random = Math.random,
Daniel@0:         cloud = {};
Daniel@0: 
Daniel@0:     cloud.start = function() {
Daniel@0:       var board = zeroArray((size[0] >> 5) * size[1]),
Daniel@0:           bounds = null,
Daniel@0:           n = words.length,
Daniel@0:           i = -1,
Daniel@0:           tags = [],
Daniel@0:           data = words.map(function(d, i) {
Daniel@0:             d.text = text.call(this, d, i);
Daniel@0:             d.font = font.call(this, d, i);
Daniel@0:             d.style = fontStyle.call(this, d, i);
Daniel@0:             d.weight = fontWeight.call(this, d, i);
Daniel@0:             d.rotate = rotate.call(this, d, i);
Daniel@0:             d.size = ~~fontSize.call(this, d, i);
Daniel@0:             d.padding = padding.call(this, d, i);
Daniel@0:             return d;
Daniel@0:           }).sort(function(a, b) { return b.size - a.size; });
Daniel@0: 
Daniel@0:       if (timer) clearInterval(timer);
Daniel@0:       timer = setInterval(step, 0);
Daniel@0:       step();
Daniel@0: 
Daniel@0:       return cloud;
Daniel@0: 
Daniel@0:       function step() {
Daniel@0:         var start = Date.now();
Daniel@0:         while (Date.now() - start < timeInterval && ++i < n && timer) {
Daniel@0:           var d = data[i];
Daniel@0:           d.x = (size[0] * (random() + .5)) >> 1;
Daniel@0:           d.y = (size[1] * (random() + .5)) >> 1;
Daniel@0:           cloudSprite(d, data, i);
Daniel@0:           if (d.hasText && place(board, d, bounds)) {
Daniel@0:             tags.push(d);
Daniel@0:             event.word(d);
Daniel@0:             if (bounds) cloudBounds(bounds, d);
Daniel@0:             else bounds = [{x: d.x + d.x0, y: d.y + d.y0}, {x: d.x + d.x1, y: d.y + d.y1}];
Daniel@0:             // Temporary hack
Daniel@0:             d.x -= size[0] >> 1;
Daniel@0:             d.y -= size[1] >> 1;
Daniel@0:           }
Daniel@0:         }
Daniel@0:         if (i >= n) {
Daniel@0:           cloud.stop();
Daniel@0:           event.end(tags, bounds);
Daniel@0:         }
Daniel@0:       }
Daniel@0:     }
Daniel@0: 
Daniel@0:     cloud.stop = function() {
Daniel@0:       if (timer) {
Daniel@0:         clearInterval(timer);
Daniel@0:         timer = null;
Daniel@0:       }
Daniel@0:       return cloud;
Daniel@0:     };
Daniel@0: 
Daniel@0:     function place(board, tag, bounds) {
Daniel@0:       var perimeter = [{x: 0, y: 0}, {x: size[0], y: size[1]}],
Daniel@0:           startX = tag.x,
Daniel@0:           startY = tag.y,
Daniel@0:           maxDelta = Math.sqrt(size[0] * size[0] + size[1] * size[1]),
Daniel@0:           s = spiral(size),
Daniel@0:           dt = random() < .5 ? 1 : -1,
Daniel@0:           t = -dt,
Daniel@0:           dxdy,
Daniel@0:           dx,
Daniel@0:           dy;
Daniel@0: 
Daniel@0:       while (dxdy = s(t += dt)) {
Daniel@0:         dx = ~~dxdy[0];
Daniel@0:         dy = ~~dxdy[1];
Daniel@0: 
Daniel@0:         if (Math.min(Math.abs(dx), Math.abs(dy)) >= maxDelta) break;
Daniel@0: 
Daniel@0:         tag.x = startX + dx;
Daniel@0:         tag.y = startY + dy;
Daniel@0: 
Daniel@0:         if (tag.x + tag.x0 < 0 || tag.y + tag.y0 < 0 ||
Daniel@0:             tag.x + tag.x1 > size[0] || tag.y + tag.y1 > size[1]) continue;
Daniel@0:         // TODO only check for collisions within current bounds.
Daniel@0:         if (!bounds || !cloudCollide(tag, board, size[0])) {
Daniel@0:           if (!bounds || collideRects(tag, bounds)) {
Daniel@0:             var sprite = tag.sprite,
Daniel@0:                 w = tag.width >> 5,
Daniel@0:                 sw = size[0] >> 5,
Daniel@0:                 lx = tag.x - (w << 4),
Daniel@0:                 sx = lx & 0x7f,
Daniel@0:                 msx = 32 - sx,
Daniel@0:                 h = tag.y1 - tag.y0,
Daniel@0:                 x = (tag.y + tag.y0) * sw + (lx >> 5),
Daniel@0:                 last;
Daniel@0:             for (var j = 0; j < h; j++) {
Daniel@0:               last = 0;
Daniel@0:               for (var i = 0; i <= w; i++) {
Daniel@0:                 board[x + i] |= (last << msx) | (i < w ? (last = sprite[j * w + i]) >>> sx : 0);
Daniel@0:               }
Daniel@0:               x += sw;
Daniel@0:             }
Daniel@0:             delete tag.sprite;
Daniel@0:             return true;
Daniel@0:           }
Daniel@0:         }
Daniel@0:       }
Daniel@0:       return false;
Daniel@0:     }
Daniel@0: 
Daniel@0:     cloud.timeInterval = function(_) {
Daniel@0:       return arguments.length ? (timeInterval = _ == null ? Infinity : _, cloud) : timeInterval;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.words = function(_) {
Daniel@0:       return arguments.length ? (words = _, cloud) : words;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.size = function(_) {
Daniel@0:       return arguments.length ? (size = [+_[0], +_[1]], cloud) : size;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.font = function(_) {
Daniel@0:       return arguments.length ? (font = d3.functor(_), cloud) : font;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.fontStyle = function(_) {
Daniel@0:       return arguments.length ? (fontStyle = d3.functor(_), cloud) : fontStyle;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.fontWeight = function(_) {
Daniel@0:       return arguments.length ? (fontWeight = d3.functor(_), cloud) : fontWeight;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.rotate = function(_) {
Daniel@0:       return arguments.length ? (rotate = d3.functor(_), cloud) : rotate;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.text = function(_) {
Daniel@0:       return arguments.length ? (text = d3.functor(_), cloud) : text;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.spiral = function(_) {
Daniel@0:       return arguments.length ? (spiral = spirals[_] || _, cloud) : spiral;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.fontSize = function(_) {
Daniel@0:       return arguments.length ? (fontSize = d3.functor(_), cloud) : fontSize;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.padding = function(_) {
Daniel@0:       return arguments.length ? (padding = d3.functor(_), cloud) : padding;
Daniel@0:     };
Daniel@0: 
Daniel@0:     cloud.random = function(_) {
Daniel@0:       return arguments.length ? (random = _, cloud) : random;
Daniel@0:     };
Daniel@0: 
Daniel@0:     return d3.rebind(cloud, event, "on");
Daniel@0:   };
Daniel@0: 
Daniel@0:   function cloudText(d) {
Daniel@0:     return d.text;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function cloudFont() {
Daniel@0:     return "serif";
Daniel@0:   }
Daniel@0: 
Daniel@0:   function cloudFontNormal() {
Daniel@0:     return "normal";
Daniel@0:   }
Daniel@0: 
Daniel@0:   function cloudFontSize(d) {
Daniel@0:     return Math.sqrt(d.value);
Daniel@0:   }
Daniel@0: 
Daniel@0:   function cloudRotate() {
Daniel@0:     return (~~(Math.random() * 6) - 3) * 30;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function cloudPadding() {
Daniel@0:     return 1;
Daniel@0:   }
Daniel@0: 
Daniel@0:   // Fetches a monochrome sprite bitmap for the specified text.
Daniel@0:   // Load in batches for speed.
Daniel@0:   function cloudSprite(d, data, di) {
Daniel@0:     if (d.sprite) return;
Daniel@0:     c.clearRect(0, 0, (cw << 5) / ratio, ch / ratio);
Daniel@0:     var x = 0,
Daniel@0:         y = 0,
Daniel@0:         maxh = 0,
Daniel@0:         n = data.length;
Daniel@0:     --di;
Daniel@0:     while (++di < n) {
Daniel@0:       d = data[di];
Daniel@0:       c.save();
Daniel@0:       c.font = d.style + " " + d.weight + " " + ~~((d.size + 1) / ratio) + "px " + d.font;
Daniel@0:       var w = c.measureText(d.text + "m").width * ratio,
Daniel@0:           h = d.size << 1;
Daniel@0:       if (d.rotate) {
Daniel@0:         var sr = Math.sin(d.rotate * cloudRadians),
Daniel@0:             cr = Math.cos(d.rotate * cloudRadians),
Daniel@0:             wcr = w * cr,
Daniel@0:             wsr = w * sr,
Daniel@0:             hcr = h * cr,
Daniel@0:             hsr = h * sr;
Daniel@0:         w = (Math.max(Math.abs(wcr + hsr), Math.abs(wcr - hsr)) + 0x1f) >> 5 << 5;
Daniel@0:         h = ~~Math.max(Math.abs(wsr + hcr), Math.abs(wsr - hcr));
Daniel@0:       } else {
Daniel@0:         w = (w + 0x1f) >> 5 << 5;
Daniel@0:       }
Daniel@0:       if (h > maxh) maxh = h;
Daniel@0:       if (x + w >= (cw << 5)) {
Daniel@0:         x = 0;
Daniel@0:         y += maxh;
Daniel@0:         maxh = 0;
Daniel@0:       }
Daniel@0:       if (y + h >= ch) break;
Daniel@0:       c.translate((x + (w >> 1)) / ratio, (y + (h >> 1)) / ratio);
Daniel@0:       if (d.rotate) c.rotate(d.rotate * cloudRadians);
Daniel@0:       c.fillText(d.text, 0, 0);
Daniel@0:       if (d.padding) c.lineWidth = 2 * d.padding, c.strokeText(d.text, 0, 0);
Daniel@0:       c.restore();
Daniel@0:       d.width = w;
Daniel@0:       d.height = h;
Daniel@0:       d.xoff = x;
Daniel@0:       d.yoff = y;
Daniel@0:       d.x1 = w >> 1;
Daniel@0:       d.y1 = h >> 1;
Daniel@0:       d.x0 = -d.x1;
Daniel@0:       d.y0 = -d.y1;
Daniel@0:       d.hasText = true;
Daniel@0:       x += w;
Daniel@0:     }
Daniel@0:     var pixels = c.getImageData(0, 0, (cw << 5) / ratio, ch / ratio).data,
Daniel@0:         sprite = [];
Daniel@0:     while (--di >= 0) {
Daniel@0:       d = data[di];
Daniel@0:       if (!d.hasText) continue;
Daniel@0:       var w = d.width,
Daniel@0:           w32 = w >> 5,
Daniel@0:           h = d.y1 - d.y0;
Daniel@0:       // Zero the buffer
Daniel@0:       for (var i = 0; i < h * w32; i++) sprite[i] = 0;
Daniel@0:       x = d.xoff;
Daniel@0:       if (x == null) return;
Daniel@0:       y = d.yoff;
Daniel@0:       var seen = 0,
Daniel@0:           seenRow = -1;
Daniel@0:       for (var j = 0; j < h; j++) {
Daniel@0:         for (var i = 0; i < w; i++) {
Daniel@0:           var k = w32 * j + (i >> 5),
Daniel@0:               m = pixels[((y + j) * (cw << 5) + (x + i)) << 2] ? 1 << (31 - (i % 32)) : 0;
Daniel@0:           sprite[k] |= m;
Daniel@0:           seen |= m;
Daniel@0:         }
Daniel@0:         if (seen) seenRow = j;
Daniel@0:         else {
Daniel@0:           d.y0++;
Daniel@0:           h--;
Daniel@0:           j--;
Daniel@0:           y++;
Daniel@0:         }
Daniel@0:       }
Daniel@0:       d.y1 = d.y0 + seenRow;
Daniel@0:       d.sprite = sprite.slice(0, (d.y1 - d.y0) * w32);
Daniel@0:     }
Daniel@0:   }
Daniel@0: 
Daniel@0:   // Use mask-based collision detection.
Daniel@0:   function cloudCollide(tag, board, sw) {
Daniel@0:     sw >>= 5;
Daniel@0:     var sprite = tag.sprite,
Daniel@0:         w = tag.width >> 5,
Daniel@0:         lx = tag.x - (w << 4),
Daniel@0:         sx = lx & 0x7f,
Daniel@0:         msx = 32 - sx,
Daniel@0:         h = tag.y1 - tag.y0,
Daniel@0:         x = (tag.y + tag.y0) * sw + (lx >> 5),
Daniel@0:         last;
Daniel@0:     for (var j = 0; j < h; j++) {
Daniel@0:       last = 0;
Daniel@0:       for (var i = 0; i <= w; i++) {
Daniel@0:         if (((last << msx) | (i < w ? (last = sprite[j * w + i]) >>> sx : 0))
Daniel@0:             & board[x + i]) return true;
Daniel@0:       }
Daniel@0:       x += sw;
Daniel@0:     }
Daniel@0:     return false;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function cloudBounds(bounds, d) {
Daniel@0:     var b0 = bounds[0],
Daniel@0:         b1 = bounds[1];
Daniel@0:     if (d.x + d.x0 < b0.x) b0.x = d.x + d.x0;
Daniel@0:     if (d.y + d.y0 < b0.y) b0.y = d.y + d.y0;
Daniel@0:     if (d.x + d.x1 > b1.x) b1.x = d.x + d.x1;
Daniel@0:     if (d.y + d.y1 > b1.y) b1.y = d.y + d.y1;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function collideRects(a, b) {
Daniel@0:     return a.x + a.x1 > b[0].x && a.x + a.x0 < b[1].x && a.y + a.y1 > b[0].y && a.y + a.y0 < b[1].y;
Daniel@0:   }
Daniel@0: 
Daniel@0:   function archimedeanSpiral(size) {
Daniel@0:     var e = size[0] / size[1];
Daniel@0:     return function(t) {
Daniel@0:       return [e * (t *= .1) * Math.cos(t), t * Math.sin(t)];
Daniel@0:     };
Daniel@0:   }
Daniel@0: 
Daniel@0:   function rectangularSpiral(size) {
Daniel@0:     var dy = 4,
Daniel@0:         dx = dy * size[0] / size[1],
Daniel@0:         x = 0,
Daniel@0:         y = 0;
Daniel@0:     return function(t) {
Daniel@0:       var sign = t < 0 ? -1 : 1;
Daniel@0:       // See triangular numbers: T_n = n * (n + 1) / 2.
Daniel@0:       switch ((Math.sqrt(1 + 4 * sign * t) - sign) & 3) {
Daniel@0:         case 0:  x += dx; break;
Daniel@0:         case 1:  y += dy; break;
Daniel@0:         case 2:  x -= dx; break;
Daniel@0:         default: y -= dy; break;
Daniel@0:       }
Daniel@0:       return [x, y];
Daniel@0:     };
Daniel@0:   }
Daniel@0: 
Daniel@0:   // TODO reuse arrays?
Daniel@0:   function zeroArray(n) {
Daniel@0:     var a = [],
Daniel@0:         i = -1;
Daniel@0:     while (++i < n) a[i] = 0;
Daniel@0:     return a;
Daniel@0:   }
Daniel@0: 
Daniel@0:   var cloudRadians = Math.PI / 180,
Daniel@0:       cw = 1 << 11 >> 5,
Daniel@0:       ch = 1 << 11,
Daniel@0:       canvas,
Daniel@0:       ratio = 1;
Daniel@0: 
Daniel@0:   if (typeof document !== "undefined") {
Daniel@0:     canvas = document.createElement("canvas");
Daniel@0:     canvas.width = 1;
Daniel@0:     canvas.height = 1;
Daniel@0:     ratio = Math.sqrt(canvas.getContext("2d").getImageData(0, 0, 1, 1).data.length >> 2);
Daniel@0:     canvas.width = (cw << 5) / ratio;
Daniel@0:     canvas.height = ch / ratio;
Daniel@0:   } else {
Daniel@0:     // Attempt to use node-canvas.
Daniel@0:     canvas = new Canvas(cw << 5, ch);
Daniel@0:   }
Daniel@0: 
Daniel@0:   var c = canvas.getContext("2d"),
Daniel@0:       spirals = {
Daniel@0:         archimedean: archimedeanSpiral,
Daniel@0:         rectangular: rectangularSpiral
Daniel@0:       };
Daniel@0:   c.fillStyle = c.strokeStyle = "red";
Daniel@0:   c.textAlign = "center";
Daniel@0: }
Daniel@0: 
Daniel@0: })();