最近业余在做一个基于结点的编辑工具玩, 遇到一个问题, 就是结点和连线多了, 经常会出现重叠交叉的问题, 导致图看不清楚:
要是这个样子, 还不如不用图清楚呢, 所心就需要找一个方法来进行自动布局, 理想情况是这样的...自动的算法肯定没有100%完美的, 但是总是能方便不少的
在google了一会儿后, 发现这种结点-线组成的图是一有个学名的: directed acyclic graph, 例如这样:
无非我这个图结点上的连接点是有限制的..., 但这个对于布局算法来说, 影响不大....因为布局只需要大体考虑每个结点的位置
那么, 这个算法需要满足几个条件:
结点之间不能有重叠
连线之间尽量减少交差
结点之间是有基本的层次关系对齐的
基于这些限制条件, google到一个比较有名的算法...Sugiyama's layout algorithm
初步看了一上, 这个算法比较复杂, 是多种算法的集合
自己不是很熟悉这方面的理论知识, 所以还是决定采用第三的算法库
C++可以使用的图绘制算法库