1 /*******************************************************************************
\r
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
\r
3 * in Industry THTH ry.
\r
4 * All rights reserved. This program and the accompanying materials
\r
5 * are made available under the terms of the Eclipse Public License v1.0
\r
6 * which accompanies this distribution, and is available at
\r
7 * http://www.eclipse.org/legal/epl-v10.html
\r
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.g2d.routing.algorithm2;
\r
14 import gnu.trove.map.hash.TObjectIntHashMap;
\r
16 import java.awt.geom.AffineTransform;
\r
17 import java.awt.geom.Path2D;
\r
18 import java.awt.geom.PathIterator;
\r
19 import java.awt.geom.Rectangle2D;
\r
20 import java.util.ArrayList;
\r
21 import java.util.Collection;
\r
23 import org.simantics.g2d.routing.Constants;
\r
24 import org.simantics.g2d.routing.IConnection;
\r
25 import org.simantics.g2d.routing.IConnection.Connector;
\r
26 import org.simantics.g2d.routing.IRouter2;
\r
28 public class Router3 implements IRouter2 {
\r
30 LocalRouter localRouter;
\r
32 public Router3(boolean roundCorners) {
\r
33 this.localRouter = new LocalRouter(roundCorners);
\r
36 private Path2D route(double beginX, double beginY, int sDir, Rectangle2D beginObstacle,
\r
37 double endX, double endY, int tDir, Rectangle2D endObstacle) {
\r
38 localRouter.sx = beginX;
\r
39 localRouter.sy = beginY;
\r
40 if(beginObstacle == null) {
\r
41 localRouter.aMinX = beginX;
\r
42 localRouter.aMinY = beginY;
\r
43 localRouter.aMaxX = beginX;
\r
44 localRouter.aMaxY = beginY;
\r
47 localRouter.aMinX = beginObstacle.getMinX();
\r
48 localRouter.aMinY = beginObstacle.getMinY();
\r
49 localRouter.aMaxX = beginObstacle.getMaxX();
\r
50 localRouter.aMaxY = beginObstacle.getMaxY();
\r
52 localRouter.sourceDirection = sDir;
\r
54 localRouter.tx = endX;
\r
55 localRouter.ty = endY;
\r
56 if(endObstacle == null) {
\r
57 localRouter.bMinX = endX;
\r
58 localRouter.bMinY = endY;
\r
59 localRouter.bMaxX = endX;
\r
60 localRouter.bMaxY = endY;
\r
63 localRouter.bMinX = endObstacle.getMinX();
\r
64 localRouter.bMinY = endObstacle.getMinY();
\r
65 localRouter.bMaxX = endObstacle.getMaxX();
\r
66 localRouter.bMaxY = endObstacle.getMaxY();
\r
68 localRouter.targetDirection = tDir;
\r
70 localRouter.route();
\r
72 return localRouter.path;
\r
76 public void route(IConnection connection) {
\r
77 // System.out.println("route");
\r
79 Collection<?> segments = connection.getSegments();
\r
80 if(segments.size() == 1)
\r
81 for(Object seg : segments) {
\r
82 Connector begin = connection.getBegin(seg);
\r
83 Connector end = connection.getEnd(seg);
\r
85 double bestLength = Double.POSITIVE_INFINITY;
\r
86 Path2D bestPath = null;
\r
88 for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])
\r
89 for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {
\r
90 Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,
\r
91 end.x, end.y, tDir, end.parentObstacle);
\r
93 double length = pathCost(path);
\r
94 if(length < bestLength) {
\r
95 bestLength = length;
\r
96 bestPath = localRouter.path;
\r
100 if(bestPath != null)
\r
101 connection.setPath(seg, bestPath);
\r
105 SegmentInfo[] sInfos = new SegmentInfo[segments.size()];
\r
106 TObjectIntHashMap<Connector> connectorIds = new TObjectIntHashMap<Connector>();
\r
109 for(Object seg : segments) {
\r
110 Connector begin = connection.getBegin(seg);
\r
111 Connector end = connection.getEnd(seg);
\r
113 SegmentInfo sInfo = new SegmentInfo();
\r
114 sInfo.segment = seg;
\r
115 if(connectorIds.contains(begin))
\r
116 sInfo.begin = connectorIds.get(begin);
\r
119 connectorIds.put(begin, cId);
\r
122 if(connectorIds.contains(end))
\r
123 sInfo.end = connectorIds.get(end);
\r
126 connectorIds.put(end, cId);
\r
130 for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])
\r
131 for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {
\r
132 Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,
\r
133 end.x, end.y, tDir, end.parentObstacle);
\r
135 sInfo.candidates.add(new SegmentCandidate(
\r
136 path, pathCost(path),
\r
141 sInfos[sId++] = sInfo;
\r
144 bestCost = Double.POSITIVE_INFINITY;
\r
145 bestPaths = new Path2D[sId];
\r
146 findBestCandidate(0, sInfos, new Path2D[sId], new int[cId], 0.0);
\r
147 //System.out.println("cost: " + bestCost);
\r
148 for(int i=0;i<sId;++i) {
\r
149 connection.setPath(sInfos[i].segment, bestPaths[i]);
\r
155 Path2D[] bestPaths;
\r
157 void findBestCandidate(int seg, SegmentInfo[] sInfos, Path2D[] chosen, int[] dirCounts, double cost) {
\r
158 if(cost >= bestCost)
\r
160 if(seg < sInfos.length) {
\r
161 for(SegmentCandidate sCand : sInfos[seg].candidates) {
\r
162 chosen[seg] = sCand.path;
\r
163 int sId = sInfos[seg].begin + sCand.sDir;
\r
164 int tId = sInfos[seg].end + sCand.tDir;
\r
165 double nCost = cost + sCand.localCost;
\r
166 if(++dirCounts[sId] > 1)
\r
168 nCost += 2.0 * (dirCounts[sId ^ 1] + dirCounts[sId ^ 3]);
\r
169 if(++dirCounts[tId] > 1)
\r
171 nCost += 2.0 * (dirCounts[tId ^ 1] + dirCounts[tId ^ 3]);
\r
172 for(int i=0;i<seg;++i)
\r
173 nCost += 10.0*intersections(chosen[i], sCand.path);
\r
174 findBestCandidate(seg+1, sInfos, chosen, dirCounts, nCost);
\r
181 System.arraycopy(chosen, 0, bestPaths, 0, seg);
\r
185 static class SegmentInfo {
\r
189 ArrayList<SegmentCandidate> candidates = new ArrayList<SegmentCandidate>(4);
\r
192 static class SegmentCandidate {
\r
198 public SegmentCandidate(Path2D path, double localCost, int sDir, int tDir) {
\r
200 this.localCost = localCost;
\r
207 final static AffineTransform identity = new AffineTransform();
\r
209 static int intersections(Path2D path1, Path2D path2) {
\r
211 PathIterator it1 = path1.getPathIterator(identity);
\r
212 double begin1X = 0.0, begin1Y = 0.0, end1X = 0.0, end1Y = 0.0;
\r
213 double begin2X = 0.0, begin2Y = 0.0, end2X = 0.0, end2Y = 0.0;
\r
214 double[] temp = new double[6];
\r
215 while(!it1.isDone()) {
\r
216 int t1 = it1.currentSegment(temp);
\r
217 if(t1 == PathIterator.SEG_MOVETO) {
\r
221 else if(t1 == PathIterator.SEG_LINETO) {
\r
227 double min1X, min1Y, max1X, max1Y;
\r
228 if(begin1X < end1X) { min1X = begin1X; max1X = end1X; }
\r
229 else { max1X = begin1X; min1X = end1X; }
\r
230 if(begin1Y < end1Y) { min1Y = begin1Y; max1Y = end1Y; }
\r
231 else { max1Y = begin1Y; min1Y = end1Y; }
\r
233 PathIterator it2 = path2.getPathIterator(identity);
\r
234 while(!it2.isDone()) {
\r
235 int t2 = it2.currentSegment(temp);
\r
236 if(t2 == PathIterator.SEG_MOVETO) {
\r
240 else if(t2 == PathIterator.SEG_LINETO) {
\r
246 double min2X, min2Y, max2X, max2Y;
\r
247 if(begin2X < end2X) { min2X = begin2X; max2X = end2X; }
\r
248 else { max2X = begin2X; min2X = end2X; }
\r
249 if(begin2Y < end2Y) { min2Y = begin2Y; max2Y = end2Y; }
\r
250 else { max2Y = begin2Y; min2Y = end2Y; }
\r
252 if( ((min1X < min2X && max2X < max1X) || (min2X < min1X && max1X < max2X)) &&
\r
253 ((min1Y < min2Y && max2Y < max1Y) || (min2Y < min1Y && max1Y < max2Y)) )
\r
264 final static AffineTransform IDENTITY = new AffineTransform();
\r
266 static double pathCost(Path2D path) {
\r
267 double length = 0.0;
\r
268 PathIterator it = path.getPathIterator(IDENTITY);
\r
269 double[] temp = new double[6];
\r
270 double x=0.0, y=0.0;
\r
271 double bendCount = 0.0;
\r
272 while(!it.isDone()) {
\r
274 if(it.currentSegment(temp) != PathIterator.SEG_MOVETO)
\r
275 length += Math.abs(x - temp[0] + y - temp[1]);
\r
280 //return length * (6.0 + bendCount);
\r
281 return bendCount - 1.0 / length;
\r