理解指南针的布局算法

Question

我想要可视化一个表示一些地理地图的图形。因此，我的图的边与指南针相关(北、南、东、西)。图本身是有向的，并且可以使其成为无环的。

例如，我有节点: House-1，House-2，House-3 with edges House-1，north-of，House-2，House-2，east-of，House-3。

我正在寻找一种可以理解指南针的布局算法(也许可以作为提示？)

我经历了JUNG，JGraph，GraphViz，似乎没有一个能做到我想要的，但我可能遗漏了一些东西。

有什么建议吗？

Answer 1

最近有一篇论文讨论了这个问题，其中他们试图重建旧的韩国土地记录(地籍)。论文中有一个布局算法，它应该可以做你想做的事情。它没有提供所有的细节，但它确实给出了大纲和对细节的引用。

李贤敏，李秀云，金南宇，徐振宇。2012年。JigsawMap:通过映射历史文本cadasters将过去与未来联系起来。在2012年ACM年度计算系统中人的因素会议论文集(CHI '12)。ACM，纽约，纽约，美国，463-472。DOI=10.1145/2207676.2207740。

​

​

Answer 2

@edallme :不错的文档，很有趣！

@道文：

我在你的帖子中所理解的是，你正在寻找一种算法来将所有的区块放在地图上，而不是一个“小部件”来做到这一点(所以可能我错了?)

如果您正在询问如何计算如何放置这些块的想法(知道“图形本身是有向的，并且可以使其成为非循环的”)，那么无论您使用的是什么图形库，下面的方法都应该有效：

您可以尝试先生成依赖图，例如每个节点都受其他节点的约束(相对位置和偏移量，例如SOUTH/30个单位)。这一堆代码也应该检查不一致性。

其次，计算每个块的相对位置，将最小值和最大值存储在某个位置(参见第3部分)，以及对具有最小/最大位置的对象的引用。

第三，您应该能够虚拟地生成具有最小/最大相对位置的全尺寸图尺寸。

然后，你“只要”从一个角落画出来。