bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/RouteGraph.java

   1 /*******************************************************************************
   2  * Copyright (c) 2011 Association for Decentralized Information Management in
   3  * 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.diagram.connection;
  13
  14 import java.awt.geom.Line2D;
  15 import java.awt.geom.Path2D;
  16 import java.awt.geom.Point2D;
  17 import java.awt.geom.Rectangle2D;
  18 import java.io.PrintStream;
  19 import java.io.Serializable;
  20 import java.util.ArrayList;
  21 import java.util.Collection;
  22 import java.util.Collections;
  23 import java.util.Comparator;
  24 import java.util.Iterator;
  25 import java.util.Map;
  26 import java.util.TreeMap;
  27
  28 import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
  29 import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
  30 import org.simantics.diagram.connection.segments.Segment;
  31 import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
  32
  33 import gnu.trove.list.array.TDoubleArrayList;
  34 import gnu.trove.map.hash.THashMap;
  35 import gnu.trove.map.hash.TObjectIntHashMap;
  36 import gnu.trove.set.hash.THashSet;
  37
  38 public class RouteGraph implements Serializable {
  39
  40     private static final long serialVersionUID = 2004022454972623908L;
  41
  42     public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
  43     public static final boolean CHECK_PARAMERS = true;
  44
  45     protected ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
  46     protected ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
  47     protected ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
  48     protected int caseId;
  49     protected boolean isSimpleConnection;
  50     protected boolean needsUpdate = false;
  51
  52     public void updateTerminals() {
  53         boolean changed = false;
  54         for(RouteTerminal terminal : terminals)
  55             changed |= terminal.updateDynamicPosition();
  56         if(changed) update();
  57     }
  58
  59     /**
  60      * Adds a route line to the graph.
  61      * @param isHorizontal true, if the line is horizontal
  62      * @param position y coordinate of the line if horizontal, x coordinate if vertical
  63      * @return The new line.
  64      */
  65     public RouteLine addLine(boolean isHorizontal, double position) {
  66         RouteLine line = new RouteLine(isHorizontal, position);
  67         lines.add(line);
  68         return line;
  69     }
  70
  71     /**
  72      * Adds a route terminal to the graph.
  73      * @param x The location of the terminal.
  74      * @param y
  75      * @param minX The avoidance area of the terminal.
  76      * @param minY
  77      * @param maxX
  78      * @param maxY
  79      * @param allowedDirections Allowed directions.
  80      *        First four bits tell with which directions
  81      *        a connection can leave the terminal. The
  82      *        Fifth bit indicates whether direct lines
  83      *        can be drawn to the terminal. Directions are
  84      * <pre>
  85      * 0 right (1,0)
  86      * 1 down  (0,1)
  87      * 2 left  (-1,0)
  88      * 3 up    (0,-1)
  89      * </pre>
  90      * @param style Tells what kind of line end is drawn
  91      *        to the connection.
  92      * @param position a provider for a dynamic position for the terminal or
  93      *        <code>null</code> if terminal position is not dynamic
  94      * @return The new terminal.
  95      */
  96     public RouteTerminal addTerminal(double x, double y,
  97             double minX, double minY,
  98             double maxX, double maxY,
  99             int allowedDirections,
 100             ILineEndStyle style, RouteTerminalPosition position) {
 101         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, position);
 102     }
 103
 104     public RouteTerminal addTerminal(double x, double y,
 105             double minX, double minY,
 106             double maxX, double maxY,
 107             int allowedDirections,
 108             ILineEndStyle style) {
 109         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, null);
 110     }
 111
 112     public RouteTerminal addTerminal(double x, double y,
 113             double minX, double minY,
 114             double maxX, double maxY,
 115             int allowedDirections,
 116             ILineEndStyle style, ILineEndStyle dynamicStyle, RouteTerminalPosition position) {
 117         if(CHECK_PARAMERS) {
 118             if(allowedDirections > 0x1f)
 119                 throw new IllegalArgumentException("Illegal allowedDirection flags.");
 120             if(minX > x || x > maxX || minY > y || y > maxY)
 121                 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
 122         }
 123         if(style == null)
 124             style = PlainLineEndStyle.INSTANCE;
 125         RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
 126                 maxX, maxY, allowedDirections, false, style, position);
 127         terminal.setDynamicStyle(dynamicStyle);
 128         terminals.add(terminal);
 129         return terminal;
 130     }
 131
 132     public RouteTerminal addBigTerminal(
 133             double minX, double minY,
 134             double maxX, double maxY,
 135             ILineEndStyle style) {
 136         return addBigTerminal(minX, minY, maxX, maxY, style, null);
 137     }
 138     public RouteTerminal addBigTerminal(
 139             double minX, double minY,
 140             double maxX, double maxY,
 141             ILineEndStyle style, ILineEndStyle dynamicStyle) {
 142         if(style == null)
 143             style = PlainLineEndStyle.INSTANCE;
 144         RouteTerminal terminal = new RouteTerminal(
 145                 0.5*(minX+maxX), 0.5*(minY+maxY),
 146                 minX, minY,
 147                 maxX, maxY,
 148                 0xf, true, style, null);
 149         terminal.setDynamicStyle(dynamicStyle);
 150
 151         terminals.add(terminal);
 152         return terminal;
 153     }
 154
 155     /**
 156      * Adds a route terminal to the graph. The avoidance
 157      * area is given as a rectangle.
 158      * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
 159      */
 160     public RouteTerminal addTerminal(double x, double y,
 161             Rectangle2D bounds,
 162             int allowedDirections,
 163             ILineEndStyle style) {
 164         return addTerminal(x, y,
 165                 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
 166                 allowedDirections, style, null);
 167     }
 168
 169     /**
 170      * Adds a copy of the given terminal to the graph.
 171      */
 172     public RouteTerminal addTerminal(RouteTerminal terminal) {
 173         RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
 174                 terminal.getMinX(), terminal.getMinY(),
 175                 terminal.getMaxX(), terminal.getMaxY(),
 176                 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle(), terminal.getDynamicPosition());
 177         newTerminal.setData(terminal.getData());
 178         return terminal;
 179     }
 180
 181     /**
 182      * Adds a route terminal to the graph. A default line end style is used.
 183      * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
 184      */
 185     public RouteTerminal addTerminal(double x, double y,
 186             double minX, double minY,
 187             double maxX, double maxY,
 188             int allowedDirections) {
 189         return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
 190                 PlainLineEndStyle.INSTANCE, null);
 191     }
 192
 193     /**
 194      * Links nodes.
 195      */
 196     public void link(RouteNode node1, RouteNode node2) {
 197         if(node1 instanceof RouteLine) {
 198             if(node2 instanceof RouteLine) {
 199                 link((RouteLine)node1, (RouteLine)node2);
 200             }
 201             else {
 202                 link((RouteLine)node1, (RouteTerminal)node2);
 203             }
 204         }
 205         else {
 206             if(node2 instanceof RouteLine) {
 207                 link((RouteTerminal)node1, (RouteLine)node2);
 208             }
 209             else {
 210                 link((RouteTerminal)node1, (RouteTerminal)node2);
 211             }
 212         }
 213     }
 214
 215     /**
 216      * Links nodes.
 217      */
 218     public void link(RouteNode ... nodes) {
 219         for(int i=1;i<nodes.length;++i)
 220             link(nodes[i-1], nodes[i]);
 221     }
 222
 223     /**
 224      * Links lines.
 225      */
 226     public void link(RouteLine node1, RouteLine node2) {
 227         new RouteLink(node1, node2);
 228         needsUpdate = true;
 229     }
 230
 231     /**
 232      * Links a terminal and a line.
 233      */
 234     public void link(RouteTerminal node1, RouteLine node2) {
 235         if(CHECK_PARAMERS) {
 236             if(node2 == null)
 237                 throw new NullPointerException();
 238             if(node1.line != null)
 239                 throw new IllegalStateException("Terminal is already connected.");
 240         }
 241         node1.line = node2;
 242         needsUpdate = true;
 243     }
 244
 245     /**
 246      * Links a line and a terminal.
 247      */
 248     public void link(RouteLine node1, RouteTerminal node2) {
 249         if(CHECK_PARAMERS) {
 250             if(node1 == null)
 251                 throw new NullPointerException();
 252             if(node2.line != null)
 253                 throw new IllegalStateException("Terminal is already connected.");
 254         }
 255         node2.line = node1;
 256         needsUpdate = true;
 257     }
 258
 259     /**
 260      * Links two terminals.
 261      */
 262     public void link(RouteTerminal node1, RouteTerminal node2) {
 263         if(CHECK_PARAMERS) {
 264             if(node1 == null)
 265                 throw new NullPointerException();
 266             if(node2 == null)
 267                 throw new NullPointerException();
 268         }
 269         isSimpleConnection = true;
 270         needsUpdate = true;
 271     }
 272
 273     protected void removeTransientRouteLines() {
 274         for(RouteLine line : transientLines)
 275             line.remove();
 276         transientLines.clear();
 277     }
 278
 279     protected void removeRouteTerminalsFromRouteLines() {
 280         for(RouteLine line : lines) {
 281             line.removeRouteTerminals();
 282         }
 283     }
 284
 285     /**
 286      * Rotates given terminal clockwise by given amount
 287      * (also negative numbers are allowed).
 288      */
 289     public void rotate(RouteTerminal terminal, int amount) {
 290         terminal.rotate(amount);
 291         needsUpdate = true;
 292     }
 293
 294     /**
 295      * Moves the given route line so that its position correspond
 296      * to given x or y depending on the orientation of the line.
 297      */
 298     public void setLocation(RouteLine line, double x, double y) {
 299         makePersistent(line);
 300         line.setLocation(x, y);
 301         needsUpdate = true;
 302     }
 303
 304     /**
 305      * Moves the terminal to given location.
 306      */
 307     public void setLocation(RouteTerminal terminal, double x, double y) {
 308         terminal.setLocation(x, y);
 309         needsUpdate = true;
 310     }
 311
 312     /**
 313      * Updates transient route lines, route link positions
 314      * and sorts route points of each route line.
 315      */
 316     public void update() {
 317         needsUpdate = false;
 318         removeTransientRouteLines();
 319         removeRouteTerminalsFromRouteLines();
 320
 321         //print();
 322
 323         for(RouteLine line : lines)
 324             line.hidden = false;
 325         for(RouteTerminal terminal : terminals)
 326             if(terminal.hasDirectConnection() && terminal.line != null)
 327                 terminal.line.hidden = true;
 328
 329         // Choose a strategy
 330         if(isSimpleConnection) {
 331             RouteTerminal a = terminals.get(0);
 332             RouteTerminal b = terminals.get(1);
 333             if(a.hasDirectConnection() || b.hasDirectConnection())
 334                 return;
 335             caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
 336             //System.out.println("caseId = " + caseId);
 337             switch(caseId) {
 338             case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
 339             case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
 340                 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
 341                 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
 342                 line.addPoint(a);
 343                 line.addPoint(b);
 344                 line.terminal = a;
 345                 transientLines.add(line);
 346
 347                 // Path terminal
 348                 a.line = line;
 349                 b.line = line;
 350
 351                 break;
 352             }
 353             case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
 354                 RouteLine line1 = new RouteLine(true, a.y);
 355                 RouteLine line2 = new RouteLine(false, b.x);
 356                 new RouteLink(line1, line2);
 357                 line1.addPoint(a);
 358                 line2.addPoint(b);
 359                 line1.terminal = a;
 360                 line2.terminal = b;
 361                 transientLines.add(line1);
 362                 transientLines.add(line2);
 363
 364                 // Path terminal
 365                 a.line = line1;
 366                 b.line = line2;
 367                 break;
 368             }
 369             case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
 370                 RouteLine line1 = new RouteLine(false, a.x);
 371                 RouteLine line2 = new RouteLine(true, b.y);
 372                 new RouteLink(line1, line2);
 373                 line1.addPoint(a);
 374                 line2.addPoint(b);
 375                 line1.terminal = a;
 376                 line2.terminal = b;
 377                 transientLines.add(line1);
 378                 transientLines.add(line2);
 379
 380                 //Path terminal
 381                 a.line = line1;
 382                 b.line = line2;
 383                 break;
 384             }
 385             case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
 386             case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
 387                 RouteLine line =
 388                         SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
 389                                 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
 390                                 ;
 391                 terminals.get(0).line = line;
 392                 terminals.get(1).line = line;
 393                 transientLines.add(line);
 394                 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
 395                 break;
 396             }
 397             }
 398             //routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
 399         }
 400         else {
 401             caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
 402             routeFromTerminals(false);
 403         }
 404
 405         // Find positions of route points
 406         for(RouteLine line : lines)
 407             line.setPointPositions();
 408         for(RouteLine line : transientLines)
 409             line.setPointPositions();
 410
 411         // Sort route points in route lines
 412         for(RouteLine line : lines) {
 413             line.sortPoints();
 414         }
 415         for(RouteLine line : transientLines) {
 416             line.sortPoints();
 417         }
 418     }
 419
 420     public static class Interval {
 421         public final double min;
 422         public final double max;
 423         public Interval(double min, double max) {
 424             this.min = min;
 425             this.max = max;
 426         }
 427     }
 428
 429     public class IntervalCache {
 430         THashMap<RouteLine, Interval> cache =
 431                 new THashMap<RouteLine, Interval>();
 432         public Interval get(RouteLine line) {
 433             Interval result = cache.get(line);
 434             if(result != null)
 435                 return result;
 436
 437             result = create(line);
 438             cache.put(line, result);
 439             return result;
 440         }
 441
 442         private Interval create(RouteLine line) {
 443             double min = Double.POSITIVE_INFINITY;
 444             double max = Double.NEGATIVE_INFINITY;
 445
 446             for(RoutePoint point : line.points) {
 447                 double temp;
 448                 if(point instanceof RouteLink) {
 449                     RouteLink link = (RouteLink)point;
 450                     if(link.a == line)
 451                         temp = link.b.position;
 452                     else
 453                         temp = link.a.position;
 454                 }
 455                 else {
 456                     RouteTerminal terminal = (RouteTerminal)point;
 457                     if(line.isHorizontal)
 458                         temp = terminal.x;
 459                     else
 460                         temp = terminal.y;
 461                 }
 462                 if(temp < min)
 463                     min = temp;
 464                 if(temp > max)
 465                     max = temp;
 466             }
 467             for(RouteTerminal terminal : terminals) {
 468                 if(terminal.line == line) {
 469                     double temp = terminal.approximatePositionToLine();
 470                     if(temp < min)
 471                         min = temp;
 472                     if(temp > max)
 473                         max = temp;
 474                 }
 475             }
 476
 477             return new Interval(min, max);
 478         }
 479     }
 480
 481     protected void routeFromTerminals(boolean boundingBoxesIntersect) {
 482         IntervalCache cache = new IntervalCache();
 483         for(RouteTerminal terminal : terminals)
 484             if(terminal.line != null) {
 485                 if(!terminal.hasDirectConnection())
 486                     terminal.route(transientLines, cache, boundingBoxesIntersect);
 487             }
 488     }
 489
 490     /**
 491      * Returns a RouteLine near the given point (x,y) (within tolerance).
 492      */
 493     public RouteLine pickLine(double x, double y, double tolerance, int mask) {
 494         if(needsUpdate)
 495             update();
 496         if(isSimpleConnection && transientLines.isEmpty()) {
 497             if(terminals.size() == 2) {
 498                 if((mask & PICK_TRANSIENT_LINES) == 0)
 499                     return null;
 500                 RouteTerminal a = terminals.get(0);
 501                 RouteTerminal b = terminals.get(1);
 502                 if(a.hasDirectConnection() || b.hasDirectConnection()) {
 503                     if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
 504                         RouteLine dummy = new RouteLine(false, y);
 505                         return dummy; // There are no lines to return
 506                     }
 507                     else
 508                         return null;
 509                 }
 510             }
 511         }
 512         if((mask & PICK_PERSISTENT_LINES) != 0)
 513             for(RouteLine line : lines)
 514                 if(line.isNear(x, y, tolerance))
 515                     return line;
 516         if((mask & PICK_TRANSIENT_LINES) != 0)
 517             for(RouteLine line : transientLines)
 518                 if(line.isNear(x, y, tolerance))
 519                     return line;
 520         if((mask & PICK_DIRECT_LINES) != 0) {
 521             RouteTerminal terminal = pickDirectLine(x, y, tolerance);
 522             if(terminal != null)
 523                 return terminal.line;
 524         }
 525         return null;
 526     }
 527
 528     public RouteLine pickLine(double x, double y, double tolerance) {
 529         return pickLine(x, y, tolerance, PICK_LINES);
 530     }
 531
 532     private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
 533         double toleranceSq = tolerance * tolerance;
 534         for(RouteTerminal terminal : terminals)
 535             if((terminal.getAllowedDirections()&0x10) != 0) {
 536                 try {
 537                     RouteLine line = terminal.getLine();
 538                     if(line == null)
 539                         continue;
 540                     RoutePoint b = line.getBegin();
 541                     double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
 542                     if(distSq <= toleranceSq) {
 543                         //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
 544                         return terminal;
 545                     }
 546                 } catch(NullPointerException e) {
 547                     //if terminal does not have a line
 548                     e.printStackTrace();
 549                 } catch(IndexOutOfBoundsException e) {
 550                     // if line does not contain points
 551                     e.printStackTrace();
 552                 }
 553             }
 554         return null;
 555     }
 556
 557     public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
 558         if(isSimpleConnection)
 559             return null;
 560         if(needsUpdate)
 561             update();
 562         RouteLine line = pickLine(x, y, tolerance);
 563         if(line == null)
 564             return null;
 565         RouteLink link = null;
 566         RoutePoint begin = line.getBegin();
 567         RoutePoint end = line.getEnd();
 568         if(line.isHorizontal) {
 569             double mx = 0.5*(begin.getX() + end.getX());
 570             if(x < mx) {
 571                 if(begin instanceof RouteLink)
 572                     link = (RouteLink)begin;
 573             }
 574             else {
 575                 if(end instanceof RouteLink)
 576                     link = (RouteLink)line.getEnd();
 577             }
 578         }
 579         else {
 580             double my = 0.5*(begin.getY() + end.getY());
 581             if(y < my) {
 582                 if(begin instanceof RouteLink)
 583                     link = (RouteLink)begin;
 584             }
 585             else {
 586                 if(end instanceof RouteLink)
 587                     link = (RouteLink)end;
 588             }
 589         }
 590         if(link == null)
 591             return null;
 592         if(link.getOther(line).isTransient())
 593             return null;
 594         return new RouteLineHalf(line, link);
 595     }
 596
 597     public Collection<RouteLineHalf> getLineHalves() {
 598         return getLineHalves(new ArrayList<RouteLineHalf>());
 599     }
 600
 601     public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
 602         for(RouteLine line : getAllLines()) {
 603             {
 604                 RoutePoint p = line.getBegin();
 605                 if(p instanceof RouteLink) {
 606                     RouteLink link = (RouteLink)p;
 607                     if(!link.getOther(line).isTransient())
 608                         result.add(new RouteLineHalf(line, link));
 609                 }
 610             }
 611             {
 612                 RoutePoint p = line.getEnd();
 613                 if(p instanceof RouteLink) {
 614                     RouteLink link = (RouteLink)p;
 615                     if(!link.getOther(line).isTransient())
 616                         result.add(new RouteLineHalf(line, link));
 617                 }
 618             }
 619         }
 620         return result;
 621     }
 622
 623     /**
 624      * Returns a RoutePoint near the given point (x,y) (within tolerance).
 625      */
 626     public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
 627         if(needsUpdate)
 628             update();
 629         if((mask&PICK_TERMINALS) != 0)
 630             for(RouteTerminal terminal : terminals)
 631                 if(terminal.isNear(x, y))
 632                     return terminal;
 633         if((mask&PICK_INTERIOR_POINTS) != 0) {
 634             for(RouteLine line : lines) {
 635                 for(RoutePoint point : line.points)
 636                     if(point.isNear(x, y, tolerance))
 637                         return point;
 638             }
 639             for(RouteLine line : transientLines) {
 640                 for(RoutePoint point : line.points)
 641                     if(point.isNear(x, y, tolerance))
 642                         return point;
 643             }
 644         }
 645         return null;
 646     }
 647
 648     public RoutePoint pickPoint(double x, double y, double tolerance) {
 649         return pickPoint(x, y, tolerance, PICK_POINTS);
 650     }
 651
 652     public static final int PICK_INTERIOR_POINTS = 1;
 653     public static final int PICK_TERMINALS = 2;
 654     public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
 655
 656     public static final int PICK_PERSISTENT_LINES = 4;
 657     public static final int PICK_TRANSIENT_LINES = 8;
 658     public static final int PICK_DIRECT_LINES = 16;
 659     public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
 660
 661     public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
 662
 663     /**
 664      * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
 665      */
 666     public Object pick(double x, double y, double tolerance, int mask) {
 667         if((mask & PICK_POINTS) != 0) {
 668             Object point = pickPoint(x, y, tolerance, mask);
 669             if(point != null)
 670                 return point;
 671         }
 672         /*if((mask & PICK_DIRECT_LINES) != 0) {
 673             RouteTerminal terminal = pickDirectLine(x, y, tolerance);
 674             if(terminal != null)
 675                 return terminal.line.getBegin();
 676         }*/
 677         if((mask & PICK_LINES) != 0)
 678             return pickLine(x, y, tolerance, mask);
 679         else
 680             return null;
 681     }
 682
 683     public Object pick(double x, double y, double tolerance) {
 684         return pick(x, y, tolerance, PICK_ALL);
 685     }
 686
 687     /**
 688      * Returns RoutePoint or RouteLine exactly under the given point (x,y).
 689      */
 690     public Object pick(double x, double y) {
 691         return pick(x, y, 0.0);
 692     }
 693
 694     /**
 695      * Prints the contents of the route graph to stdout.
 696      */
 697     public void print() {
 698         print(System.out);
 699     }
 700
 701     /**
 702      * Prints the contents of the route graph to given print stream.
 703      */
 704     public void print(PrintStream out) {
 705         if(needsUpdate)
 706             update();
 707         if(isSimpleConnection)
 708             out.println("=== SIMPLE CONNECTION ===");
 709         else
 710             out.println("=== COMPLEX CONNECTION ===");
 711         for(RouteLine line : lines) {
 712             out.print("perst");
 713             line.print(out);
 714         }
 715         for(RouteLine line : transientLines) {
 716             out.print("trans");
 717             line.print(out);
 718         }
 719         for(RouteTerminal terminal : terminals) {
 720             out.print("term");
 721             terminal.print(out);
 722         }
 723     }
 724
 725     public void makePersistent(RouteLine line) {
 726         prepareForModification();
 727         if(isSimpleConnection || line.isTransient()) {
 728             if(isSimpleConnection) {
 729                 isSimpleConnection = false;
 730                 for(RouteTerminal terminal : terminals)
 731                     terminal.line = line;
 732                 transientLines.remove(line);
 733                 lines.add(line);
 734                 Iterator<RoutePoint> it = line.points.iterator();
 735                 while(it.hasNext()) {
 736                     RoutePoint point = it.next();
 737                     if(point instanceof RouteTerminal)
 738                         it.remove();
 739                 }
 740                 line.terminal = null;
 741                 line.nextTransient = null;
 742             }
 743             else {
 744                 line.terminal.line = line;
 745                 do {
 746                     transientLines.remove(line);
 747                     lines.add(line);
 748                     Iterator<RoutePoint> it = line.points.iterator();
 749                     while(it.hasNext()) {
 750                         RoutePoint point = it.next();
 751                         if(point instanceof RouteTerminal)
 752                             it.remove();
 753                     }
 754                     line.terminal = null;
 755                     RouteLine temp = line.nextTransient;
 756                     line.nextTransient = null;
 757                     line = temp;
 758                 } while(line != null);
 759             }
 760             needsUpdate = true;
 761         }
 762     }
 763
 764     void prepareForModification() {
 765         if(caseId == 4) {
 766             RouteLine line = transientLines.remove(0);
 767             line.terminal = null;
 768             lines.add(line);
 769             for(RouteTerminal terminal : terminals)
 770                 terminal.line = line;
 771             isSimpleConnection = false;
 772             caseId = 6;
 773         }
 774     }
 775
 776     public double[] getLineLengths(RouteTerminal terminal) {
 777         if(needsUpdate)
 778             update();
 779         if(lines.size()==0 && transientLines.size()==1)
 780             return new double[] { transientLines.get(0).getLength() };
 781
 782         RouteLine line = null;
 783         fLoop:
 784         for(RouteLine l : transientLines)
 785             if(l.isTransient()) {
 786                 for(RoutePoint p : l.points)
 787                     if(!(p instanceof RouteLink)) {
 788                         line = l;
 789                         break fLoop;
 790                     }
 791             }
 792         TDoubleArrayList result = new TDoubleArrayList();
 793         THashSet<RouteLine> set = new THashSet<RouteLine>();
 794         set.add(line);
 795         loop:
 796         while(true) {
 797             result.add(line.getLength());
 798             for(RoutePoint point : line.points)
 799                 if(point instanceof RouteLink) {
 800                     RouteLink link = (RouteLink)point;
 801                     if(set.add(link.a)) {
 802                         line = link.a;
 803                         continue loop;
 804                     }
 805                     if(set.add(link.b)) {
 806                         line = link.b;
 807                         continue loop;
 808                     }
 809                 }
 810             break;
 811         }
 812         return result.toArray();
 813     }
 814
 815     public void split(RouteLine rl1, double splitPosition) {
 816         if(needsUpdate)
 817             update();
 818         boolean isHorizontal = rl1.isHorizontal();
 819         if(isSimpleConnection) {
 820             isSimpleConnection = false;
 821             if(caseId < 2) {
 822                 RouteLine sp = addLine(!isHorizontal, splitPosition);
 823                 for(RouteTerminal terminal : terminals)
 824                     terminal.line = sp;
 825                 update();
 826                 return;
 827             }
 828             else if(caseId < 4) {
 829                 RouteLine sp = addLine(!isHorizontal, splitPosition);
 830                 RouteLine l = addLine(isHorizontal, rl1.position);
 831                 link(l, sp);
 832                 rl1.terminal.line = sp;
 833                 for(RouteTerminal terminal : terminals)
 834                     if(terminal != rl1.terminal)
 835                         terminal.line = l;
 836                 update();
 837                 return;
 838             }
 839             else
 840                 prepareForModification();
 841         }
 842
 843         RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
 844         RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
 845
 846         ArrayList<RoutePoint> points = rl1.points;
 847
 848         int splitPos;
 849         {
 850             int minPos = 0;
 851             int maxPos = points.size();
 852             while(minPos != maxPos) {
 853                 int c = (minPos + maxPos)/2;
 854                 if(isHorizontal
 855                         ? points.get(c).getX() > splitPosition
 856                         : points.get(c).getY() > splitPosition)
 857                     maxPos = c;
 858                 else
 859                     minPos = c+1;
 860             }
 861             splitPos = minPos;
 862         }
 863
 864         for(int i=points.size()-1;i>=splitPos;--i) {
 865             RoutePoint point = points.remove(i);
 866             if(point instanceof RouteLink) {
 867                 RouteLink link = (RouteLink)point;
 868                 link.replace(rl1, rl2);
 869             }
 870         }
 871
 872         if(rl1.isTransient()) {
 873             boolean p1 = rl1.isConnectedToPeristentLine();
 874             boolean p2 = rl2.isConnectedToPeristentLine();
 875
 876             RouteTerminal terminal = rl1.terminal;
 877             if(p1) {
 878                 makePersistent(rl1);
 879                 transientLines.add(rl2);
 880             }
 881             else if(p2) {
 882                 lines.add(rl2);
 883             }
 884             else {
 885                 transientLines.add(rl2);
 886                 if(lines.isEmpty())
 887                     for(RouteTerminal t : terminals)
 888                         t.line = sp;
 889             }
 890             terminal.line = sp;
 891         }
 892         else
 893             lines.add(rl2);
 894
 895         new RouteLink(rl1, sp);
 896         new RouteLink(sp, rl2);
 897         lines.add(sp);
 898         update();
 899     }
 900
 901     public boolean merge(RouteLine line) {
 902         int count = 0;
 903         double sum = 0;
 904         for(RoutePoint point : line.points) {
 905             if(point instanceof RouteLink) {
 906                 RouteLink link = (RouteLink)point;
 907                 RouteLine other = link.getOther(line);
 908                 if(!other.isTransient()) {
 909                     sum += other.position;
 910                     ++count;
 911                 }
 912             }
 913         }
 914         return merge(line, sum / count);
 915     }
 916
 917     /**
 918      * Removes given route line and collapses all its neighbor
 919      * route lines into one line with given position.
 920      */
 921     public boolean merge(RouteLine line, double position) {
 922         if(needsUpdate)
 923             update();
 924         if(isSimpleConnection || line.isTransient())
 925             return false;
 926
 927         if(lines.size() == 1) {
 928             if(terminals.size() != 2)
 929                 return false;
 930             lines.remove(0);
 931             isSimpleConnection = true;
 932             for(RouteTerminal terminal : terminals)
 933                 terminal.line = null;
 934             update();
 935             return true;
 936         }
 937
 938         ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
 939         for(RoutePoint point : line.points) {
 940             /* Because line.terminal == null, there should be
 941              * not RouteTerminals
 942              *
 943              * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
 944              */
 945             if (point instanceof RouteLink) {
 946                 RouteLine l = ((RouteLink)point).getOther(line);
 947                 l.points.remove(point);
 948                 if(!l.isTransient())
 949                     nLines.add(l);
 950             }
 951         }
 952
 953         if(nLines.isEmpty())
 954             return false;
 955         RouteLine merged = nLines.remove(nLines.size()-1);
 956         merged.position = position;
 957         for(RouteLine l : nLines) {
 958             for(RoutePoint point : l.points) {
 959                 /* Because l.terminal == null, there should be
 960                  * not RouteTerminals
 961                  *
 962                  * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
 963                  */
 964                 if (point instanceof RouteLink) {
 965                     RouteLink link = (RouteLink)point;
 966                     link.replace(l, merged);
 967                 }
 968             }
 969         }
 970         THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
 971         removedLines.addAll(nLines);
 972         lines.removeAll(removedLines);
 973         removedLines.add(line);
 974         lines.remove(line);
 975         for(RouteTerminal terminal : terminals)
 976             if(removedLines.contains(terminal.line))
 977                 terminal.line = merged;
 978         update();
 979         return true;
 980     }
 981
 982     public void deleteCorner(RouteLink link) {
 983         if(needsUpdate)
 984             update();
 985         RouteLine a = link.getA();
 986         RouteLine b = link.getB();
 987         if(a.isTransient() || b.isTransient()
 988                 || a.points.size() != 2 || b.points.size() != 2)
 989             return;
 990         RouteLine na=null, nb=null;
 991         for(RoutePoint p : a.points) {
 992             RouteLink l = (RouteLink)p;
 993             if(l.a == a && l.b != b) {
 994                 na = l.b;
 995                 break;
 996             }
 997             else if(l.b == a && l.a != b) {
 998                 na = l.a;
 999                 break;
1000             }
1001         }
1002         for(RoutePoint p : b.points) {
1003             RouteLink l = (RouteLink)p;
1004             if(l.a == b && l.b != a) {
1005                 nb = l.b;
1006                 break;
1007             }
1008             else if(l.b == b && l.a != a) {
1009                 nb = l.a;
1010                 break;
1011             }
1012         }
1013         if(na == null || nb == null) {
1014             System.err.println("Internal error in router.");
1015             return;
1016         }
1017         a.remove();
1018         b.remove();
1019         lines.remove(a);
1020         lines.remove(b);
1021         link(na, nb);
1022         if(na.terminal != null)
1023             na.terminal.line = nb;
1024         if(nb.terminal != null)
1025             nb.terminal.line = na;
1026         update();
1027     }
1028
1029     public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
1030         Object target = pick(x, y, tolerance);
1031         if(target instanceof RouteLine) {
1032             RouteLine line = (RouteLine)target;
1033             RouteTerminal involvedTerminal =
1034                     line.isTransient() ? line.terminal : null;
1035             makePersistent(line);
1036             terminal.line = null; // TODO this is a workaround
1037
1038             int lineDir = line.isHorizontal
1039                     ? (line.position < terminal.y ? 3 : 1)
1040                     : (line.position < terminal.x ? 2 : 0)
1041                     ;
1042
1043             if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1044                 RouteLine l2;
1045                 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1046                     RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1047                     l2 = addLine(false, x);
1048                     link(terminal, l1, l2, line);
1049                 }
1050                 else {
1051                     l2 = addLine(false, x);
1052                     link(terminal, l2, line);
1053                 }
1054                 if(involvedTerminal != null)
1055                     involvedTerminal.line = l2;
1056             }
1057             else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1058                 RouteLine l2;
1059                 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1060                     RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1061                     l2 = addLine(true, y);
1062                     link(terminal, l1, l2, line);
1063                 }
1064                 else {
1065                     l2 = addLine(true, y);
1066                     link(terminal, l2, line);
1067                 }
1068                 if(involvedTerminal != null)
1069                     involvedTerminal.line = l2;
1070             }
1071             else {
1072                 link(terminal, line);
1073             }
1074             update();
1075             return true;
1076         }
1077         else
1078             return false;
1079     }
1080
1081     public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1082         Object target = pick(x, y, tolerance);
1083         if(target instanceof RouteLine) {
1084             RouteLine line = (RouteLine)target;
1085             RouteTerminal involvedTerminal =
1086                     line.isTransient() ? line.terminal : null;
1087             makePersistent(line);
1088             if(line.isHorizontal == sLine.isHorizontal) {
1089                 RouteLine l = addLine(!sLine.isHorizontal,
1090                         sLine.isHorizontal ? x : y);
1091                 link(sLine, l, line);
1092                 if(involvedTerminal != null)
1093                     involvedTerminal.line = l;
1094             }
1095             else {
1096                 link(sLine, line);
1097                 if(involvedTerminal != null)
1098                     involvedTerminal.line = sLine;
1099             }
1100             update();
1101             return true;
1102         }
1103         else
1104             return false;
1105     }
1106
1107     /**
1108      * Makes a deep copy of the route graph and stores
1109      * the correspondences between original and copied
1110      * objects into the given map.
1111      */
1112     public RouteGraph copy(THashMap<Object, Object> map) {
1113         RouteGraph copy = new RouteGraph();
1114         copy.isSimpleConnection = isSimpleConnection;
1115         copy.caseId = caseId;
1116         copy.needsUpdate = needsUpdate;
1117         for(RouteLine line : lines)
1118             copy.lines.add(line.copy(map));
1119         for(RouteLine line : transientLines)
1120             copy.transientLines.add(line.copy(map));
1121         for(RouteTerminal terminal : terminals)
1122             copy.terminals.add(terminal.copy(map));
1123         return copy;
1124     }
1125
1126     /**
1127      * Makes a deep copy of the route graph.
1128      */
1129     public RouteGraph copy() {
1130         THashMap<Object, Object> map = new THashMap<Object, Object>();
1131         return copy(map);
1132     }
1133
1134     /**
1135      * Removes route lines that are conneted to at most
1136      * one other route line or terminal.
1137      */
1138     public void removeExtraConnections() {
1139         TObjectIntHashMap<RouteLine> counts =
1140                 new TObjectIntHashMap<RouteLine>();
1141         removeTransientRouteLines();
1142         for(RouteLine line : lines) {
1143             int count = 0;
1144             for(RoutePoint point : line.points)
1145                 if(point instanceof RouteLink)
1146                     ++count;
1147             counts.put(line, count);
1148         }
1149         for(RouteTerminal terminal : terminals)
1150             counts.adjustOrPutValue(terminal.line, 1, 1);
1151         boolean removed;
1152         do {
1153             removed = false;
1154             Iterator<RouteLine> it = lines.iterator();
1155             while(it.hasNext()) {
1156                 RouteLine line = it.next();
1157                 if(counts.get(line) <= 1) {
1158                     for(RoutePoint point : line.points)
1159                         if(point instanceof RouteLink)
1160                             counts.adjustValue(((RouteLink)point).getOther(line), -1);
1161                     line.remove();
1162                     it.remove();
1163                     removed = true;
1164                 }
1165             }
1166         } while(removed);
1167         update();
1168     }
1169
1170     /**
1171      * Removes a terminal and all route lines that become degenerated by the removal.
1172      */
1173     public void remove(RouteTerminal terminal) {
1174         terminals.remove(terminal);
1175         removeExtraConnections();
1176     }
1177
1178     public void disconnect(RouteTerminal terminal) {
1179         terminal.line = null;
1180         removeExtraConnections();
1181     }
1182
1183     public void remove(RouteLink link) {
1184         link.a.points.remove(link);
1185         link.b.points.remove(link);
1186     }
1187
1188     public void toggleDirectLines(RouteTerminal terminal) {
1189         terminal.toggleDirectLines();
1190         needsUpdate = true;
1191     }
1192
1193     /**
1194      * Returns all persistent route lines of the route graph.
1195      */
1196     public Collection<RouteLine> getLines() {
1197         if(needsUpdate)
1198             update();
1199         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1200             return Collections.unmodifiableList(lines);
1201         else
1202             return lines;
1203     }
1204
1205     /*
1206      * Returns all transient route lines of the route graph.
1207      */
1208     public Collection<RouteLine> getTransientLines() {
1209         if(needsUpdate)
1210             update();
1211         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1212             return Collections.unmodifiableList(transientLines);
1213         else
1214             return transientLines;
1215     }
1216
1217     /**
1218      * Returns all terminals of the route graph.
1219      */
1220     public Collection<RouteTerminal> getTerminals() {
1221         if(RETURN_UNMODIFIABLE_COLLECTIONS)
1222             return Collections.unmodifiableList(terminals);
1223         else
1224             return terminals;
1225     }
1226
1227     /**
1228      * Returns all route lines, both persistent and transient,
1229      * of the route graph.
1230      */
1231     public Collection<RouteLine> getAllLines() {
1232         if(needsUpdate)
1233             update();
1234         ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1235         allLines.addAll(lines);
1236         allLines.addAll(transientLines);
1237         return allLines;
1238     }
1239
1240     /**
1241      * Returns all route lines, both persistent and transient, of the route
1242      * graph, added to the specified collection. Avoids allocation of new
1243      * {@link ArrayList} compared to {@link #getAllLines()}.
1244      */
1245     public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1246         if (result == null)
1247             throw new NullPointerException("null result collection");
1248         if(needsUpdate)
1249             update();
1250         result.addAll(lines);
1251         result.addAll(transientLines);
1252         return result;
1253     }
1254
1255     /**
1256      * Returns true, if the route graph is connected and contains no cycles.
1257      */
1258     public boolean isTree() {
1259         if(isSimpleConnection)
1260             return true;
1261         for(RouteTerminal terminal : terminals)
1262             if(terminal.line == null)
1263                 return false;
1264         THashSet<RouteLine> visited = new THashSet<RouteLine>();
1265         ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1266         int linkCount = 0;
1267         visited.add(lines.get(0));
1268         stack.add(lines.get(0));
1269         while(!stack.isEmpty()) {
1270             RouteLine cur = stack.remove(stack.size()-1);
1271             for(RouteLine n : cur.getPersistentNeighbors()) {
1272                 ++linkCount;
1273                 if(visited.add(n))
1274                     stack.add(n);
1275             }
1276         }
1277         return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1278     }
1279
1280     /**
1281      * Returns if the connection is simple. A connection is simple, if it has just
1282      * two terminals connected together directly without (persistent) route lines.
1283      */
1284     public boolean isSimpleConnection() {
1285         return isSimpleConnection;
1286     }
1287
1288     public void replaceBy(RouteGraph rg) {
1289         this.lines = rg.lines;
1290         this.terminals = rg.terminals;
1291         this.transientLines = rg.transientLines;
1292         this.caseId = rg.caseId;
1293         this.isSimpleConnection = rg.isSimpleConnection;
1294         this.needsUpdate = rg.needsUpdate;
1295         rg.reset();
1296     }
1297
1298     private void reset() {
1299         lines = new ArrayList<RouteLine>();
1300         terminals = new ArrayList<RouteTerminal>();
1301         transientLines = new ArrayList<RouteLine>();
1302         caseId = 0;
1303         isSimpleConnection = false;
1304         needsUpdate = false;
1305     }
1306
1307     public Rectangle2D getBounds() {
1308         Rectangle2D bounds = new Rectangle2D.Double();
1309         getBounds(bounds);
1310         return bounds;
1311     }
1312
1313     public void getBounds(Rectangle2D bounds) {
1314         if(needsUpdate)
1315             update();
1316         double minX = Double.POSITIVE_INFINITY;
1317         double maxX = Double.NEGATIVE_INFINITY;
1318         double minY = Double.POSITIVE_INFINITY;
1319         double maxY = Double.NEGATIVE_INFINITY;
1320         for(RouteLine line : lines) {
1321             double position = line.position;
1322             if(line.isHorizontal) {
1323                 minY = Math.min(minY, position);
1324                 maxY = Math.max(maxY, position);
1325             }
1326             else {
1327                 minX = Math.min(minX, position);
1328                 maxX = Math.max(maxX, position);
1329             }
1330         }
1331         for(RouteLine line : transientLines) {
1332             double position = line.position;
1333             if(line.isHorizontal) {
1334                 minY = Math.min(minY, position);
1335                 maxY = Math.max(maxY, position);
1336             }
1337             else {
1338                 minX = Math.min(minX, position);
1339                 maxX = Math.max(maxX, position);
1340             }
1341         }
1342         for(RouteTerminal terminal : terminals) {
1343             double x = terminal.x;
1344             double y = terminal.y;
1345             minX = Math.min(minX, x);
1346             maxX = Math.max(maxX, x);
1347             minY = Math.min(minY, y);
1348             maxY = Math.max(maxY, y);
1349         }
1350         bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1351     }
1352
1353     private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1354         double x = cur.x, y = cur.y;
1355         if(cur instanceof RouteTerminal) {
1356             ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1357             if(line.isHorizontal()) {
1358                 if(cur == line.getBegin())
1359                     x += style.getLineEndLength(0);
1360                 else
1361                     x -= style.getLineEndLength(2);
1362             }
1363             else {
1364                 if(cur == line.getBegin())
1365                     y += style.getLineEndLength(1);
1366                 else
1367                     y -= style.getLineEndLength(3);
1368             }
1369         }
1370         path.moveTo(x, y);
1371     }
1372
1373     private static final Comparator<RoutePoint> RG_COMP = (o1, o2) -> {
1374         if (o1.getX() < o2.getX())
1375             return -1;
1376         else if (o1.getX() > o2.getX())
1377             return 1;
1378         if (o1.getY() < o2.getY())
1379             return -1;
1380         else if (o1.getY() > o2.getY())
1381             return 1;
1382         return 0;
1383     };
1384
1385     private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1386         double x = cur.x, y = cur.y;
1387         if(cur instanceof RouteTerminal) {
1388             ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1389             if(line.isHorizontal()) {
1390                 if(cur == line.getBegin())
1391                     x += style.getLineEndLength(0);
1392                 else
1393                     x -= style.getLineEndLength(2);
1394             }
1395             else {
1396                 if(cur == line.getBegin())
1397                     y += style.getLineEndLength(1);
1398                 else
1399                     y -= style.getLineEndLength(3);
1400             }
1401         }
1402         path.lineTo(x, y);
1403     }
1404
1405     public void getPath2D(Path2D path) {
1406         if(needsUpdate)
1407             update();
1408
1409         if(isSimpleConnection && transientLines.isEmpty()) {
1410             if(terminals.size() == 2) {
1411                 RouteTerminal a = terminals.get(0);
1412                 RouteTerminal b = terminals.get(1);
1413                 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1414                     path.moveTo(a.x, a.y);
1415                     path.lineTo(b.x, b.y);
1416                     return;
1417                 }
1418             }
1419         }
1420
1421         // Analyze graph
1422         Map<RoutePoint, RouteLine> begins =
1423 //                new THashMap<RoutePoint, RouteLine>(); //The ordering of the coordinates in the path should be deterministic between scenegraphs
1424                 new TreeMap<RoutePoint, RouteLine>(RG_COMP);
1425         for(RouteLine line : lines) {
1426             add(begins, line);
1427         }
1428         for(RouteLine line : transientLines) {
1429             add(begins, line);
1430         }
1431         for(RouteTerminal terminal : terminals)
1432             if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1433                 begins.remove(terminal.line.getBegin());
1434                 drawContinuousPath(path, begins, terminal, terminal.line);
1435             }
1436
1437         // Create paths
1438         for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
1439             RouteLine curLine = begins.remove(begin);
1440             drawContinuousPath(path, begins, begin, curLine);
1441         }
1442     }
1443
1444     private void drawContinuousPath(Path2D path, Map<RoutePoint, RouteLine> begins,
1445             RoutePoint cur, RouteLine curLine) {
1446         if(curLine == null)
1447             return;
1448         addPathBegin(path, cur, curLine);
1449
1450         while(true) {
1451             if(cur != curLine.getEnd())
1452                 cur = curLine.getEnd();
1453             else
1454                 cur = curLine.getBegin();
1455             if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1456                 addPathEnd(path, cur, curLine);
1457                 return;
1458             }
1459             if(cur instanceof RouteLink) {
1460                 if(!curLine.isDegenerated() ||
1461                         path.getCurrentPoint().getX() != cur.x ||
1462                         path.getCurrentPoint().getY() != cur.y)
1463                     path.lineTo(cur.x, cur.y);
1464                 RouteLink link = (RouteLink)cur;
1465                 if(link.a != curLine)
1466                     curLine = link.a;
1467                 else
1468                     curLine = link.b;
1469             }
1470         }
1471     }
1472
1473     private static void add(Map<RoutePoint, RouteLine> begins,
1474             RouteLine line) {
1475         if(line.points.size() > 1) {
1476             {
1477                 RoutePoint p = line.getBegin();
1478                 if(begins.remove(p) == null)
1479                     begins.put(p, line);
1480             }
1481             {
1482                 RoutePoint p = line.getEnd();
1483                 if(begins.remove(p) == null)
1484                     begins.put(p, line);
1485             }
1486         }
1487     }
1488
1489     public Collection<Segment> getSegments() {
1490         if (needsUpdate)
1491             update();
1492         ArrayList<Segment> segments = new ArrayList<Segment>();
1493         for(RouteLine routeLine : lines)
1494             routeLine.collectSegments(segments);
1495         for(RouteLine routeLine : transientLines)
1496             routeLine.collectSegments(segments);
1497         return segments;
1498     }
1499
1500     public Segment findNearestSegment(double x, double y) {
1501         Segment nearest = null;
1502         double minDistanceSq = Double.MAX_VALUE;
1503
1504         for (Segment segment : getSegments()) {
1505             RoutePoint p1 = segment.p1;
1506             RoutePoint p2 = segment.p2;
1507
1508             double distanceSq = Line2D.ptSegDistSq(p1.x, p1.y, p2.x, p2.y, x, y);
1509             if (distanceSq < minDistanceSq) {
1510                 minDistanceSq = distanceSq;
1511                 nearest = segment;
1512             }
1513         }
1514         return nearest;
1515     }
1516
1517     public Point2D findNearestPoint(double x, double y) {
1518         Segment nearest = findNearestSegment(x, y);
1519         if (nearest == null) return null;
1520
1521         RoutePoint p1 = nearest.p1;
1522         RoutePoint p2 = nearest.p2;
1523
1524         double d = Math.pow(p2.x - p1.x, 2.0) + Math.pow(p2.y - p1.y, 2.0);
1525
1526         if (d == 0) {
1527             return new Point2D.Double(p1.x, p1.y);
1528         } else {
1529             double u = ((x - p1.x) * (p2.x - p1.x) + (y - p1.y) * (p2.y - p1.y)) / d;
1530             if (u > 1.0) {
1531                 return new Point2D.Double(p2.x, p2.y);
1532             } else if (u <= 0.0) {
1533                 return new Point2D.Double(p1.x, p1.y);
1534             } else {
1535                 return new Point2D.Double(p2.x * u + p1.x * (1.0-u), (p2.y * u + p1.y * (1.0- u)));
1536             }
1537         }
1538     }
1539
1540     public Path2D getPath2D() {
1541         Path2D result = new Path2D.Double();
1542         getPath2D(result);
1543         return result;
1544     }
1545
1546     public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1547         THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1548         THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1549         THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1550         THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1551         THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1552         THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1553
1554         if(splitLine.isTransient()) {
1555             RouteTerminal terminal = splitLine.terminal;
1556
1557             if(splitLine.beginsWithTerminal()) {
1558                 lines2.addAll(getLines());
1559                 terminals2.addAll(getTerminals());
1560                 terminals1.add(terminal);
1561                 terminals2.remove(terminal);
1562                 interfaceNodes1.add(terminal);
1563                 if(isSimpleConnection())
1564                     interfaceNodes2.addAll(terminals2);
1565                 else
1566                     interfaceNodes2.add(terminal.line);
1567             }
1568             else {
1569                 lines1.addAll(getLines());
1570                 terminals1.addAll(getTerminals());
1571                 terminals2.add(terminal);
1572                 terminals1.remove(terminal);
1573                 interfaceNodes2.add(terminal);
1574                 if(isSimpleConnection())
1575                     interfaceNodes1.addAll(terminals1);
1576                 else
1577                     interfaceNodes1.add(terminal.line);
1578             }
1579         }
1580         else {
1581             for(RoutePoint rp : splitLine.getPoints()) {
1582                 double p = splitLine.isHorizontal ? rp.x : rp.y;
1583                 if(rp instanceof RouteLink) {
1584                     RouteLink link = (RouteLink)rp;
1585                     RouteLine otherLine = link.getA() != splitLine ? link.getA()
1586                             : link.getB();
1587                     if(otherLine.isTransient()) {
1588                         if(p < position) {
1589                             interfaceNodes1.add(otherLine.terminal);
1590                             terminals1.add(otherLine.terminal);
1591                         }
1592                         else {
1593                             interfaceNodes2.add(otherLine.terminal);
1594                             terminals2.add(otherLine.terminal);
1595                         }
1596                         continue;
1597                     }
1598
1599                     if(p < position) {
1600                         interfaceNodes1.add(otherLine);
1601                         traverseGraph(link, otherLine, lines1);
1602                     }
1603                     else {
1604                         interfaceNodes2.add(otherLine);
1605                         traverseGraph(link, otherLine, lines2);
1606                     }
1607                 }
1608             }
1609
1610             for(RouteTerminal terminal : getTerminals())
1611                 if(lines1.contains(terminal.line))
1612                     terminals1.add(terminal);
1613                 else if(lines2.contains(terminal.line))
1614                     terminals2.add(terminal);
1615         }
1616
1617         return new SplittedRouteGraph(splitLine,
1618                 interfaceNodes1, lines1, terminals1,
1619                 interfaceNodes2, lines2, terminals2);
1620     }
1621
1622     private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1623             THashSet<RouteLine> lines) {
1624         if(lines.add(line)) {
1625             for(RoutePoint rp : line.getPoints()) {
1626                 if(rp != previousPoint && rp instanceof RouteLink) {
1627                     RouteLink link = (RouteLink)rp;
1628                     RouteLine otherLine = line != link.getA()
1629                             ? link.getA() : link.getB();
1630                     if(otherLine.isTransient())
1631                         continue;
1632                     traverseGraph(rp, otherLine, lines);
1633                 }
1634             }
1635         }
1636     }
1637
1638     public void reclaimTransientMemory() {
1639         removeTransientRouteLines();
1640         needsUpdate = true;
1641     }
1642
1643 }