图形连线路由算法

      最近打算将工作流引擎设计器使用html5技术进行重构，所以研究了一下html5中绘图技术，今天在这里主要是探讨一下图形之间连线处理算法，之前在网上找到了这篇博文：连线自动路由算法，感兴趣的大家可以参考一下（不过这个是基于GEF的），基于Javascript的尚未找到比较好的解决方案，因此决定自己动手(毕竟后面要实现整个设计器也必须得自己动手)。

       图形之间的连线路由算法大致有下面几种：1）拐点路由(Bendpoint Connection Router)；2）最短路路由(Shortest Path Connection Router)；3）曼哈顿路由(Manhattan Connection Router)。其中曼哈顿路由算法也就是我们常见的直角连线算法。对于前面的两种路由算法这里暂不讨论，下面主要针对曼哈顿路由算法进行说明。在进入讨论之前先来直观上感受一下最终实现的效果：

请先无视其它功能，因为这个仅仅是一个框架，仅仅测试了连线路由算法。

       在考虑如何实现曼哈顿路由算法时，自己想了几种方案最后又都被自己给否定了。最终选用了最笨的方法：穷举+连线优先模式，即先列举出可能的连线方式及存在的条件，然后当一些条件不是那么容易检测时采用直接判断是否可以使用某种连线。为了方便我们列举出连线方式我们给图形定义一下图形边界，最终产生的连线由可进行连接的两个边界决定。图形边界定义如下图所示：

N：North（北）  E：East（东）  S：South（南）  W：West（西）。

      我们先看一下以源图形E边可以连接类型：1：E--W ；2：E--S；3：E--N；4：E--E，4种，如下图所示：

源图形W边可以连接类型：5：W--E ；6：W--S；7：W--N，3种，如下图所示： 

 这里你可能会说还有W--W这种情况，其实这个基本上可以使用E--E来代替，所以可不考虑。如果说你追求更加完美的解决方案，比如考虑画布边界等，那么此时需要考虑W--W这种情况。

源图形N边可以连接类型：8：N--S ；9：N--W；10：N--E；11：N--N；12：N--W；13：N--E，6种，其中12、13分别是9、10的变种，即当两个图形相交时，如下图所示： 

 源图形S边可以连接类型：14：S--N ；15：S--W；16：S--E；17：S--W；18：S--E，5种，其中17、18分别是15、16的变种，即当两个图形相交时，如下图所示： 

所以整体来说会有18种可能的情况需要我们进行考虑。

在代码实现上分成两个步骤来计算曼哈顿路由的各拐点坐标：

1. 计算可进行连接的两个边界，返回值是两个边界的名称，如：["E", "W"]，及连接线从源图形的E边，连接到目标图形的W边；
2. 根据可进行连接的两个边界计算相应的连接点。