词云图(wordcloud)布局算法

背景

本文简析词云（wordcloud）的源码。

布局算法

1. 初始化：设置画布大小、背景色、网格大小等。
2. 词处理：每个词根据其重要性（频率、权重等）被赋予一个大小。
3. 位置选择：算法在画布上为每个词寻找合适的位置。这通常通过在画布中心开始，并向外螺旋（或其他形状，如圆形、星形等）搜索空间来实现。
4. 碰撞检测：在放置每个词时，算法会检查该位置是否会与已放置的词重叠。这通常通过一个网格来实现，网格记录了画布上的哪些区域是空的，哪些已被占用。
5. 绘制：一旦找到空间，词就会在画布上绘制出来，并更新网格状态。
6. 迭代：重复上述过程，直到所有词都被尝试放置。

核心方法

• weightFactor 和 shape 函数用于计算词的大小和布局形状。
• getPointsAtRadius 函数计算给定半径上的点，这些点可能是词云中词的候选放置位置。
• getTextInfo 函数计算单个词的布局信息，如大小和旋转。
• canFitText 检查一个词是否可以放在特定位置而不覆盖已有的词。
• drawText 将文本实际绘制到canvas上。
• updateGrid 更新网格状态，标记已被占用的区域。

算法细节

位置选择

1. 优先从画布中心开始绘制文字。
2. 基于不同的布局图形、在每个半径上生成一系列的坐标点用于尝试绘制图形。

例如：

• 圆形：

  // theta 可以理解为 基于弧度均分的坐标点。
  points.push([
      center[0] + radius * rx * Math.cos(theta * 2 * Math.PI),
      center[1] +
      radius * rx * Math.sin(theta* 2 * Math.PI) * settings.ellipticity,
      theta * 2 * Math.PI
  ]);

• 矩形：

  settings.shape = function shapeSquare(theta) {
      return Math.min(
      1 / Math.abs(Math.cos(theta)),
      1 / Math.abs(Math.sin(theta))
      );
  };

碰撞检测

在绘制文字之前，获取文字的信息，查看文字需要详细占用哪些网格，与整体canvas的网格做比对，如果没有重叠则绘制、如果有重叠则尝试下一个坐标点。

每次在绘制文字之后更新了网格。将文字已占用的网格在整体canvas的网格上标记。

附录：

核心代码

// 主循环 用于绘制词云
 function loop() {
    if (!layouting) {
        return;
    }
    if (i >= settings.list.length) {
        stoppingFunction(timer[timerId]);
        sendEvent('wordcloudstop', false);
        removeEventListener('wordcloudstart', anotherWordCloudStart);
        delete timer[timerId];
        return;
    }
    escapeTime = new Date().getTime();
    // 绘制单个词
    var drawn = putWord(settings.list[i], 0);
    var canceled = !sendEvent('wordclouddrawn', true, {
        item: settings.list[i],
        drawn: drawn
    });
    if (exceedTime() || canceled) {
        stoppingFunction(timer[timerId]);
        settings.abort();
        sendEvent('wordcloudabort', false);
        sendEvent('wordcloudstop', false);
        removeEventListener('wordcloudstart', anotherWordCloudStart);
        return;
    }
    i++;
    timer[timerId] = loopingFunction(loop, settings.wait);
},

// 绘制单个词
var putWord = function putWord(item, loopIndex) {
    if (loopIndex > 20) {
      return null;
    }

    var word, weight, attributes;
    if (Array.isArray(item)) {
      word = item[0];
      weight = item[1];
    } else {
      word = item.word;
      weight = item.weight;
      attributes = item.attributes;
    }
    // 获取绘制角度
    var rotateDeg = getRotateDeg();

    var extraDataArray = getItemExtraData(item);

    // 获取一些必要的文字信息：字号、边界框、横向/纵向占用的网格数量、占用的具体网格坐标。
    var info = getTextInfo(word, weight, rotateDeg, extraDataArray);

    // not getting the info means we shouldn't be drawing this one.
    if (!info) {
      return false;
    }

    if (exceedTime()) {
      return false;
    }

    // If drawOutOfBound is set to false,
    // skip the loop if we have already know the bounding box of
    // word is larger than the canvas.
    if (!settings.drawOutOfBound && !settings.shrinkToFit) {
      var bounds = info.bounds;
      if (bounds[1] - bounds[3] + 1 > ngx || bounds[2] - bounds[0] + 1 > ngy) {
        return false;
      }
    }

    // Determine the position to put the text by
    // start looking for the nearest points
    var r = maxRadius + 1;

    // 尝试在一个坐标上绘制文字
    // gxy 即为网格坐标。
    var tryToPutWordAtPoint = function (gxy) {
      // 文字的中心对其网格的中心
      var gx = Math.floor(gxy[0] - info.gw / 2);
      var gy = Math.floor(gxy[1] - info.gh / 2);
      var gw = info.gw;
      var gh = info.gh;

      // 是否能绘制文字（是否有重叠）
      if (!canFitText(gx, gy, gw, gh, info.occupied)) {
        return false;
      }

      // 绘制文字
      drawText(
        gx,
        gy,
        info,
        word,
        weight,
        maxRadius - r,
        gxy[2],
        rotateDeg,
        attributes,
        extraDataArray
      );

      // 更新网格状态
      updateGrid(gx, gy, gw, gh, info, item);

      return {
        gx: gx,
        gy: gy,
        rot: rotateDeg,
        info: info
      };
    };

    // 从画布中心以螺旋向外的形式开始尝试绘制单词
    while (r--) {
      // 基于半径 获取尝试绘制文字的网格坐标
      var points = getPointsAtRadius(maxRadius - r);

      if (settings.shuffle) {
        points = [].concat(points);
        shuffleArray(points);
      }

      // 在这些坐标点上尝试绘制文字
      for (var i = 0; i < points.length; i++) {
        var res = tryToPutWordAtPoint(points[i]);
        if (res) {
          return res;
        }
      }

      // var drawn = points.some(tryToPutWordAtPoint);
      // if (drawn) {
      //   // leave putWord() and return true
      //   return true;
      // }
    }

    if (settings.shrinkToFit) {
      if (Array.isArray(item)) {
        item[1] = (item[1] * 3) / 4;
      } else {
        item.weight = (item.weight * 3) / 4;
      }
      return putWord(item, loopIndex + 1);
    }

    // we tried all distances but text won't fit, return null
    return null;
  };

// 获取当前半径上可尝试绘制文字的坐标点
var getPointsAtRadius = function getPointsAtRadius(radius) {
    if (pointsAtRadius[radius]) {
      return pointsAtRadius[radius];
    }

    // 基于半径的大小 获取可放置文字的坐标点的个数
    var T = radius * 8;

    // Getting all the points at this radius
    var t = T;
    var points = [];

    if (radius === 0) {
      points.push([center[0], center[1], 0]);
    }

    // 基于不同的布局图形（圆/矩形/棱型等）生成坐标点。
    while (t--) {
      // distort the radius to put the cloud in shape
      var rx = 1;
      if (settings.shape !== 'circle') {
        rx = settings.shape((t / T) * 2 * Math.PI); // 0 to 1
      }

      // Push [x, y, t]; t is used solely for getTextColor()
      points.push([
        center[0] + radius * rx * Math.cos((-t / T) * 2 * Math.PI),
        center[1] +
        radius * rx * Math.sin((-t / T) * 2 * Math.PI) * settings.ellipticity,
        (t / T) * 2 * Math.PI
      ]);
    }

    pointsAtRadius[radius] = points;
    return points;
  };

var canFitText = function canFitText(gx, gy, gw, gh, occupied) {

    var i = occupied.length;
    while (i--) {
      var px = gx + occupied[i][0];
      var py = gy + occupied[i][1];

      if (px >= ngx || py >= ngy || px < 0 || py < 0) {
        // 超出边界则返回
        if (!settings.drawOutOfBound) {
          return false;
        }
        continue;
      }

      // 坐标被占用 返回false
      if (!grid[px][py]) {
        return false;
      }
    }
    // 坐标全部未被占用则返回true
    return true;
  };