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