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