如何实现一个词云？

各位同学大家好，今天我们给大家带来的是一篇字节跳动数据平台的 hunmix 的文章《如何实现一个词云？》，阅读时长偏长，mark起来。

预计阅读时间：20分钟

什么是词云？

标签云或词云是关键词的视觉化描述，是对文本中出现频率较高的关键词予以视觉上的突出，形成关键词云层或关键词渲染，从而过滤掉大量的文本信息，使浏览网页者只要一眼扫过文本就可以领略文本的主旨。

对词云不了解的同学可以加入我们「可视化团队」，「豆皮范儿」后台回复加群，欢迎咨询和交流，我们一起来做可视化库，查看词云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' }]

我们需要做的就是将词汇按照权重从大到小进行排序，对于每一个单词：

•选择一个初始位置•尝试放置，看是否与已经放置的单词发生重叠。如果可以放下，则记录该单词放置坐标，尝试放置下一个单词；如果不能放下，则根据布局逻辑移动到下一个位置，再次进行尝试，直到能够放下或到达放置的最外边界(即后面的位置已经不可能放下该单词了)。

如此循环直到所有的单词都尝试完毕，此时可以得到一个待放置的词汇数组，最后遍历该数组根据词汇的坐标、颜色、字体大小等信息依次绘制到画布即可。

流程图如下：

image.png

关键问题

按照上述思路，实现一个简单的词云，至少需要解决两个关键问题：

• 文字布局算法，它决定了单词以怎样的路径尝试放置，即放置不下时获取下一个放置坐标的值。

• 文字碰撞算法，进行放置尝试时的重叠判断，它决定了文字是否可以放置。

文字布局算法

一般情况下，词云的布局以中心为起始点，逐渐以环形向外围扩展，形成文字从中间到外围权重逐渐递减的效果。

如下图，权重大的词多数分布在靠近中心的地方，越靠外，词汇权重越低，整体呈环形向外扩展。

阿基米德螺线

阿基米德螺线(亦称“等速螺线”)可以方便的实现上述布局效果，这种螺线从中心开始向外旋转，的每条臂的间距永远相等，我们可以在悬臂上取点作为放置坐标，从中心点开始放置，沿着悬臂将单词均匀的从中心向外围放置。其曲线绘制如下图：

相关公式

代码实现

实现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 = 0b1001B = 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数组，再次进行尝试，直到达到最大缩放比或所有单词均可放置。获取所有单词放置坐标后，将所有单词字号及坐标位置乘以缩放比例即可。

自定义词云形状

可以通过用户上传图片的方式在自定义形状，在实现上，只需要获取图片中有绘制内容的部分，存储为一个数组。在随后的碰撞检测中，也与该数组进行一次比较，就可以达到图像内放置单词的需求。

性能优化

单词缓存

经过测试，在几千个单词时，计算时间将会非常长，经过排查后发现大部分时间消耗在于放置单词的步骤。为此我们增加一个单词缓存，在相同旋转角度下，缓存最大不可放置的宽高，当开始放置时查询到当前单词的宽高大于或等于已缓存的最小宽高时，跳过尝试放置该单词。这个策略在单词量大，且有大量相同字号，相同字数的单词时会有明显优化效果。

参考资料

https://github.com/jasondavies/d3-cloud

https://www.jasondavies.com/wordcloud/about/

福利

特意为大家准备了以下礼物进行抽奖：

那么如何获奖呢？

获奖分为以下3步

•第1步：关注本公众号「豆皮范儿」•第2步：转发本文到朋友圈并截图。•第3步：在本公众号「豆皮范儿」下回复你的截图

抽奖和领取奖品等其他事项：

•  「豆皮范儿」公众号后台回复「加群」，•  会在粉丝群公开抽奖过程，抽奖结果会单独发文章出来。

The     End

如果你觉得这篇文章对你有帮助，有启发，我想请你帮我2个小忙：

1、点个「在看」，让更多的人也能看到这篇文章内容；

2、关注公众号「豆皮范儿」，公众号后台回复「加群」 加入我们一起学习；

关注公众号的福利持续更新，公众号后台送学习资料：

1、豆皮范儿后台回复「vis」，还可以获取更多可视化免费学习资料。

2、豆皮范儿后台回复「webgl」，还可以获取webgl免费学习资料。

3、豆皮范儿后台回复「算法」，还可以获取算法的学习资料。

4、豆皮范儿后台回复「招聘」，获取各种内推。

字节跳动数据平台前端团队，在公司内负责大数据相关产品的研发。我们在前端技术上保持着非常强的热情，除了数据产品相关的研发外，在数据可视化、海量数据处理优化、web excel、WebIDE、私有化部署、工程工具都方面都有很多的探索和积累，有兴趣可以与我们联系。

投递简历，更多精彩文章，欢迎关注 “豆皮范儿” 

点个在看你最好看