bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/LocalRouter.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 java.awt.geom.Path2D;\r
  15 \r
  16 import org.simantics.g2d.routing.Constants;\r
  17 \r
  18 public class LocalRouter {\r
  19 \r
  20     static final double   CORNER_SIZE = 1.0;\r
  21 \r
  22     boolean roundCorners;\r
  23 \r
  24     double aMinX;\r
  25     double aMinY;\r
  26     double aMaxX;\r
  27     double aMaxY;\r
  28 \r
  29     double bMinX;\r
  30     double bMinY;\r
  31     double bMaxX;\r
  32     double bMaxY;\r
  33 \r
  34     double sx;\r
  35     double sy;\r
  36 \r
  37     double tx;\r
  38     double ty;\r
  39 \r
  40     int sourceDirection;\r
  41     int targetDirection;\r
  42 \r
  43     Path2D path;\r
  44 \r
  45     public LocalRouter(boolean roundCorners) {\r
  46         this.roundCorners = roundCorners;\r
  47     }\r
  48 \r
  49     /**\r
  50      * Case where both source and target connection directions\r
  51      * are to east.\r
  52      */\r
  53     void routeEast() {\r
  54         if(bMinX >= aMaxX || tx >= 0 && !(bMaxY < aMinY || aMaxY < bMinY)) {\r
  55             if(ty != 0.0) {\r
  56                 /*  ______           ______\r
  57                  * |      |         |      |\r
  58                  * |      |----\    |      |\r
  59                  * |      |    \--->|      |\r
  60                  * |______|         |______|\r
  61                  */\r
  62                 double mx = 0.5 * (aMaxX + bMinX);\r
  63                 point(mx, 0.0);\r
  64                 point(mx, ty);\r
  65             }\r
  66             else\r
  67                 ; // Just a straight line\r
  68         }\r
  69         else {\r
  70             double x0 = bMinX;\r
  71             double x1 = aMaxX;\r
  72             double my;\r
  73             /*      ______\r
  74              *     |      |\r
  75              *     |      |\r
  76              *  /->|      |\r
  77              *  |  |______|\r
  78              *  |\r
  79              *  \-------------\\r
  80              *        ______  |\r
  81              *       |      | |\r
  82              *       |      |-/\r
  83              *       |      |\r
  84              *       |______|\r
  85              * \r
  86              * If the elements are separated in Y-direction,\r
  87              * route between the elements (this is always the shortest path).\r
  88              */\r
  89             if(bMaxY < aMinY)      my = 0.5 * (aMinY + bMaxY);\r
  90             else if(aMaxY < bMinY) my = 0.5 * (aMaxY + bMinY);\r
  91             else {\r
  92                 /*\r
  93                  *  /------------------------\\r
  94                  *  |   ______      ______   |\r
  95                  *  |  |      |    |      |  |\r
  96                  *  |  |      |    |      |--+\r
  97                  *  +->|      |    |      |  |\r
  98                  *  |  |______|    |______|  |\r
  99                  *  |                        |\r
 100                  *  \------------------------/\r
 101                  * \r
 102                  * or\r
 103                  * \r
 104                  *    /-----------\\r
 105                  *    |   ______  |\r
 106                  *    |  |      | |\r
 107                  *    |  |      | |\r
 108                  * /--+->|      | |\r
 109                  * |  ___|______| |\r
 110                  * | |      |     |\r
 111                  * | |      |-+---/\r
 112                  * | |      | |\r
 113                  * | |______| |\r
 114                  * |          |\r
 115                  * \----------/\r
 116                  * \r
 117                  * We may choose either lower or upper path.\r
 118                  */\r
 119                 double upperX0 = bMinX;\r
 120                 double upperX1 = aMaxX;\r
 121                 double lowerX0 = bMinX;\r
 122                 double lowerX1 = aMaxX;\r
 123                 double upperY = Math.min(aMinY, bMinY);\r
 124                 double lowerY = Math.max(aMaxY, bMaxY);\r
 125 \r
 126                 if(aMinX < bMinX) {\r
 127                     if(ty < 0.5 * (aMinY + aMaxY))\r
 128                         lowerX0 = aMinX;\r
 129                     else\r
 130                         upperX0 = aMinX;\r
 131                 }\r
 132 \r
 133                 if(bMaxX > aMaxX) {\r
 134                     if(ty < 0.5 * (aMinY + aMaxY))\r
 135                         upperX1 = bMaxX;\r
 136                     else\r
 137                         lowerX1 = bMaxX;\r
 138                 }\r
 139 \r
 140                 double upperLength = upperX1 - upperY + (upperX1 - upperX0) + (ty - upperY) + (tx - upperX0);\r
 141                 double lowerLength = lowerX1 + lowerY + (lowerX1 - lowerX0) + (lowerY - ty) + (tx - lowerX0);\r
 142 \r
 143                 if(upperLength < lowerLength) {\r
 144                     x0 = upperX0;\r
 145                     x1 = upperX1;\r
 146                     my = upperY;\r
 147                 }\r
 148                 else {\r
 149                     x0 = lowerX0;\r
 150                     x1 = lowerX1;\r
 151                     my = lowerY;\r
 152                 }\r
 153             }\r
 154             point(x1, 0.0);\r
 155             point(x1, my);\r
 156             point(x0, my);\r
 157             point(x0, ty);\r
 158         }\r
 159     }\r
 160 \r
 161     void routeWest() {\r
 162         if(tx >= 0.0) {\r
 163             double fx = Math.max(aMaxX, bMaxX);\r
 164             double mx = 0.5 * (aMaxX + bMinX);\r
 165             if(bMinY >= 0.0 || bMaxY <= 0.0 || mx < 0.0) {\r
 166                 /*                   ______\r
 167                  *                  |      |\r
 168                  *                  |      |\r
 169                  *                  |      |<-\\r
 170                  *  ______          |______|  |\r
 171                  * |      |                   |\r
 172                  * |      |-------------------/\r
 173                  * |      |\r
 174                  * |______|\r
 175                  */\r
 176                 point(fx, 0.0);\r
 177             }\r
 178             else {\r
 179                 /*             /-------------\\r
 180                  *             |    ______   |\r
 181                  *             |   |      |  |\r
 182                  *  ______     |   |      |  |\r
 183                  * |      |    |   |      |<-+\r
 184                  * |      |----+   |______|  |\r
 185                  * |      |    |             |\r
 186                  * |______|    \-------------/\r
 187                  * \r
 188                  * We may choose either upper or lower path\r
 189                  * by the path length.\r
 190                  */\r
 191                 double my =\r
 192                     Math.abs(bMinY) + Math.abs(ty - bMinY)\r
 193                     < Math.abs(bMaxY) + Math.abs(ty - bMaxY)\r
 194                     ? bMinY : bMaxY;\r
 195                 point(mx, 0.0);\r
 196                 point(mx, my);\r
 197                 point(fx, my);\r
 198             }\r
 199             point(fx, ty);\r
 200         }\r
 201         else {\r
 202             double fx = Math.max(aMaxX, bMaxX);\r
 203             double mx = 0.5 * (aMinX + bMaxX);\r
 204             point(fx, 0.0);\r
 205             if(ty <= aMinY || ty >= aMaxY || (tx >= mx && ty >= aMinY && ty <= aMaxY)) {\r
 206                 /*                   ______\r
 207                  *                  |      |\r
 208                  *                  |      |\r
 209                  *                  |      |--\\r
 210                  *  ______          |______|  |\r
 211                  * |      |                   |\r
 212                  * |      |<------------------/\r
 213                  * |      |\r
 214                  * |______|\r
 215                  */\r
 216                 point(fx, ty);\r
 217             }\r
 218             else {\r
 219                 /*             /-------------\\r
 220                  *             |    ______   |\r
 221                  *             |   |      |  |\r
 222                  *  ______     |   |      |  |\r
 223                  * |      |    |   |      |--+\r
 224                  * |      |<---+   |______|  |\r
 225                  * |      |    |             |\r
 226                  * |______|    \-------------/\r
 227                  * \r
 228                  * We may choose either upper or lower path\r
 229                  * by the path length.\r
 230                  */\r
 231                 double my =\r
 232                     Math.abs(aMinY) + Math.abs(ty - aMinY)\r
 233                     < Math.abs(aMaxY) + Math.abs(ty - aMaxY)\r
 234                     ? aMinY : aMaxY;\r
 235                 point(fx, my);\r
 236                 point(mx, my);\r
 237                 point(mx, ty);\r
 238             }\r
 239         }\r
 240     }\r
 241 \r
 242     void routeSouth() {\r
 243         if(tx > 0.0 && (bMinY >= 0.0 || (ty > 0.0 && bMinX <= aMaxX)))\r
 244             point(tx, 0.0);\r
 245         else if(bMinX > aMaxX) {\r
 246             double mx = 0.5 * (aMaxX + bMinX);\r
 247             point(mx, 0.0);\r
 248             point(mx, bMinY);\r
 249             point(tx, bMinY);\r
 250         }\r
 251         else {\r
 252             double fx = aMaxX;\r
 253             double my = 0.5 * (aMaxY + bMinY);\r
 254             if(my < aMaxY && (tx < aMinX || ty < aMinY)) {\r
 255                 my = Math.min(aMinY, bMinY);\r
 256                 if(bMaxX > aMaxX)\r
 257                     fx = bMaxX;\r
 258             }\r
 259             point(fx, 0.0);\r
 260             point(fx, my);\r
 261             point(tx, my);\r
 262         }\r
 263     }\r
 264 \r
 265     double xx, xy, yx, yy;\r
 266     void point(double x, double y) {\r
 267         if (roundCorners) {\r
 268             continuePath(x*xx + y*yx + sx, x*xy + y*yy + sy);\r
 269         } else {\r
 270             path.lineTo(x*xx + y*yx + sx, x*xy + y*yy + sy);\r
 271         }\r
 272     }\r
 273 \r
 274     double prevX, prevY, curX, curY, nextX, nextY;\r
 275     boolean first;\r
 276     void beginPath(double x, double y) {\r
 277         path.moveTo(x, y);\r
 278         nextX = x;\r
 279         nextY = y;\r
 280         first = true;\r
 281     }\r
 282 \r
 283     static double dd(double d) {\r
 284         if(Math.abs(d) < CORNER_SIZE*2.0)\r
 285             return d*0.5;\r
 286         else\r
 287             return Math.signum(d)*CORNER_SIZE;\r
 288     }\r
 289 \r
 290     void continuePath(double x, double y) {\r
 291         prevX = curX;\r
 292         prevY = curY;\r
 293         curX = nextX;\r
 294         curY = nextY;\r
 295         nextX = x;\r
 296         nextY = y;\r
 297 \r
 298         if(first)\r
 299             first = false;\r
 300         else {\r
 301             double prevDeltaX = dd(prevX - curX);\r
 302             double prevDeltaY = dd(prevY - curY);\r
 303             double nextDeltaX = dd(nextX - curX);\r
 304             double nextDeltaY = dd(nextY - curY);\r
 305 \r
 306 \r
 307             path.lineTo(curX+prevDeltaX, curY+prevDeltaY);\r
 308             path.quadTo(\r
 309                     curX, curY,\r
 310                     curX+nextDeltaX, curY+nextDeltaY);\r
 311             //path.lineTo(curX+nextDeltaX, curY+nextDeltaY);\r
 312 \r
 313             //path.lineTo(curX, curY);\r
 314         }\r
 315     }\r
 316 \r
 317     void endPath() {\r
 318         path.lineTo(nextX, nextY);\r
 319     }\r
 320 \r
 321     void rotate() {\r
 322         double temp;\r
 323 \r
 324         temp = tx;\r
 325         tx = ty;\r
 326         ty = -temp;\r
 327 \r
 328         temp = aMinX;\r
 329         aMinX = aMinY;\r
 330         aMinY = -aMaxX;\r
 331         aMaxX = aMaxY;\r
 332         aMaxY = -temp;\r
 333 \r
 334         temp = bMinX;\r
 335         bMinX = bMinY;\r
 336         bMinY = -bMaxX;\r
 337         bMaxX = bMaxY;\r
 338         bMaxY = -temp;\r
 339 \r
 340         temp = xx;\r
 341         xx = -xy;\r
 342         xy = temp;\r
 343 \r
 344         temp = yx;\r
 345         yx = -yy;\r
 346         yy = temp;\r
 347 \r
 348         --targetDirection;\r
 349         if(targetDirection < 0)\r
 350             targetDirection += 4;\r
 351         --sourceDirection;\r
 352     }\r
 353 \r
 354     void flip() {\r
 355         double temp;\r
 356 \r
 357         ty = -ty;\r
 358 \r
 359         temp = aMinY;\r
 360         aMinY = -aMaxY;\r
 361         aMaxY = -temp;\r
 362 \r
 363         temp = bMinY;\r
 364         bMinY = -bMaxY;\r
 365         bMaxY = -temp;\r
 366 \r
 367         yx = -yx;\r
 368         yy = -yy;\r
 369 \r
 370         targetDirection = (targetDirection + 2) % 4;\r
 371     }\r
 372 \r
 373     /*\r
 374      * Puts source terminal to origo and rotates the situation\r
 375      * so that the connection leaves to east. Finally, the\r
 376      * case where target direction is to south is eliminated\r
 377      * by optionally flipping the situation.\r
 378      */\r
 379     void canonicalize() {\r
 380         aMinX -= sx;\r
 381         aMinY -= sy;\r
 382         aMaxX -= sx;\r
 383         aMaxY -= sy;\r
 384         bMinX -= sx;\r
 385         bMinY -= sy;\r
 386         bMaxX -= sx;\r
 387         bMaxY -= sy;\r
 388         tx -= sx;\r
 389         ty -= sy;\r
 390         xx = yy = 1.0;\r
 391         xy = yx = 0.0;\r
 392         while(sourceDirection > 0)\r
 393             rotate();\r
 394 \r
 395         if(targetDirection == Constants.SOUTH)\r
 396             flip();\r
 397     }\r
 398 \r
 399     public void route() {\r
 400         //System.out.println("route");\r
 401         //System.out.println(sourceDirection + " " + targetDirection);\r
 402 \r
 403         path = new Path2D.Double();\r
 404 \r
 405         if (roundCorners) {\r
 406             \r
 407             beginPath(sx, sy);\r
 408             \r
 409             if(bMinX < sx && sx < bMaxX && bMinY < sy && sy < bMaxY)\r
 410                 targetDirection = (targetDirection+2)&3;\r
 411             if(aMinX < tx && tx < aMaxX && aMinY < ty && ty < aMaxY)\r
 412                 sourceDirection = (sourceDirection+2)&3;\r
 413 \r
 414 //            // Vertical and horizontal cases\r
 415 //            if(Math.abs(sx - tx) < 1e-5 || Math.abs(sy - ty) < 1e-5) {\r
 416 //                path.lineTo(tx, ty);\r
 417 //                return;\r
 418 //            }\r
 419             \r
 420         } else {\r
 421             \r
 422             path.moveTo(sx, sy);\r
 423             \r
 424             // Vertical and horizontal cases\r
 425             // TODO Removed this seemingly incorrect code (they were already disabled in roundCorners case\r
 426             /*if(Math.abs(sx - tx) < 1e-5 || Math.abs(sy - ty) < 1e-5) {\r
 427                 path.lineTo(tx, ty);\r
 428                 return;\r
 429             }*/\r
 430             \r
 431         }\r
 432 \r
 433         canonicalize();\r
 434         switch(targetDirection) {\r
 435             case Constants.EAST: routeWest(); break;\r
 436             case Constants.WEST: routeEast(); break;\r
 437             case Constants.NORTH: routeSouth(); break;\r
 438         }\r
 439         point(tx, ty);\r
 440 \r
 441         if (roundCorners) {\r
 442             endPath();\r
 443         }\r
 444         //System.out.println(sourceDirection + " " + targetDirection);\r
 445     }\r
 446 \r
 447 }\r