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

Question

我有几个节点（例如应用程序名称）和几个带标签的边（例如信息 flows/system 与其信息对象的接口）。我希望能够编写一个 javascript-script 以无重叠的方式绘制节点网格（例如信息流图），这意味着：

边的标签没有被节点and/or彼此重叠
节点没有被边缘线重叠and/or 边缘标签and/or 彼此

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

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

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

placing/moving 分区
绘制 svg 线
任何类型的数据转换工作方式或数据资产的培训（向量、矩阵、稀疏矩阵...）

我从类似的东西开始：

将只有一条边的节点放在 canvas
将连接到它们的节点靠近它们

这样我就可以在我的 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" />

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

algorithm approach to render a node mesh in an overlap free way

javascript

algorithm

mesh