javascript - 以无重叠方式渲染节点网格的算法方法

Question

我有几个节点(例如应用程序名称)和几个带标签的边(例如信息流/系统接口(interface)及其信息对象)。我希望能够编写一个 javascript 脚本，以无重叠的方式绘制节点网格(例如信息流图)，这意味着:

• 边的标签不被节点和/或彼此重叠
• 节点不被边缘线和/或边缘标签和/或彼此重叠

节点的放置方式也需要尽可能多的边缘线是可见的并且不会相互混淆 - 所以需要进行某种优化。 一个要求是任何节点都可能连接到任何其他节点。

为了做到这一点，我正在寻找一个关于如何做到这一点的粗略想法(高级伪代码)或者一个现成的 javascript 实现。

我对以下内容不感兴趣，因为我知道它是如何工作的:

• 放置/移动div
• 绘制svg线条
• 任何类型的数据转换工作方式或数据 Assets 必须如何进行的培训(向量、矩阵、稀疏矩阵...)

我从这样的事情开始:

1. 将只有一条边的节点放到 Canvas 的外层空间
2. 将连接到它们的节点靠近它们

这样我就可以轻松地在 Canvas 上展开一棵树。最初的想法是从那里进行一些排序和分组。但是，我很难从网格结构中将子树分组，并且不知何故陷入其中。

我也在想碰撞检测可能对我有帮助。但是，我没有说到这如何帮助我放置节点，以便边缘在可见性方面是最佳的。

为了使它更加明显，这里是输入数据结构的样子:

var nodeseq=[  // id,name
{id:'i1',name:'app1'},
{id:'i2',name:'app2'};
...
];

var edgeseq=[  // id,sourcenodeid,targetnodeid,label
{id:'i1',sourcenodeid:'i33',targetnodeid:'i25',label:'Invoice'},
{id:'i2',sourcenodeid:'i3',targetnodeid:'i5',label:'Advise'},
...
];

Answer 1

or alternatively a ready-to-go javascript implementation

Springy.js可能适合您的需求...自从我上次使用它以来已经有一段时间了，但它有一个非常简单的 API，因此值得一试。一个例子:

var nodeseq = [  // id,name
  {id:'i1',name:'app1'},
  {id:'i2',name:'app2'},
  {id:'i3',name:'app3'},
  {id:'i4',name:'app4'},
];

var edgeseq = [  // id,sourcenodeid,targetnodeid,label
  {id:'i1',sourcenodeid:'i1',targetnodeid:'i2',label:'Invoice'},
  {id:'i2',sourcenodeid:'i1',targetnodeid:'i3',label:'Advise'},
  {id:'i3',sourcenodeid:'i3',targetnodeid:'i3',label:'Test'},
  {id:'i4',sourcenodeid:'i3',targetnodeid:'i4',label:'Test'},
  {id:'i5',sourcenodeid:'i2',targetnodeid:'i3',label:'Test'},
];

var graph = new Springy.Graph();
var createNode = node => graph.newNode({label: node.name });

var nodeMap = makeMap("id", nodeseq, createNode);

// connect them with an edge
edgeseq.forEach(edge => graph.newEdge(
  nodeMap[edge.sourcenodeid],
  nodeMap[edge.targetnodeid],
  { label: edge.label }
));

$('canvas').springy({ graph: graph });

// Utils
function makeMap(prop, arr, t) {
  t = t || (v => v);
  return arr
    .reduce((map, item) => Object.assign(map, { 
      [item[prop]] : t(item) 
      }), {}); 
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/springy/2.7.1/springyui.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/springy/2.7.1/springy.min.js"></script>
<canvas width="400" height="200" />