流程图连线正交路由算法设计
实现效果
平时看到流程图设计工具里的元素间的连线，能够实现自动避障和布线。最近参考了网上的一篇文章[1]，参考里面的思路自己实现了一遍，还是挺好玩的。
算法设计
方案的思路其实很简单，首先基于待寻路元素的上中下，左中右六个方向分别绘制一条延长线
将12条延长线的交点记录下来，计算最小包围盒，区域往外拓展一个阈值距离，作为寻路空间（灰色区域）
寻路空间被划分成若干个区域，蓝色为最小包围盒内的区域，粉红色为拓展区域，橙色为边角区域
对于三种不同类型的划分，分别添加可选路径点（去重）：
- 蓝色区域：4个角点 + 4个边缘中点 + 中心点
- 橙色区域：4个角点
- 粉色区域：4个边缘中点
将路径点连起来，就可以得到一个寻路的网格图，后面的寻路算法就是基于这个网格图上的点进行路径的查找
最短路径采用Dijkstra 算法，路径点的权重由两个方面决定：
- 到目标点的距离
- 方向变换的惩罚
参考文献
[1] https://medium.com/swlh/routing-orthogonal-diagram-connectors-in-javascript-191dc2c5ff70
