我正在写一个软件,我需要用拓扑数据(边,顶点及其连接数据的矢量)以正交的方式表示图。

图由一组顶点和一组边组成,每个顶点连接两个顶点。一个顶点可能具有任意数量的连接边,因此使问题变得更加复杂。

我已经阅读了一些文章,看起来像Kandinsky模型是受欢迎的帖子一。但是我只是不知道算法,解决问题的任何其他解决方案(算法)也非常受欢迎。


edit之后添加

以下图片显示了一个实际的电气网络示例,该示例应视为原始数据,为了从该网络创建图形,必须完成一些初步任务。

输入数据:



我正在寻找的结果如下所示,
如果您选择仔细观察一下:

上图(输入数据)中间的红色多边形表示一个变电站,该变电站本身是一个节点,可以连接到四个以上的边缘。
红色多边形更多,但是上面的图片只能容纳一个,但是,如您所见,下一个图片的覆盖范围可能比红色多边形要大得多,这意味着它可以映射更大的区域,因此下面的图片更加密集。

在示意图中,红色多边形(变电站)通常彼此相对保持相对的位置,因此,如果我们设法缩小地图以查看上述地图的范围之外,我们几乎应该看到一个三角形这显然可以在下面看到,而左边一个在左边,向下一个在下面.....(这不是规则,但是我认为可能是所需算法的先行一步)




评论

在这种情况下,正交是否意味着仅使用垂直和水平边缘?您是否正在寻找一种方法来表示在单个顶点上相交的4个以上的边?

确实,@ trichoplax,我非常感谢您的帮助。

该图是否保证是平面的,以便在暂时忘掉正交边的情况下可以绘制没有重叠边的图?

通用的图形布局算法很烦人的编程和实现。即使只是从文学中找到合适的人也是痛苦的。您应该多描述一些您所期望的东西,画一幅画。

顶点已经在2D中(或在球面上)具有给定的位置,所以这更多是边缘布线问题?平凡的解决方案是先沿x沿每个边,然后沿y轴(或以另一种方式“倒圆”)布线。如果这是正确的话,那么解释这个简单的解决方案可能会有所帮助。我通过为问题分配惩罚来想象一个最小化的问题...

#1 楼

libCola

cola.js(又名WebCola)是libcola的基于JavaScript的重写,可与D3.js很好地配合使用。

http://marvl.infotech.monash.edu/ webcola /

栅格化的布局示例:

http://marvl.infotech.monash.edu/webcola/examples/dotpowergraph.html

OGDF

Open Graph绘图框架

具有正交布局


正交:具有用于形状和形状步骤的模块的正交布局
压缩,ClusterOrthoLayout


http://www.ogdf.net/doku.php/ogdf:features

检查使用OGDF的项目

http://www.ogdf.net/doku.php/project:external

HOLA

类人正交布局算法

https://vimeo.com/150509722

基弗,史蒂夫,蒂姆·德怀尔,金·万豪和迈克尔·怀伯罗。 “ Hola:类似人的正交网络布局。”可视化和计算机图形学,IEEE Transactions on 22,no。 1(2016):349-358。

评论


$ \ begingroup $
这听起来很有希望。您可以编辑以添加一些细节吗?
$ \ endgroup $
– trichoplax
16年7月4日在12:24

$ \ begingroup $
概述每种算法的工作方式也很有用,这样就可以比较它们而无需离开答案。
$ \ endgroup $
– trichoplax
16年7月5日在1:21