摘要：通過(guò)力導(dǎo)向算法計(jì)算位置，繪制出對(duì)應(yīng)的力導(dǎo)向圖，這樣的分配是最佳位置的分布圖。力導(dǎo)向算法是根據(jù)自然界中電子直接互相作用的原理來(lái)實(shí)現(xiàn)的，自然界中。

說(shuō)到力導(dǎo)向可能很多小伙伴都只是會(huì)使用，不知道其中的實(shí)現(xiàn)原理，今天，我們一起來(lái)自己實(shí)現(xiàn)一套力導(dǎo)向算法，然后做一些技術(shù)相關(guān)的延伸。發(fā)散下思維。

根據(jù)百科的介紹：力導(dǎo)向算法是指通過(guò)對(duì)每個(gè)節(jié)點(diǎn)的計(jì)算，算出引力和排斥力綜合的合力，再由此合力來(lái)移動(dòng)節(jié)點(diǎn)的位置。

通過(guò)力導(dǎo)向算法計(jì)算位置，繪制出對(duì)應(yīng)的力導(dǎo)向圖，這樣的分配是最佳位置的分布圖。echarts和d3js里面也有力導(dǎo)向布局圖。首先來(lái)看一下力導(dǎo)向圖。

力導(dǎo)向算法是根據(jù)自然界中電子直接互相作用的原理來(lái)實(shí)現(xiàn)的，自然界中。兩個(gè)電子靠的太近會(huì)產(chǎn)生斥力，隔的太遠(yuǎn)會(huì)產(chǎn)生引力，這樣保持一個(gè)平衡狀態(tài)，最終達(dá)到維持物體的形態(tài)的目的，這里就涉及到了一個(gè)庫(kù)侖定律（百科：是靜止點(diǎn)電荷相互作用力的規(guī)律。1785年法國(guó)科學(xué)家C,-A.de庫(kù)倫由實(shí)驗(yàn)得出，真空中兩個(gè)靜止的點(diǎn)電荷之間的相互作用力同它們的電荷量的乘積成正比，與它們的距離的二次方成反比，作用力的方向在它們的連線上，同名電荷相斥，異名電荷相吸），這里就涉及到一個(gè)庫(kù)倫公式。，如果假設(shè)電子q=1，那么 F=k/(r^2) * e（e為從q1到q2方向的矢徑；k為庫(kù)侖常數(shù)（靜電力常量））。那這里的F可以假設(shè)為某個(gè)方向的瞬間速度，e正好代表正負(fù)方向，有的力導(dǎo)向圖算法中加入了彈簧力，讓e有了緩動(dòng)效果，但是，這里我們就不加入彈簧力了，主要是研究這個(gè)庫(kù)倫公式公式，如果進(jìn)一步簡(jiǎn)化，我們可以把F看做成一次函數(shù)的變化，這樣盡可能的簡(jiǎn)化我們的代碼。復(fù)雜的問(wèn)題簡(jiǎn)單化，再慢慢深入。最終理解其原理。

如果要用代碼去實(shí)現(xiàn)簡(jiǎn)化后的力導(dǎo)向圖的布局，我們需要幾個(gè)步驟。

設(shè)置點(diǎn)數(shù)據(jù)nodes, 鏈接數(shù)據(jù)links。

對(duì)點(diǎn)進(jìn)行隨機(jī)定位。

渲染視圖

執(zhí)行力算法計(jì)算位置，渲染視圖

重復(fù)執(zhí)行4操作N次，得到想要的力導(dǎo)向圖形。在執(zhí)行力算法的時(shí)候，這里我們把庫(kù)倫公式簡(jiǎn)化成了一次函數(shù)，所以，要么減一個(gè)數(shù)，要么加一個(gè)數(shù)去改變點(diǎn)的坐標(biāo)。理解起來(lái)就很容易了，當(dāng)然，實(shí)際上我們應(yīng)該加上電子作用力（庫(kù)倫公式）和彈簧力（胡克定律），讓力導(dǎo)向的效果更接近自然界的作用結(jié)果。

原理圖：

設(shè)置數(shù)據(jù)

/**
   * @desc 模擬數(shù)據(jù)
  */
  function getData(num, exLink) {
    const data = { nodes: new Array(num).fill(1), links: [] };
    data.nodes = data.nodes.map((d, id) => {
      return {
        id,
        name: d,
        position: [0, 0],
        childs: []
      }
    });

    data.nodes.forEach((d, i) => {
      // 都和0相連
      if (d.id !== 0) {
        data.links.push({
          source: 0,
          target: d.id,
          sourceNode: data.nodes[0],
          targetNode: d
        });
      }
    });

    // 隨機(jī)抽取其中2個(gè)相連
    const randomLink = () => {
      data.nodes.sort(() => 0.5 - Math.random());
      data.links.push({
        source: data.nodes[0].id,
        target: data.nodes[1].id,
        sourceNode: data.nodes[0],
        targetNode: data.nodes[1]
      });
    }

    for (let i = 0; i < exLink; i++) {
      randomLink();
    };

    // 添加數(shù)據(jù)。childs
    const obj = {};
    data.nodes.forEach(d => {
      if (!obj[d.id]) {
        obj[d.id] = d;
      }
    });
    data.links.forEach(d => {
      obj[d.source].childs.push(d.targetNode);
      obj[d.target].childs.push(d.sourceNode);
    });

    return data;
  }

隨機(jī)定位

/**
   * @desc 獲取隨機(jī)數(shù)
  */
  function getRandom(min, max) {
    return Math.floor(min + Math.random() * (max - min));
  }

/**
   * @desc 打亂順序定位
   * @param data 數(shù)據(jù)
   * @param size 畫布大小
  */
  function randomPosition(data, size) {
    const { nodes, links } = data;
    nodes.forEach(d => {
      let x = getRandom(0, size);
      let y = getRandom(0, size);
      d.position = [x, y];
    });
  }

渲染視圖

/**
   * @desc 繪制
   * @param ctx canvas上下文
   * @param data 數(shù)據(jù)
   * @param size 畫布大小
  */
  function render(ctx, data, size) {
    ctx.clearRect(0, 0, size, size); //清空所有的內(nèi)容
    const box = 20;
    ctx.fillStyle = "#FF0000";
    data.links.forEach(d => {
      let { sourceNode, targetNode } = d;
      let [x1, y1] = sourceNode.position;
      let [x2, y2] = targetNode.position;
      ctx.beginPath(); //新建一條path
      ctx.moveTo(x1, y1); //把畫筆移動(dòng)到指定的坐標(biāo)
      ctx.lineTo(x2, y2);  //繪制一條從當(dāng)前位置到指定坐標(biāo)(200, 50)的直線.
      ctx.closePath();
      ctx.stroke(); //繪制路徑。
    });
    data.nodes.forEach(d => {
      let [x, y] = d.position;
      ctx.fillText(d.id, x, y + box);
      ctx.fillRect(x - box / 2, y - box / 2, box, box);
    });
  }

模擬作用力計(jì)算位置

/**
   * @desc 力算法
  */
  function force(data, ctx, size) {
    const { nodes, links } = data;

    // 需要參數(shù)
    const maxInterval = 300; // 平衡位置間距
    const maxOffset = 10; // 最大變化位移
    const minOffset = 0; // 最小變化位移
    const count = 100; // force次數(shù)
    const attenuation = 40; // 力衰減
    const doforce = () => {
      // 計(jì)算開(kāi)始
      nodes.forEach(d => {
        let [x1, y1] = d.position;
        nodes.forEach(e => {
          if (d.id === e.id) {
            return;
          }
          let [x2, y2] = e.position;
          // 計(jì)算兩點(diǎn)距離
          let interval = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
          // console.log("interval", d.id + "-" + e.id, interval);
          // 力衰減變量
          let forceOffset = 0;
          let x3, y3;
          // 如果大于平橫間距，靠攏，如果小于平衡間距，排斥。這里計(jì)算第三點(diǎn)的坐標(biāo)用到了相似三角形原理
          if (interval > maxInterval) {
            forceOffset = (interval - maxInterval) / attenuation; // 力衰減
            forceOffset = forceOffset > maxOffset ? maxOffset : forceOffset;
            forceOffset = forceOffset < minOffset ? minOffset : forceOffset;
            forceOffset += e.childs.length / attenuation;
            // console.log("如果大于平橫間距，靠攏", interval, d.id + "-" + e.id, ~~forceOffset);
            let k = forceOffset / interval;
            x3 = k * (x1 - x2) + x2;
            y3 = k * (y1 - y2) + y2;
          } else if (interval < maxInterval && interval > 0) { // 如果小于平橫間距，分開(kāi)
            forceOffset = (maxInterval - interval) / attenuation; // 力衰減
            forceOffset = forceOffset > maxOffset ? maxOffset : forceOffset;
            forceOffset = forceOffset < minOffset ? minOffset : forceOffset;
            forceOffset += e.childs.length / attenuation;
            // console.log("如果小于平橫間距，分開(kāi)", interval, d.id + "-" + e.id, ~~forceOffset);
            let k = forceOffset / (interval + forceOffset);
            x3 = (k * x1 - x2) / (k - 1);
            y3 = (k * y1 - y2) / (k - 1);
          } else {
            x3 = x2;
            y3 = y2;
          }

          // 邊界設(shè)置
          x3 > size ? x3 -= 10 : null;
          x3 < 0 ? x3 += 10 : null;
          y3 > size ? y3 -= 10 : null;
          y3 < 0 ? y3 += 10 : null;
          e.position = [x3, y3];
        });
      })
    }

    let countForce = 0;
    const forceRun = () => {
      setTimeout(() => {
        countForce++;
        if (countForce > count) {
          return;
        }
        doforce();
        render(ctx, data, size);
        forceRun();
      }, 1000 / 30)
      // requestAnimationFrame(forceRun);
    }

    forceRun();

  }

main 函數(shù)

  /*
  
    您的瀏覽器不支持
  
   */
  const size = 800;
  // 1.獲取數(shù)據(jù)
  const data = getData(30, 0);
  // 2.隨機(jī)定位
  randomPosition(data, size);
  // 3.渲染
  let cav = document.getElementById("forceMap");
  let ctx = cav.getContext("2d");
  render(ctx, data, size);
  // 4.執(zhí)行力算法
  force(data, ctx, size);

最終生成的效果：

這里，我們?cè)O(shè)置了最大的位移maxOffset，以及最小的位移minOffset。如果沒(méi)有達(dá)到平衡點(diǎn)（兩點(diǎn)之間距離為maxInterval）的時(shí)候，會(huì)互相靠近或者遠(yuǎn)離，距離變化我們來(lái)的比較暴力，當(dāng)然，實(shí)際上我們應(yīng)該加上電子作用力（庫(kù)倫公式）和彈簧力（胡克定律），讓力導(dǎo)向的效果更接近自然界的作用結(jié)果。

知識(shí)延伸一下：這里我們是對(duì)nodes兩兩比較。如果我們只對(duì)兩個(gè)鏈接點(diǎn)進(jìn)行兩兩比較，又會(huì)是這樣的結(jié)果呢，改動(dòng)如下？

得到圖形：

這個(gè)代碼只是為了讓大家入門學(xué)習(xí)使用，真正的力導(dǎo)向算法比這個(gè)復(fù)雜的多，還可以做很多優(yōu)化，比如最新版本的d3js里面的力導(dǎo)向算法就用四叉樹(shù)算法對(duì)其進(jìn)行了優(yōu)化，拋磚引玉到此為止，歡迎大家指正！