bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router4.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.Collection;
  21
  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;
  26
  27 public class Router4 implements IRouter2 {
  28
  29     LocalRouter localRouter;
  30
  31     public Router4() {
  32         this(false);
  33     }
  34
  35     public Router4(boolean roundCorners) {
  36         this.localRouter = new LocalRouter(roundCorners);
  37     }
  38
  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;
  48         }
  49         else {
  50             localRouter.aMinX = beginObstacle.getMinX();
  51             localRouter.aMinY = beginObstacle.getMinY();
  52             localRouter.aMaxX = beginObstacle.getMaxX();
  53             localRouter.aMaxY = beginObstacle.getMaxY();
  54         }
  55         localRouter.sourceDirection = sDir;
  56
  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;
  64         }
  65         else {
  66             localRouter.bMinX = endObstacle.getMinX();
  67             localRouter.bMinY = endObstacle.getMinY();
  68             localRouter.bMaxX = endObstacle.getMaxX();
  69             localRouter.bMaxY = endObstacle.getMaxY();
  70         }
  71         localRouter.targetDirection = tDir;
  72
  73         localRouter.route();
  74
  75         return localRouter.path;
  76     }
  77
  78     @Override
  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);
  85
  86                 double bestLength = Double.POSITIVE_INFINITY;
  87                 Path2D bestPath = null;
  88
  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);
  93
  94                         double length = pathCost(path);
  95                         if(length < bestLength) {
  96                             bestLength = length;
  97                             bestPath = localRouter.path;
  98                         }
  99                     }
 100
 101                 if(bestPath != null)
 102                     connection.setPath(seg, bestPath);
 103             }
 104         else {
 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);
 116                 }
 117                 else {
 118                     leftSegments.adjustOrPutValue(begin, 1, 1);
 119                     rightSegments.adjustOrPutValue(end, 1, 1);
 120                 }
 121                 if(begin.y < end.y) {
 122                     upSegments.adjustOrPutValue(end, 1, 1);
 123                     downSegments.adjustOrPutValue(begin, 1, 1);
 124                 }
 125                 else {
 126                     upSegments.adjustOrPutValue(begin, 1, 1);
 127                     downSegments.adjustOrPutValue(end, 1, 1);
 128                 }
 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);
 137             }
 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;
 143
 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)
 149                                 allowedBegin = 1;
 150                             else
 151                                 allowedBegin = 11;
 152                         }
 153                         if(allowedEnd == 0xf) {
 154                             if(leftSegments.get(end) <= 1)
 155                                 allowedEnd = 4;
 156                             else
 157                                 allowedEnd = 14;
 158                         }
 159                     }
 160                     else {
 161                         if(allowedBegin == 0xf) {
 162                             if(leftSegments.get(begin) <= 1)
 163                                 allowedBegin = 4;
 164                             else
 165                                 allowedBegin = 14;
 166                         }
 167                         if(allowedEnd == 0xf) {
 168                             if(rightSegments.get(end) <= 1)
 169                                 allowedEnd = 1;
 170                             else
 171                                 allowedEnd = 11;
 172                         }
 173                     }
 174                 }
 175                 else {
 176                     //System.out.println("vertical");
 177                     if(begin.y < end.y) {
 178                         if(allowedBegin == 0xf) {
 179                             if(downSegments.get(begin) <= 1)
 180                                 allowedBegin = 2;
 181                             else
 182                                 allowedBegin = 7;
 183                         }
 184                         if(allowedEnd == 0xf) {
 185                             if(upSegments.get(end) <= 1)
 186                                 allowedEnd = 8;
 187                             else
 188                                 allowedEnd = 13;
 189                         }
 190                     }
 191                     else {
 192                         if(allowedBegin == 0xf) {
 193                             if(upSegments.get(begin) <= 1)
 194                                 allowedBegin = 8;
 195                             else
 196                                 allowedBegin = 13;
 197                         }
 198                         if(allowedEnd == 0xf) {
 199                             if(downSegments.get(end) <= 1)
 200                                 allowedEnd = 2;
 201                             else
 202                                 allowedEnd = 7;
 203                         }
 204                     }
 205                 }
 206
 207                 //System.out.println(allowedBegin + " " + allowedEnd);
 208
 209                 double bestLength = Double.POSITIVE_INFINITY;
 210                 Path2D bestPath = null;
 211
 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);
 216
 217                         double length = pathCost(path);
 218                         if(length < bestLength) {
 219                             bestLength = length;
 220                             bestPath = localRouter.path;
 221                         }
 222                     }
 223
 224                 if(bestPath != null)
 225                     connection.setPath(seg, bestPath);
 226             }
 227         }
 228     }
 229
 230     final static AffineTransform IDENTITY = new AffineTransform();
 231
 232     static double pathCost(Path2D path) {
 233         double length = 0.0;
 234         PathIterator it = path.getPathIterator(IDENTITY);
 235         double[] temp = new double[6];
 236         double x=0.0, y=0.0;
 237         double bendCount = 0.0;
 238         while(!it.isDone()) {
 239             bendCount += 1.0;
 240             if(it.currentSegment(temp) != PathIterator.SEG_MOVETO)
 241                 length += Math.abs(x - temp[0] + y - temp[1]);
 242             x = temp[0];
 243             y = temp[1];
 244             it.next();
 245         }
 246         //return length * (6.0 + bendCount);
 247         return bendCount - 1.0 / length;
 248     }
 249 }