bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router3.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management
   3  * in Industry THTH ry.
   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
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.g2d.routing.algorithm2;
  13
  14 import gnu.trove.map.hash.TObjectIntHashMap;
  15
  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.ArrayList;
  21 import java.util.Collection;
  22
  23 import org.simantics.g2d.routing.Constants;
  24 import org.simantics.g2d.routing.IConnection;
  25 import org.simantics.g2d.routing.IConnection.Connector;
  26 import org.simantics.g2d.routing.IRouter2;
  27
  28 public class Router3 implements IRouter2 {
  29
  30     LocalRouter localRouter;
  31
  32     public Router3(boolean roundCorners) {
  33         this.localRouter = new LocalRouter(roundCorners);
  34     }
  35
  36     private Path2D route(double beginX, double beginY, int sDir, Rectangle2D beginObstacle,
  37             double endX, double endY, int tDir, Rectangle2D endObstacle) {
  38         localRouter.sx = beginX;
  39         localRouter.sy = beginY;
  40         if(beginObstacle == null) {
  41             localRouter.aMinX = beginX;
  42             localRouter.aMinY = beginY;
  43             localRouter.aMaxX = beginX;
  44             localRouter.aMaxY = beginY;
  45         }
  46         else {
  47             localRouter.aMinX = beginObstacle.getMinX();
  48             localRouter.aMinY = beginObstacle.getMinY();
  49             localRouter.aMaxX = beginObstacle.getMaxX();
  50             localRouter.aMaxY = beginObstacle.getMaxY();
  51         }
  52         localRouter.sourceDirection = sDir;
  53
  54         localRouter.tx = endX;
  55         localRouter.ty = endY;
  56         if(endObstacle == null) {
  57             localRouter.bMinX = endX;
  58             localRouter.bMinY = endY;
  59             localRouter.bMaxX = endX;
  60             localRouter.bMaxY = endY;
  61         }
  62         else {
  63             localRouter.bMinX = endObstacle.getMinX();
  64             localRouter.bMinY = endObstacle.getMinY();
  65             localRouter.bMaxX = endObstacle.getMaxX();
  66             localRouter.bMaxY = endObstacle.getMaxY();
  67         }
  68         localRouter.targetDirection = tDir;
  69
  70         localRouter.route();
  71
  72         return localRouter.path;
  73     }
  74
  75     @Override
  76     public void route(IConnection connection) {
  77 //        System.out.println("route");
  78
  79         Collection<?> segments = connection.getSegments();
  80         if(segments.size() == 1)
  81             for(Object seg : segments) {
  82                 Connector begin = connection.getBegin(seg);
  83                 Connector end = connection.getEnd(seg);
  84
  85                 double bestLength = Double.POSITIVE_INFINITY;
  86                 Path2D bestPath = null;
  87
  88                 for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])
  89                     for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {
  90                         Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,
  91                                 end.x, end.y, tDir, end.parentObstacle);
  92
  93                         double length = pathCost(path);
  94                         if(length < bestLength) {
  95                             bestLength = length;
  96                             bestPath = localRouter.path;
  97                         }
  98                     }
  99
 100                 if(bestPath != null)
 101                     connection.setPath(seg, bestPath);
 102             }
 103         else {
 104
 105             SegmentInfo[] sInfos = new SegmentInfo[segments.size()];
 106             TObjectIntHashMap<Connector> connectorIds = new TObjectIntHashMap<Connector>();
 107             int sId = 0;
 108             int cId = 0;
 109             for(Object seg : segments) {
 110                 Connector begin = connection.getBegin(seg);
 111                 Connector end = connection.getEnd(seg);
 112
 113                 SegmentInfo sInfo = new SegmentInfo();
 114                 sInfo.segment = seg;
 115                 if(connectorIds.contains(begin))
 116                     sInfo.begin = connectorIds.get(begin);
 117                 else {
 118                     sInfo.begin = cId;
 119                     connectorIds.put(begin, cId);
 120                     cId += 4;
 121                 }
 122                 if(connectorIds.contains(end))
 123                     sInfo.end = connectorIds.get(end);
 124                 else {
 125                     sInfo.end = cId;
 126                     connectorIds.put(end, cId);
 127                     cId += 4;
 128                 }
 129
 130                 for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])
 131                     for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {
 132                         Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,
 133                                 end.x, end.y, tDir, end.parentObstacle);
 134
 135                         sInfo.candidates.add(new SegmentCandidate(
 136                                 path, pathCost(path),
 137                                 sDir, tDir
 138                         ));
 139                     }
 140
 141                 sInfos[sId++] = sInfo;
 142             }
 143
 144             bestCost = Double.POSITIVE_INFINITY;
 145             bestPaths = new Path2D[sId];
 146             findBestCandidate(0, sInfos, new Path2D[sId], new int[cId], 0.0);
 147             //System.out.println("cost: " + bestCost);
 148             for(int i=0;i<sId;++i) {
 149                 connection.setPath(sInfos[i].segment, bestPaths[i]);
 150             }
 151         }
 152     }
 153
 154     double bestCost;
 155     Path2D[] bestPaths;
 156
 157     void findBestCandidate(int seg, SegmentInfo[] sInfos, Path2D[] chosen, int[] dirCounts, double cost) {
 158         if(cost >= bestCost)
 159             return;
 160         if(seg < sInfos.length) {
 161             for(SegmentCandidate sCand : sInfos[seg].candidates) {
 162                 chosen[seg] = sCand.path;
 163                 int sId = sInfos[seg].begin + sCand.sDir;
 164                 int tId = sInfos[seg].end + sCand.tDir;
 165                 double nCost = cost + sCand.localCost;
 166                 if(++dirCounts[sId] > 1)
 167                     nCost += 10.0;
 168                 nCost += 2.0 * (dirCounts[sId ^ 1] + dirCounts[sId ^ 3]);
 169                 if(++dirCounts[tId] > 1)
 170                     nCost += 10.0;
 171                 nCost += 2.0 * (dirCounts[tId ^ 1] + dirCounts[tId ^ 3]);
 172                 for(int i=0;i<seg;++i)
 173                     nCost += 10.0*intersections(chosen[i], sCand.path);
 174                 findBestCandidate(seg+1, sInfos, chosen, dirCounts, nCost);
 175                 --dirCounts[sId];
 176                 --dirCounts[tId];
 177             }
 178         }
 179         else {
 180             bestCost = cost;
 181             System.arraycopy(chosen, 0, bestPaths, 0, seg);
 182         }
 183     }
 184
 185     static class SegmentInfo {
 186         Object segment;
 187         int begin;
 188         int end;
 189         ArrayList<SegmentCandidate> candidates = new ArrayList<SegmentCandidate>(4);
 190     }
 191
 192     static class SegmentCandidate {
 193         Path2D path;
 194         double localCost;
 195         int sDir;
 196         int tDir;
 197
 198         public SegmentCandidate(Path2D path, double localCost, int sDir, int tDir) {
 199             this.path = path;
 200             this.localCost = localCost;
 201             this.sDir = sDir;
 202             this.tDir = tDir;
 203         }
 204
 205     }
 206
 207     final static AffineTransform identity = new AffineTransform();
 208
 209     static int intersections(Path2D path1, Path2D path2) {
 210         int count = 0;
 211         PathIterator it1 = path1.getPathIterator(identity);
 212         double begin1X = 0.0, begin1Y = 0.0, end1X = 0.0, end1Y = 0.0;
 213         double begin2X = 0.0, begin2Y = 0.0, end2X = 0.0, end2Y = 0.0;
 214         double[] temp = new double[6];
 215         while(!it1.isDone()) {
 216             int t1 = it1.currentSegment(temp);
 217             if(t1 == PathIterator.SEG_MOVETO) {
 218                 end1X = temp[0];
 219                 end1Y = temp[1];
 220             }
 221             else if(t1 == PathIterator.SEG_LINETO) {
 222                 begin1X = end1X;
 223                 begin1Y = end1Y;
 224                 end1X = temp[0];
 225                 end1Y = temp[1];
 226
 227                 double min1X, min1Y, max1X, max1Y;
 228                 if(begin1X < end1X) { min1X = begin1X; max1X = end1X; }
 229                 else                { max1X = begin1X; min1X = end1X; }
 230                 if(begin1Y < end1Y) { min1Y = begin1Y; max1Y = end1Y; }
 231                 else                { max1Y = begin1Y; min1Y = end1Y; }
 232
 233                 PathIterator it2 = path2.getPathIterator(identity);
 234                 while(!it2.isDone()) {
 235                     int t2 = it2.currentSegment(temp);
 236                     if(t2 == PathIterator.SEG_MOVETO) {
 237                         end2X = temp[0];
 238                         end2Y = temp[1];
 239                     }
 240                     else if(t2 == PathIterator.SEG_LINETO) {
 241                         begin2X = end2X;
 242                         begin2Y = end2Y;
 243                         end2X = temp[0];
 244                         end2Y = temp[1];
 245
 246                         double min2X, min2Y, max2X, max2Y;
 247                         if(begin2X < end2X) { min2X = begin2X; max2X = end2X; }
 248                         else                { max2X = begin2X; min2X = end2X; }
 249                         if(begin2Y < end2Y) { min2Y = begin2Y; max2Y = end2Y; }
 250                         else                { max2Y = begin2Y; min2Y = end2Y; }
 251
 252                         if( ((min1X < min2X && max2X < max1X) || (min2X < min1X && max1X < max2X)) &&
 253                                 ((min1Y < min2Y && max2Y < max1Y) || (min2Y < min1Y && max1Y < max2Y)) )
 254                             ++ count;
 255                     }
 256                     it2.next();
 257                 }
 258             }
 259             it1.next();
 260         }
 261         return count;
 262     }
 263
 264     final static AffineTransform IDENTITY = new AffineTransform();
 265
 266     static double pathCost(Path2D path) {
 267         double length = 0.0;
 268         PathIterator it = path.getPathIterator(IDENTITY);
 269         double[] temp = new double[6];
 270         double x=0.0, y=0.0;
 271         double bendCount = 0.0;
 272         while(!it.isDone()) {
 273             bendCount += 1.0;
 274             if(it.currentSegment(temp) != PathIterator.SEG_MOVETO)
 275                 length += Math.abs(x - temp[0] + y - temp[1]);
 276             x = temp[0];
 277             y = temp[1];
 278             it.next();
 279         }
 280         //return length * (6.0 + bendCount);
 281         return bendCount - 1.0 / length;
 282     }
 283 }