深入理解 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 種情況：

1. 四叉樹為空，節點添加為根節點。

2. 當前查詢節點為索引節點且添加處範圍矩陣為空，直接添加。

3. 當前查詢節點為真實節點且添加節點座標相等且無數組索引，建立數組索引，再次劃分該矩陣，直到查詢節點與添加節點處於不同矩陣。

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

遇見的問題

1. Svg 中繪製複雜內容

可以使用 foreignObject 節點進行繪製，在 foreignObject 中可以編寫 XML 命名空間的元素。

2. 節點迭代次數過多，導致頁面卡頓

通常初次生成圖佈局的時候，需要一個過渡動畫，在模擬退火的過程中，節點、線會不斷的移動。監聽數據的變化，使用 React.memo 和 useCallback 減少不必要的運算。

3. 節點間重疊，相互遮蓋

增大排斥力，增常線段長度，增加碰撞體積。但是在有限的空間內，仍然無法完全避免重疊的問題。

4. 節點過多，超出畫布

使用設備的寬高作為畫布，對內容進行縮放和拖拽，讓用户可以查看到所有內容。

參考

1. GitHub - d3/d3-force: Force-directed graph layout using velocity Verlet integration. ^[8]

2. D3.js(Data-Driver Documents)力導向圖理論知識 ^[9]

參考資料

- END -