詞雲布局知多少

WordCloud詞雲是一種有效的文本數據可視化方法， 常用於展示大量文本數據。在詞雲中，一般來說，權重較高的詞相比於權重低的詞更容易被人所get到，因此能夠幫助用戶對比文本的組成及其權重。詞雲也有許多擴展，例如：詞的傾斜角度、字體、顏色等屬性都可以被作為有意義的可視映射元素；和地理信息結合使得詞的位置更有意義等。

那麼，詞雲是如何布局的呢？在其布局演算法中又有哪些有意思的東西呢？接下來小編將和大家一起開始探索詞雲的世界。

布局演算法

詞雲採用隨機貪心演算法（Randomized Greedy Algorithm）進行布局，演算法過程從權重最大的也就是最重要的單詞開始：

1. 嘗試把單詞放在指定的初始位置，一般來說是放置在中心區域；

2. 如果目標單詞和已放置的單詞有重疊，則以螺旋形狀向外移動一步，直到不再和已放置單詞交叉為止。

詞雲的基本布局演算法是不是很簡單，躁動的你是不是已經躍躍欲試了呢。

但是保證效率，高效的生成詞雲呢？布局過程中的重疊檢測會嚴重影響整個演算法的複雜度，進而我們把問題轉化為如何高效的進行重疊檢測呢？

重疊檢測演算法

檢測兩個單詞是否有重疊最簡單的辦法就是檢測它們的bounding box是否交叉，但其實單詞並不是完全充滿整個bounding box的，會浪費大量屏幕空間。

啟發式的演算法是對每個詞遞歸構造一棵層次邊界箱樹（Hierarchical Bounding Box Tree），然後對層次樹進行重疊檢測。

構造HierarchicalBounding Box Tree的方法如下：

class HierarchyTree { constructor (x0, y0, x1, y1) { this.x0 = x0 this.y0 = y0 this.x1 = x1 this.y1 = y1 this.children = [] } // 添加孩子節點 addChildren (children) { this.children = [].concat(this.children, children) }}// 構建單詞的層次樹const cosntructTree = (wordPixel, bbox) => { let {x0, y0, x1, y1} = bbox // 檢測指定bbox是否包含在單詞內容里 if (isTargetBoxInWord(wordPixel, bbox)) { // debugger return new HierarchyTree(x0, y0, x1, y1) } else if (isTargetBoxIntersectsWord(wordPixel, bbox)) { // 如果單詞和BBox有交叉 // debugger let tree = new HierarchyTree(x0, y0, x1, y1) if (x1 - x0 > MinBoxSize || y1 - y0 > MinBoxSize) { let cx = ~~((x0 + x1) / 2) let cy = ~~((y0 + y1) / 2) let tl = cosntructTree(wordPixel, {x0, y0, x1: cx, y1: cy}) let tr = cosntructTree(wordPixel, {x0: cx, y0, x1, y1: cy}) let bl = cosntructTree(wordPixel, {x0, y0: cy, x1: cx, y1}) let br = cosntructTree(wordPixel, {x0: cx, y0: cy, x1, y1}) tl && tree.addChildren(tl) tr && tree.addChildren(tr) bl && tree.addChildren(bl) br && tree.addChildren(br) } return tree } return null}

當需要檢測單詞間的重疊時只需要檢測對應的層次樹是否重疊，檢測過程如下：

const treesOverlap = (treeA, treeB, posA, posB) => { let [ax, ay] = posA let [bx, by] = posB if (bboxOverlap(treeA, treeB, posA, posB)) { if (!treeA.children.length) { if (!treeB.children.length) return true else for (let i = 0, n = treeB.children.length; i < n; i++) { if (treesOverlap(treeA, treeB.children[i], posA, posB)) return true } } else for (let i = 0, n = treeA.children.length; i < n; i++) { if (treesOverlap(treeB, treeA.children[i], posB, posA)) return true } } return false}

重疊檢測直觀示例如下：

代碼請戳：https://codepen.io/gracelinmumu/pen/wmVddg

歡迎留言其它有意思的思路和方法，共同探討~

參考資料：

[1] Viegas F B, Wattenberg M, Feinberg J. Participatory visualization with wordle[J]. IEEE transactions on visualization and computer graphics, 2009, 15(6).

[2] Li, Chenlu, Xiaoju Dong, and Xiaoru Yuan. "Metro-Wordle: An Interactive Visualization for Urban Text Distributions Based on Wordle." Visual Informatics 2.1 (2018): 50-59.

[3] https://www.jasondavies.com/wordcloud/.

[4] http://www.wordle.net/.