图形连线路由算法

cd826

浏览: 129032 次
性别:

最近访客更多访客>>

bingshuihe

boboy666

bambino

heijian202

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

kinetic
BPMN
javascript
html5

最近打算将工作流引擎设计器使用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种可能的情况需要我们进行考虑。

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

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

计算连接边界的算法代码如下：

// 计算两个图形之间的连接方向
	var standardWidth = 20;
	function getConnectionDirection(sourceRect, targetRect){
		// 先计算是否两个图形之间有足够的距离绘制连接线
		var sourcePoint = sourceRect.getCoordinate("EM");
		var targetPoint = targetRect.getCoordinate("WM");
		if((targetPoint.x - sourcePoint.x) > standardWidth){
			return ["E", "W"];
		}
		
		sourcePoint = sourceRect.getCoordinate("WM");
		targetPoint = targetRect.getCoordinate("EM");
		if((sourcePoint.x - targetPoint.x) > standardWidth){
			return ["W", "E"];
		}
		
		sourcePoint = sourceRect.getCoordinate("NC");
		targetPoint = targetRect.getCoordinate("SC");
		if((sourcePoint.y - targetPoint.y) > standardWidth){
			return ["N", "S"];
		} 
		
		sourcePoint = sourceRect.getCoordinate("SC");
		targetPoint = targetRect.getCoordinate("NC");
		if((targetPoint.y - sourcePoint.y) > standardWidth){
			return ["S", "N"];
		}
		
		// 再是否可以通过拐点进行连接
		sourcePoint = sourceRect.getCoordinate("EM");
		targetPoint = targetRect.getCoordinate("NC");
		if(((targetPoint.x - sourcePoint.x) > 0.5 * standardWidth) && ((targetPoint.y - sourcePoint.y) > standardWidth)){
			return ["E", "N"];
		}
		targetPoint = targetRect.getCoordinate("SC");
		if(((targetPoint.x - sourcePoint.x) > 0.5 * standardWidth) && ((sourcePoint.y - targetPoint.y) > standardWidth)){
			return ["E", "S"];
		}
		
		sourcePoint = sourceRect.getCoordinate("WM");
		targetPoint = targetRect.getCoordinate("SC");
		if(((sourcePoint.x - targetPoint.x) > 0.5 * standardWidth) && ((sourcePoint.y - targetPoint.y) > standardWidth)){
			return ["W", "S"];
		}			
		targetPoint = targetRect.getCoordinate("NC");
		if(((sourcePoint.x - targetPoint.x) > 0.5 * standardWidth) && ((targetPoint.y - sourcePoint.y) > standardWidth)){
			return ["W", "N"];
		}
		
		sourcePoint = sourceRect.getCoordinate("NC");
		targetPoint = targetRect.getCoordinate("EM");
		if(((sourcePoint.y - targetPoint.y) > 0.5 * standardWidth) && ((sourcePoint.x - targetPoint.x) > standardWidth)){
			return ["N", "E"];
		}
		targetPoint = targetRect.getCoordinate("WM");
		if(((sourcePoint.y - targetPoint.y) > 0.5 * standardWidth) && ((targetPoint.x - sourcePoint.x) > standardWidth)){
			return ["N", "W"];
		}
		
		sourcePoint = sourceRect.getCoordinate("SC");
		targetPoint = targetRect.getCoordinate("EM");
		if(((targetPoint.y - sourcePoint.y) > 0.5 * standardWidth) && ((sourcePoint.x - targetPoint.x) > standardWidth)){
			return ["S", "E"];
		}
		targetPoint = targetRect.getCoordinate("WM");
		if(((targetPoint.y - sourcePoint.y) > 0.5 * standardWidth) && ((targetPoint.x - sourcePoint.x) > standardWidth)){
			return ["S", "W"];
		}
		
		// 最后计算可用的连接点，然后从中选择。两个连接点可连接优先级为：NN >> EE >> NE >> NW >> SE >> SW
		sourcePoint = sourceRect.getCoordinate("NC");
		targetPoint = targetRect.getCoordinate("NC");
		if((!targetRect.inRect(sourcePoint)) && (!sourceRect.inRect(targetPoint))){
			if((sourcePoint.y - targetPoint.y) < 0){
				if(Math.abs(sourcePoint.x - targetPoint.x) > ((sourceRect.getWidth() + standardWidth) / 2))
					return ["N", "N"];
			}else{
				if(Math.abs(sourcePoint.x - targetPoint.x) > (targetRect.getWidth() / 2))
					return ["N", "N"];
			}
		}
		
		sourcePoint = sourceRect.getCoordinate("EM");
		targetPoint = targetRect.getCoordinate("EM");
		if((!targetRect.inRect(sourcePoint)) && (!sourceRect.inRect(targetPoint))){
			if((sourcePoint.x - targetPoint.x) > 0){
				if(Math.abs(sourcePoint.y - targetPoint.y) > ((sourceRect.getHeight() + standardWidth) / 2))
					return ["E", "E"];
			}else{
				if(Math.abs(sourcePoint.y - targetPoint.y) > (targetRect.getHeight() / 2))
					return ["E", "E"];
			}
		}
		
		// 其次判断NE、NW是否可用
		sourcePoint = sourceRect.getCoordinate("NC");
		targetPoint = targetRect.getCoordinate("EM");
		if((!targetRect.inRect(sourcePoint)) && (!sourceRect.inRect(targetPoint))){
			return ["N", "E"];
		}
		targetPoint = targetRect.getCoordinate("WM");
		if((!targetRect.inRect(sourcePoint)) && (!sourceRect.inRect(targetPoint))){
			return ["N", "W"];
		}
		
		// 最后判断SE、SW是否可用
		sourcePoint = sourceRect.getCoordinate("SC");
		targetPoint = targetRect.getCoordinate("EM");
		if((!targetRect.inRect(sourcePoint)) && (!sourceRect.inRect(targetPoint))){
			return ["S", "E"];
		}
		targetPoint = targetRect.getCoordinate("WM");
		if((!targetRect.inRect(sourcePoint)) && (!sourceRect.inRect(targetPoint))){
			return ["S", "W"];
		}
		
		// 只能返回这个
		return ["E", "W"];
	}

计算连接点的算法代码如下：

	// 计算两个图形之间的拐点
	function calcBendPoints(sourceRect, targetRect, connectionDir){
		var points = [], startPoint, endPoint;
		if("E" == connectionDir[0]){
			startPoint = sourceRect.getCoordinate("EM");
			points.push(startPoint);
			if("S" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("SC");
				points.push({x: endPoint.x, y: startPoint.y});
				points.push(endPoint);
			}else if("N" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("NC");
				points.push({x: endPoint.x, y: startPoint.y});
				points.push(endPoint);
			}else if("E" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("EM");
				points.push({x: Math.max(startPoint.x, endPoint.x) + 1.5 * standardWidth, y: startPoint.y});
				points.push({x: Math.max(startPoint.x, endPoint.x) + 1.5 * standardWidth, y: endPoint.y});
				points.push(endPoint);
			}else{
				endPoint = targetRect.getCoordinate("WM");
				if(endPoint.y != startPoint.y){
					points.push({x: (startPoint.x + endPoint.x) / 2, y: startPoint.y});
					points.push({x: (startPoint.x + endPoint.x) / 2, y: endPoint.y});
				}
				points.push(endPoint);
			}
		}else if("W" == connectionDir[0]){
			startPoint = sourceRect.getCoordinate("WM");
			points.push(startPoint);
			if("S" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("SC");
				points.push({x: endPoint.x, y: startPoint.y});
				points.push(endPoint);
			}else if("N" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("NC");
				points.push({x: endPoint.x, y: startPoint.y});
				points.push(endPoint);
			}else{
				endPoint = targetRect.getCoordinate("EM");
				if(endPoint.y != startPoint.y){
					points.push({x: (startPoint.x + endPoint.x) / 2, y: startPoint.y});
					points.push({x: (startPoint.x + endPoint.x) / 2, y: endPoint.y});
				}
				points.push(endPoint);
			}
		}else if("N" == connectionDir[0]){
			startPoint = sourceRect.getCoordinate("NC");
			points.push(startPoint);
			if("E" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("EM");
				if((endPoint.x - startPoint.x) > 0){
					points.push({x: startPoint.x, y: startPoint.y - standardWidth});
					points.push({x: endPoint.x + 1.5 * standardWidth, y: startPoint.y - standardWidth});
					points.push({x: endPoint.x + 1.5 * standardWidth, y: endPoint.y});
				}else{
					points.push({x: startPoint.x, y: endPoint.y});
				}
				points.push(endPoint);
			}else if("W" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("WM");
				if((endPoint.x - startPoint.x) < 0){
					points.push({x: startPoint.x, y: startPoint.y - standardWidth});
					points.push({x: endPoint.x - 1.5 * standardWidth, y: startPoint.y - standardWidth});
					points.push({x: endPoint.x - 1.5 * standardWidth, y: endPoint.y});
				}else{
					points.push({x: startPoint.x, y: endPoint.y});
				}
				points.push(endPoint);
			}else if("N" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("NC");
				points.push({x: startPoint.x, y: Math.min(startPoint.y, endPoint.y) - 1.5 * standardWidth});
				points.push({x: endPoint.x, y: Math.min(startPoint.y, endPoint.y) - 1.5 * standardWidth});
				points.push(endPoint);
			}else{
				endPoint = targetRect.getCoordinate("SC");
				if(endPoint.x != startPoint.x){
					points.push({x: startPoint.x, y: (startPoint.y + endPoint.y) / 2});
					points.push({x: endPoint.x, y: (startPoint.y + endPoint.y) / 2});
				}
				points.push(endPoint);
			}
		}else if("S" == connectionDir[0]){
			startPoint = sourceRect.getCoordinate("SC");
			points.push(startPoint);
			if("E" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("EM");
				if((endPoint.x - startPoint.x) > 0){
					points.push({x: startPoint.x, y: startPoint.y + standardWidth});
					points.push({x: endPoint.x + 1.5 * standardWidth, y: startPoint.y + standardWidth});
					points.push({x: endPoint.x + 1.5 * standardWidth, y: endPoint.y});
				}else{
					points.push({x: startPoint.x, y: endPoint.y});
				}
				points.push(endPoint);
			}else if("W" == connectionDir[1]){
				endPoint = targetRect.getCoordinate("WM");
				if((endPoint.x - startPoint.x) < 0){
					points.push({x: startPoint.x, y: startPoint.y + standardWidth});
					points.push({x: endPoint.x - 1.5 * standardWidth, y: startPoint.y + standardWidth});
					points.push({x: endPoint.x - 1.5 * standardWidth, y: endPoint.y});
				}else{
					points.push({x: startPoint.x, y: endPoint.y});
				}
				points.push(endPoint);
			}else{
				endPoint = targetRect.getCoordinate("NC");
				if(endPoint.x != startPoint.x){
					points.push({x: startPoint.x, y: (startPoint.y + endPoint.y) / 2});
					points.push({x: endPoint.x, y: (startPoint.y + endPoint.y) / 2});
				}
				points.push(endPoint);
			}
		}
		return points;
	}

实现的代码还是非常简单的，效果自己还是满意的。当然这个只是一个简单的实现框架，如果真要实用还要考虑不同形状的图形的连接限制，用户自己拖拽连接线之后的处理等等。这里先抛个砖吧，欢迎大家讨论指正。

可运行的代码在附件中可下载。

P.S.

在开发时了解一下目前开源的几个Html5绘图框架，最终选择了kinetic这个框架，使用起来感觉也比较顺手。这里有一个教程有兴趣的同学可以去看看。