深入理解 D3.js 可視化庫之力導向圖原理與實現
大 廠 技 術 堅 持 周 更 精 選 好 文
簡介
D3.js [1] 是一個基於 web 標準的 JS 可視化庫,它藉助 SVG、Canvas 和 HTML 進行數據可視化。在數據可視化中,我們很多時候會使用圖來表達數據中所藴含的信息,圖方便讓我們清晰的理清各個節點之間的聯繫,快速提取有用信息。而圖佈局算法可以使散亂的信息 (信息多以點線的關係承載) 通過一種清晰的方式呈現出來,符合相應的美學標準。
不同的 圖佈局 [2] 也有不同的應用場景,例如樹形佈局 / Dagre佈局,它是一個有向無環圖,具有的拓撲性質,可以用作流程表達的場景。
同心圓佈局,圖分析的場景中通常是將節點先按照度數排序,度數最大的節點會排列在最中心的位置,越往外度數越小,整體成同心圓形式排列。
力導佈局,通過節點之間的互斥力,減少重疊,但是在有限的空間內避免所有節點不重疊目前還是無解的。我們今天講一下,簡單的力導佈局的實現。建立在物理理論基礎上,將節點模擬為原子,通過原子之間作用力的相互影響,最終達到平衡狀態,這就是 力導向圖 [3] 。
思路
整體可以拆解為 2 個實體和 1 個作用因子:節點、線、力。d3-force的實現與傳統的 FR 算法思路一樣,可以分成三個部分組成,先計算節點間的互斥力,再計算連接點的吸引力,得出最終的作用力,得到每個節點的速度。使用模擬退火的衰減方案,達到穩定。
http://jsfiddle.net/smallstars/h8y6e031/51/
d3-force原理
節點處理
初始化導入節點
將節點導入 d3 中,需要對節點進行預處理,按照一定的半徑和角度進行環繞。
// d3-force/simulation.js
var initialRadius = 10,
initialAngle = Math.PI * (3 - Math.sqrt(5));
function initializeNodes() {
for (var i = 0, n = nodes.length, node; i < n; ++i) {
node = nodes[i], node.index = i;
if (node.fx != null) node.x = node.fx;
if (node.fy != null) node.y = node.fy;
// 初始位置
if (isNaN(node.x) || isNaN(node.y)) {
var radius = initialRadius * Math.sqrt(0.5 + i), angle = i * initialAngle;
node.x = radius * Math.cos(angle);
node.y = radius * Math.sin(angle);
}
// vx, vy為 x, y 的速度
if (isNaN(node.vx) || isNaN(node.vy)) {
node.vx = node.vy = 0;
}
}
}
建立節點四叉樹
四叉樹(quad-tree)
這裏採取四叉樹的結構原因是方便做碰撞檢測, 四叉樹是從根節點開始,每一個節點下面最多有四個子樹的數據結構。通常我們把一部分二維空間細分為四象限,每一個節點存儲相應的象限信息。
遍歷導入所有節點數據,求出最小值,最大值,最小值,最大值,將與進行增幅,滿足,。2的倍數滿足四叉樹在一維上對半分的特徵。我們在添加節點的時候,總共會有下面 4 種情況:
-
四叉樹為空,節點添加為根節點。
-
當前查詢節點為索引節點且添加處範圍矩陣為空,直接添加。
-
當前查詢節點為真實節點且添加節點座標相等且無數組索引,建立數組索引,再次劃分該矩陣,直到查詢節點與添加節點處於不同矩陣。
-
當前查詢節點為真實節點且添加節點座標相等且有數組索引,直接下掛。
// d3-force/collide.js
for (var k = 0; k < iterations; ++k) {
// 調用 d3-quadtree 進行add
tree = quadtree(nodes, x, y).visitAfter(prepare);
for (i = 0; i < n; ++i) {
node = nodes[i];
ri = radii[node.index], ri2 = ri * ri;
xi = node.x + node.vx;
yi = node.y + node.vy;
tree.visit(apply);
}
}
// d3-quadtree/add.js
function add(tree, x, y, d) {
if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points
var parent,
node = tree._root,
leaf = {data: d},
// 象限座標
x0 = tree._x0,
y0 = tree._y0,
x1 = tree._x1,
y1 = tree._y1,
xm,
ym,
xp,
yp,
right,
bottom,
i,
j;
// case1: If the tree is empty, initialize the root as a leaf.
if (!node) return tree._root = leaf, tree;
// 類似二分,自上向下搜索
// Find the existing leaf for the new point, or add it.
while (node.length) {
if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
// case2: 判斷當前添加節點所在象限是否為空
if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree;
}
// case4: 添加節點是否與父節點重合
// Is the new point is exactly coincident with the existing point?
xp = +tree._x.call(null, node.data);
yp = +tree._y.call(null, node.data);
if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree;
// case3: 不停分割,直到處於不同象限
// Otherwise, split the leaf node until the old and new point are separated.
do {
parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4);
if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
} while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));
return parent[j] = node, parent[i] = leaf, tree;
}
斥力的優化求解
節點間的斥力優化關鍵為 電荷斥力 [4] 求解優化,最基本的一個節點所受的力,需要與其他所有節點進行計算求和,複雜度為。
整合受力
而四叉樹結構與 Barnes-Hut [5] 近似,複雜度可降為。當前節點所受周圍點的斥力進行整合處理,大小由 Barnes-Hut 近似精度(默認值為) 決定,最後根據 Velocity Verlet [6] 對速度進行求解。
象限面積,節點(node)與象限點(quad)形成的面積
// d3-force/manyBody.js
var distanceMin2 = 1,
distanceMax2 = Infinity,
theta2 = 0.81;
function apply(quad, x1, _, x2) {
if (!quad.value) return true;
var x = quad.x - node.x,
y = quad.y - node.y,
w = x2 - x1,
l = x * x + y * y;
// Barnes-Hut成立
// 如何點非常近,衝突的時候隨機方向
if (w * w / theta2 < l) {
if (l < distanceMax2) {
if (x === 0) x = jiggle(random), l += x * x;
if (y === 0) y = jiggle(random), l += y * y;
if (l < distanceMin2) l = Math.sqrt(distanceMin2 * l);
node.vx += x * quad.value * alpha / l;
node.vy += y * quad.value * alpha / l;
}
return true;
}
// Barnes-Hut不成立且 quad 有節點
else if (quad.length || l >= distanceMax2) return;
// 排除自身對自身影響,還可以繼續向下遍歷
if (quad.data !== node || quad.next) {
if (x === 0) x = jiggle(random), l += x * x;
if (y === 0) y = jiggle(random), l += y * y;
if (l < distanceMin2) l = Math.sqrt(distanceMin2 * l);
}
do if (quad.data !== node) {
w = strengths[quad.data.index] * alpha / l;
node.vx += x * w;
node.vy += y * w;
} while (quad = quad.next);
}
節點連線的處理
先初始化連線,計算節點的度和每一條邊對起始節點度(source/target degree)的佔比,使,alpha為阻尼係數,默認邊長度(distance)為30,默認彈簧勁度(strength)為,減少度大節點的引力,提高穩定性。計算連線兩邊的引力,最終推導出速度的變化。
同理可得出
// d3-force/link.js
function force(alpha) {
for (var k = 0, n = links.length; k < iterations; ++k) {
for (var i = 0, link, source, target, x, y, l, b; i < n; ++i) {
link = links[i], source = link.source, target = link.target;
x = target.x + target.vx - source.x - source.vx || jiggle(random);
y = target.y + target.vy - source.y - source.vy || jiggle(random);
l = Math.sqrt(x * x + y * y);
l = (l - distances[i]) / l * alpha * strengths[i];
x *= l, y *= l;
target.vx -= x * (b = bias[i]);
target.vy -= y * b;
source.vx += x * (b = 1 - b);
source.vy += y * b;
}
}
}
佈局的形成
通過不斷的迭代運算,每次運算都可以看做一步,通過模擬退火的衰減方案最後達到穩定狀態。
// d3-force/simulation.js
var simulation,
alpha = 1,
alphaMin = 0.001,
// alpha衰減率
alphaDecay = 1 - Math.pow(alphaMin, 1 / 300),
alphaTarget = 0,
// 速度衰減
velocityDecay = 0.6,
stepper = timer(step),
// tick事件與end事件
event = dispatch("tick", "end");
function step() {
tick();
event.call("tick", simulation);
if (alpha < alphaMin) {
stepper.stop();
event.call("end", simulation);
}
}
function tick() {
// alpha不斷衰減
alpha += (alphaTarget - alpha) * alphaDecay;
// 不停迭代
forces.each(function(force) {
force(alpha);
});
// 速度轉化為距離改變
for (i = 0; i < n; ++i) {
node = nodes[i];
if (node.fx == null) node.x += node.vx *= velocityDecay;
// 具有fx,説明當前節點被控制,不需要受到力的影響,速度置為0
else node.x = node.fx, node.vx = 0;
if (node.fy == null) node.y += node.vy *= velocityDecay;
else node.y = node.fy, node.vy = 0;
}
}
實戰示例
Demo:
React-d3js [7]
代碼:
http://github.com/SmaIIstars/react-demo/blob/master/src/pages/d3-force/index.tsx
遇見的問題
-
Svg 中繪製複雜內容
可以使用 foreignObject 節點進行繪製,在 foreignObject 中可以編寫 XML 命名空間的元素。
-
節點迭代次數過多,導致頁面卡頓
通常初次生成圖佈局的時候,需要一個過渡動畫,在模擬退火的過程中,節點、線會不斷的移動。監聽數據的變化,使用 React.memo 和 useCallback 減少不必要的運算。
-
節點間重疊,相互遮蓋
增大排斥力,增常線段長度,增加碰撞體積。但是在有限的空間內,仍然無法完全避免重疊的問題。
-
節點過多,超出畫布
使用設備的寬高作為畫布,對內容進行縮放和拖拽,讓用户可以查看到所有內容。
參考
-
GitHub - d3/d3-force: Force-directed graph layout using velocity Verlet integration. [8]
-
D3.js(Data-Driver Documents)力導向圖理論知識 [9]
參考資料
D3.js: http://github.com/d3/d3
圖佈局: http://segmentfault.com/a/1190000039054038
力導向圖: http://observablehq.com/@sandravizmad/force-directed-layout
電荷斥力: http://bytedance.feishu.cn/docs/doccnyBnKUxyMSdw74Tws6lavfd#8M5j10
Barnes-Hut: http://bytedance.feishu.cn/docs/doccnyBnKUxyMSdw74Tws6lavfd#yeVWli
Velocity Verlet: http://bytedance.feishu.cn/docs/doccnyBnKUxyMSdw74Tws6lavfd#lfo9UK
React-d3js: http://demo.smallstars.top/demo/d3-force
GitHub - d3/d3-force: Force-directed graph layout using velocity Verlet integration.: http://github.com/d3/d3-force
D3.js(Data-Driver Documents)力導向圖理論知識: http://bytedance.feishu.cn/docs/doccnyBnKUxyMSdw74Tws6lavfd#WmTLGZ
- END -
:heart: 謝謝支持
以上便是本次分享的全部內容,希望對你有所幫助^_^
喜歡的話別忘了 分享、點贊、收藏 三連哦~。
歡迎關注公眾號 ELab團隊 收貨大廠一手好文章~
字 節 跳 動 校 / 社 招 內 推 碼 : 13HAUHW
投 遞 鏈 接 : http://jobs.toutiao.com/s/LvNLPHX
- 使用 WebAssembly 打造定製 JS Runtime
- 前端也要懂算法,不會算法也能微調一個 NLP 預訓練模型
- 聯機遊戲原理入門即入土 -- 入門篇
- Plasmo Framework:次世代的瀏覽器插件開發框架
- 深入理解 Mocha 測試框架:從零實現一個 Mocha
- Single Source of Truth:XCode SwiftUI 的界面編輯的設計理念
- 深入理解 D3.js 可視化庫之力導向圖原理與實現
- 淺析神經網絡 Neural Networks
- Cutter - Web視頻剪輯工具原理淺析
- 你可能需要一個四捨五入的工具函數
- 淺析eslint原理
- 最小編譯器the-super-tiny-compiler
- Git存儲原理及部分實現
- 淺談短鏈的設計
- Web組件構建庫-Lit
- 使用Svelte開發Chrome Extension
- Web3.0開發入門
- vscode插件原理淺析與實戰
- 深入淺出 Web Audio API
- 探祕HTTPS