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

   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
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.g2d.routing.algorithm2;\r
  13 \r
  14 import gnu.trove.map.hash.TObjectIntHashMap;\r
  15 \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.Collection;\r
  21 \r
  22 import org.simantics.g2d.routing.Constants;\r
  23 import org.simantics.g2d.routing.IConnection;\r
  24 import org.simantics.g2d.routing.IConnection.Connector;\r
  25 import org.simantics.g2d.routing.IRouter2;\r
  26 \r
  27 public class Router4 implements IRouter2 {\r
  28 \r
  29     LocalRouter localRouter;\r
  30 \r
  31     public Router4() {\r
  32         this(false);\r
  33     }\r
  34 \r
  35     public Router4(boolean roundCorners) {\r
  36         this.localRouter = new LocalRouter(roundCorners);\r
  37     }\r
  38 \r
  39     private Path2D route(double beginX, double beginY, int sDir, Rectangle2D beginObstacle,\r
  40             double endX, double endY, int tDir, Rectangle2D endObstacle) {\r
  41         localRouter.sx = beginX;\r
  42         localRouter.sy = beginY;\r
  43         if(beginObstacle == null) {\r
  44             localRouter.aMinX = beginX;\r
  45             localRouter.aMinY = beginY;\r
  46             localRouter.aMaxX = beginX;\r
  47             localRouter.aMaxY = beginY;\r
  48         }\r
  49         else {\r
  50             localRouter.aMinX = beginObstacle.getMinX();\r
  51             localRouter.aMinY = beginObstacle.getMinY();\r
  52             localRouter.aMaxX = beginObstacle.getMaxX();\r
  53             localRouter.aMaxY = beginObstacle.getMaxY();\r
  54         }\r
  55         localRouter.sourceDirection = sDir;\r
  56 \r
  57         localRouter.tx = endX;\r
  58         localRouter.ty = endY;\r
  59         if(endObstacle == null) {\r
  60             localRouter.bMinX = endX;\r
  61             localRouter.bMinY = endY;\r
  62             localRouter.bMaxX = endX;\r
  63             localRouter.bMaxY = endY;\r
  64         }\r
  65         else {\r
  66             localRouter.bMinX = endObstacle.getMinX();\r
  67             localRouter.bMinY = endObstacle.getMinY();\r
  68             localRouter.bMaxX = endObstacle.getMaxX();\r
  69             localRouter.bMaxY = endObstacle.getMaxY();\r
  70         }\r
  71         localRouter.targetDirection = tDir;\r
  72 \r
  73         localRouter.route();\r
  74 \r
  75         return localRouter.path;\r
  76     }\r
  77 \r
  78     @Override\r
  79     public void route(IConnection connection) {\r
  80         Collection<?> segments = connection.getSegments();\r
  81         if(segments.size() == 1)\r
  82             for(Object seg : segments) {\r
  83                 Connector begin = connection.getBegin(seg);\r
  84                 Connector end = connection.getEnd(seg);\r
  85 \r
  86                 double bestLength = Double.POSITIVE_INFINITY;\r
  87                 Path2D bestPath = null;\r
  88 \r
  89                 for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])\r
  90                     for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {\r
  91                         Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,\r
  92                                 end.x, end.y, tDir, end.parentObstacle);\r
  93 \r
  94                         double length = pathCost(path);\r
  95                         if(length < bestLength) {\r
  96                             bestLength = length;\r
  97                             bestPath = localRouter.path;\r
  98                         }\r
  99                     }\r
 100 \r
 101                 if(bestPath != null)\r
 102                     connection.setPath(seg, bestPath);\r
 103             }\r
 104         else {\r
 105             TObjectIntHashMap<Connector> leftSegments = new TObjectIntHashMap<Connector>();\r
 106             TObjectIntHashMap<Connector> rightSegments = new TObjectIntHashMap<Connector>();\r
 107             TObjectIntHashMap<Connector> upSegments = new TObjectIntHashMap<Connector>();\r
 108             TObjectIntHashMap<Connector> downSegments = new TObjectIntHashMap<Connector>();\r
 109             TObjectIntHashMap<Connector> horizontalCount = new TObjectIntHashMap<Connector>();\r
 110             for(Object seg : segments) {\r
 111                 Connector begin = connection.getBegin(seg);\r
 112                 Connector end = connection.getEnd(seg);\r
 113                 if(begin.x < end.x) {\r
 114                     leftSegments.adjustOrPutValue(end, 1, 1);\r
 115                     rightSegments.adjustOrPutValue(begin, 1, 1);\r
 116                 }\r
 117                 else {\r
 118                     leftSegments.adjustOrPutValue(begin, 1, 1);\r
 119                     rightSegments.adjustOrPutValue(end, 1, 1);\r
 120                 }\r
 121                 if(begin.y < end.y) {\r
 122                     upSegments.adjustOrPutValue(end, 1, 1);\r
 123                     downSegments.adjustOrPutValue(begin, 1, 1);\r
 124                 }\r
 125                 else {\r
 126                     upSegments.adjustOrPutValue(begin, 1, 1);\r
 127                     downSegments.adjustOrPutValue(end, 1, 1);\r
 128                 }\r
 129                 if((begin.allowedDirections & 5) != 0)\r
 130                     horizontalCount.adjustOrPutValue(end, 1, 1);\r
 131                 if((begin.allowedDirections & 10) != 0)\r
 132                     horizontalCount.adjustOrPutValue(end, -1, -1);\r
 133                 if((end.allowedDirections & 5) != 0)\r
 134                     horizontalCount.adjustOrPutValue(begin, 1, 1);\r
 135                 if((end.allowedDirections & 10) != 0)\r
 136                     horizontalCount.adjustOrPutValue(begin, -1, -1);\r
 137             }\r
 138             for(Object seg : segments) {\r
 139                 Connector begin = connection.getBegin(seg);\r
 140                 Connector end = connection.getEnd(seg);\r
 141                 int allowedBegin = begin.allowedDirections;\r
 142                 int allowedEnd = end.allowedDirections;\r
 143 \r
 144                 if(horizontalCount.get(begin) + horizontalCount.get(end) >= 0) {\r
 145                     //System.out.println("horizontal");\r
 146                     if(begin.x < end.x) {\r
 147                         if(allowedBegin == 0xf) {\r
 148                             if(rightSegments.get(begin) <= 1)\r
 149                                 allowedBegin = 1;\r
 150                             else\r
 151                                 allowedBegin = 11;\r
 152                         }\r
 153                         if(allowedEnd == 0xf) {\r
 154                             if(leftSegments.get(end) <= 1)\r
 155                                 allowedEnd = 4;\r
 156                             else\r
 157                                 allowedEnd = 14;\r
 158                         }\r
 159                     }\r
 160                     else {\r
 161                         if(allowedBegin == 0xf) {\r
 162                             if(leftSegments.get(begin) <= 1)\r
 163                                 allowedBegin = 4;\r
 164                             else\r
 165                                 allowedBegin = 14;\r
 166                         }\r
 167                         if(allowedEnd == 0xf) {\r
 168                             if(rightSegments.get(end) <= 1)\r
 169                                 allowedEnd = 1;\r
 170                             else\r
 171                                 allowedEnd = 11;\r
 172                         }\r
 173                     }\r
 174                 }\r
 175                 else {\r
 176                     //System.out.println("vertical");\r
 177                     if(begin.y < end.y) {\r
 178                         if(allowedBegin == 0xf) {\r
 179                             if(downSegments.get(begin) <= 1)\r
 180                                 allowedBegin = 2;\r
 181                             else\r
 182                                 allowedBegin = 7;\r
 183                         }\r
 184                         if(allowedEnd == 0xf) {\r
 185                             if(upSegments.get(end) <= 1)\r
 186                                 allowedEnd = 8;\r
 187                             else\r
 188                                 allowedEnd = 13;\r
 189                         }\r
 190                     }\r
 191                     else {\r
 192                         if(allowedBegin == 0xf) {\r
 193                             if(upSegments.get(begin) <= 1)\r
 194                                 allowedBegin = 8;\r
 195                             else\r
 196                                 allowedBegin = 13;\r
 197                         }\r
 198                         if(allowedEnd == 0xf) {\r
 199                             if(downSegments.get(end) <= 1)\r
 200                                 allowedEnd = 2;\r
 201                             else\r
 202                                 allowedEnd = 7;\r
 203                         }\r
 204                     }\r
 205                 }\r
 206 \r
 207                 //System.out.println(allowedBegin + " " + allowedEnd);\r
 208 \r
 209                 double bestLength = Double.POSITIVE_INFINITY;\r
 210                 Path2D bestPath = null;\r
 211 \r
 212                 for(int sDir : Constants.POSSIBLE_DIRECTIONS[allowedBegin])\r
 213                     for(int tDir : Constants.POSSIBLE_DIRECTIONS[allowedEnd]) {\r
 214                         Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,\r
 215                                 end.x, end.y, tDir, end.parentObstacle);\r
 216 \r
 217                         double length = pathCost(path);\r
 218                         if(length < bestLength) {\r
 219                             bestLength = length;\r
 220                             bestPath = localRouter.path;\r
 221                         }\r
 222                     }\r
 223 \r
 224                 if(bestPath != null)\r
 225                     connection.setPath(seg, bestPath);\r
 226             }\r
 227         }\r
 228     }\r
 229 \r
 230     final static AffineTransform IDENTITY = new AffineTransform();\r
 231 \r
 232     static double pathCost(Path2D path) {\r
 233         double length = 0.0;\r
 234         PathIterator it = path.getPathIterator(IDENTITY);\r
 235         double[] temp = new double[6];\r
 236         double x=0.0, y=0.0;\r
 237         double bendCount = 0.0;\r
 238         while(!it.isDone()) {\r
 239             bendCount += 1.0;\r
 240             if(it.currentSegment(temp) != PathIterator.SEG_MOVETO)\r
 241                 length += Math.abs(x - temp[0] + y - temp[1]);\r
 242             x = temp[0];\r
 243             y = temp[1];\r
 244             it.next();\r
 245         }\r
 246         //return length * (6.0 + bendCount);\r
 247         return bendCount - 1.0 / length;\r
 248     }\r
 249 }\r