1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.g2d.routing.algorithm2;
14 import gnu.trove.map.hash.TObjectIntHashMap;
16 import java.awt.geom.AffineTransform;
17 import java.awt.geom.Path2D;
18 import java.awt.geom.PathIterator;
19 import java.awt.geom.Rectangle2D;
20 import java.util.Collection;
22 import org.simantics.g2d.routing.Constants;
23 import org.simantics.g2d.routing.IConnection;
24 import org.simantics.g2d.routing.IConnection.Connector;
25 import org.simantics.g2d.routing.IRouter2;
27 public class Router4 implements IRouter2 {
29 LocalRouter localRouter;
35 public Router4(boolean roundCorners) {
36 this.localRouter = new LocalRouter(roundCorners);
39 private Path2D route(double beginX, double beginY, int sDir, Rectangle2D beginObstacle,
40 double endX, double endY, int tDir, Rectangle2D endObstacle) {
41 localRouter.sx = beginX;
42 localRouter.sy = beginY;
43 if(beginObstacle == null) {
44 localRouter.aMinX = beginX;
45 localRouter.aMinY = beginY;
46 localRouter.aMaxX = beginX;
47 localRouter.aMaxY = beginY;
50 localRouter.aMinX = beginObstacle.getMinX();
51 localRouter.aMinY = beginObstacle.getMinY();
52 localRouter.aMaxX = beginObstacle.getMaxX();
53 localRouter.aMaxY = beginObstacle.getMaxY();
55 localRouter.sourceDirection = sDir;
57 localRouter.tx = endX;
58 localRouter.ty = endY;
59 if(endObstacle == null) {
60 localRouter.bMinX = endX;
61 localRouter.bMinY = endY;
62 localRouter.bMaxX = endX;
63 localRouter.bMaxY = endY;
66 localRouter.bMinX = endObstacle.getMinX();
67 localRouter.bMinY = endObstacle.getMinY();
68 localRouter.bMaxX = endObstacle.getMaxX();
69 localRouter.bMaxY = endObstacle.getMaxY();
71 localRouter.targetDirection = tDir;
75 return localRouter.path;
79 public void route(IConnection connection) {
80 Collection<?> segments = connection.getSegments();
81 if(segments.size() == 1)
82 for(Object seg : segments) {
83 Connector begin = connection.getBegin(seg);
84 Connector end = connection.getEnd(seg);
86 double bestLength = Double.POSITIVE_INFINITY;
87 Path2D bestPath = null;
89 for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])
90 for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {
91 Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,
92 end.x, end.y, tDir, end.parentObstacle);
94 double length = pathCost(path);
95 if(length < bestLength) {
97 bestPath = localRouter.path;
102 connection.setPath(seg, bestPath);
105 TObjectIntHashMap<Connector> leftSegments = new TObjectIntHashMap<Connector>();
106 TObjectIntHashMap<Connector> rightSegments = new TObjectIntHashMap<Connector>();
107 TObjectIntHashMap<Connector> upSegments = new TObjectIntHashMap<Connector>();
108 TObjectIntHashMap<Connector> downSegments = new TObjectIntHashMap<Connector>();
109 TObjectIntHashMap<Connector> horizontalCount = new TObjectIntHashMap<Connector>();
110 for(Object seg : segments) {
111 Connector begin = connection.getBegin(seg);
112 Connector end = connection.getEnd(seg);
113 if(begin.x < end.x) {
114 leftSegments.adjustOrPutValue(end, 1, 1);
115 rightSegments.adjustOrPutValue(begin, 1, 1);
118 leftSegments.adjustOrPutValue(begin, 1, 1);
119 rightSegments.adjustOrPutValue(end, 1, 1);
121 if(begin.y < end.y) {
122 upSegments.adjustOrPutValue(end, 1, 1);
123 downSegments.adjustOrPutValue(begin, 1, 1);
126 upSegments.adjustOrPutValue(begin, 1, 1);
127 downSegments.adjustOrPutValue(end, 1, 1);
129 if((begin.allowedDirections & 5) != 0)
130 horizontalCount.adjustOrPutValue(end, 1, 1);
131 if((begin.allowedDirections & 10) != 0)
132 horizontalCount.adjustOrPutValue(end, -1, -1);
133 if((end.allowedDirections & 5) != 0)
134 horizontalCount.adjustOrPutValue(begin, 1, 1);
135 if((end.allowedDirections & 10) != 0)
136 horizontalCount.adjustOrPutValue(begin, -1, -1);
138 for(Object seg : segments) {
139 Connector begin = connection.getBegin(seg);
140 Connector end = connection.getEnd(seg);
141 int allowedBegin = begin.allowedDirections;
142 int allowedEnd = end.allowedDirections;
144 if(horizontalCount.get(begin) + horizontalCount.get(end) >= 0) {
145 //System.out.println("horizontal");
146 if(begin.x < end.x) {
147 if(allowedBegin == 0xf) {
148 if(rightSegments.get(begin) <= 1)
153 if(allowedEnd == 0xf) {
154 if(leftSegments.get(end) <= 1)
161 if(allowedBegin == 0xf) {
162 if(leftSegments.get(begin) <= 1)
167 if(allowedEnd == 0xf) {
168 if(rightSegments.get(end) <= 1)
176 //System.out.println("vertical");
177 if(begin.y < end.y) {
178 if(allowedBegin == 0xf) {
179 if(downSegments.get(begin) <= 1)
184 if(allowedEnd == 0xf) {
185 if(upSegments.get(end) <= 1)
192 if(allowedBegin == 0xf) {
193 if(upSegments.get(begin) <= 1)
198 if(allowedEnd == 0xf) {
199 if(downSegments.get(end) <= 1)
207 //System.out.println(allowedBegin + " " + allowedEnd);
209 double bestLength = Double.POSITIVE_INFINITY;
210 Path2D bestPath = null;
212 for(int sDir : Constants.POSSIBLE_DIRECTIONS[allowedBegin])
213 for(int tDir : Constants.POSSIBLE_DIRECTIONS[allowedEnd]) {
214 Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,
215 end.x, end.y, tDir, end.parentObstacle);
217 double length = pathCost(path);
218 if(length < bestLength) {
220 bestPath = localRouter.path;
225 connection.setPath(seg, bestPath);
230 final static AffineTransform IDENTITY = new AffineTransform();
232 static double pathCost(Path2D path) {
234 PathIterator it = path.getPathIterator(IDENTITY);
235 double[] temp = new double[6];
237 double bendCount = 0.0;
238 while(!it.isDone()) {
240 if(it.currentSegment(temp) != PathIterator.SEG_MOVETO)
241 length += Math.abs(x - temp[0] + y - temp[1]);
246 //return length * (6.0 + bendCount);
247 return bendCount - 1.0 / length;