力导向算法从入门到放弃！

摘要：通过力导向算法计算位置，绘制出对应的力导向图，这样的分配是最佳位置的分布图。力导向算法是根据自然界中电子直接互相作用的原理来实现的，自然界中。

说到力导向可能很多小伙伴都只是会使用，不知道其中的实现原理，今天，我们一起来自己实现一套力导向算法，然后做一些技术相关的延伸。发散下思维。

根据百科的介绍：力导向算法是指通过对每个节点的计算，算出引力和排斥力综合的合力，再由此合力来移动节点的位置。

通过力导向算法计算位置，绘制出对应的力导向图，这样的分配是最佳位置的分布图。echarts和d3js里面也有力导向布局图。首先来看一下力导向图。

力导向算法是根据自然界中电子直接互相作用的原理来实现的，自然界中。两个电子靠的太近会产生斥力，隔的太远会产生引力，这样保持一个平衡状态，最终达到维持物体的形态的目的，这里就涉及到了一个库仑定律（百科：是静止点电荷相互作用力的规律。1785年法国科学家C,-A.de库伦由实验得出，真空中两个静止的点电荷之间的相互作用力同它们的电荷量的乘积成正比，与它们的距离的二次方成反比，作用力的方向在它们的连线上，同名电荷相斥，异名电荷相吸），这里就涉及到一个库伦公式。，如果假设电子q=1，那么 F=k/(r^2) * e（e为从q1到q2方向的矢径；k为库仑常数（静电力常量））。那这里的F可以假设为某个方向的瞬间速度，e正好代表正负方向，有的力导向图算法中加入了弹簧力，让e有了缓动效果，但是，这里我们就不加入弹簧力了，主要是研究这个库伦公式公式，如果进一步简化，我们可以把F看做成一次函数的变化，这样尽可能的简化我们的代码。复杂的问题简单化，再慢慢深入。最终理解其原理。

如果要用代码去实现简化后的力导向图的布局，我们需要几个步骤。

设置点数据nodes, 链接数据links。

对点进行随机定位。

渲染视图

执行力算法计算位置，渲染视图

重复执行4操作N次，得到想要的力导向图形。在执行力算法的时候，这里我们把库伦公式简化成了一次函数，所以，要么减一个数，要么加一个数去改变点的坐标。理解起来就很容易了，当然，实际上我们应该加上电子作用力（库伦公式）和弹簧力（胡克定律），让力导向的效果更接近自然界的作用结果。

原理图：

设置数据

/**
   * @desc 模拟数据
  */
  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
        });
      }
    });

    // 随机抽取其中2个相连
    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();
    };

    // 添加数据。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;
  }

随机定位

/**
   * @desc 获取随机数
  */
  function getRandom(min, max) {
    return Math.floor(min + Math.random() * (max - min));
  }

/**
   * @desc 打乱顺序定位
   * @param data 数据
   * @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 数据
   * @param size 画布大小
  */
  function render(ctx, data, size) {
    ctx.clearRect(0, 0, size, size); //清空所有的内容
    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); //把画笔移动到指定的坐标
      ctx.lineTo(x2, y2);  //绘制一条从当前位置到指定坐标(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);
    });
  }

模拟作用力计算位置

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

    // 需要参数
    const maxInterval = 300; // 平衡位置间距
    const maxOffset = 10; // 最大变化位移
    const minOffset = 0; // 最小变化位移
    const count = 100; // force次数
    const attenuation = 40; // 力衰减
    const doforce = () => {
      // 计算开始
      nodes.forEach(d => {
        let [x1, y1] = d.position;
        nodes.forEach(e => {
          if (d.id === e.id) {
            return;
          }
          let [x2, y2] = e.position;
          // 计算两点距离
          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;
          // 如果大于平横间距，靠拢，如果小于平衡间距，排斥。这里计算第三点的坐标用到了相似三角形原理
          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) { // 如果小于平横间距，分开
            forceOffset = (maxInterval - interval) / 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 + forceOffset);
            x3 = (k * x1 - x2) / (k - 1);
            y3 = (k * y1 - y2) / (k - 1);
          } else {
            x3 = x2;
            y3 = y2;
          }

          // 边界设置
          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 函数

  /*
  
    您的浏览器不支持
  
   */
  const size = 800;
  // 1.获取数据
  const data = getData(30, 0);
  // 2.随机定位
  randomPosition(data, size);
  // 3.渲染
  let cav = document.getElementById("forceMap");
  let ctx = cav.getContext("2d");
  render(ctx, data, size);
  // 4.执行力算法
  force(data, ctx, size);

最终生成的效果：

这里，我们设置了最大的位移maxOffset，以及最小的位移minOffset。如果没有达到平衡点（两点之间距离为maxInterval）的时候，会互相靠近或者远离，距离变化我们来的比较暴力，当然，实际上我们应该加上电子作用力（库伦公式）和弹簧力（胡克定律），让力导向的效果更接近自然界的作用结果。

知识延伸一下：这里我们是对nodes两两比较。如果我们只对两个链接点进行两两比较，又会是这样的结果呢，改动如下？

得到图形：

这个代码只是为了让大家入门学习使用，真正的力导向算法比这个复杂的多，还可以做很多优化，比如最新版本的d3js里面的力导向算法就用四叉树算法对其进行了优化，抛砖引玉到此为止，欢迎大家指正！