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