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

布局算法

初始化：设置画布大小、背景色、网格大小等。

词处理：每个词根据其重要性（频率、权重等）被赋予一个大小。

位置选择：算法在画布上为每个词寻找合适的位置。这通常通过在画布中心开始，并向外螺旋（或其他形状，如圆形、星形等）搜索空间来实现。

碰撞检测：在放置每个词时，算法会检查该位置是否会与已放置的词重叠。这通常通过一个网格来实现，网格记录了画布上的哪些区域是空的，哪些已被占用。

绘制：一旦找到空间，词就会在画布上绘制出来，并更新网格状态。

迭代：重复上述过程，直到所有词都被尝试放置。

核心方法

weightFactor 和 shape 函数用于计算词的大小和布局形状。

getPointsAtRadius 函数计算给定半径上的点，这些点可能是词云中词的候选放置位置。

getTextInfo 函数计算单个词的布局信息，如大小和旋转。

canFitText 检查一个词是否可以放在特定位置而不覆盖已有的词。

drawText 将文本实际绘制到canvas上。

updateGrid 更新网格状态，标记已被占用的区域。

算法细节位置选择

优先从画布中心开始绘制文字。

基于不同的布局图形、在每个半径上生成一系列的坐标点用于尝试绘制图形。

例如：

圆形：

1234567// 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]);

矩形：

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

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

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

附录：核心代码123456789101112131415161718192021222324252627282930// 主循环 用于绘制词云 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);},

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122// 绘制单个词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; };

12345678910111213141516171819202122232425262728293031323334353637// 获取当前半径上可尝试绘制文字的坐标点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; };

1234567891011121314151617181920212223var 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; };