如何實現一個詞雲

2021 年 9 月 23 日
筆記

文章轉自豆皮范兒-如何實現一個詞雲

什麼是詞雲？

標籤雲或詞雲是關鍵詞的視覺化描述，是對文本中出現頻率較高的關鍵詞予以視覺上的突出，形成關鍵詞雲層或關鍵詞渲染，從而過濾掉大量的文本資訊，使瀏覽網頁者只要一眼掃過文本就可以領略文本的主旨。

對詞雲不了解的同學可以加入我們「可視化團隊」，「豆皮范兒」後台回復加群，歡迎諮詢和交流，我們一起來做可視化庫，查看詞雲demo進行了解。

步驟拆分

繪製一個詞雲大致分為如下步驟

數據處理：將數據中的資訊映射到單詞的繪製屬性，如字型大小、顏色、字重等。
布局演算法：計算每個單詞的放置位置。
繪製：將計算後的資訊繪製到畫布上。

實現思路

這裡不詳細展開第一個步驟的實現，假設我們已經有了一組處理過的數據，格式如下:

const data = [

  {

    text: '螺螄粉',

    fontSize: 40,

    color: 'red'

  },

  {

    text: '重慶小面',

    fontSize: 35,

    color: 'blue'

  },

  {

    text: '肉夾饃',

    fontSize: 35,

    color: 'blue'

  },

  {

    text: '炸醬麵',

    fontSize: 32,

    color: 'blue'

  },

  {

    text: '沙縣小吃',

    fontSize: 25,

    color: 'blue'

  },

  {

    text: '烤冷麵',

    fontSize: 23,

    color: 'blue'

  },

  {

    text: '臭豆腐',

    fontSize: 23,

    color: 'blue'

  },

  {

    text: '缽缽雞',

    fontSize: 20,

    color: 'red'

  },

  {

    text: '酸辣粉',

    fontSize: 19,

    color: 'blue'

  },

  {

    text: '冒菜',

    fontSize: 15,

    color: 'blue'

  },

  {

    text: '驢打滾',

    fontSize: 12,

    color: 'blue'

  },

  {

    text: '板栗',

    fontSize: 11,

    color: 'red'

  },

  {

    text: '醪糟',

    fontSize: 10,

    color: 'blue'

  }

]

我們需要做的就是將辭彙按照權重從大到小進行排序，對於每一個單詞：

選擇一個初始位置
嘗試放置，看是否與已經放置的單詞發生重疊。如果可以放下，則記錄該單詞放置坐標，嘗試放置下一個單詞；如果不能放下，則根據布局邏輯移動到下一個位置，再次進行嘗試，直到能夠放下或到達放置的最外邊界(即後面的位置已經不可能放下該單詞了)。

如此循環直到所有的單詞都嘗試完畢，此時可以得到一個待放置的辭彙數組，最後遍歷該數組根據辭彙的坐標、顏色、字體大小等資訊依次繪製到畫布即可。

流程圖如下：

關鍵問題

按照上述思路，實現一個簡單的詞雲，至少需要解決兩個關鍵問題：

文字布局演算法，它決定了單詞以怎樣的路徑嘗試放置，即放置不下時獲取下一個放置坐標的值。

文字碰撞演算法，進行放置嘗試時的重疊判斷，它決定了文字是否可以放置。

文字布局演算法

一般情況下，詞雲的布局以中心為起始點，逐漸以環形向外圍擴展，形成文字從中間到外圍權重逐漸遞減的效果。

如下圖，權重大的詞多數分布在靠近中心的地方，越靠外，辭彙權重越低，整體呈環形向外擴展。

阿基米德螺線

阿基米德螺線(亦稱「等速螺線」)可以方便的實現上述布局效果，這種螺線從中心開始向外旋轉，的每條臂的間距永遠相等，我們可以在懸臂上取點作為放置坐標，從中心點開始放置，沿著懸臂將單詞均勻的從中心向外圍放置。其曲線繪製如下圖：

程式碼實現

實現archimedeanSpiral來獲取坐標點，paintSpiral函數用於繪製螺線輔助觀察。

/**

 * 阿基米德螺線, 用於初始化位置函數, 調用後返回一個獲取位置的函數

 * @param {*} size 畫布大小, [width, height]

 * @param {*} { step = 0.1, b = 1, a = 0 }  步長(弧度), 螺距, 起始點距中心的距離

 * @returns 

 */

export function archimedeanSpiral(size, { step = 0.1, b = 1, a = 0 } = {}) {

  const e = size[0] / size[1]; // 根據畫布長寬比例進行對應縮放

  // 參數t為當前弧度值

  return function(t) {

    return [e * (a + b * (t *= step)) * Math.cos(t), (a + b * t) * Math.sin(t)];

  };

}



/**

 * 輔助函數, 繪製阿基米德螺線

 * @param {*} size 畫布大小, [width, height]

 * @param {*} getPosition 布局函數, 調用archimedeanSpiral獲取的返回值

 * @param {*} params { showIndex } 是否顯示序號 

 */

export function paintSpiral (size, getPosition, { showIndex = false } = {}) {

    const points = [] // 所有放置點



    let dxdy,

      maxDelta = Math.sqrt(size[0] * size[0] + size[1] * size[1]), // 最大半徑

      t = 1, // 阿基米德弧度

      index = 0, // 當前位置序號

      dx, // x坐標

      dy; // y坐標

    // 通過每次增加的步長固定為1，實際步長為 step * 1，來獲取下一個放置點

    while (dxdy = getPosition(t += 1)) {

      dx = dxdy[0]

      dy = dxdy[1]



      if (Math.min(Math.abs(dx), Math.abs(dy)) >= maxDelta) break; // (dx, dy)距離中心超過maxDelta，跳出螺旋返回false



      points.push([dx, dy, index++])

    }

    // 初始化畫布

    const canvas = document.createElement('canvas')

    canvas.width = size[0]

    canvas.height = size[1]

    canvas.style.width = size[0]

    canvas.style.height = size[1]

    const ctx = canvas.getContext('2d')

    ctx.fillStyle = '#f11';

    ctx.strokeStyle = 'black';

    let last = [0, 0]



    // 將放置點繪製出來

    for(let point of points) {

      ctx.beginPath();

      ctx.moveTo(last[0] + size[0] / 2, last[1] + size[1] / 2)

      ctx.lineTo(point[0] + size[0] / 2, point[1] + size[1] / 2)

      last = point

      ctx.stroke();

      

      ctx.beginPath();

      ctx.arc(point[0] + size[0] / 2, point[1] + size[1] / 2, 2, 0, 2 * Math.PI, false);

      ctx.font = '20px serif'

      // 繪製序號

      showIndex && ctx.fillText(point[2], point[0] + size[0] / 2, point[1] + size[1] / 2)

      ctx.fill()

    }

    document.body.append(canvas)

  }

繪製影像

調用paintSpiral函數進行繪製，紅色圓形標記點是我們獲取的放置坐標，用黑線連接放置點，用於看清螺線的形狀(實際使用時只需要放置點即可)。

// 畫布寬高

const CANVAS_SIZE = [500, 500]

// 繪製螺線

const getPosition = archimedeanSpiral(CANVAS_SIZE, { step: 0.1, b: 1 })

paintSpiral(CANVAS_SIZE, getPosition, { showIndex: false })

為了方便觀察，增大螺距與步長，繪製一個比較稀疏的螺線，同時標記出點的放置順序。

const getPosition = archimedeanSpiral(CANVAS_SIZE, { step: 1, b: 10 })

paintSpiral(CANVAS_SIZE, getPosition, { showIndex: true })

可以看到將螺距調大後每一圈的螺線相距的更遠了，而調整步長後每一圈取的標記點數量變少了。接下來嘗試將文字按照放置點順序進行擺放。

實現一個drawWords函數來根據布局函數放置辭彙。

/**

 * 根據阿基米德螺線繪製辭彙

 * @param {*} data 辭彙數據

 * @param {*} getPosition 布局函數

 */

const drawWords = (data, size, getPosition, ) => {

  let t = 0

  const { context, canvas } = createCanvas(size[0], size[1])

 

  data.forEach((word, index) => {

    const [dx, dy] = getPosition(t += 1)

    word.x = size[0] / 2 + dx

    word.y = size[1] / 2 + dy

    word.fontSize = Math.floor(word.fontSize / 2)

    word.text = `${index}-${word.text}`

    drawText(context, word)

  })

  

  document.body.appendChild(canvas)

}

繪製螺線與辭彙

// 繪製一遍螺線用於對比

const getPosition = archimedeanSpiral(CANVAS_SIZE, { step: 1, b: 10 })

paintSpiral(CANVAS_SIZE, getPosition, { showIndex: true })



// 繪製單詞, 這裡的data為文章開頭的數據

drawWords(data, size, getPosition)

辭彙現在可以按照螺線的形狀進行排布了，但是由於沒有做碰撞檢測，放置點相近得單詞重疊在了一起。接下來只需要知道放置辭彙時是否會重疊，就可以沿著螺線進行放置嘗試，直至所有單詞嘗試完畢。

碰撞檢測演算法

碰撞檢測有多種實現方式，我們採用逐像素比較的方式。使用一個數組來記錄整個畫布中每個像素點的佔用情況，每個單詞則在初始化時保存自己的像素佔用資訊。在放置單詞時，將單詞的像素佔用資訊與畫布中對應位置的像素資訊做對比。在文字放置後，更新畫布對應位置的像素佔用資訊。

為了便於比較和操作，使用一維數組來存儲像素資訊，在全局初始化一個board數組用於保存整個畫布的像素佔用情況(長度為畫布寬高)，每個辭彙新建一個sprite數組用於保存自身文字的像素佔用情況(長度為文字寬高)。

碰撞檢測過程

假設變數board存儲了整個畫布像素資訊，每個單詞使用sprite存儲自身的像素佔用資訊。

下圖為放置”L”單詞時的簡單示意圖，左側為board數組，右側為單詞的sprite數組。首先需要根據文字布局函數找到要放置的點。如第一個點根據布局函數，在畫布的中心。

紅點為嘗試在畫布中放置的位置，根據放置的坐標與文字的寬高等資訊，可以計算出board中對應像素範圍（綠色框內），遍歷sprite數組，將sprite中的像素與board綠色框中的像素一一做比較，若結果為兩者不同時為1，則不重疊。顯然，在下面的圖中單詞”L”與畫布中已存在的”H”有重疊，則”L”不能放置在紅點處，調用布局函數尋找下一個放置點嘗試。

經過多次嘗試失敗後找到下圖紅點位置，經過對比發現沒有重疊，則認為紅點處可以放置下單詞”L”，更新”L”單詞的最終繪製坐標x, y。

更新”L”坐標資訊後，意味著單詞”L”已經確定在畫布最終繪製時的位置，這時將”L”的像素佔用資訊更新到board數組中。隨後開始進行下一個單詞的放置嘗試，直到所有單詞放置完畢。

像素數據的存儲方式

由於畫布上的像素點是二維資訊，而我們使用一維數組進行存儲，所以在保存時需要記錄寬度資訊，即幾個元素為一行，用以還原它在二維畫布上的位置資訊，使用1表示已佔用，0表示未佔用。

以一個”L”字母為例，假設”L”單詞的包圍盒寬為8，高為11，則可以新建一個長度為 88 (8 * 11)的一維數組來存儲像素佔用情況，同時記錄該單詞寬度為8。如下圖：

此時檢測一次的時間複雜度為：$$wordWidth * wordHeight$$

使用二進位存儲像素資訊

一個canvas畫布上的像素點數量可能非常龐大，如一個解析度為1，500 * 500的畫布上，有250000個像素點，如果使用一個整數存儲一個像素資訊的方法，需要一個長度為250000的數組來存儲整個畫布的資訊。操作一個大數組會導致記憶體佔用變大，同時遍歷效率也會變低。

在碰撞檢測的場景中，對於每一個像素，我們只需要記錄”已佔用”和”未佔用”兩種情況。這兩種狀態可以使用二進位的1和0來表示，因此我們可以使用整數表示一個32位的二進位數，其中1表示已佔用，0表示未佔用。

對於500 * 500的畫布，只需要一個長度為7812的數組即可保存。以同一個”L”字母為例，優化後只需要一個長度為8的數組就可以存儲下單詞”L”的sprite資訊。如下圖：

此時放置檢測的時間複雜度為：$$wordWidth * wordHeight / 32$$

可視化查看像素資訊

為了更直觀的觀察數組中存儲的像素佔用情況，編寫一個printPixelArray函數來將數組中的數值以二維的形式列印出來。

數組列印函數實現如下:

/**

 * 列印像素佔用數組

 * @param {*} board 

 * @param {*} w 

 * @returns 

 */

export const printPixelArray = (board, w) => {

  let bitStr = ''

  let intStr = ''

  for (let i = 0; i < board.length / w; i++) {

    for (let j = 0; j < w; j++) {

      bitStr += `${(board[i * w + j] >>> 0).toString(2).padStart(32,'0')}|`

      intStr += `${board[i * w + j].toString(10).padEnd(32)}|`

    }

    // 整數格式

    bitStr += '\n'

    // 二進位格式

    intStr += '\n'

  }

  return { bitStr, intStr }

}

以單詞”螺獅粉”為例，下圖是將”螺螄粉”的sprite數組的值列印出來的結果，根據單詞的寬度進行換行，每個整數之間使用|分割。可以看到一維數組已經還原成了二維的平面，”螺螄粉”一行使用六個整數來記錄像素資訊。

將整數轉換為二進位的格式進行顯示，可以更直觀地觀察到像素的佔用情況。

將整數轉換為二進位可以清楚的看到每個像素的佔用情況。然而由於字元串佔據面積太大，不方便整體調試，所以我們再編寫一個paint函數來將數組中的像素佔用情況繪製到一個等比例的canvas中。

實現程式碼如下:

/**

 * 根據數組中存儲的像素資訊繪製canvas

 * @param {*} board 

 * @param {*} paintSize 

 */

export const paint = (board, paintSize) => {

  const curSize = paintSize

  const imageData = new ImageData(curSize[0], curSize[1]);

  let array = imageData.data

  for (let i = 0; i < curSize[1]; i++) {

    for (let j = 0; j < (curSize[0] >> 5); j++) {

      let value = board[i * (curSize[0] >> 5) + j]

      for (let k = 0; k < 32; k++) {

        // 遮罩，獲取對應位置bit值

        const msk = 0b1 << (32 - k)

        if (value & msk) {

          // 佔用像素, 填充白色

          for(let l = 0; l < 4; l++) {

            array[i * curSize[0] * 4 + j * 32 * 4 + k * 4 + l] = 255;

          }

        } else {

          // 未佔用像素, 填充黑色

          for(let l = 0; l < 3; l++) {

            array[i * curSize[0] * 4 + j * 32 * 4 + k * 4 + l] = 0;

          }

          array[i * curSize[0] * 4 + j * 32 * 4 + k * 4 + 3] = 255;

        }

        // 數組元素分割線, 填充紅色, 間隔32px

        if (k === 0) {

          array[i * curSize[0] * 4 + j * 32 * 4 + k * 4 + 0] = 255;

          array[i * curSize[0] * 4 + j * 32 * 4 + k * 4 + 1] = 0;

          array[i * curSize[0] * 4 + j * 32 * 4 + k * 4 + 2] = 0;

        }

      }

    }

  }

  const canvas = document.createElement('canvas')

  canvas.width = curSize[0]

  canvas.height = curSize[1]

  const ctx = canvas.getContext('2d')

  ctx.putImageData(imageData, 0, 0)

  canvas.style.marginRight = '10px'

  document.body.appendChild(canvas)

}

const word = data[0]

// 繪製螺螄粉的像素資訊

paint(word.sprite, [word.w, word.h])

繪製效果如圖:

其中「已佔用」像素以白色繪製，「未佔用」像素使用黑色繪製，紅色豎線為數組中每個元素的分割線，即兩條紅色豎線之間為一個整數所保存的32個像素的佔用資訊。

初始化像素資訊

在全局初始化變數board來存儲整個畫布的像素資訊，board的長度為要繪製的畫布的寬 * 高，初始全部填充為0(畫布上沒有放置任何單詞)。

const size = [500, 500] // [寬，高]

const board = new Array(size[0], size[1]).fill(0)

為了獲取單詞的像素資訊，需要計算單詞寬高，將單詞繪製到畫布上，然後使用ctx.getImageData(sx, sy, sw, sh)方法來獲取像素資訊。它的四個參數分別是起始點x坐標，起始點y坐標，截取寬度，截取高度。

ImageData的data中使用四個整數來表示一個像素點的顏色，沒有被繪製到的部分默認值為0, 0, 0, 0。我們只需要知道當前像素是否被佔用，所以只要取alpha的值即可，1為佔用，0為為佔用。

通過ctx.measureText方法獲取文字的寬度，為了避免文字被截斷，使用字型大小 * 2作為單詞高度，文字的寬高決定了sprite數組的大小。

為了盡量少的操作canvas節省性能，獲取像素資訊的方案採取類似css精靈圖的方案。首先初始化一個大的畫布，然後一次儘可能多的在一個大畫布上繪製文字，使用ctx.getImageData(0, 0, 畫布寬度, 畫布高度)獲取整個畫布的像素資訊數組，然後根據文字的繪製坐標及寬高資訊，在整個畫布數組中截取文字對應的像素佔用資訊並保存到辭彙的sprite數組中。

注意，辭彙的sprite不是一次全部獲取完成的。在嘗試放置辭彙時，會嘗試獲取該辭彙對應的sprite，如果發現sprite還未初始化，則以當前辭彙為起始索引開始一輪辭彙sprite初始化。初始的canvas大小為2048 * 2048，當繪製不下時停止繪製，更新已繪製的辭彙sprite，隨後進行放置嘗試。直到放置單詞的sprite不存在時，再進行第下一次的批量sprite獲取。

獲取單詞像素佔用資訊(sprite數組)流程圖：

無法複製載入中的內容

程式碼實現：

/**

 * 獲取單詞sprite數組

 * @param {*} contextAndRatio canvas上下文和畫布比例

 * @param {*} d 單詞資訊

 * @param {*} data 所有單詞

 * @param {*} di 當前單詞index

 */

function cloudSprite(contextAndRatio, d, data, di) {

  // 如果當前單詞已經擁有sprite資訊，跳過

  if (d.sprite) return;

  // 精靈圖畫布大小為2048 * 2048

  var c = contextAndRatio.context,

      ratio = contextAndRatio.ratio;



  c.clearRect(0, 0, (cw << 5) / ratio, ch / ratio);

  var x = 0,

      y = 0,

      maxh = 0,

      n = data.length,

      w, // 單詞長度(px)

      w32, // 畫布長度(數組中一行的元素個數)

      h, // 單詞高(px)

      i,

      j;

  --di;

  while (++di < n) {

    d = data[di];

    c.save();

    c.font = d.style + " " + d.weight + " " + ~~((d.size + 1) / ratio) + "px " + d.font; // 設置文字屬性

    w = c.measureText(d.text + "m").width * ratio; // 獲取文字寬度

    h = d.size << 1; // 因為沒有獲取文字高度的api，為了保證截取像素完整，默認高度為單詞fontSize * 2

    // 如果單詞有旋轉屬性，計算旋轉後的寬高

    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;

    }

    // w, h為旋轉後，詞語所佔區域的寬高

    if (h > maxh) maxh = h; // 記錄當前行最大高度

    // 如果當前行放不下，就另起一行，y方向向下移動當前行的最大高度

    if (x + w >= (cw << 5)) {

      x = 0;

      y += maxh;

      maxh = 0;

    }



    if (y + h >= ch) break; // 繪製區域的高度為2048px，超過長度下次繪製

    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);

    }

    c.restore();

    // 詞語繪製完成，記錄其在畫布上的相對位置和範圍

    d.width = w;

    d.height = h;

    d.xoff = x;

    d.yoff = y;

    // x0, x1, y0, y1是四角相對於中心點的相對坐標

    d.x1 = w >> 1;

    d.y1 = h >> 1;

    d.x0 = -d.x1;

    d.y0 = -d.y1;

    d.hasText = true;

    // x位置右移，等待下一個詞語繪製

    x += w;

  }

  // 獲取整個精靈圖畫布的像素資訊

  var pixels = c.getImageData(0, 0, (cw << 5) / ratio, ch / ratio).data,

      sprite = [];

  // 根據單詞的位置和長寬資訊從pixels中截取並保存單詞部分的像素資訊

  while (--di >= 0) {

    d = data[di];

    if (!d.hasText) continue;

    w = d.width;

    w32 = w >> 5;

    h = d.y1 - d.y0;

    // Zero the buffer

    for (i = 0; i < h * w32; i++) sprite[i] = 0;

    x = d.xoff;

    if (x == null) return;

    y = d.yoff;

    var seen = 0,

        seenRow = -1;

 

    // 遍歷像素，根據單詞的繪製坐標與寬高資訊，在畫布中獲取對應像素資訊，保存至sprite

    for (j = 0; j < h; j++) {

      for (i = 0; i < w; i++) {

        // 在sprite數組中，每一個Uint32的數字記錄了32個像素的繪製情況

        // 在pixels中，只取alpha通道的值，因此需要每個像素需要 << 2 得到alpha通道

        var k = w32 * j + (i >> 5),

            m = pixels[((y + j) * (cw << 5) + (x + i)) << 2] ? 1 << (31 - (i % 32)) : 0;

        sprite[k] |= m; // 更新sprite對應像素資訊

        seen |= m; // 記錄當前行是否有著色資訊

      }

      // 如果當前行發現著色，開始記錄行號

      if (seen) seenRow = j;

      else {

        // 如果當前行未發現著色，則在結果中省去該行（高度--，y坐標++，左上角相對坐標++）

        d.y0++;

        h--;

        j--;

        y++;

      }

    }

    d.y1 = d.y0 + seenRow; // 更新右下角相對坐標

    d.sprite = sprite.slice(0, (d.y1 - d.y0) * w32); // 捨棄數組中冗餘部分

  }

}

// 獲取單詞的寬高、左右邊界坐標、像素佔用等資訊。

data.forEach((word, index) => cloudSprite(contextAndRatio, word, data, index))

將繪製後的canvas顯示出來如下:

下圖是使用paint函數繪製的各單詞的sprite數組:

處理後的單詞對象如下:

const word = {

    w: number; // 寬

    h: number; // 高

    x0: number; // x左邊界偏移量，<= 0

    x1: number; // x右邊界偏移量，>= 0

    y0: number; // y上邊界偏移量，<= 0

    y1: number; // y下邊界偏移量，>= 0

    sprite: number[]; // 單詞的像素佔用資訊，數組長度為w * h / 32

    x: number; // 繪製坐標

    y: number; // 繪製坐標

}

碰撞檢測的偏移處理

碰撞檢測計算

有了單詞的sprite資訊後，就可以使用它與board進行碰撞檢測了。

這裡要注意的是，現在存在兩個單位概念。

真實畫布的單位，即像素

通過布局函數獲取的文字繪製坐標以像素為單位。

用於存儲的最小單位，即一個整數，記錄32個像素

在計算單詞是否重疊時是以整數為最小單位進行運算。在判斷兩個整數單位中是否有像素點重疊時，只需將兩個整數進行”與”運算，如結果為1，則說明重疊了，如結果為0，則說明沒有重疊。

在進行碰撞檢測時，通常需要對整數進行位運算來達到判斷重疊和獲取特定數值的操作。

位運算基本知識

接下來可能要用到一些簡單的位運算知識～先來複習一下吧

假設我們有兩個二進位數A和B，0b為二進位前綴

A = 0b1001

B = 0b0011

按位與(&)

對每一位執行”與”操作，對應位置都為1時，結果才為1，否則為0。

與操作可用於進行像素對比。

按位或(|)

對每一位執行”或”操作，對應位置有一個都為0時，結果為0，否則為1。

或操作可以用於將兩個整數合成一個。

左移運算符(<<)

各二進位全部左移若干位，高位丟棄，低位補0

右移運算符(>>)

各二進位全部右移若干位，對無符號數，高位補0。

左移與右移可用於截取左邊或右邊的部分值。

上述的碰撞檢測中，是假設是像素為單位進行計算的，在像素為單位的情況下，只需在board中找到

辭彙碰撞檢測的通用處理

在實際進行單詞放置時，單詞坐標是以像素為單位，這就會造成進行碰撞檢測時，board的整數與sprite的整數是錯位的，無法直接進行”與”運算來獲取碰撞結果。

這時就需要將對應位置的像素資訊提取出來，組成一個新的整數來與board中的數值進行運算。

上圖中，實際需要比較黃色透明矩形(畫布)與綠色矩形(單詞)內的像素。對於這種情況，需要分別對1、2、3列內的像素進行比較，因為單詞的像素矩形與畫布的矩形存在錯位的情況，以第一個1列為例，需要將單詞B區域的像素取出，在左側補零，組成一個新的整數，然後在於畫布對應位置的整數進行運算。對於第二列來說，需要取單詞第一個整數的右邊部分像素，與第二個單元格的左邊部分像素來組成一個整數計算。

對於一個32位的二進位數，我們可以方便的用>>或<<實現保留左側部分資訊或保留右側部分資訊，分別計算後再進行一次或操作即可得到一個新的32位數。

獲取紅色透明矩形部分第一行像素佔用的偽程式碼：

// 設wordSpriteLeft為第一行第一個數值

// wordSpriteRight為第一行第二個數值

// 設偏移量為x

// 獲取第一個數值右側部分

const leftPartInBoard = wordSpriteLeft << (32 - x)

// 獲取第二個數值左側部分

const rightPartInBoard = wordSpriteRight >> x

// 合併組成新數值

const newValue = leftPartInBoard | rightPartInBoard

// 碰撞檢測

const isCollide = newValue & board[i]

碰撞檢測程式碼實現

/**

 * 檢測單詞是否重疊

 * @param {*} tag 單詞

 * @param {*} board 畫布像素佔用資訊

 * @param {*} sw 畫布長度

 */

function cloudCollide(tag, board, sw) {

  sw >>= 5; // 獲取畫布長度在數組中對應的寬度

  var sprite = tag.sprite,

      w = tag.width >> 5, // 單詞在數組中的寬

      lx = tag.x - (w << 4), // 單詞左邊界x坐標(px)

      sx = lx & 0x7f, // 單詞偏移（px）, 當前元素右側移除數量

      msx = 32 - sx, // 需要從sprite上一個元素中移除的數量

      h = tag.y1 - tag.y0, // 單詞高度

      x = (tag.y + tag.y0) * sw + (lx >> 5), // 數組中的起始位置

      last;

  

  // 逐行遍歷單詞sprite，判斷與已繪製內容重疊

  for (var j = 0; j < h; j++) {

    last = 0;

    for (var i = 0; i <= w; i++) {

      // last << msx 獲取sprite前一個元素超出board左側邊界的部分

      // (last = sprite[j * w + i]) >>> sx 獲取sprite超出board右側邊界的部分，並將值賦給last，便於下一個元素的計算

      // 將以上兩部分進行"或"操作，合併成完整的32位像素資訊

      // 將新合併的數字與board對應數組進行"與"操作，值為0則不重疊，返回true，否則返回false

      if (((last << msx) | (i < w ? (last = sprite[j * w + i]) >>> sx : 0))

          & board[x + i]) return true;

    }

    x += sw;

  }

  return false;

}

放置單詞函數程式碼實現

// 遍歷螺線線上的點，檢測單詞是否可以放置

export const place = (board, word, bounds, size, getPosition) => {

  const startX = word.x; // 初始值為畫布 x 中點

  const startY = word.y; // 初始值為畫布 y 中點

  const maxDelta = Math.sqrt(size[0] * size[0] + size[1] * size[1])

  const s = getPosition; // 阿基米德螺線函數

  const dt = Math.random() < .5 ? 1 : -1;

  let t = -dt;

  let dxdy,

      dx,

      dy;



  while (dxdy = s(t += dt)) {

    dx = ~~dxdy[0]; // x 偏移量

    dy = ~~dxdy[1]; // y 偏移量

    

    // 超出最大範圍，單詞無法放置

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



    word.x = startX + dx; // 獲取單詞在畫布中的 x 坐標

    word.y = startY + dy; // 獲取單詞在畫布中的 y 坐標



    // 文字超出畫布範圍時跳過

    if (word.x + word.x0 < 0 || word.y + word.y0 < 0 ||

        word.x + word.x1 > size[0] || word.y + word.y1 > size[1]) continue;

    // 碰撞檢測

    if (!bounds || !cloudCollide(word, board, size[0])) {

      // 與board進行像素對比

      if (!bounds || collideRects(word, bounds)) {

        // 將單詞的像素佔用資訊更新到board

        let sprite = word.sprite,

            w = word.width >> 5,

            sw = size[0] >> 5,

            lx = word.x - (w << 4),

            sx = lx & 0x7f, // sprite數組左側偏移

            msx = 32 - sx, // 位移遮罩

            h = word.y1 - word.y0,

            x = (word.y + word.y0) * sw + (lx >> 5),

            last;

        // 逐行遍歷

        for (let j = 0; j < h; j++) {

          last = 0;

          for (let i = 0; i <= w; i++) {

            board[x + i] |= (last << msx) | (i < w ? (last = sprite[j * w + i]) >>> sx : 0);

          }

          x += sw;

        }

        word.sprite = null;

        // 可以放置該單詞

        return true;

      }

    }

  }

  // 該單詞無法放置

  return false;

}

繪製詞雲

渲染函數

/**

 * 渲染詞雲

 * @param {*} size 

 * @param {*} data 

 */

const renderWordCloud = (size, data) => {

  const center = [size[0] / 2, size[1] / 2]

  const results = []

  const board = new Array((size[0] >> 5) * size[1]).fill(0);

  const getPosition = archimedeanSpiral(size);

  // const getPosition = archimedeanSpiral(size, {step: 1, b: 10});

  let bounds = null

  let i = 0

  // data = data.map((data, i) => {data.text = `${i}${data.text}`;return data})

  while (i < data.length) {

    var d = data[i];

    d.x = center[0]

    d.y = center[1]



    // 收集辭彙像素佔用情況

    cloudSprite(cloudSpriteCanvasInfo, d, data, i, size[0] >> 5, size[1]);

    if (d.hasText && place(board, d, bounds, [...size], getPosition)) {

      results.push(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;

    }

    i++

  }

  const resultCanvasInfo = createCanvas(size[0], size[1])

  results.map(word => {

    word.x = word.x + center[0];

    word.y = word.y + center[1];

    return word

  }).forEach(word => drawText(resultCanvasInfo.context, word))

  paint(board, size)

  document.body.appendChild(resultCanvasInfo.canvas)

}

一個簡單的詞雲就完成了～

其他功能支援

文字大小自適應

在實際使用中，會遇到權重最大的單詞比較長的問題，由於字型大小也設置的比較大，會導致畫布無法放置這個單詞。解決這個問題，可以對整體進行一個縮放，具體操作是判斷到文字超出邊界時，擴大board數組，再次進行嘗試，直到達到最大縮放比或所有單詞均可放置。獲取所有單詞放置坐標後，將所有單詞字型大小及坐標位置乘以縮放比例即可。

自定義詞雲形狀

可以通過用戶上傳圖片的方式在自定義形狀，在實現上，只需要獲取圖片中有繪製內容的部分，存儲為一個數組。在隨後的碰撞檢測中，也與該數組進行一次比較，就可以達到影像內放置單詞的需求。

性能優化

單詞快取

經過測試，在幾千個單詞時，計算時間將會非常長，經過排查後發現大部分時間消耗在於放置單詞的步驟。為此我們增加一個單詞快取，在相同旋轉角度下，快取最大不可放置的寬高，當開始放置時查詢到當前單詞的寬高大於或等於已快取的最小寬高時，跳過嘗試放置該單詞。這個策略在單詞量大，且有大量相同字型大小，相同字數的單詞時會有明顯優化效果。

參考資料

//github.com/jasondavies/d3-cloud

//www.jasondavies.com/wordcloud/about/

字節跳動數據平台前端團隊，在公司內負責大數據相關產品的研發。我們在前端技術上保持著非常強的熱情，除了數據產品相關的研發外，在數據可視化、海量數據處理優化、web excel、WebIDE、私有化部署、工程工具都方面都有很多的探索和積累，有興趣可以與我們聯繫。