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