X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=blobdiff_plain;f=bundles%2Forg.simantics.diagram.connection%2Fsrc%2Forg%2Fsimantics%2Fdiagram%2Fconnection%2FRouteGraph.java;fp=bundles%2Forg.simantics.diagram.connection%2Fsrc%2Forg%2Fsimantics%2Fdiagram%2Fconnection%2FRouteGraph.java;h=e72c42fbceafbaf7f29e3d08387ad09981fb9813;hp=0000000000000000000000000000000000000000;hb=969bd23cab98a79ca9101af33334000879fb60c5;hpb=866dba5cd5a3929bbeae85991796acb212338a08

diff --git a/bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/RouteGraph.java b/bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/RouteGraph.java
new file mode 100644
index 000000000..e72c42fbc
--- /dev/null
+++ b/bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/RouteGraph.java
@@ -0,0 +1,1548 @@
+/*******************************************************************************
+ * Copyright (c) 2011 Association for Decentralized Information Management in
+ * Industry THTH ry.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     VTT Technical Research Centre of Finland - initial API and implementation
+ *******************************************************************************/
+package org.simantics.diagram.connection;
+
+import gnu.trove.list.array.TDoubleArrayList;
+import gnu.trove.map.hash.THashMap;
+import gnu.trove.map.hash.TObjectIntHashMap;
+import gnu.trove.set.hash.THashSet;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Path2D;
+import java.awt.geom.Rectangle2D;
+import java.io.PrintStream;
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+
+import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
+import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
+import org.simantics.diagram.connection.segments.Segment;
+import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
+
+public class RouteGraph implements Serializable {
+
+    private static final long serialVersionUID = 2004022454972623908L;
+
+    public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
+    public static final boolean CHECK_PARAMERS = true;
+
+    ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
+    ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
+    ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
+    int caseId;
+    boolean isSimpleConnection;
+    boolean needsUpdate = false;
+
+    /**
+     * Adds a route line to the graph.
+     * @param isHorizontal true, if the line is horizontal
+     * @param position y coordinate of the line if horizontal, x coordinate if vertical
+     * @return The new line.
+     */
+    public RouteLine addLine(boolean isHorizontal, double position) {
+        RouteLine line = new RouteLine(isHorizontal, position); 
+        lines.add(line);
+        return line;
+    }
+
+    /**
+     * Adds a route terminal to the graph.
+     * @param x The location of the terminal.
+     * @param y 
+     * @param minX The avoidance area of the terminal.
+     * @param minY
+     * @param maxX
+     * @param maxY
+     * @param allowedDirections Allowed directions. 
+     *        First four bits tell with which directions
+     *        a connection can leave the terminal. The
+     *        Fifth bit indicates whether direct lines
+     *        can be drawn to the terminal. Directions are
+     * <pre>
+     * 0 right (1,0)
+     * 1 down  (0,1)
+     * 2 left  (-1,0)
+     * 3 up    (0,-1)
+     * </pre>
+     * @param style Tells what kind of line end is drawn 
+     *        to the connection.
+     * @return The new terminal.
+     */
+    public RouteTerminal addTerminal(double x, double y, 
+            double minX, double minY,
+            double maxX, double maxY, 
+            int allowedDirections,
+            ILineEndStyle style) {
+    	return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null);
+    	
+    }
+    public RouteTerminal addTerminal(double x, double y, 
+            double minX, double minY,
+            double maxX, double maxY, 
+            int allowedDirections,
+            ILineEndStyle style, ILineEndStyle dynamicStyle) {
+        if(CHECK_PARAMERS) {
+            if(allowedDirections > 0x1f)
+                throw new IllegalArgumentException("Illegal allowedDirection flags.");
+            if(minX > x || x > maxX || minY > y || y > maxY)
+                throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
+        }
+        if(style == null)
+            style = PlainLineEndStyle.INSTANCE;
+        RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
+                maxX, maxY, allowedDirections, false, style); 
+        terminal.setDynamicStyle(dynamicStyle);
+        terminals.add(terminal);
+        return terminal;
+    }
+    
+    public RouteTerminal addBigTerminal( 
+            double minX, double minY,
+            double maxX, double maxY,
+            ILineEndStyle style) {
+    	return addBigTerminal(minX, minY, maxX, maxY, style, null);
+    }
+    public RouteTerminal addBigTerminal( 
+            double minX, double minY,
+            double maxX, double maxY,
+            ILineEndStyle style, ILineEndStyle dynamicStyle) {
+        if(style == null)
+            style = PlainLineEndStyle.INSTANCE;
+        RouteTerminal terminal = new RouteTerminal(
+                0.5*(minX+maxX), 0.5*(minY+maxY),
+                minX, minY,
+                maxX, maxY, 
+                0xf, true, style); 
+        terminal.setDynamicStyle(dynamicStyle);
+        
+        terminals.add(terminal);
+        return terminal;
+    }
+
+    /**
+     * Adds a route terminal to the graph. The avoidance
+     * area is given as a rectangle.
+     * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
+     */
+    public RouteTerminal addTerminal(double x, double y, 
+            Rectangle2D bounds, 
+            int allowedDirections,
+            ILineEndStyle style) {
+        return addTerminal(x, y, 
+                bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(), 
+                allowedDirections, style);
+    }
+
+    /**
+     * Adds a copy of the given terminal to the graph.
+     */
+    public RouteTerminal addTerminal(RouteTerminal terminal) {
+        RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
+                terminal.getMinX(), terminal.getMinY(),
+                terminal.getMaxX(), terminal.getMaxY(),
+                terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle());
+        newTerminal.setData(terminal.getData());
+        return terminal;
+    }
+
+    /**
+     * Adds a route terminal to the graph. A default line end style is used.
+     * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
+     */
+    public RouteTerminal addTerminal(double x, double y, 
+            double minX, double minY,
+            double maxX, double maxY, 
+            int allowedDirections) {
+        return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, 
+                PlainLineEndStyle.INSTANCE);
+    }
+    
+    /**
+     * Links nodes.
+     */
+    public void link(RouteNode node1, RouteNode node2) {
+        if(node1 instanceof RouteLine) {
+            if(node2 instanceof RouteLine) {
+                link((RouteLine)node1, (RouteLine)node2);
+            }
+            else {
+                link((RouteLine)node1, (RouteTerminal)node2);
+            }
+        }
+        else {
+            if(node2 instanceof RouteLine) {
+                link((RouteTerminal)node1, (RouteLine)node2);
+            }
+            else {
+                link((RouteTerminal)node1, (RouteTerminal)node2);
+            }
+        }
+    }
+    
+    /**
+     * Links nodes.
+     */
+    public void link(RouteNode ... nodes) {
+        for(int i=1;i<nodes.length;++i)
+            link(nodes[i-1], nodes[i]);
+    }
+    
+    /**
+     * Links lines.
+     */
+    public void link(RouteLine node1, RouteLine node2) {
+        new RouteLink(node1, node2);
+        needsUpdate = true;
+    }
+    
+    /**
+     * Links a terminal and a line.
+     */
+    public void link(RouteTerminal node1, RouteLine node2) {
+        if(CHECK_PARAMERS) {
+            if(node2 == null)
+                throw new NullPointerException();
+            if(node1.line != null)
+                throw new IllegalStateException("Terminal is already connected.");
+        }
+        node1.line = node2;
+        needsUpdate = true;
+    }
+
+    /**
+     * Links a line and a terminal.
+     */
+    public void link(RouteLine node1, RouteTerminal node2) {
+        if(CHECK_PARAMERS) {
+            if(node1 == null)
+                throw new NullPointerException();
+            if(node2.line != null)
+                throw new IllegalStateException("Terminal is already connected.");
+        }
+        node2.line = node1;
+        needsUpdate = true;
+    }
+
+    /**
+     * Links two terminals.
+     */
+    public void link(RouteTerminal node1, RouteTerminal node2) {
+        if(CHECK_PARAMERS) {
+            if(node1 == null)
+                throw new NullPointerException();
+            if(node2 == null)
+                throw new NullPointerException();
+        }
+        isSimpleConnection = true;
+        needsUpdate = true;
+    }
+    
+    void removeTransientRouteLines() {
+        for(RouteLine line : transientLines)
+            line.remove();
+        transientLines.clear();
+    }
+    
+    /**
+     * Rotates given terminal clockwise by given amount
+     * (also negative numbers are allowed). 
+     */
+    public void rotate(RouteTerminal terminal, int amount) {
+        terminal.rotate(amount);
+        needsUpdate = true;
+    }
+    
+    /**
+     * Moves the given route line so that its position correspond
+     * to given x or y depending on the orientation of the line. 
+     */
+    public void setLocation(RouteLine line, double x, double y) {
+        makePersistent(line);
+        line.setLocation(x, y);
+        needsUpdate = true;
+    }
+    
+    /**
+     * Moves the terminal to given location.
+     */
+    public void setLocation(RouteTerminal terminal, double x, double y) {
+        terminal.setLocation(x, y);
+        needsUpdate = true;
+    }
+
+    /**
+     * Updates transient route lines, route link positions
+     * and sorts route points of each route line.
+     */
+    public void update() {
+        needsUpdate = false;
+        removeTransientRouteLines();
+
+        //print();
+        
+        for(RouteLine line : lines)
+            line.hidden = false;
+        for(RouteTerminal terminal : terminals)
+            if(terminal.hasDirectConnection() && terminal.line != null)
+                terminal.line.hidden = true;
+
+        // Choose a strategy
+        if(isSimpleConnection) {
+            RouteTerminal a = terminals.get(0);
+            RouteTerminal b = terminals.get(1);
+            if(a.hasDirectConnection() || b.hasDirectConnection())
+                return;
+            caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
+            //System.out.println("caseId = " + caseId);
+            switch(caseId) {
+            case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION: 
+            case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
+                boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
+                RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
+                line.addPoint(a);
+                line.addPoint(b);
+                line.terminal = a;
+                transientLines.add(line);
+                break;
+            }
+            case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
+                RouteLine line1 = new RouteLine(true, a.y);
+                RouteLine line2 = new RouteLine(false, b.x);
+                new RouteLink(line1, line2);
+                line1.addPoint(a);
+                line2.addPoint(b);
+                line1.terminal = a;
+                line2.terminal = b;
+                transientLines.add(line1);
+                transientLines.add(line2);
+                break;
+            }
+            case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
+                RouteLine line1 = new RouteLine(false, a.x);
+                RouteLine line2 = new RouteLine(true, b.y);
+                new RouteLink(line1, line2);
+                line1.addPoint(a);
+                line2.addPoint(b);
+                line1.terminal = a;
+                line2.terminal = b;
+                transientLines.add(line1);
+                transientLines.add(line2);
+                break;
+            }
+            case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT: 
+            case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
+                RouteLine line =
+                        SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
+                                caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
+                                ;
+                terminals.get(0).line = line;
+                terminals.get(1).line = line;
+                transientLines.add(line);
+                routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
+                break;
+            }
+            }
+        }
+        else {
+            caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
+            routeFromTerminals(false);
+        }
+        
+        // Find positions of route points
+        for(RouteLine line : lines) 
+            line.setPointPositions();
+        for(RouteLine line : transientLines) 
+            line.setPointPositions();
+        
+        // Sort route points in route lines
+        for(RouteLine line : lines) {
+            line.sortPoints();
+        }
+        for(RouteLine line : transientLines) {
+            line.sortPoints();
+        }
+    }
+    
+    static class Interval {
+        public final double min;
+        public final double max;
+        public Interval(double min, double max) {
+            this.min = min;
+            this.max = max;
+        }
+    }
+    
+    class IntervalCache {
+        THashMap<RouteLine, Interval> cache = 
+                new THashMap<RouteLine, Interval>();
+        public Interval get(RouteLine line) {
+            Interval result = cache.get(line);
+            if(result != null)
+                return result;
+            
+            result = create(line);
+            cache.put(line, result);
+            return result;
+        }
+        
+        private Interval create(RouteLine line) {
+            double min = Double.POSITIVE_INFINITY;
+            double max = Double.NEGATIVE_INFINITY;
+            
+            for(RoutePoint point : line.points) {
+                double temp;
+                if(point instanceof RouteLink) {
+                    RouteLink link = (RouteLink)point;
+                    if(link.a == line)
+                        temp = link.b.position;
+                    else
+                        temp = link.a.position;
+                }
+                else {
+                    RouteTerminal terminal = (RouteTerminal)point;
+                    if(line.isHorizontal)
+                        temp = terminal.x;
+                    else
+                        temp = terminal.y;
+                }
+                if(temp < min)
+                    min = temp;
+                if(temp > max)
+                    max = temp;
+            }
+            for(RouteTerminal terminal : terminals) {
+                if(terminal.line == line) {
+                    double temp = terminal.approximatePositionToLine();
+                    if(temp < min)
+                        min = temp;
+                    if(temp > max)
+                        max = temp;
+                }
+            }
+            
+            return new Interval(min, max);
+        }
+    } 
+    
+    private void routeFromTerminals(boolean boundingBoxesIntersect) {
+        IntervalCache cache = new IntervalCache();
+        for(RouteTerminal terminal : terminals) 
+            if(terminal.line != null) {
+                if(!terminal.hasDirectConnection())
+                    terminal.route(transientLines, cache, boundingBoxesIntersect);
+            }
+    }
+        
+    /**
+     * Returns a RouteLine near the given point (x,y) (within tolerance).
+     */
+    public RouteLine pickLine(double x, double y, double tolerance, int mask) {
+        if(needsUpdate)
+            update();
+        if(isSimpleConnection && transientLines.isEmpty()) {
+            if(terminals.size() == 2) {
+                if((mask & PICK_TRANSIENT_LINES) == 0)
+                    return null;
+                RouteTerminal a = terminals.get(0);
+                RouteTerminal b = terminals.get(1);
+                if(a.hasDirectConnection() || b.hasDirectConnection()) {
+                    if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
+                        RouteLine dummy = new RouteLine(false, y);
+                        return dummy; // There are no lines to return
+                    }
+                    else
+                        return null;
+                }
+            }
+        }
+        if((mask & PICK_PERSISTENT_LINES) != 0)
+            for(RouteLine line : lines)
+                if(line.isNear(x, y, tolerance))
+                    return line;
+        if((mask & PICK_TRANSIENT_LINES) != 0)
+            for(RouteLine line : transientLines)
+                if(line.isNear(x, y, tolerance))
+                    return line;
+        if((mask & PICK_DIRECT_LINES) != 0) {
+            RouteTerminal terminal = pickDirectLine(x, y, tolerance);
+            if(terminal != null)
+                return terminal.line;
+        }
+        return null;
+    }
+    
+    public RouteLine pickLine(double x, double y, double tolerance) {
+        return pickLine(x, y, tolerance, PICK_LINES);
+    }
+    
+    private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
+        double toleranceSq = tolerance * tolerance;
+        for(RouteTerminal terminal : terminals)
+            if((terminal.getAllowedDirections()&0x10) != 0) {     
+                try {
+                	RouteLine line = terminal.getLine();
+                	if(line == null)
+                		continue;
+                    RoutePoint b = line.getBegin();
+                    double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y); 
+                    if(distSq <= toleranceSq) {
+                        //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
+                        return terminal;
+                    }
+                } catch(NullPointerException e) {
+                    //if terminal does not have a line
+                    e.printStackTrace();
+                } catch(IndexOutOfBoundsException e) {
+                    // if line does not contain points
+                    e.printStackTrace();
+                }
+            }
+        return null;
+    }
+
+    public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
+        if(isSimpleConnection)
+            return null;
+        if(needsUpdate)
+            update();
+        RouteLine line = pickLine(x, y, tolerance);
+        if(line == null)
+            return null;
+        RouteLink link = null;
+        RoutePoint begin = line.getBegin();
+        RoutePoint end = line.getEnd();
+        if(line.isHorizontal) {
+            double mx = 0.5*(begin.getX() + end.getX());
+            if(x < mx) {
+                if(begin instanceof RouteLink)
+                    link = (RouteLink)begin;
+            }
+            else {
+                if(end instanceof RouteLink)
+                    link = (RouteLink)line.getEnd();
+            }
+        }
+        else {
+            double my = 0.5*(begin.getY() + end.getY());
+            if(y < my) {
+                if(begin instanceof RouteLink)
+                    link = (RouteLink)begin;
+            }
+            else {
+                if(end instanceof RouteLink)
+                    link = (RouteLink)end;
+            }
+        }
+        if(link == null)
+            return null;
+        if(link.getOther(line).isTransient())
+            return null;
+        return new RouteLineHalf(line, link);
+    }
+
+    public Collection<RouteLineHalf> getLineHalves() {
+        return getLineHalves(new ArrayList<RouteLineHalf>());
+    }
+
+    public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
+        for(RouteLine line : getAllLines()) {
+            {
+                RoutePoint p = line.getBegin();
+                if(p instanceof RouteLink) {
+                    RouteLink link = (RouteLink)p;
+                    if(!link.getOther(line).isTransient())
+                        result.add(new RouteLineHalf(line, link));
+                }
+            }
+            {
+                RoutePoint p = line.getEnd();
+                if(p instanceof RouteLink) {
+                    RouteLink link = (RouteLink)p;
+                    if(!link.getOther(line).isTransient())
+                        result.add(new RouteLineHalf(line, link));
+                }
+            }
+        }
+        return result;
+    }
+
+    /**
+     * Returns a RoutePoint near the given point (x,y) (within tolerance).
+     */
+    public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
+        if(needsUpdate)
+            update();
+        if((mask&PICK_TERMINALS) != 0)
+            for(RouteTerminal terminal : terminals)
+                if(terminal.isNear(x, y))
+                    return terminal;
+        if((mask&PICK_INTERIOR_POINTS) != 0) {
+            for(RouteLine line : lines) {
+                for(RoutePoint point : line.points)
+                    if(point.isNear(x, y, tolerance))
+                        return point;
+            }
+            for(RouteLine line : transientLines) {
+                for(RoutePoint point : line.points)
+                    if(point.isNear(x, y, tolerance))
+                        return point;
+            }
+        }
+        return null;
+    }
+    
+    public RoutePoint pickPoint(double x, double y, double tolerance) {
+        return pickPoint(x, y, tolerance, PICK_POINTS);
+    }
+    
+    public static final int PICK_INTERIOR_POINTS = 1;
+    public static final int PICK_TERMINALS = 2;
+    public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
+    
+    public static final int PICK_PERSISTENT_LINES = 4;
+    public static final int PICK_TRANSIENT_LINES = 8;
+    public static final int PICK_DIRECT_LINES = 16;
+    public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
+    
+    public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
+    
+    /**
+     * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
+     */
+    public Object pick(double x, double y, double tolerance, int mask) {
+        if((mask & PICK_POINTS) != 0) {
+            Object point = pickPoint(x, y, tolerance, mask);
+            if(point != null)
+            	return point;
+        }
+        /*if((mask & PICK_DIRECT_LINES) != 0) {
+            RouteTerminal terminal = pickDirectLine(x, y, tolerance);
+            if(terminal != null)
+                return terminal.line.getBegin();
+        }*/
+        if((mask & PICK_LINES) != 0)
+            return pickLine(x, y, tolerance, mask);
+        else
+            return null;
+    }
+    
+    public Object pick(double x, double y, double tolerance) {
+        return pick(x, y, tolerance, PICK_ALL);
+    }
+    
+    /**
+     * Returns RoutePoint or RouteLine exactly under the given point (x,y).
+     */
+    public Object pick(double x, double y) {
+        return pick(x, y, 0.0);
+    }
+    
+    /**
+     * Prints the contents of the route graph to stdout.
+     */
+    public void print() {
+        print(System.out);
+    }
+    
+    /**
+     * Prints the contents of the route graph to given print stream.
+     */
+    public void print(PrintStream out) {
+        if(needsUpdate)
+            update();
+        if(isSimpleConnection)
+            out.println("=== SIMPLE CONNECTION ===");
+        else
+            out.println("=== COMPLEX CONNECTION ===");
+        for(RouteLine line : lines) {
+            out.print("perst");
+            line.print(out);
+        }
+        for(RouteLine line : transientLines) {
+            out.print("trans");
+            line.print(out);
+        }
+        for(RouteTerminal terminal : terminals) {
+            out.print("term");
+            terminal.print(out);
+        }
+    }
+
+    public void makePersistent(RouteLine line) {
+        prepareForModification();
+        if(isSimpleConnection || line.isTransient()) {
+            if(isSimpleConnection) {
+                isSimpleConnection = false;
+                for(RouteTerminal terminal : terminals)
+                    terminal.line = line;
+                transientLines.remove(line);
+                lines.add(line);  
+                Iterator<RoutePoint> it = line.points.iterator();
+                while(it.hasNext()) {
+                    RoutePoint point = it.next();
+                    if(point instanceof RouteTerminal)
+                        it.remove();
+                }
+                line.terminal = null;
+                line.nextTransient = null;
+            }
+            else {
+                line.terminal.line = line;
+                do {
+                    transientLines.remove(line);
+                    lines.add(line);  
+                    Iterator<RoutePoint> it = line.points.iterator();
+                    while(it.hasNext()) {
+                        RoutePoint point = it.next();
+                        if(point instanceof RouteTerminal)
+                            it.remove();
+                    }
+                    line.terminal = null;
+                    RouteLine temp = line.nextTransient;
+                    line.nextTransient = null;
+                    line = temp;
+                } while(line != null);
+            }
+            needsUpdate = true;
+        }
+    }
+
+    void prepareForModification() {
+        if(caseId == 4) {
+            RouteLine line = transientLines.remove(0);
+            line.terminal = null;
+            lines.add(line);
+            for(RouteTerminal terminal : terminals)
+                terminal.line = line;
+            isSimpleConnection = false;
+            caseId = 6;
+        }
+    }
+    
+    public double[] getLineLengths(RouteTerminal terminal) {
+        if(needsUpdate)
+            update();
+        if(lines.size()==0 && transientLines.size()==1)
+            return new double[] { transientLines.get(0).getLength() };
+        
+        RouteLine line = null;
+        fLoop:
+        for(RouteLine l : transientLines)
+            if(l.isTransient()) {
+                for(RoutePoint p : l.points)
+                    if(!(p instanceof RouteLink)) {
+                        line = l;
+                        break fLoop;
+                    }
+            }
+        TDoubleArrayList result = new TDoubleArrayList();
+        THashSet<RouteLine> set = new THashSet<RouteLine>();
+        set.add(line);
+        loop:
+        while(true) {            
+            result.add(line.getLength());
+            for(RoutePoint point : line.points)
+                if(point instanceof RouteLink) {
+                    RouteLink link = (RouteLink)point; 
+                    if(set.add(link.a)) {
+                        line = link.a;
+                        continue loop;
+                    }
+                    if(set.add(link.b)) {
+                        line = link.b;
+                        continue loop;
+                    }
+                }
+            break;
+        }
+        return result.toArray();
+    }
+
+    public void split(RouteLine rl1, double splitPosition) {
+        if(needsUpdate)
+            update();
+        boolean isHorizontal = rl1.isHorizontal();
+        if(isSimpleConnection) {
+            isSimpleConnection = false;
+            if(caseId < 2) {
+                RouteLine sp = addLine(!isHorizontal, splitPosition);
+                for(RouteTerminal terminal : terminals)
+                    terminal.line = sp;
+                update();
+                return;
+            }
+            else if(caseId < 4) {
+                RouteLine sp = addLine(!isHorizontal, splitPosition);
+                RouteLine l = addLine(isHorizontal, rl1.position);
+                link(l, sp);
+                rl1.terminal.line = sp;
+                for(RouteTerminal terminal : terminals)
+                    if(terminal != rl1.terminal)
+                        terminal.line = l;
+                update();
+                return;
+            }
+            else
+                prepareForModification();
+        }
+
+        RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
+        RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
+
+        ArrayList<RoutePoint> points = rl1.points;
+
+        int splitPos;
+        {
+            int minPos = 0;
+            int maxPos = points.size();
+            while(minPos != maxPos) {
+                int c = (minPos + maxPos)/2;
+                if(isHorizontal 
+                        ? points.get(c).getX() > splitPosition 
+                        : points.get(c).getY() > splitPosition)
+                    maxPos = c;
+                else
+                    minPos = c+1;
+            }
+            splitPos = minPos;
+        }
+
+        for(int i=points.size()-1;i>=splitPos;--i) {
+            RoutePoint point = points.remove(i);
+            if(point instanceof RouteLink) {
+                RouteLink link = (RouteLink)point;
+                link.replace(rl1, rl2);
+            }
+        }
+
+        if(rl1.isTransient()) {
+            boolean p1 = rl1.isConnectedToPeristentLine();
+            boolean p2 = rl2.isConnectedToPeristentLine();
+
+            RouteTerminal terminal = rl1.terminal;
+            if(p1) {
+                makePersistent(rl1);
+                transientLines.add(rl2);
+            }
+            else if(p2) {
+                lines.add(rl2);
+            }
+            else {
+                transientLines.add(rl2);
+                if(lines.isEmpty())
+                    for(RouteTerminal t : terminals)
+                        t.line = sp;
+            }
+            terminal.line = sp;
+        }
+        else
+            lines.add(rl2);
+
+        new RouteLink(rl1, sp);
+        new RouteLink(sp, rl2);
+        lines.add(sp);
+        update();
+    }
+
+    public boolean merge(RouteLine line) {
+        int count = 0;
+        double sum = 0;
+        for(RoutePoint point : line.points) {
+            if(point instanceof RouteLink) {
+                RouteLink link = (RouteLink)point;
+                RouteLine other = link.getOther(line);
+                if(!other.isTransient()) {
+                    sum += other.position;
+                    ++count;
+                }
+            }
+        }
+        return merge(line, sum / count);
+    }
+
+    /**
+     * Removes given route line and collapses all its neighbor
+     * route lines into one line with given position.
+     */
+    public boolean merge(RouteLine line, double position) {
+        if(needsUpdate)
+            update();
+        if(isSimpleConnection || line.isTransient())
+            return false;
+        
+        if(lines.size() == 1) {
+            if(terminals.size() != 2)
+                return false;
+            lines.remove(0);
+            isSimpleConnection = true;
+            for(RouteTerminal terminal : terminals)
+                terminal.line = null;
+            update();
+            return true;
+        }
+        
+        ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
+        for(RoutePoint point : line.points) {
+            /* Because line.terminal == null, there should be 
+             * not RouteTerminals 
+             * 
+             * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal. 
+             */
+        	if (point instanceof RouteLink) {
+	            RouteLine l = ((RouteLink)point).getOther(line);
+	            l.points.remove(point);
+	            if(!l.isTransient())
+	                nLines.add(l);
+        	}
+        }
+        
+        if(nLines.isEmpty())
+            return false;
+        RouteLine merged = nLines.remove(nLines.size()-1);
+        merged.position = position;
+        for(RouteLine l : nLines) {
+            for(RoutePoint point : l.points) {
+                /* Because l.terminal == null, there should be 
+                 * not RouteTerminals 
+                 * 
+                 * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal. 
+                 */
+            	if (point instanceof RouteLink) {
+	                RouteLink link = (RouteLink)point;
+	                link.replace(l, merged);
+            	}
+            }
+        }
+        THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
+        removedLines.addAll(nLines);
+        lines.removeAll(removedLines);
+        removedLines.add(line);
+        lines.remove(line);
+        for(RouteTerminal terminal : terminals)
+            if(removedLines.contains(terminal.line))
+                terminal.line = merged;
+        update();
+        return true;
+    }
+
+    public void deleteCorner(RouteLink link) {
+        if(needsUpdate)
+            update();
+        RouteLine a = link.getA();
+        RouteLine b = link.getB();
+        if(a.isTransient() || b.isTransient() 
+                || a.points.size() != 2 || b.points.size() != 2)
+            return;
+        RouteLine na=null, nb=null;
+        for(RoutePoint p : a.points) {
+            RouteLink l = (RouteLink)p;
+            if(l.a == a && l.b != b) {
+                na = l.b;
+                break;
+            }
+            else if(l.b == a && l.a != b) {
+                na = l.a;
+                break;
+            }
+        }        
+        for(RoutePoint p : b.points) {
+            RouteLink l = (RouteLink)p;
+            if(l.a == b && l.b != a) {
+                nb = l.b;
+                break;
+            }
+            else if(l.b == b && l.a != a) {
+                nb = l.a;
+                break;
+            }
+        }
+        if(na == null || nb == null) {
+            System.err.println("Internal error in router.");
+            return;
+        }
+        a.remove();
+        b.remove();
+        lines.remove(a);
+        lines.remove(b);
+        link(na, nb);
+        if(na.terminal != null)
+            na.terminal.line = nb;
+        if(nb.terminal != null)
+            nb.terminal.line = na;
+        update();
+    }
+    
+    public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
+        Object target = pick(x, y, tolerance);
+        if(target instanceof RouteLine) {
+            RouteLine line = (RouteLine)target;
+            RouteTerminal involvedTerminal = 
+                    line.isTransient() ? line.terminal : null;
+            makePersistent(line);
+            terminal.line = null; // TODO this is a workaround
+            
+            int lineDir = line.isHorizontal 
+                    ? (line.position < terminal.y ? 3 : 1)
+                    : (line.position < terminal.x ? 2 : 0)
+                    ;
+                    
+            if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
+                RouteLine l2;
+                if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
+                    RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
+                    l2 = addLine(false, x);
+                    link(terminal, l1, l2, line);
+                }
+                else {
+                    l2 = addLine(false, x);
+                    link(terminal, l2, line);
+                }
+                if(involvedTerminal != null)
+                    involvedTerminal.line = l2;
+            }
+            else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
+                RouteLine l2;
+                if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
+                    RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
+                    l2 = addLine(true, y);
+                    link(terminal, l1, l2, line);
+                }
+                else {
+                    l2 = addLine(true, y);
+                    link(terminal, l2, line);
+                }
+                if(involvedTerminal != null)
+                    involvedTerminal.line = l2;
+            }
+            else {
+                link(terminal, line);
+            }
+            update();
+            return true;
+        }
+        else
+            return false;
+    }
+    
+    public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
+        Object target = pick(x, y, tolerance);
+        if(target instanceof RouteLine) {
+            RouteLine line = (RouteLine)target;
+            RouteTerminal involvedTerminal = 
+                    line.isTransient() ? line.terminal : null;
+            makePersistent(line);
+            if(line.isHorizontal == sLine.isHorizontal) {
+                RouteLine l = addLine(!sLine.isHorizontal, 
+                        sLine.isHorizontal ? x : y); 
+                link(sLine, l, line);
+                if(involvedTerminal != null)
+                    involvedTerminal.line = l;
+            }
+            else {
+                link(sLine, line);
+                if(involvedTerminal != null)
+                    involvedTerminal.line = sLine;
+            }
+            update();
+            return true;
+        }
+        else
+            return false;
+    }
+
+    /**
+     * Makes a deep copy of the route graph and stores
+     * the correspondences between original and copied
+     * objects into the given map.
+     */
+    public RouteGraph copy(THashMap<Object, Object> map) {
+        RouteGraph copy = new RouteGraph();
+        copy.isSimpleConnection = isSimpleConnection;
+        copy.caseId = caseId;
+        copy.needsUpdate = needsUpdate;
+        for(RouteLine line : lines)
+            copy.lines.add(line.copy(map));
+        for(RouteLine line : transientLines)
+            copy.transientLines.add(line.copy(map));
+        for(RouteTerminal terminal : terminals)
+            copy.terminals.add(terminal.copy(map));
+        return copy;
+    }
+    
+    /**
+     * Makes a deep copy of the route graph.
+     */
+    public RouteGraph copy() {
+        THashMap<Object, Object> map = new THashMap<Object, Object>(); 
+        return copy(map);
+    }
+    
+    /**
+     * Removes route lines that are conneted to at most
+     * one other route line or terminal.
+     */
+    public void removeExtraConnections() {
+        TObjectIntHashMap<RouteLine> counts = 
+                new TObjectIntHashMap<RouteLine>();
+        removeTransientRouteLines();
+        for(RouteLine line : lines) {
+            int count = 0;
+            for(RoutePoint point : line.points)
+                if(point instanceof RouteLink)
+                    ++count;
+            counts.put(line, count);
+        }
+        for(RouteTerminal terminal : terminals)
+            counts.adjustOrPutValue(terminal.line, 1, 1);
+        boolean removed;
+        do {
+            removed = false;
+            Iterator<RouteLine> it = lines.iterator();
+            while(it.hasNext()) {
+                RouteLine line = it.next();
+                if(counts.get(line) <= 1) {
+                    for(RoutePoint point : line.points)
+                        if(point instanceof RouteLink)
+                            counts.adjustValue(((RouteLink)point).getOther(line), -1);
+                    line.remove();
+                    it.remove();
+                    removed = true;
+                }
+            }
+        } while(removed);
+        update();
+    }
+    
+    /**
+     * Removes a terminal and all route lines that become degenerated by the removal. 
+     */
+    public void remove(RouteTerminal terminal) {
+        terminals.remove(terminal);
+        removeExtraConnections();
+    }
+    
+    public void disconnect(RouteTerminal terminal) {
+        terminal.line = null;
+        removeExtraConnections();
+    }
+
+    public void remove(RouteLink link) {
+        link.a.points.remove(link);
+        link.b.points.remove(link);
+    }
+
+    public void toggleDirectLines(RouteTerminal terminal) {
+        terminal.toggleDirectLines();
+        needsUpdate = true;
+    }
+
+    /**
+     * Returns all persistent route lines of the route graph.
+     */
+    public Collection<RouteLine> getLines() {
+        if(needsUpdate)
+            update();
+        if(RETURN_UNMODIFIABLE_COLLECTIONS)
+            return Collections.unmodifiableList(lines);
+        else
+            return lines;
+    }
+
+    /*
+     * Returns all transient route lines of the route graph.
+     */
+    public Collection<RouteLine> getTransientLines() {
+        if(needsUpdate)
+            update();
+        if(RETURN_UNMODIFIABLE_COLLECTIONS)
+            return Collections.unmodifiableList(transientLines);
+        else
+            return transientLines;
+    }
+
+    /**
+     * Returns all terminals of the route graph.
+     */
+    public Collection<RouteTerminal> getTerminals() {
+        if(RETURN_UNMODIFIABLE_COLLECTIONS)
+            return Collections.unmodifiableList(terminals);
+        else
+            return terminals;
+    }
+    
+    /**
+     * Returns all route lines, both persistent and transient,
+     * of the route graph.
+     */
+    public Collection<RouteLine> getAllLines() {
+        if(needsUpdate)
+            update();
+        ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
+        allLines.addAll(lines);
+        allLines.addAll(transientLines);
+        return allLines;
+    }
+    
+    /**
+     * Returns all route lines, both persistent and transient, of the route
+     * graph, added to the specified collection. Avoids allocation of new
+     * {@link ArrayList} compared to {@link #getAllLines()}.
+     */
+    public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
+        if (result == null)
+            throw new NullPointerException("null result collection");
+        if(needsUpdate)
+            update();
+        result.addAll(lines);
+        result.addAll(transientLines);
+        return result;
+    }
+    
+    /**
+     * Returns true, if the route graph is connected and contains no cycles.
+     */
+    public boolean isTree() {
+        if(isSimpleConnection)
+            return true;
+        for(RouteTerminal terminal : terminals)
+            if(terminal.line == null)
+                return false;
+        THashSet<RouteLine> visited = new THashSet<RouteLine>(); 
+        ArrayList<RouteLine> stack = new ArrayList<RouteLine>(); 
+        int linkCount = 0;
+        visited.add(lines.get(0));
+        stack.add(lines.get(0));
+        while(!stack.isEmpty()) {
+            RouteLine cur = stack.remove(stack.size()-1);
+            for(RouteLine n : cur.getPersistentNeighbors()) {
+                ++linkCount;
+                if(visited.add(n))
+                    stack.add(n);
+            }
+        }
+        return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
+    }
+    
+    /**
+     * Returns if the connection is simple. A connection is simple, if it has just
+     * two terminals connected together directly without (persistent) route lines.
+     */
+    public boolean isSimpleConnection() {
+        return isSimpleConnection;
+    }
+
+    public void replaceBy(RouteGraph rg) {
+        this.lines = rg.lines;
+        this.terminals = rg.terminals;
+        this.transientLines = rg.transientLines;
+        this.caseId = rg.caseId;
+        this.isSimpleConnection = rg.isSimpleConnection;
+        this.needsUpdate = rg.needsUpdate;
+        rg.reset();
+    }
+
+    private void reset() {
+        lines = new ArrayList<RouteLine>();
+        terminals = new ArrayList<RouteTerminal>();
+        transientLines = new ArrayList<RouteLine>();
+        caseId = 0;
+        isSimpleConnection = false;
+        needsUpdate = false;
+    }
+
+    public Rectangle2D getBounds() {
+        Rectangle2D bounds = new Rectangle2D.Double();
+        getBounds(bounds);
+        return bounds;
+    }
+
+    public void getBounds(Rectangle2D bounds) {
+        if(needsUpdate)
+            update();
+        double minX = Double.POSITIVE_INFINITY;
+        double maxX = Double.NEGATIVE_INFINITY;
+        double minY = Double.POSITIVE_INFINITY;
+        double maxY = Double.NEGATIVE_INFINITY;
+        for(RouteLine line : lines) {
+            double position = line.position;
+            if(line.isHorizontal) {
+                minY = Math.min(minY, position);
+                maxY = Math.max(maxY, position);
+            }
+            else {
+                minX = Math.min(minX, position);
+                maxX = Math.max(maxX, position);
+            }
+        }
+        for(RouteLine line : transientLines) {
+            double position = line.position;
+            if(line.isHorizontal) {
+                minY = Math.min(minY, position);
+                maxY = Math.max(maxY, position);
+            }
+            else {
+                minX = Math.min(minX, position);
+                maxX = Math.max(maxX, position);
+            }
+        }
+        for(RouteTerminal terminal : terminals) {
+            double x = terminal.x;
+            double y = terminal.y;
+            minX = Math.min(minX, x);
+            maxX = Math.max(maxX, x);
+            minY = Math.min(minY, y);
+            maxY = Math.max(maxY, y);
+        }
+        bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
+    }
+
+    private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
+        double x = cur.x, y = cur.y;
+        if(cur instanceof RouteTerminal) {
+            ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
+            if(line.isHorizontal()) {
+                if(cur == line.getBegin())
+                    x += style.getLineEndLength(0);
+                else
+                    x -= style.getLineEndLength(2);
+            }
+            else {
+                if(cur == line.getBegin())
+                    y += style.getLineEndLength(1);
+                else
+                    y -= style.getLineEndLength(3);
+            }
+        }
+        path.moveTo(x, y);
+    }
+    
+    private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
+        double x = cur.x, y = cur.y;
+        if(cur instanceof RouteTerminal) {
+            ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
+            if(line.isHorizontal()) {
+                if(cur == line.getBegin())
+                    x += style.getLineEndLength(0);
+                else
+                    x -= style.getLineEndLength(2);
+            }
+            else {
+                if(cur == line.getBegin())
+                    y += style.getLineEndLength(1);
+                else
+                    y -= style.getLineEndLength(3);
+            }
+        }
+        path.lineTo(x, y);
+    }
+    
+    public void getPath2D(Path2D path) {
+        if(needsUpdate)
+            update();
+        
+        if(isSimpleConnection && transientLines.isEmpty()) {
+            if(terminals.size() == 2) {
+                RouteTerminal a = terminals.get(0);
+                RouteTerminal b = terminals.get(1);
+                if(a.hasDirectConnection() || b.hasDirectConnection()) {
+                    path.moveTo(a.x, a.y);
+                    path.lineTo(b.x, b.y);
+                    return;
+                }
+            }
+        }
+
+        // Analyze graph
+        THashMap<RoutePoint, RouteLine> begins = 
+                new THashMap<RoutePoint, RouteLine>();
+        for(RouteLine line : lines) {
+            add(begins, line);
+        }
+        for(RouteLine line : transientLines) {
+            add(begins, line);
+        }
+        for(RouteTerminal terminal : terminals)
+            if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
+                begins.remove(terminal.line.getBegin());
+                drawContinuousPath(path, begins, terminal, terminal.line);
+            }
+
+        // Create paths
+        for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
+            RouteLine curLine = begins.remove(begin);
+            drawContinuousPath(path, begins, begin, curLine);
+        }
+    }
+    
+    private void drawContinuousPath(Path2D path, THashMap<RoutePoint, RouteLine> begins,
+            RoutePoint cur, RouteLine curLine) {
+        if(curLine == null)
+            return;
+        addPathBegin(path, cur, curLine);
+
+        while(true) {
+            if(cur != curLine.getEnd())                    
+                cur = curLine.getEnd();
+            else
+                cur = curLine.getBegin();
+            if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
+                addPathEnd(path, cur, curLine);
+                return;
+            }
+            if(cur instanceof RouteLink) {
+                if(!curLine.isDegenerated() || 
+                        path.getCurrentPoint().getX() != cur.x || 
+                        path.getCurrentPoint().getY() != cur.y)
+                    path.lineTo(cur.x, cur.y);
+                RouteLink link = (RouteLink)cur;
+                if(link.a != curLine)
+                    curLine = link.a;
+                else
+                    curLine = link.b;
+            }
+        }
+    }
+
+    private static void add(THashMap<RoutePoint, RouteLine> begins,
+            RouteLine line) { 
+        if(line.points.size() > 1) {
+            {
+                RoutePoint p = line.getBegin();
+                if(begins.remove(p) == null)
+                    begins.put(p, line);
+            }
+            {
+                RoutePoint p = line.getEnd();
+                if(begins.remove(p) == null)
+                    begins.put(p, line);
+            }
+        }
+    }
+
+    public Collection<Segment> getSegments() {
+        if (needsUpdate)
+            update();
+        ArrayList<Segment> segments = new ArrayList<Segment>();
+        for(RouteLine routeLine : lines)
+            routeLine.collectSegments(segments);
+        for(RouteLine routeLine : transientLines)
+            routeLine.collectSegments(segments);
+        return segments;
+    }
+
+    public Path2D getPath2D() {
+        Path2D result = new Path2D.Double();
+        getPath2D(result);
+        return result;
+    }
+    
+    public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
+        THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
+        THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
+        THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
+        THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
+        THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
+        THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
+
+        if(splitLine.isTransient()) {
+            RouteTerminal terminal = splitLine.terminal;
+            
+            if(splitLine.beginsWithTerminal()) {
+                lines2.addAll(getLines());
+                terminals2.addAll(getTerminals());
+                terminals1.add(terminal);
+                terminals2.remove(terminal);
+                interfaceNodes1.add(terminal);
+                if(isSimpleConnection())
+                    interfaceNodes2.addAll(terminals2);
+                else
+                    interfaceNodes2.add(terminal.line);
+            }
+            else {
+                lines1.addAll(getLines());
+                terminals1.addAll(getTerminals());
+                terminals2.add(terminal);
+                terminals1.remove(terminal);
+                interfaceNodes2.add(terminal);
+                if(isSimpleConnection())
+                    interfaceNodes1.addAll(terminals1);
+                else
+                    interfaceNodes1.add(terminal.line);
+            }
+        }
+        else {
+            for(RoutePoint rp : splitLine.getPoints()) {
+                double p = splitLine.isHorizontal ? rp.x : rp.y;
+                if(rp instanceof RouteLink) {
+                    RouteLink link = (RouteLink)rp;
+                    RouteLine otherLine = link.getA() != splitLine ? link.getA()
+                            : link.getB();
+                    if(otherLine.isTransient()) {
+                        if(p < position) {
+                            interfaceNodes1.add(otherLine.terminal);
+                            terminals1.add(otherLine.terminal);
+                        }
+                        else {
+                            interfaceNodes2.add(otherLine.terminal);
+                            terminals2.add(otherLine.terminal);
+                        }
+                        continue;
+                    }                
+                
+                    if(p < position) {
+                        interfaceNodes1.add(otherLine);
+                        traverseGraph(link, otherLine, lines1);
+                    }
+                    else {
+                        interfaceNodes2.add(otherLine);
+                        traverseGraph(link, otherLine, lines2);
+                    }   
+                }
+            }
+            
+            for(RouteTerminal terminal : getTerminals())
+                if(lines1.contains(terminal.line))
+                    terminals1.add(terminal);
+                else if(lines2.contains(terminal.line))
+                    terminals2.add(terminal);        
+        }
+        
+        return new SplittedRouteGraph(splitLine, 
+                interfaceNodes1, lines1, terminals1, 
+                interfaceNodes2, lines2, terminals2);
+    }
+
+    private void traverseGraph(RoutePoint previousPoint, RouteLine line,
+            THashSet<RouteLine> lines) {
+        if(lines.add(line)) {
+            for(RoutePoint rp : line.getPoints()) {
+                if(rp != previousPoint && rp instanceof RouteLink) {
+                    RouteLink link = (RouteLink)rp;
+                    RouteLine otherLine = line != link.getA() 
+                            ? link.getA() : link.getB();
+                    if(otherLine.isTransient())
+                        continue;
+                    traverseGraph(rp, otherLine, lines);
+                }
+            }
+        }
+    }
+    
+    public void reclaimTransientMemory() {
+    	removeTransientRouteLines();
+    	needsUpdate = true;
+    }
+
+}