d3.layout.cloud.tagpies.js

/*

Copyright (C) 2015, Stefan Jänicke.

Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

1. The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

2. It is prohibited to remove, hide or modify any visual copyright notice
generated by this Software.

3. When using screenshots of any part of the visual output generated by
this Software for presentations or on websites the following link MUST
be clearly visible for the beholder: http://tagpies.vizcovery.org

4. When using screenshots of any part of the visual output generated by
this Software in publications, the following reference MUST be inserted: 

S. Jänicke, J. Blumenstein, M. Rücker, D. Zeckzer and G. Scheuermann (2015). 
Visualizing the Results of Search Queries on Ancient Text Corpora with Tag Pies. 
Digital Humanities Quarterly.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

(Fair Academic License (FAL), http://vizcovery.org/fal.html)

*/

/*
Copyright (c) 2013, Jason Davies.
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

  * Redistributions of source code must retain the above copyright notice, this
    list of conditions and the following disclaimer.

  * Redistributions in binary form must reproduce the above copyright notice,
    this list of conditions and the following disclaimer in the documentation
    and/or other materials provided with the distribution.

  * The name Jason Davies may not be used to endorse or promote products
    derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL JASON DAVIES BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
// Word cloud layout by Jason Davies, http://www.jasondavies.com/word-cloud/
// Algorithm due to Jonathan Feinberg, http://static.mrfeinberg.com/bv_ch03.pdf
(function(exports) {
  function cloud() {
    var size = [256, 256],
        text = cloudText,
        font = cloudFont,
	type = cloudType,
	style = cloudStyle,
	radius = cloudRadius,
        fontSize = cloudFontSize,
        fontStyle = cloudFontNormal,
        fontWeight = cloudFontNormal,
        rotate = cloudRotate,
        padding = cloudPadding,
        spiral = archimedeanSpiral,
        words = [],
        timeInterval = Infinity,
        event = d3.dispatch("word", "end"),
        timer = null,
        cloud = {},
        facets = 0,
        facetWeights = [],
        angles = [],
        barycenters = [],
        barycenterData = [];

    cloud.start = function() {
      var board = zeroArray((size[0] >> 5) * size[1]),
          bounds = null,
          n = words.length,
          i = -1,
          tags = [],
          data = words.map(function(d, i) {
            d.text = text.call(this, d, i);
            d.font = font.call(this, d, i);
            d.style = fontStyle.call(this, d, i);
            d.weight = fontWeight.call(this, d, i);
            d.rotate = rotate.call(this, d, i);
            d.size = ~~fontSize.call(this, d, i);
            d.padding = padding.call(this, d, i);
            return d;
          });

      var helperDiv = $('<label>').appendTo("body");
      for( var j=0; j<words.length; j++ ){
        if( words[j].facet > facets ){
          facets = words[j].facet;
        }
      }
      for( var j=0; j<facets; j++ ){
        facetWeights.push(0);
      }
      for( var j=0; j<words.length; j++ ){
        $(helperDiv).html(words[j].key.replace(/-/g,""));
        $(helperDiv).css("font",words[j].size+"px "+words[j].font);
        facetWeights[words[j].facet-1] += $(helperDiv).width()*$(helperDiv).height();
	words[j].twidth = $(helperDiv).width();
      }
      $(helperDiv).remove();
		
		var s = 0;
		for( var j=0; j<facetWeights.length; j++ ){
			s += facetWeights[j];
		}
		for( var j=0; j<facetWeights.length; j++ ){
			facetWeights[j] /= s;
		}

	angles.push(0);
	var a = 0;
		for( var j=0; j<facetWeights.length-1; j++ ){
			a += facetWeights[j]*360;
			angles.push(a);
		}
	angles.push(360);

      if (timer) clearInterval(timer);
      timer = setInterval(step, 0);
      step();

      return cloud;
 
      function step() {
        var start = +new Date,
            d;
        while (+new Date - start < timeInterval && ++i < n && timer) {
          d = data[i];
          d.x = Math.floor(size[0]/2);
          d.y = Math.floor(size[1]/2);
          cloudSprite(d, data, i, type, style);
          if (d.hasText && place(board, d, bounds,tags)) {
            tags.push(d);
            event.word(d);
            if (bounds) cloudBounds(bounds, d);
            else bounds = [{x: d.x + d.x0, y: d.y + d.y0}, {x: d.x + d.x1, y: d.y + d.y1}];
            // Temporary hack
            d.x -= size[0] >> 1;
            d.y -= size[1] >> 1;
          }
        }
        if (i >= n) {
          cloud.stop();
          event.end(tags, bounds);
        }
      }
    }
    cloud.stop = function() {
      if (timer) {
        clearInterval(timer);
        timer = null;
      }
      return cloud;
    };

    cloud.timeInterval = function(x) {
      if (!arguments.length) return timeInterval;
      timeInterval = x == null ? Infinity : x;
      return cloud;
    };

    function correctSphere(tag,tags){
      var tagx = tag.x-size[0]/2;
      var tagy = tag.y-size[1]/2;
      for( var i=0; i<tags.length; i++ ){
        var tag2 = tags[i];
        if( typeof tag2.x == "undefined" ){
          continue;
	}
        if( tag2 == tag ){
          continue;
        }
        var tag2x = tag2.x;
        var tag2y = tag2.y;
        var w = tag2.twidth/2;
        var h1 = tag2.size/3*2;
        var h2 = tag2.size/3;
	if( tag.facet > tag2.facet && tag2.facet > 1 ){
		if( tagy >= 0 && tagx >= 0 && (tag2x+w >= tagx && tag2y+h2 >= tagy) ){
		  return false;
		}
		if( tagy < 0 && tagx >= 0 && (tag2x+w >= tagx && tag2y-h1 < tagy) ){
		  return false;
		}
		if( tagy < 0 && tagx < 0 && (tag2x-w < tagx && tag2y-h1 < tagy) ){
		  return false;
		}
		if( tagy >= 0 && tagx < 0 && (tag2x-w < tagx && tag2y+h2 >= tagy) ){
		  return false;
		}
	}
      }
      return true;
    }

    function placeMajor(tag){
      var steps = 1;
      var isLeft = function(a,b,c){
        return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)) > 0;
      }
      var a1 = angles[tag.facet-1];
      var a2 = angles[tag.facet];
      var a = (a1+a2)/2;
      var v = { x: Math.cos(a*Math.PI/180), y: Math.sin(a*Math.PI/180) };
      var v1 = { x: Math.cos(a1*Math.PI/180), y: Math.sin(a1*Math.PI/180) };
      var v2 = { x: Math.cos(a2*Math.PI/180), y: Math.sin(a2*Math.PI/180) };
      var multiplier = steps;
      var runs = 0;
      do {
        runs++;
        var x1 = (multiplier*v.x + tag.x0)*-1;
        var x2 = (multiplier*v.x + tag.x1)*-1;
        var y1 = (multiplier*v.y - tag.size/2)*-1;
        var y2 = (multiplier*v.y + tag.size/2)*-1;
        var p1 = { x: x1, y: y1 };
        var p2 = { x: x2, y: y1 };
        var p3 = { x: x1, y: y2 };
        var p4 = { x: x2, y: y2 };
        var outside = true;
        if( !isLeft({x:0,y:0},v1,p1) && isLeft({x:0,y:0},v2,p1) && !isLeft({x:0,y:0},v1,p2) && isLeft({x:0,y:0},v2,p2)
             && !isLeft({x:0,y:0},v1,p3) && isLeft({x:0,y:0},v2,p3) && !isLeft({x:0,y:0},v1,p4) && isLeft({x:0,y:0},v2,p4) ){
           outside = false;
           tag.x = Math.round((x1+x2)/2 + size[0]/2);
           tag.y = Math.round((y1+y2)/2 + size[1]/2);
        }
        multiplier += steps;
      }
      while(outside && runs < 1000);
    }

    function placeMajor2(tag,size,board){
      var a1 = angles[tag.facet-1];
      var a2 = angles[tag.facet];
      var a = (a1+a2)/2;
      var v = { x: Math.cos(a*Math.PI/180), y: Math.sin(a*Math.PI/180) };
      var gap = 0;
      do {
        var x1 = ((radius/2+gap)*v.x + tag.x0)*-1;
        var x2 = ((radius/2+gap)*v.x + tag.x1)*-1;
        var y1 = ((radius/2+gap)*v.y - tag.size/2)*-1;
        var y2 = ((radius/2+gap)*v.y + tag.size/2)*-1;
        tag.x = Math.round((x1+x2)/2 + size[0]/2);
        tag.y = Math.round((y1+y2)/2 + size[1]/2);
        gap += 5;
      }
      while(cloudCollide(tag, board, size[0]));
    }

    function correctSector(tag,size){
      if( tag.facet == 0 ){
        return true;
      }
      var tagx = tag.x-size[0]/2;
      var tagy = tag.y-size[1]/2;
      var a1 = angles[tag.facet-1];
      var a2 = angles[tag.facet];
      var p = { x: tagx, y: tagy };
      var isLeft = function(a,b,c){
        return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)) > 0;
      }
      if( a2-a1 > 180 ){
        var v = { x: Math.cos(a1*Math.PI/180), y: Math.sin(a1*Math.PI/180) };
        if( !isLeft({x:0,y:0},v,p) )
          return true;
        a1 += 180;
      }
      var v1 = { x: Math.cos(a1*Math.PI/180), y: Math.sin(a1*Math.PI/180) };
      var v2 = { x: Math.cos(a2*Math.PI/180), y: Math.sin(a2*Math.PI/180) };
      if( isLeft({x:0,y:0},v1,p) || !isLeft({x:0,y:0},v2,p) )
        return false;
      return true;
    }

    function place(board, tag, bounds,tags) {
      var perimeter = [{x: 0, y: 0}, {x: size[0], y: size[1]}],
          startX = tag.x,
          startY = tag.y,
          maxDelta = Math.sqrt(size[0] * size[0] + size[1] * size[1]),
          s = spiral(size),
          dt = Math.random() < .5 ? 1 : -1,
          t = -dt,
          dxdy,
          dx,
          dy;

      var put = function(){
            var sprite = tag.sprite,
                w = tag.width >> 5,
                sw = size[0] >> 5,
                lx = tag.x - (w << 4),
                sx = lx & 0x7f,
                msx = 32 - sx,
                h = tag.y1 - tag.y0,
                x = (tag.y + tag.y0) * sw + (lx >> 5),
                last;
            for (var j = 0; j < h; j++) {
              last = 0;
              for (var i = 0; i <= w; i++) {
                board[x + i] |= (last << msx) | (i < w ? (last = sprite[j * w + i]) >>> sx : 0);
              }
              x += sw;
            }
            delete tag.sprite;
            return true;
      }

      if( type == "pie" && !tag.major ){
        if( radius == 0 ){
          placeMajor(tag,size);
	}
        else {
          placeMajor2(tag,size,board);
        }
        put();
        return true;
      }

      while (dxdy = s(t += dt)) {
        dx = ~~dxdy[0];
        dy = ~~dxdy[1];

        if (Math.min(dx, dy) > maxDelta) break;

        tag.x = startX + dx;
        tag.y = startY + dy;

        if (tag.x + tag.x0 < 0 || tag.y + tag.y0 < 0 ||
            tag.x + tag.x1 > size[0] || tag.y + tag.y1 > size[1]) continue;
        // TODO only check for collisions within current bounds.
        if (!bounds || !cloudCollide(tag, board, size[0])) {
          if (!bounds || collideRects(tag, bounds)) {
            if( type == "pie" && !correctSector(tag,size) ){
              continue;
            }
            put();
            return true;
          }
        }
      }
      return false;
    }

    cloud.words = function(x) {
      if (!arguments.length) return words;
      words = x;
      return cloud;
    };

    cloud.size = function(x) {
      if (!arguments.length) return size;
      size = [+x[0], +x[1]];
      return cloud;
    };

    cloud.font = function(x) {
      if (!arguments.length) return font;
      font = d3.functor(x);
      return cloud;
    };

    cloud.fontStyle = function(x) {
      if (!arguments.length) return fontStyle;
      fontStyle = d3.functor(x);
      return cloud;
    };

    cloud.fontWeight = function(x) {
      if (!arguments.length) return fontWeight;
      fontWeight = d3.functor(x);
      return cloud;
    };

    cloud.rotate = function(x) {
      if (!arguments.length) return rotate;
      rotate = d3.functor(x);
      return cloud;
    };

    cloud.text = function(x) {
      if (!arguments.length) return text;
      text = d3.functor(x);
      return cloud;
    };

    cloud.type = function(x) {
      if (!arguments.length) return type;
      type = x;
      return cloud;
    };

    cloud.style = function(x) {
      if (!arguments.length) return style;
      style = x;
      return cloud;
    };

    cloud.radius = function(x) {
      if (!arguments.length) return radius;
      radius = x;
      return cloud;
    };

    cloud.spiral = function(x) {
      if (!arguments.length) return spiral;
      spiral = spirals[x + ""] || x;
      return cloud;
    };

    cloud.fontSize = function(x) {
      if (!arguments.length) return fontSize;
      fontSize = d3.functor(x);
      return cloud;
    };

    cloud.padding = function(x) {
      if (!arguments.length) return padding;
      padding = d3.functor(x);
      return cloud;
    };

    return d3.rebind(cloud, event, "on");
  }

  function cloudText(d) {
    return d.text;
  }

  function cloudFont() {
    return "serif";
  }

  function cloudType() {
    return "compact";
  }

  function cloudStyle() {
    return "basic";
  }

  function cloudRadius() {
    return 0;
  }

  function cloudFontNormal() {
    return "normal";
  }

  function cloudFontSize(d) {
    return Math.sqrt(d.value);
  }

  function cloudRotate() {
    return (~~(Math.random() * 6) - 3) * 30;
  }

  function cloudPadding() {
    return 1;
  }

  // Fetches a monochrome sprite bitmap for the specified text.
  // Load in batches for speed.
  function cloudSprite(d, data, di, type, style) {
    if (d.sprite) return;
    c.clearRect(0, 0, (cw << 5) / ratio, ch / ratio);
    var x = 0,
        y = 0,
        maxh = 0,
        n = data.length;
    --di;
    while (++di < n) {
      d = data[di];
      c.save();
      c.font = "normal " + ~~((d.size + 1) / ratio) + "px " + d.font;
      if( type == "pie" && !d.major ||
          type == "pie" && style == "italics-bold" && d.multiplicity == 1 ||
          type == "pie" && style == "bold-italics" && d.multiplicity > 1 ){
        c.font = "bold " + ~~((d.size + 1) / ratio) + "px " + d.font;
      }
      var w = c.measureText(d.text + "m").width * ratio,
          h = d.size << 1;
      if (d.rotate) {
        var sr = Math.sin(d.rotate * cloudRadians),
            cr = Math.cos(d.rotate * cloudRadians),
            wcr = w * cr,
            wsr = w * sr,
            hcr = h * cr,
            hsr = h * sr;
        w = (Math.max(Math.abs(wcr + hsr), Math.abs(wcr - hsr)) + 0x1f) >> 5 << 5;
        h = ~~Math.max(Math.abs(wsr + hcr), Math.abs(wsr - hcr));
      } else {
        w = (w + 0x1f) >> 5 << 5;
      }
      if (h > maxh) maxh = h;
      if (x + w >= (cw << 5)) {
        x = 0;
        y += maxh;
        maxh = 0;
      }
      if (y + h >= ch) break;
      c.translate((x + (w >> 1)) / ratio, (y + (h >> 1)) / ratio);
      if (d.rotate) c.rotate(d.rotate * cloudRadians);
      c.fillText(d.text, 0, 0);
      if (d.padding) c.lineWidth = 2 * d.padding, c.strokeText(d.text, 0, 0);
      if( !d.major || 
          type == "pie" && style == "bars" && d.facets && d.facets.f.length > 1 ||
          type == "pie" && ( style == "merged" || style == "merged-black" ) && d.facets && d.facets.length > 1 ){
		 var wi = c.measureText(d.text).width * ratio;
		 c.fillRect(-wi/2,0,wi,5);
      }
      c.restore();
      d.width = w;
      d.height = h;
      d.xoff = x;
      d.yoff = y;
      d.x1 = w >> 1;
      d.y1 = h >> 1;
      d.x0 = -d.x1;
      d.y0 = -d.y1;
      d.hasText = true;
      x += w;
    }
    var pixels = c.getImageData(0, 0, (cw << 5) / ratio, ch / ratio).data,
        sprite = [];
    while (--di >= 0) {
      d = data[di];
      if (!d.hasText) continue;
      var w = d.width,
          w32 = w >> 5,
          h = d.y1 - d.y0;
          p = d.padding;
      // Zero the buffer
      for (var i = 0; i < h * w32; i++) sprite[i] = 0;
      x = d.xoff;
      if (x == null) return;
      y = d.yoff;
      var seen = 0,
          seenRow = -1;
      for (var j = 0; j < h; j++) {
        for (var i = 0; i < w; i++) {
          var k = w32 * j + (i >> 5),
              m = pixels[((y + j) * (cw << 5) + (x + i)) << 2] ? 1 << (31 - (i % 32)) : 0;
          if (p) {
            if (j) sprite[k - w32] |= m;
            if (j < w - 1) sprite[k + w32] |= m;
            m |= (m << 1) | (m >> 1);
          }
          sprite[k] |= m;
          seen |= m;
        }
        if (seen) seenRow = j;
        else {
          d.y0++;
          h--;
          j--;
          y++;
        }
      }
      d.y1 = d.y0 + seenRow;
      d.sprite = sprite.slice(0, (d.y1 - d.y0) * w32);
    }
  }

  // Use mask-based collision detection.
  function cloudCollide(tag, board, sw) {
    sw >>= 5;
    var sprite = tag.sprite,
        w = tag.width >> 5,
        lx = tag.x - (w << 4),
        sx = lx & 0x7f,
        msx = 32 - sx,
        h = tag.y1 - tag.y0,
        x = (tag.y + tag.y0) * sw + (lx >> 5),
        last;
    for (var j = 0; j < h; j++) {
      last = 0;
      for (var i = 0; i <= w; i++) {
        if (((last << msx) | (i < w ? (last = sprite[j * w + i]) >>> sx : 0))
            & board[x + i]) return true;
      }
      x += sw;
    }
    return false;
  }

  function overlap(x1_min,x1_max,x2_min,x2_max,y1_min,y1_max,y2_min,y2_max){
	if( x1_min >= x2_max || x1_max <= x2_min || y1_min >= y2_max || y1_max <= y2_min ){
		return false;
	}
	return true;
  }

  function cloudBounds(bounds, d) {
    var b0 = bounds[0],
        b1 = bounds[1];
    if (d.x + d.x0 < b0.x) b0.x = d.x + d.x0;
    if (d.y + d.y0 < b0.y) b0.y = d.y + d.y0;
    if (d.x + d.x1 > b1.x) b1.x = d.x + d.x1;
    if (d.y + d.y1 > b1.y) b1.y = d.y + d.y1;
  }

  function collideRects(a, b) {
    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;
  }

  function archimedeanSpiral(size) {
    var e = size[0] / size[1];
    return function(t) {
      return [e * (t *= .1) * Math.cos(t), t * Math.sin(t)];
    };
  }

  function rectangularSpiral(size) {
    var dy = 4,
        dx = dy * size[0] / size[1],
        x = 0,
        y = 0;
    return function(t) {
      var sign = t < 0 ? -1 : 1;
      // See triangular numbers: T_n = n * (n + 1) / 2.
      switch ((Math.sqrt(1 + 4 * sign * t) - sign) & 3) {
        case 0:  x += dx; break;
        case 1:  y += dy; break;
        case 2:  x -= dx; break;
        default: y -= dy; break;
      }
      return [x, y];
    };
  }

  // TODO reuse arrays?
  function zeroArray(n) {
    var a = [],
        i = -1;
    while (++i < n) a[i] = 0;
    return a;
  }

  var cloudRadians = Math.PI / 180,
      cw = 1 << 11 >> 5,
      ch = 1 << 11,
      canvas,
      ratio = 1;

  if (typeof document !== "undefined") {
    canvas = document.createElement("canvas");
    canvas.width = 1;
    canvas.height = 1;
    ratio = Math.sqrt(canvas.getContext("2d").getImageData(0, 0, 1, 1).data.length >> 2);
    canvas.width = (cw << 5) / ratio;
    canvas.height = ch / ratio;
  } else {
    // node-canvas support
    var Canvas = require("canvas");
    canvas = new Canvas(cw << 5, ch);
  }

  var c = canvas.getContext("2d"),
      spirals = {
        archimedean: archimedeanSpiral,
        rectangular: rectangularSpiral
      };
  c.fillStyle = c.strokeStyle = "red";
  c.textAlign = "center";

  exports.cloud = cloud;
})(typeof exports === "undefined" ? d3.layout || (d3.layout = {}) : exports);