bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router3.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.ArrayList;\r
  21 import java.util.Collection;\r
  22 \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
  27 \r
  28 public class Router3 implements IRouter2 {\r
  29 \r
  30     LocalRouter localRouter;\r
  31 \r
  32     public Router3(boolean roundCorners) {\r
  33         this.localRouter = new LocalRouter(roundCorners);\r
  34     }\r
  35 \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
  45         }\r
  46         else {\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
  51         }\r
  52         localRouter.sourceDirection = sDir;\r
  53 \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
  61         }\r
  62         else {\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
  67         }\r
  68         localRouter.targetDirection = tDir;\r
  69 \r
  70         localRouter.route();\r
  71 \r
  72         return localRouter.path;\r
  73     }\r
  74 \r
  75     @Override\r
  76     public void route(IConnection connection) {\r
  77 //        System.out.println("route");\r
  78 \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
  84 \r
  85                 double bestLength = Double.POSITIVE_INFINITY;\r
  86                 Path2D bestPath = null;\r
  87 \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
  92 \r
  93                         double length = pathCost(path);\r
  94                         if(length < bestLength) {\r
  95                             bestLength = length;\r
  96                             bestPath = localRouter.path;\r
  97                         }\r
  98                     }\r
  99 \r
 100                 if(bestPath != null)\r
 101                     connection.setPath(seg, bestPath);\r
 102             }\r
 103         else {\r
 104 \r
 105             SegmentInfo[] sInfos = new SegmentInfo[segments.size()];\r
 106             TObjectIntHashMap<Connector> connectorIds = new TObjectIntHashMap<Connector>();\r
 107             int sId = 0;\r
 108             int cId = 0;\r
 109             for(Object seg : segments) {\r
 110                 Connector begin = connection.getBegin(seg);\r
 111                 Connector end = connection.getEnd(seg);\r
 112 \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
 117                 else {\r
 118                     sInfo.begin = cId;\r
 119                     connectorIds.put(begin, cId);\r
 120                     cId += 4;\r
 121                 }\r
 122                 if(connectorIds.contains(end))\r
 123                     sInfo.end = connectorIds.get(end);\r
 124                 else {\r
 125                     sInfo.end = cId;\r
 126                     connectorIds.put(end, cId);\r
 127                     cId += 4;\r
 128                 }\r
 129 \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
 134 \r
 135                         sInfo.candidates.add(new SegmentCandidate(\r
 136                                 path, pathCost(path),\r
 137                                 sDir, tDir\r
 138                         ));\r
 139                     }\r
 140 \r
 141                 sInfos[sId++] = sInfo;\r
 142             }\r
 143 \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
 150             }\r
 151         }\r
 152     }\r
 153 \r
 154     double bestCost;\r
 155     Path2D[] bestPaths;\r
 156 \r
 157     void findBestCandidate(int seg, SegmentInfo[] sInfos, Path2D[] chosen, int[] dirCounts, double cost) {\r
 158         if(cost >= bestCost)\r
 159             return;\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
 167                     nCost += 10.0;\r
 168                 nCost += 2.0 * (dirCounts[sId ^ 1] + dirCounts[sId ^ 3]);\r
 169                 if(++dirCounts[tId] > 1)\r
 170                     nCost += 10.0;\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
 175                 --dirCounts[sId];\r
 176                 --dirCounts[tId];\r
 177             }\r
 178         }\r
 179         else {\r
 180             bestCost = cost;\r
 181             System.arraycopy(chosen, 0, bestPaths, 0, seg);\r
 182         }\r
 183     }\r
 184 \r
 185     static class SegmentInfo {\r
 186         Object segment;\r
 187         int begin;\r
 188         int end;\r
 189         ArrayList<SegmentCandidate> candidates = new ArrayList<SegmentCandidate>(4);\r
 190     }\r
 191 \r
 192     static class SegmentCandidate {\r
 193         Path2D path;\r
 194         double localCost;\r
 195         int sDir;\r
 196         int tDir;\r
 197 \r
 198         public SegmentCandidate(Path2D path, double localCost, int sDir, int tDir) {\r
 199             this.path = path;\r
 200             this.localCost = localCost;\r
 201             this.sDir = sDir;\r
 202             this.tDir = tDir;\r
 203         }\r
 204 \r
 205     }\r
 206 \r
 207     final static AffineTransform identity = new AffineTransform();\r
 208 \r
 209     static int intersections(Path2D path1, Path2D path2) {\r
 210         int count = 0;\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
 218                 end1X = temp[0];\r
 219                 end1Y = temp[1];\r
 220             }\r
 221             else if(t1 == PathIterator.SEG_LINETO) {\r
 222                 begin1X = end1X;\r
 223                 begin1Y = end1Y;\r
 224                 end1X = temp[0];\r
 225                 end1Y = temp[1];\r
 226 \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
 232 \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
 237                         end2X = temp[0];\r
 238                         end2Y = temp[1];\r
 239                     }\r
 240                     else if(t2 == PathIterator.SEG_LINETO) {\r
 241                         begin2X = end2X;\r
 242                         begin2Y = end2Y;\r
 243                         end2X = temp[0];\r
 244                         end2Y = temp[1];\r
 245 \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
 251 \r
 252                         if( ((min1X < min2X && max2X < max1X) || (min2X < min1X && max1X < max2X)) &&\r
 253                                 ((min1Y < min2Y && max2Y < max1Y) || (min2Y < min1Y && max1Y < max2Y)) )\r
 254                             ++ count;\r
 255                     }\r
 256                     it2.next();\r
 257                 }\r
 258             }\r
 259             it1.next();\r
 260         }\r
 261         return count;\r
 262     }\r
 263 \r
 264     final static AffineTransform IDENTITY = new AffineTransform();\r
 265 \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
 273             bendCount += 1.0;\r
 274             if(it.currentSegment(temp) != PathIterator.SEG_MOVETO)\r
 275                 length += Math.abs(x - temp[0] + y - temp[1]);\r
 276             x = temp[0];\r
 277             y = temp[1];\r
 278             it.next();\r
 279         }\r
 280         //return length * (6.0 + bendCount);\r
 281         return bendCount - 1.0 / length;\r
 282     }\r
 283 }\r