连线⾃动路由算法：在GEF中实现连线的⾃动直⾓路由，智能避障并绕开模型，选择最佳路径进⾏布。。。
在使⽤GEF（图形编辑框架）开发建模⼯具时，⽐如利⽤GEF实现程序流程图建模功能，有时对连线的路由⽅式会有⽐较⾼的要求，⽐如连线⾃动采⽤直⾓布局，要能够智能地避障并绕开模型，选择最佳路径进⾏布线。在建模类⼯具中，Microsoft Visio基本流程图中的连线的智能效果做的是同类⼯具中最好的，起码作者感觉如此。这篇博客就介绍如何在GEF中为连线实现类似Visio中的智能效果。当然，本⽂以GEF为背景和实例进⾏介绍，⽂中的路由算法和思想同样可以应⽤于其他有类似需求的应⽤，在此不做赘述。
⾸先对GEF框架提供的连线路由进⾏简单介绍。除了最基本的两点之间的直线布局以外，GEF提供的连线路由主要有3种：
1. 拐点路由(BendpointConnectionRouter)
2. 最短路路由(ShortestPathConnectionRouter)
3. 曼哈顿路由（ManhattanConnectionRouter）
以上3种路由⽅式均不能满⾜本⽂第⼀段提出的⼀些连线路由的要求。要实现仿Visio连线的效果，我们
需要⾸先对Visio中连线的路由的特点进⾏总结，其特点包括：
1. ⼀旦⽤户对某条连线的路由⽅式进⾏了调整，就不再为其提供智能路由布线的功能。
虽然Visio连线的路由已经做的⾜够智能，但依旧不可能满⾜⽤户的所有的布线要求，故Visio中的连线依旧提供着⽤户对连线的路由进⾏调整的功能。当⽤户对⼀条连线的路由进⾏调整后，⼯具将不再为该连线提供路由⽀持，⽽是采⽤⽤户调整以后的路由⽅式来布线，即便发⽣了连线与模型的布局冲突依旧如此。
2. ⽤户是否对连线的路径进⾏了调整的信息是需要持久存储的。
对⼀幅图中的每⼀条连线，⽤户对哪些进⾏了路由调整需要进⾏记录，当这幅图关闭下次重新打开时，需要知道应该为哪些连线提供路由⽀持，不为哪些连线提供路由⽀持。
3. ⽤户在建模时，只有当发⽣了连线和模型的布局冲突时，才对存在布局冲突的连线进⾏路由调整，对其他连线不做更改。
本⽂的连线路由算法以GEF提供的拐点路由(BendpointConnectionRouter)为基础，对拐点路由做进⼀步改进，以实现智能路由的效果。以拐点路由(BendpointConnectionRouter)为基础的好处是，可以很好的利⽤该路由⽀持⽤户对连线路径进⾏调整的功能。⾸先，我们来了解⼀下拐点路由(BendpointCo
nnectionRouter)连线的⼀些基本知识。
采⽤拐点路由的连线上保存着⼀个⼀个的拐点（BendpointModel），BendpointModel是Bendpoint的⼦类，只有2个属性d1和d2，类型均为Dimension。d1保存拐点相对于连线起点的偏移量，d2保存拐点相对于连线终点的偏移量。d1的类型为Dimension，width对应x 坐标偏移，height对应y坐标偏移，d2与之相同。（⼀点题外话，当连线的起点、终点和拐点相对于起点的偏移量d1已知时，拐点相对于连线终点的偏移量d2时唯⼀确定的，本⼈认为BendpiointModel中同时记录着d1和d2有些冗余）这⾥还需要说明⼀点，本⽂要实现路由算法的连线不是GEF默认提供的连线，⽽是对默认连线改造后两端能够悬空存在的连线，。
1. 实现连线和模型布局的冲突检测。
什么样的布局可以被认为是冲突的呢？当连线发⽣紧贴模型，或连线横穿模型时，就可以认为连线和模型的布局发⽣了布局冲突，见下图，此时就需要对连线的路由⽅式进⾏调整。需要说明⼀点，布局冲突检测只负责检测直⾓连线（如果⼀条连线被拐点分割开的所有的线段均处于⽔平或垂直⽅向，没有斜线，我们称这样的连线为直⾓连线）的布局冲突，后⾯会解释为什么只要进⾏这种检测就已经⾜够了。
算法1：连线与箭头箭尾模型布局冲突检测算法：
* 检测连线是否与箭尾和箭头模型存在布局上的冲突。即判断⼀条连线是否发⽣了横穿或紧贴模型的情况。
*
* @param flowChartConnecter
* @return 如果存在连线横穿模型的情况，则返回true；否则，返回fal。
*/
public static boolean hitTestWithTailAndHeadModel(
FlowChartConnecterModel flowChartConnecter) {
if (flowChartConnecter == null)
return fal;
FlowChartModel tailModel = TailModel();
FlowChartModel headModel = HeadModel();
// 箭尾模型处是否发⽣了冲突
boolean tailConflict = fal;
// 箭头模型处是否发⽣了冲突
boolean headConflict = fal;
// 判断箭尾模型是否与连线发⽣了冲突
if (tailModel != null) {
ConnecterAnchorModel tailAnchor = Tail();
int tailAnchorPosition = getConnectedPosition(tailAnchor);
int tailConnecterDirection = getConnecterDirectionInDetail(tailAnchor);
if (tailAnchorPosition != tailConnecterDirection) {
tailConflict = true;
}
}
// 判断箭头模型是否与连线发⽣了冲突
if (headModel != null) {
ConnecterAnchorModel headAnchor = Head();
int headAnchorPosition = getConnectedPosition(headAnchor);
int headConnecterDirection = getConnecterDirectionInDetail(headAnchor);
if (headAnchorPosition != headConnecterDirection) {
headConflict = true;
}
}
if (tailConflict || headConflict) {
return true;
}
return fal;
}
对该算法的解释：当箭头或箭尾处发⽣了连线和模型的布局冲突时，就认为存在布局冲突。下⾯以箭尾处为例来介绍如何判断。对于⼀个矩形模型⽽⾔，它允许连线的地⽅有4个，即上下左右边的中点，这⾥我们以东西南北来称呼这4个位置。同样箭尾处连线的⽅向也可以⽤东西南北来标识。如下图：
当连线的⽅向和它与模型的连接位置相同时，则认为不存在布局冲突；否则，认为存在冲突。算法中，getConnectedPosition（）获取连线锚点与模型的连接位置，返回值为东、西、南或北（东西南北为定义的整形常量）；getConnecterDirectionInDetail（）获取箭头或箭尾处连线的⽅向，返回值为东、西、南或北。
算法2： 连线与横穿模型的情况的布局冲突检测算法
* 检查某条连线是否与某个矩形发⽣了布局冲突
*
* @param connecter
* @param rectangle
* @return
*/
private static boolean hitTestWithSingleRectangle(
FlowChartConnecterModel connecter, Rectangle rectangle) {
if (connecter == null || rectangle == null) {
return fal;
}
ArrayList<Segment> gmentList = getSegmentList(connecter);
ArrayList<Rectangle> rectangleList = new ArrayList<Rectangle>();
rectangleList.add(rectangle);
for (Segment gment : gmentList) {
Object result = gmentHitTest(rectangleList, gment, true);
if (result != null) {// 如果发⽣冲突
// 就没有必要再对剩下的线段进⾏测试了
return true;
}
}
return fal;
}
该算法⽤于检测⼀条连线是否和⼀个矩形发⽣了布局冲突。实现思路为获取连线上线段的集合，然后对线段集合进⾏遍历，判断每⼀个线段是否与给定矩形发⽣布局冲突。只要存在任何⼀个线段与矩形发⽣了布局冲突，则认为连线与矩形见存在布局冲突。类Segment表⽰⼀个线段，其中保存了线段的起点和终点，类的定义如下：
算法2中gmentHitTest（）的作⽤为检测⼀个线段是否和图元（矩形）发⽣了布局冲突。如果存在布局冲突，返回存在布局冲突的矩形集合；否则，返回null。该⽅法的定义如下：
/**
* 检查⼀个线段是否和图元发⽣了布局冲突
*
* @param rectangleList
* @param location1
* 绝对坐标
* @param location2
* 绝对坐标
* @param gment
* 线段的2端不分先后顺序
* @param cornerConflictContained
* 是否包含拐⾓冲突的情况
* @return 存在布局冲突时，返回存在布局冲突的矩形的集合；不存在布局冲突时返回null。
*/
private static ArrayList<Rectangle> gmentHitTest(
ArrayList<Rectangle> rectangleList, Segment gment,
boolean cornerConflictContained) {
if (rectangleList == null || gment == null) {
return null;
}
// 起点
Point startingPoint = StartingPoint();
// 终点
Point finishingPoint = FinishingPoint();
int direction = getDirection(startingPoint, finishingPoint);
if (direction != PositionConstants.NORTH
&& direction != PositionConstants.SOUTH
&& direction != PositionConstants.WEST
&& direction != PositionConstants.WEST
&& direction != PositionConstants.EAST) {
// 允许有6个像素的误差
if (Math.abs(startingPoint.x - finishingPoint.x) <= 6) {
// 垂直
if (startingPoint.y >= finishingPoint.y) {
direction = PositionConstants.NORTH;
} el {
direction = PositionConstants.SOUTH;
}
}
if (Math.abs(startingPoint.y - finishingPoint.y) <= 6) {
// ⽔平
if (startingPoint.x >= finishingPoint.y) {
direction = PositionConstants.WEST;
} el {
direction = PositionConstants.EAST;
}
}
}
// 垂直⽅向
if (direction == PositionConstants.NORTH
|| direction == PositionConstants.SOUTH) {
// 垂直线段的x坐标
int x = startingPoint.x;
// 所有横跨指定x坐标的矩形
ArrayList<Rectangle> rectanglesCrossingX = getRectangleCrossingX(
rectangleList, x);
// 与线段存在布局冲突的矩形
ArrayList<Rectangle> conflictedRectangles = new ArrayList<Rectangle>(); int smallY = 0;// 线段北端点的y坐标
int bigY = 0;// 线段南端点的y坐标
if (startingPoint.y > finishingPoint.y) {
smallY = finishingPoint.y;
bigY = startingPoint.y;
} el {
smallY = startingPoint.y;
bigY = finishingPoint.y;
}
// 对矩形进⾏遍历
for (Rectangle rect : rectanglesCrossingX) {
if (cornerConflictContained) {// 包含拐⾓冲突的情况
if (rect.y > bigY || rect.y + rect.height < smallY) {
// 不冲突
} el {
conflictedRectangles.add(rect);
}
} el {// 不包含拐⾓冲突的情况
if (rect.y > smallY && rect.y + rect.height < bigY) {
conflictedRectangles.add(rect);
}
}
}
if (conflictedRectangles.size() == 0) {
return null;
}
return conflictedRectangles;
}
// ⽔平⽅向
el if (direction == PositionConstants.EAST
|| direction == PositionConstants.WEST) {
// 垂直线段的x坐标
int y = startingPoint.y;
// 所有横跨指定x坐标的矩形
// 所有横跨指定x坐标的矩形
ArrayList<Rectangle> rectanglesCrossingY = getRectangleCrossingY(
rectangleList, y);
/
/ 与线段存在布局冲突的矩形
ArrayList<Rectangle> conflictedRectangles = new ArrayList<Rectangle>();
int smallX = 0;// 线段西侧端点的x坐标
int bigX = 0;// 线段东侧端点的x坐标
if (startingPoint.x > finishingPoint.x) {
smallX = finishingPoint.x;
bigX = startingPoint.x;
} el {
smallX = startingPoint.x;
bigX = finishingPoint.x;
}
/
/ 对矩形进⾏遍历
for (Rectangle rect : rectanglesCrossingY) {
if (cornerConflictContained) {// 包含拐⾓冲突的情况
if (rect.x > bigX || rect.x + rect.width < smallX) {
// 不冲突
} el {
conflictedRectangles.add(rect);
}
} el {// 不包含拐⾓冲突的情况
if (rect.x > smallX && rect.x + rect.width < bigX) {
conflictedRectangles.add(rect);
}
}
}
if (conflictedRectangles.size() == 0) {
return null;
}
return conflictedRectangles;
}
return null;
}
在该⽅法中，第⼀个参数rectangleList表⽰进⾏冲突检测的所有矩形；第⼆个参数gment表⽰进⾏冲
突检测的线段；第三个参数表⽰cornerConflictContained表⽰冲突检测时是否考虑拐⾓冲突的情况（如果线段线段没有横穿矩形，⽽是线段的⼀个端点位于矩形内部或2个端点均位于矩形内部，称这种情况为拐⾓冲突）。如下图中的2种情况为拐⾓冲突的情况，如果cornerConflictContained为true，则认为存在布局冲突，如果cornerConflictContained为fal，则认为不存在布局冲突。
这个算法的实现思路⽐较简单，⾸先判断线段是⽔平还是垂直⽅向，对于垂直⽅向的线段，⾸先找到图中所有跨过线段x坐标的矩形，再对该集合进⾏遍历，判断矩形的上沿和下沿的坐标是否位于线段的范围内；⽔平⽅向的线段的处理⽅法与之类似。实现过程相见上⾯的代码，从⽽最终判断处线段是否与矩形发⽣了布局冲突。在该⽅法中需要说明的⽅法有，getDirection()⽤于判断⼀个坐标位于另⼀个坐标的什么⽅向，如果2个点坐标相同，则返回NONE，否则，返回东、南、西、北、东北、东南、西北或西南。getRectangleCrossingX（）⽤于获取所有横跨X坐标的矩形（矩形的某个边紧贴坐标x时同样认为该矩形横跨了指定坐标）；getRectangleCrossingY（）获取所有横跨y坐标的矩形（矩形的某个边紧贴线段时同样认为横跨了指定坐标）；
算法3：拐点归并算法
算法3是整个连线路由算法的核⼼，该算法对连线上的所有拐点进⾏检查，将距离⼩于误差容忍度的拐点进⾏归并，并处理存在斜线的拐点。（需要说明的⼀点是，该算法虽然名称叫做拐点归并算法，
但该算法中不只是对拐点进⾏归并删除，有点情况也会在连线上增加必要的拐点，以使连线成为直⾓连线。）什么是误差容忍度呢？误差容忍度是定义的⼀个整数常量，这⾥定义为10个像素。⽔平或垂直⽅向上坐标差⼩于误差容忍度的2个拐点可以认为是出于同⼀条直线上的拐点，应该对这种拐点进⾏归并。注，下⽂中会提到定长这⼀个称呼，定长制的就是此处的误差容忍度。如下图所⽰，如果点线段BC的长度⼩于误差容忍度，则需要将直⾓连线ABCD归并为直线EF：
