图的可视化

Question

波波老师您好。我在自己用H5的canvas编写tree和graph的可视化，用一个个圆形表示每一个节点。tree比较好办，我是递归的计算出每个节点圆心的x, y值。但在画graph的各个节点时，我没有想到一个好的方法，根据什么规则把N个节点画到canvas上。波波老师有什么建议吗？有没有某一个算法能够比较优雅的画出N个节点？

Answer 1

liuyubobobo 2018-01-09 14:40:58

对于一个已知图将其“平面化”，是一个经典且复杂的问题。如果希望了解更多，可以搜索学习Planar Graph的相关理论。

我的建议是：如果是随机生成图，不要先生成图再平面化，而是直接在二维平面上随机生成节点的二维坐标，每一个节点只和离其最近的k个节点随机生成边。（k为超参数，可以自己指定，也可以在生成的时候判定边之间不相交即可。判定平面上线的相交，又是一个经典的计算几何的问题。）

如果图的规模比较小，手动指定图的每个节点在二维平面上的坐标和相应的边，也是一种选择。

• 提问者 JamesChi #1

  感谢老师指点迷津