1 /*******************************************************************************
2 * Copyright (c) 2011 Association for Decentralized Information Management in
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.diagram.connection;
14 import java.awt.geom.Line2D;
15 import java.awt.geom.Path2D;
16 import java.awt.geom.Point2D;
17 import java.awt.geom.Rectangle2D;
18 import java.io.PrintStream;
19 import java.io.Serializable;
20 import java.util.ArrayList;
21 import java.util.Collection;
22 import java.util.Collections;
23 import java.util.Comparator;
24 import java.util.HashMap;
25 import java.util.Iterator;
27 import java.util.stream.Collectors;
29 import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
30 import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
31 import org.simantics.diagram.connection.segments.Segment;
32 import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
34 import gnu.trove.list.array.TDoubleArrayList;
35 import gnu.trove.map.hash.THashMap;
36 import gnu.trove.map.hash.TObjectIntHashMap;
37 import gnu.trove.set.hash.THashSet;
39 public class RouteGraph implements Serializable {
41 private static final long serialVersionUID = 2004022454972623908L;
43 public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
44 public static final boolean CHECK_PARAMERS = true;
46 protected ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
47 protected ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
48 protected ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
50 protected boolean isSimpleConnection;
51 protected boolean needsUpdate = false;
53 public void updateTerminals() {
54 boolean changed = false;
55 for(RouteTerminal terminal : terminals)
56 changed |= terminal.updateDynamicPosition();
61 * Adds a route line to the graph.
62 * @param isHorizontal true, if the line is horizontal
63 * @param position y coordinate of the line if horizontal, x coordinate if vertical
64 * @return The new line.
66 public RouteLine addLine(boolean isHorizontal, double position) {
67 RouteLine line = new RouteLine(isHorizontal, position);
73 * Adds a route terminal to the graph.
74 * @param x The location of the terminal.
76 * @param minX The avoidance area of the terminal.
80 * @param allowedDirections Allowed directions.
81 * First four bits tell with which directions
82 * a connection can leave the terminal. The
83 * Fifth bit indicates whether direct lines
84 * can be drawn to the terminal. Directions are
91 * @param style Tells what kind of line end is drawn
93 * @param position a provider for a dynamic position for the terminal or
94 * <code>null</code> if terminal position is not dynamic
95 * @return The new terminal.
97 public RouteTerminal addTerminal(double x, double y,
98 double minX, double minY,
99 double maxX, double maxY,
100 int allowedDirections,
101 ILineEndStyle style, RouteTerminalPosition position) {
102 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, position);
105 public RouteTerminal addTerminal(double x, double y,
106 double minX, double minY,
107 double maxX, double maxY,
108 int allowedDirections,
109 ILineEndStyle style) {
110 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, null);
113 public RouteTerminal addTerminal(double x, double y,
114 double minX, double minY,
115 double maxX, double maxY,
116 int allowedDirections,
117 ILineEndStyle style, ILineEndStyle dynamicStyle, RouteTerminalPosition position) {
119 if(allowedDirections > 0x1f)
120 throw new IllegalArgumentException("Illegal allowedDirection flags.");
121 if(minX > x || x > maxX || minY > y || y > maxY)
122 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
125 style = PlainLineEndStyle.INSTANCE;
126 RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
127 maxX, maxY, allowedDirections, false, style, position);
128 terminal.setDynamicStyle(dynamicStyle);
129 terminals.add(terminal);
133 public RouteTerminal addBigTerminal(
134 double minX, double minY,
135 double maxX, double maxY,
136 ILineEndStyle style) {
137 return addBigTerminal(minX, minY, maxX, maxY, style, null);
139 public RouteTerminal addBigTerminal(
140 double minX, double minY,
141 double maxX, double maxY,
142 ILineEndStyle style, ILineEndStyle dynamicStyle) {
144 style = PlainLineEndStyle.INSTANCE;
145 RouteTerminal terminal = new RouteTerminal(
146 0.5*(minX+maxX), 0.5*(minY+maxY),
149 0xf, true, style, null);
150 terminal.setDynamicStyle(dynamicStyle);
152 terminals.add(terminal);
157 * Adds a route terminal to the graph. The avoidance
158 * area is given as a rectangle.
159 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
161 public RouteTerminal addTerminal(double x, double y,
163 int allowedDirections,
164 ILineEndStyle style) {
165 return addTerminal(x, y,
166 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
167 allowedDirections, style, null);
171 * Adds a copy of the given terminal to the graph.
173 public RouteTerminal addTerminal(RouteTerminal terminal) {
174 RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
175 terminal.getMinX(), terminal.getMinY(),
176 terminal.getMaxX(), terminal.getMaxY(),
177 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle(), terminal.getDynamicPosition());
178 newTerminal.setData(terminal.getData());
183 * Adds a route terminal to the graph. A default line end style is used.
184 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
186 public RouteTerminal addTerminal(double x, double y,
187 double minX, double minY,
188 double maxX, double maxY,
189 int allowedDirections) {
190 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
191 PlainLineEndStyle.INSTANCE, null);
197 public void link(RouteNode node1, RouteNode node2) {
198 if(node1 instanceof RouteLine) {
199 if(node2 instanceof RouteLine) {
200 link((RouteLine)node1, (RouteLine)node2);
203 link((RouteLine)node1, (RouteTerminal)node2);
207 if(node2 instanceof RouteLine) {
208 link((RouteTerminal)node1, (RouteLine)node2);
211 link((RouteTerminal)node1, (RouteTerminal)node2);
219 public void link(RouteNode ... nodes) {
220 for(int i=1;i<nodes.length;++i)
221 link(nodes[i-1], nodes[i]);
227 public void link(RouteLine node1, RouteLine node2) {
228 new RouteLink(node1, node2);
233 * Links a terminal and a line.
235 public void link(RouteTerminal node1, RouteLine node2) {
238 throw new NullPointerException();
239 if(node1.line != null)
240 throw new IllegalStateException("Terminal is already connected.");
247 * Links a line and a terminal.
249 public void link(RouteLine node1, RouteTerminal node2) {
252 throw new NullPointerException();
253 if(node2.line != null)
254 throw new IllegalStateException("Terminal is already connected.");
261 * Links two terminals.
263 public void link(RouteTerminal node1, RouteTerminal node2) {
266 throw new NullPointerException();
268 throw new NullPointerException();
270 isSimpleConnection = true;
274 protected void removeTransientRouteLines() {
275 for(RouteLine line : transientLines)
277 transientLines.clear();
281 * Rotates given terminal clockwise by given amount
282 * (also negative numbers are allowed).
284 public void rotate(RouteTerminal terminal, int amount) {
285 terminal.rotate(amount);
290 * Moves the given route line so that its position correspond
291 * to given x or y depending on the orientation of the line.
293 public void setLocation(RouteLine line, double x, double y) {
294 makePersistent(line);
295 line.setLocation(x, y);
300 * Moves the terminal to given location.
302 public void setLocation(RouteTerminal terminal, double x, double y) {
303 terminal.setLocation(x, y);
308 * Updates transient route lines, route link positions
309 * and sorts route points of each route line.
311 public void update() {
313 removeTransientRouteLines();
317 for(RouteLine line : lines)
319 for(RouteTerminal terminal : terminals)
320 if(terminal.hasDirectConnection() && terminal.line != null)
321 terminal.line.hidden = true;
324 if(isSimpleConnection) {
325 RouteTerminal a = terminals.get(0);
326 RouteTerminal b = terminals.get(1);
327 if(a.hasDirectConnection() || b.hasDirectConnection())
329 caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
330 //System.out.println("caseId = " + caseId);
332 case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
333 case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
334 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
335 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
339 transientLines.add(line);
347 case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
348 RouteLine line1 = new RouteLine(true, a.y);
349 RouteLine line2 = new RouteLine(false, b.x);
350 new RouteLink(line1, line2);
355 transientLines.add(line1);
356 transientLines.add(line2);
363 case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
364 RouteLine line1 = new RouteLine(false, a.x);
365 RouteLine line2 = new RouteLine(true, b.y);
366 new RouteLink(line1, line2);
371 transientLines.add(line1);
372 transientLines.add(line2);
379 case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
380 case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
382 SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
383 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
385 terminals.get(0).line = line;
386 terminals.get(1).line = line;
387 transientLines.add(line);
388 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
392 //routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
395 caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
396 routeFromTerminals(false);
399 // Find positions of route points
400 for(RouteLine line : lines)
401 line.setPointPositions();
402 for(RouteLine line : transientLines)
403 line.setPointPositions();
405 // Sort route points in route lines
406 for(RouteLine line : lines) {
409 for(RouteLine line : transientLines) {
414 public static class Interval {
415 public final double min;
416 public final double max;
417 public Interval(double min, double max) {
423 public class IntervalCache {
424 THashMap<RouteLine, Interval> cache =
425 new THashMap<RouteLine, Interval>();
426 public Interval get(RouteLine line) {
427 Interval result = cache.get(line);
431 result = create(line);
432 cache.put(line, result);
436 private Interval create(RouteLine line) {
437 double min = Double.POSITIVE_INFINITY;
438 double max = Double.NEGATIVE_INFINITY;
440 for(RoutePoint point : line.points) {
442 if(point instanceof RouteLink) {
443 RouteLink link = (RouteLink)point;
445 temp = link.b.position;
447 temp = link.a.position;
450 RouteTerminal terminal = (RouteTerminal)point;
451 if(line.isHorizontal)
461 for(RouteTerminal terminal : terminals) {
462 if(terminal.line == line) {
463 double temp = terminal.approximatePositionToLine();
471 return new Interval(min, max);
475 protected void routeFromTerminals(boolean boundingBoxesIntersect) {
476 IntervalCache cache = new IntervalCache();
477 for(RouteTerminal terminal : terminals)
478 if(terminal.line != null) {
479 if(!terminal.hasDirectConnection())
480 terminal.route(transientLines, cache, boundingBoxesIntersect);
485 * Returns a RouteLine near the given point (x,y) (within tolerance).
487 public RouteLine pickLine(double x, double y, double tolerance, int mask) {
490 if(isSimpleConnection && transientLines.isEmpty()) {
491 if(terminals.size() == 2) {
492 if((mask & PICK_TRANSIENT_LINES) == 0)
494 RouteTerminal a = terminals.get(0);
495 RouteTerminal b = terminals.get(1);
496 if(a.hasDirectConnection() || b.hasDirectConnection()) {
497 if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
498 RouteLine dummy = new RouteLine(false, y);
499 return dummy; // There are no lines to return
506 if((mask & PICK_PERSISTENT_LINES) != 0)
507 for(RouteLine line : lines)
508 if(line.isNear(x, y, tolerance))
510 if((mask & PICK_TRANSIENT_LINES) != 0)
511 for(RouteLine line : transientLines)
512 if(line.isNear(x, y, tolerance))
514 if((mask & PICK_DIRECT_LINES) != 0) {
515 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
517 return terminal.line;
522 public RouteLine pickLine(double x, double y, double tolerance) {
523 return pickLine(x, y, tolerance, PICK_LINES);
526 private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
527 double toleranceSq = tolerance * tolerance;
528 for(RouteTerminal terminal : terminals)
529 if((terminal.getAllowedDirections()&0x10) != 0) {
531 RouteLine line = terminal.getLine();
534 RoutePoint b = line.getBegin();
535 double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
536 if(distSq <= toleranceSq) {
537 //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
540 } catch(NullPointerException e) {
541 //if terminal does not have a line
543 } catch(IndexOutOfBoundsException e) {
544 // if line does not contain points
551 public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
552 if(isSimpleConnection)
556 RouteLine line = pickLine(x, y, tolerance);
559 RouteLink link = null;
560 RoutePoint begin = line.getBegin();
561 RoutePoint end = line.getEnd();
562 if(line.isHorizontal) {
563 double mx = 0.5*(begin.getX() + end.getX());
565 if(begin instanceof RouteLink)
566 link = (RouteLink)begin;
569 if(end instanceof RouteLink)
570 link = (RouteLink)line.getEnd();
574 double my = 0.5*(begin.getY() + end.getY());
576 if(begin instanceof RouteLink)
577 link = (RouteLink)begin;
580 if(end instanceof RouteLink)
581 link = (RouteLink)end;
586 if(link.getOther(line).isTransient())
588 return new RouteLineHalf(line, link);
591 public Collection<RouteLineHalf> getLineHalves() {
592 return getLineHalves(new ArrayList<RouteLineHalf>());
595 public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
596 for(RouteLine line : getAllLines()) {
598 RoutePoint p = line.getBegin();
599 if(p instanceof RouteLink) {
600 RouteLink link = (RouteLink)p;
601 if(!link.getOther(line).isTransient())
602 result.add(new RouteLineHalf(line, link));
606 RoutePoint p = line.getEnd();
607 if(p instanceof RouteLink) {
608 RouteLink link = (RouteLink)p;
609 if(!link.getOther(line).isTransient())
610 result.add(new RouteLineHalf(line, link));
618 * Returns a RoutePoint near the given point (x,y) (within tolerance).
620 public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
623 if((mask&PICK_TERMINALS) != 0)
624 for(RouteTerminal terminal : terminals)
625 if(terminal.isNear(x, y))
627 if((mask&PICK_INTERIOR_POINTS) != 0) {
628 for(RouteLine line : lines) {
629 for(RoutePoint point : line.points)
630 if(point.isNear(x, y, tolerance))
633 for(RouteLine line : transientLines) {
634 for(RoutePoint point : line.points)
635 if(point.isNear(x, y, tolerance))
642 public RoutePoint pickPoint(double x, double y, double tolerance) {
643 return pickPoint(x, y, tolerance, PICK_POINTS);
646 public static final int PICK_INTERIOR_POINTS = 1;
647 public static final int PICK_TERMINALS = 2;
648 public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
650 public static final int PICK_PERSISTENT_LINES = 4;
651 public static final int PICK_TRANSIENT_LINES = 8;
652 public static final int PICK_DIRECT_LINES = 16;
653 public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
655 public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
658 * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
660 public Object pick(double x, double y, double tolerance, int mask) {
661 if((mask & PICK_POINTS) != 0) {
662 Object point = pickPoint(x, y, tolerance, mask);
666 /*if((mask & PICK_DIRECT_LINES) != 0) {
667 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
669 return terminal.line.getBegin();
671 if((mask & PICK_LINES) != 0)
672 return pickLine(x, y, tolerance, mask);
677 public Object pick(double x, double y, double tolerance) {
678 return pick(x, y, tolerance, PICK_ALL);
682 * Returns RoutePoint or RouteLine exactly under the given point (x,y).
684 public Object pick(double x, double y) {
685 return pick(x, y, 0.0);
689 * Prints the contents of the route graph to stdout.
691 public void print() {
696 * Prints the contents of the route graph to given print stream.
698 public void print(PrintStream out) {
701 if(isSimpleConnection)
702 out.println("=== SIMPLE CONNECTION ===");
704 out.println("=== COMPLEX CONNECTION ===");
705 for(RouteLine line : lines) {
709 for(RouteLine line : transientLines) {
713 for(RouteTerminal terminal : terminals) {
719 public void makePersistent(RouteLine line) {
720 prepareForModification();
721 if(isSimpleConnection || line.isTransient()) {
722 if(isSimpleConnection) {
723 isSimpleConnection = false;
724 for(RouteTerminal terminal : terminals)
725 terminal.line = line;
726 transientLines.remove(line);
728 Iterator<RoutePoint> it = line.points.iterator();
729 while(it.hasNext()) {
730 RoutePoint point = it.next();
731 if(point instanceof RouteTerminal)
734 line.terminal = null;
735 line.nextTransient = null;
738 line.terminal.line = line;
740 transientLines.remove(line);
742 Iterator<RoutePoint> it = line.points.iterator();
743 while(it.hasNext()) {
744 RoutePoint point = it.next();
745 if(point instanceof RouteTerminal)
748 line.terminal = null;
749 RouteLine temp = line.nextTransient;
750 line.nextTransient = null;
752 } while(line != null);
758 void prepareForModification() {
760 RouteLine line = transientLines.remove(0);
761 line.terminal = null;
763 for(RouteTerminal terminal : terminals)
764 terminal.line = line;
765 isSimpleConnection = false;
770 public double[] getLineLengths(RouteTerminal terminal) {
773 if(lines.size()==0 && transientLines.size()==1)
774 return new double[] { transientLines.get(0).getLength() };
776 RouteLine line = null;
778 for(RouteLine l : transientLines)
779 if(l.isTransient()) {
780 for(RoutePoint p : l.points)
781 if(!(p instanceof RouteLink)) {
786 TDoubleArrayList result = new TDoubleArrayList();
787 THashSet<RouteLine> set = new THashSet<RouteLine>();
791 result.add(line.getLength());
792 for(RoutePoint point : line.points)
793 if(point instanceof RouteLink) {
794 RouteLink link = (RouteLink)point;
795 if(set.add(link.a)) {
799 if(set.add(link.b)) {
806 return result.toArray();
809 public void split(RouteLine rl1, double splitPosition) {
812 boolean isHorizontal = rl1.isHorizontal();
813 if(isSimpleConnection) {
814 isSimpleConnection = false;
816 RouteLine sp = addLine(!isHorizontal, splitPosition);
817 for(RouteTerminal terminal : terminals)
822 else if(caseId < 4) {
823 RouteLine sp = addLine(!isHorizontal, splitPosition);
824 RouteLine l = addLine(isHorizontal, rl1.position);
826 rl1.terminal.line = sp;
827 for(RouteTerminal terminal : terminals)
828 if(terminal != rl1.terminal)
834 prepareForModification();
837 RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
838 RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
840 ArrayList<RoutePoint> points = rl1.points;
845 int maxPos = points.size();
846 while(minPos != maxPos) {
847 int c = (minPos + maxPos)/2;
849 ? points.get(c).getX() > splitPosition
850 : points.get(c).getY() > splitPosition)
858 for(int i=points.size()-1;i>=splitPos;--i) {
859 RoutePoint point = points.remove(i);
860 if(point instanceof RouteLink) {
861 RouteLink link = (RouteLink)point;
862 link.replace(rl1, rl2);
866 if(rl1.isTransient()) {
867 boolean p1 = rl1.isConnectedToPeristentLine();
868 boolean p2 = rl2.isConnectedToPeristentLine();
870 RouteTerminal terminal = rl1.terminal;
873 transientLines.add(rl2);
879 transientLines.add(rl2);
881 for(RouteTerminal t : terminals)
889 new RouteLink(rl1, sp);
890 new RouteLink(sp, rl2);
895 public boolean merge(RouteLine line) {
898 for(RoutePoint point : line.points) {
899 if(point instanceof RouteLink) {
900 RouteLink link = (RouteLink)point;
901 RouteLine other = link.getOther(line);
902 if(!other.isTransient()) {
903 sum += other.position;
908 return merge(line, sum / count);
912 * Removes given route line and collapses all its neighbor
913 * route lines into one line with given position.
915 public boolean merge(RouteLine line, double position) {
918 if(isSimpleConnection || line.isTransient())
921 if(lines.size() == 1) {
922 if(terminals.size() != 2)
925 isSimpleConnection = true;
926 for(RouteTerminal terminal : terminals)
927 terminal.line = null;
932 ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
933 for(RoutePoint point : line.points) {
934 /* Because line.terminal == null, there should be
937 * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
939 if (point instanceof RouteLink) {
940 RouteLine l = ((RouteLink)point).getOther(line);
941 l.points.remove(point);
949 RouteLine merged = nLines.remove(nLines.size()-1);
950 merged.position = position;
951 for(RouteLine l : nLines) {
952 for(RoutePoint point : l.points) {
953 /* Because l.terminal == null, there should be
956 * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
958 if (point instanceof RouteLink) {
959 RouteLink link = (RouteLink)point;
960 link.replace(l, merged);
964 THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
965 removedLines.addAll(nLines);
966 lines.removeAll(removedLines);
967 removedLines.add(line);
969 for(RouteTerminal terminal : terminals)
970 if(removedLines.contains(terminal.line))
971 terminal.line = merged;
976 public void deleteCorner(RouteLink link) {
979 RouteLine a = link.getA();
980 RouteLine b = link.getB();
981 if(a.isTransient() || b.isTransient()
982 || a.points.size() != 2 || b.points.size() != 2)
984 RouteLine na=null, nb=null;
985 for(RoutePoint p : a.points) {
986 RouteLink l = (RouteLink)p;
987 if(l.a == a && l.b != b) {
991 else if(l.b == a && l.a != b) {
996 for(RoutePoint p : b.points) {
997 RouteLink l = (RouteLink)p;
998 if(l.a == b && l.b != a) {
1002 else if(l.b == b && l.a != a) {
1007 if(na == null || nb == null) {
1008 System.err.println("Internal error in router.");
1016 if(na.terminal != null)
1017 na.terminal.line = nb;
1018 if(nb.terminal != null)
1019 nb.terminal.line = na;
1023 public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
1024 Object target = pick(x, y, tolerance);
1025 if(target instanceof RouteLine) {
1026 RouteLine line = (RouteLine)target;
1027 RouteTerminal involvedTerminal =
1028 line.isTransient() ? line.terminal : null;
1029 makePersistent(line);
1030 terminal.line = null; // TODO this is a workaround
1032 int lineDir = line.isHorizontal
1033 ? (line.position < terminal.y ? 3 : 1)
1034 : (line.position < terminal.x ? 2 : 0)
1037 if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1039 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1040 RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1041 l2 = addLine(false, x);
1042 link(terminal, l1, l2, line);
1045 l2 = addLine(false, x);
1046 link(terminal, l2, line);
1048 if(involvedTerminal != null)
1049 involvedTerminal.line = l2;
1051 else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1053 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1054 RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1055 l2 = addLine(true, y);
1056 link(terminal, l1, l2, line);
1059 l2 = addLine(true, y);
1060 link(terminal, l2, line);
1062 if(involvedTerminal != null)
1063 involvedTerminal.line = l2;
1066 link(terminal, line);
1075 public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1076 Object target = pick(x, y, tolerance);
1077 if(target instanceof RouteLine) {
1078 RouteLine line = (RouteLine)target;
1079 RouteTerminal involvedTerminal =
1080 line.isTransient() ? line.terminal : null;
1081 makePersistent(line);
1082 if(line.isHorizontal == sLine.isHorizontal) {
1083 RouteLine l = addLine(!sLine.isHorizontal,
1084 sLine.isHorizontal ? x : y);
1085 link(sLine, l, line);
1086 if(involvedTerminal != null)
1087 involvedTerminal.line = l;
1091 if(involvedTerminal != null)
1092 involvedTerminal.line = sLine;
1102 * Makes a deep copy of the route graph and stores
1103 * the correspondences between original and copied
1104 * objects into the given map.
1106 public RouteGraph copy(THashMap<Object, Object> map) {
1107 RouteGraph copy = new RouteGraph();
1108 copy.isSimpleConnection = isSimpleConnection;
1109 copy.caseId = caseId;
1110 copy.needsUpdate = needsUpdate;
1111 for(RouteLine line : lines)
1112 copy.lines.add(line.copy(map));
1113 for(RouteLine line : transientLines)
1114 copy.transientLines.add(line.copy(map));
1115 for(RouteTerminal terminal : terminals)
1116 copy.terminals.add(terminal.copy(map));
1121 * Makes a deep copy of the route graph.
1123 public RouteGraph copy() {
1124 THashMap<Object, Object> map = new THashMap<Object, Object>();
1129 * Removes route lines that are conneted to at most
1130 * one other route line or terminal.
1132 public void removeExtraConnections() {
1133 TObjectIntHashMap<RouteLine> counts =
1134 new TObjectIntHashMap<RouteLine>();
1135 removeTransientRouteLines();
1136 for(RouteLine line : lines) {
1138 for(RoutePoint point : line.points)
1139 if(point instanceof RouteLink)
1141 counts.put(line, count);
1143 for(RouteTerminal terminal : terminals)
1144 counts.adjustOrPutValue(terminal.line, 1, 1);
1148 Iterator<RouteLine> it = lines.iterator();
1149 while(it.hasNext()) {
1150 RouteLine line = it.next();
1151 if(counts.get(line) <= 1) {
1152 for(RoutePoint point : line.points)
1153 if(point instanceof RouteLink)
1154 counts.adjustValue(((RouteLink)point).getOther(line), -1);
1165 * Removes a terminal and all route lines that become degenerated by the removal.
1167 public void remove(RouteTerminal terminal) {
1168 terminals.remove(terminal);
1169 removeExtraConnections();
1172 public void disconnect(RouteTerminal terminal) {
1173 terminal.line = null;
1174 removeExtraConnections();
1177 public void remove(RouteLink link) {
1178 link.a.points.remove(link);
1179 link.b.points.remove(link);
1182 public void toggleDirectLines(RouteTerminal terminal) {
1183 terminal.toggleDirectLines();
1188 * Returns all persistent route lines of the route graph.
1190 public Collection<RouteLine> getLines() {
1193 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1194 return Collections.unmodifiableList(lines);
1200 * Returns all transient route lines of the route graph.
1202 public Collection<RouteLine> getTransientLines() {
1205 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1206 return Collections.unmodifiableList(transientLines);
1208 return transientLines;
1212 * Returns all terminals of the route graph.
1214 public Collection<RouteTerminal> getTerminals() {
1215 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1216 return Collections.unmodifiableList(terminals);
1222 * Returns all route lines, both persistent and transient,
1223 * of the route graph.
1225 public Collection<RouteLine> getAllLines() {
1228 ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1229 allLines.addAll(lines);
1230 allLines.addAll(transientLines);
1235 * Returns all route lines, both persistent and transient, of the route
1236 * graph, added to the specified collection. Avoids allocation of new
1237 * {@link ArrayList} compared to {@link #getAllLines()}.
1239 public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1241 throw new NullPointerException("null result collection");
1244 result.addAll(lines);
1245 result.addAll(transientLines);
1250 * Returns true, if the route graph is connected and contains no cycles.
1252 public boolean isTree() {
1253 if(isSimpleConnection)
1255 for(RouteTerminal terminal : terminals)
1256 if(terminal.line == null)
1258 THashSet<RouteLine> visited = new THashSet<RouteLine>();
1259 ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1261 visited.add(lines.get(0));
1262 stack.add(lines.get(0));
1263 while(!stack.isEmpty()) {
1264 RouteLine cur = stack.remove(stack.size()-1);
1265 for(RouteLine n : cur.getPersistentNeighbors()) {
1271 return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1275 * Returns if the connection is simple. A connection is simple, if it has just
1276 * two terminals connected together directly without (persistent) route lines.
1278 public boolean isSimpleConnection() {
1279 return isSimpleConnection;
1282 public void replaceBy(RouteGraph rg) {
1283 this.lines = rg.lines;
1284 this.terminals = rg.terminals;
1285 this.transientLines = rg.transientLines;
1286 this.caseId = rg.caseId;
1287 this.isSimpleConnection = rg.isSimpleConnection;
1288 this.needsUpdate = rg.needsUpdate;
1292 private void reset() {
1293 lines = new ArrayList<RouteLine>();
1294 terminals = new ArrayList<RouteTerminal>();
1295 transientLines = new ArrayList<RouteLine>();
1297 isSimpleConnection = false;
1298 needsUpdate = false;
1301 public Rectangle2D getBounds() {
1302 Rectangle2D bounds = new Rectangle2D.Double();
1307 public void getBounds(Rectangle2D bounds) {
1310 double minX = Double.POSITIVE_INFINITY;
1311 double maxX = Double.NEGATIVE_INFINITY;
1312 double minY = Double.POSITIVE_INFINITY;
1313 double maxY = Double.NEGATIVE_INFINITY;
1314 for(RouteLine line : lines) {
1315 double position = line.position;
1316 if(line.isHorizontal) {
1317 minY = Math.min(minY, position);
1318 maxY = Math.max(maxY, position);
1321 minX = Math.min(minX, position);
1322 maxX = Math.max(maxX, position);
1325 for(RouteLine line : transientLines) {
1326 double position = line.position;
1327 if(line.isHorizontal) {
1328 minY = Math.min(minY, position);
1329 maxY = Math.max(maxY, position);
1332 minX = Math.min(minX, position);
1333 maxX = Math.max(maxX, position);
1336 for(RouteTerminal terminal : terminals) {
1337 double x = terminal.x;
1338 double y = terminal.y;
1339 minX = Math.min(minX, x);
1340 maxX = Math.max(maxX, x);
1341 minY = Math.min(minY, y);
1342 maxY = Math.max(maxY, y);
1344 bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1347 private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1348 double x = cur.x, y = cur.y;
1349 if(cur instanceof RouteTerminal) {
1350 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1351 if(line.isHorizontal()) {
1352 if(cur == line.getBegin())
1353 x += style.getLineEndLength(0);
1355 x -= style.getLineEndLength(2);
1358 if(cur == line.getBegin())
1359 y += style.getLineEndLength(1);
1361 y -= style.getLineEndLength(3);
1367 private static final Comparator<RoutePoint> RG_COMP = (o1, o2) -> {
1368 if (o1.getX() < o2.getX())
1370 else if (o1.getX() > o2.getX())
1372 if (o1.getY() < o2.getY())
1374 else if (o1.getY() > o2.getY())
1379 private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1380 double x = cur.x, y = cur.y;
1381 if(cur instanceof RouteTerminal) {
1382 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1383 if(line.isHorizontal()) {
1384 if(cur == line.getBegin())
1385 x += style.getLineEndLength(0);
1387 x -= style.getLineEndLength(2);
1390 if(cur == line.getBegin())
1391 y += style.getLineEndLength(1);
1393 y -= style.getLineEndLength(3);
1399 public void getPath2D(Path2D path) {
1403 if(isSimpleConnection && transientLines.isEmpty()) {
1404 if(terminals.size() == 2) {
1405 RouteTerminal a = terminals.get(0);
1406 RouteTerminal b = terminals.get(1);
1407 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1408 path.moveTo(a.x, a.y);
1409 path.lineTo(b.x, b.y);
1416 Map<RoutePoint, RouteLine> begins = new HashMap<RoutePoint, RouteLine>();
1417 for(RouteLine line : lines) {
1420 for(RouteLine line : transientLines) {
1423 for(RouteTerminal terminal : terminals)
1424 if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1425 begins.remove(terminal.line.getBegin());
1426 drawContinuousPath(path, begins, terminal, terminal.line);
1430 // Sort the begins so that the order of segments is deterministic. This is required when comparing e.g. SVG diagrams.
1431 // In case of overlapping begins the order may vary.
1432 for(RoutePoint begin : begins.keySet().stream().sorted(RG_COMP).collect(Collectors.toList())) {
1433 RouteLine curLine = begins.remove(begin);
1434 drawContinuousPath(path, begins, begin, curLine);
1438 private void drawContinuousPath(Path2D path, Map<RoutePoint, RouteLine> begins,
1439 RoutePoint cur, RouteLine curLine) {
1442 addPathBegin(path, cur, curLine);
1445 if(cur != curLine.getEnd())
1446 cur = curLine.getEnd();
1448 cur = curLine.getBegin();
1449 if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1450 addPathEnd(path, cur, curLine);
1453 if(cur instanceof RouteLink) {
1454 if(!curLine.isDegenerated() ||
1455 path.getCurrentPoint().getX() != cur.x ||
1456 path.getCurrentPoint().getY() != cur.y)
1457 path.lineTo(cur.x, cur.y);
1458 RouteLink link = (RouteLink)cur;
1459 if(link.a != curLine)
1467 private static void add(Map<RoutePoint, RouteLine> begins,
1469 if(line.points.size() > 1) {
1471 RoutePoint p = line.getBegin();
1472 if(begins.remove(p) == null)
1473 begins.put(p, line);
1476 RoutePoint p = line.getEnd();
1477 if(begins.remove(p) == null)
1478 begins.put(p, line);
1483 public Collection<Segment> getSegments() {
1486 ArrayList<Segment> segments = new ArrayList<Segment>();
1487 for(RouteLine routeLine : lines)
1488 routeLine.collectSegments(segments);
1489 for(RouteLine routeLine : transientLines)
1490 routeLine.collectSegments(segments);
1494 public Segment findNearestSegment(double x, double y) {
1495 Segment nearest = null;
1496 double minDistanceSq = Double.MAX_VALUE;
1498 for (Segment segment : getSegments()) {
1499 RoutePoint p1 = segment.p1;
1500 RoutePoint p2 = segment.p2;
1502 double distanceSq = Line2D.ptSegDistSq(p1.x, p1.y, p2.x, p2.y, x, y);
1503 if (distanceSq < minDistanceSq) {
1504 minDistanceSq = distanceSq;
1511 public Point2D findNearestPoint(double x, double y) {
1512 Segment nearest = findNearestSegment(x, y);
1513 if (nearest == null) return null;
1515 RoutePoint p1 = nearest.p1;
1516 RoutePoint p2 = nearest.p2;
1518 double d = Math.pow(p2.x - p1.x, 2.0) + Math.pow(p2.y - p1.y, 2.0);
1521 return new Point2D.Double(p1.x, p1.y);
1523 double u = ((x - p1.x) * (p2.x - p1.x) + (y - p1.y) * (p2.y - p1.y)) / d;
1525 return new Point2D.Double(p2.x, p2.y);
1526 } else if (u <= 0.0) {
1527 return new Point2D.Double(p1.x, p1.y);
1529 return new Point2D.Double(p2.x * u + p1.x * (1.0-u), (p2.y * u + p1.y * (1.0- u)));
1534 public Path2D getPath2D() {
1535 Path2D result = new Path2D.Double();
1540 public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1541 THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1542 THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1543 THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1544 THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1545 THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1546 THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1548 if(splitLine.isTransient()) {
1549 RouteTerminal terminal = splitLine.terminal;
1551 if(splitLine.beginsWithTerminal()) {
1552 lines2.addAll(getLines());
1553 terminals2.addAll(getTerminals());
1554 terminals1.add(terminal);
1555 terminals2.remove(terminal);
1556 interfaceNodes1.add(terminal);
1557 if(isSimpleConnection())
1558 interfaceNodes2.addAll(terminals2);
1560 interfaceNodes2.add(terminal.line);
1563 lines1.addAll(getLines());
1564 terminals1.addAll(getTerminals());
1565 terminals2.add(terminal);
1566 terminals1.remove(terminal);
1567 interfaceNodes2.add(terminal);
1568 if(isSimpleConnection())
1569 interfaceNodes1.addAll(terminals1);
1571 interfaceNodes1.add(terminal.line);
1575 for(RoutePoint rp : splitLine.getPoints()) {
1576 double p = splitLine.isHorizontal ? rp.x : rp.y;
1577 if(rp instanceof RouteLink) {
1578 RouteLink link = (RouteLink)rp;
1579 RouteLine otherLine = link.getA() != splitLine ? link.getA()
1581 if(otherLine.isTransient()) {
1583 interfaceNodes1.add(otherLine.terminal);
1584 terminals1.add(otherLine.terminal);
1587 interfaceNodes2.add(otherLine.terminal);
1588 terminals2.add(otherLine.terminal);
1594 interfaceNodes1.add(otherLine);
1595 traverseGraph(link, otherLine, lines1);
1598 interfaceNodes2.add(otherLine);
1599 traverseGraph(link, otherLine, lines2);
1604 for(RouteTerminal terminal : getTerminals())
1605 if(lines1.contains(terminal.line))
1606 terminals1.add(terminal);
1607 else if(lines2.contains(terminal.line))
1608 terminals2.add(terminal);
1611 return new SplittedRouteGraph(splitLine,
1612 interfaceNodes1, lines1, terminals1,
1613 interfaceNodes2, lines2, terminals2);
1616 private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1617 THashSet<RouteLine> lines) {
1618 if(lines.add(line)) {
1619 for(RoutePoint rp : line.getPoints()) {
1620 if(rp != previousPoint && rp instanceof RouteLink) {
1621 RouteLink link = (RouteLink)rp;
1622 RouteLine otherLine = line != link.getA()
1623 ? link.getA() : link.getB();
1624 if(otherLine.isTransient())
1626 traverseGraph(rp, otherLine, lines);
1632 public void reclaimTransientMemory() {
1633 removeTransientRouteLines();