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.Iterator;
26 import java.util.TreeMap;
28 import org.simantics.diagram.connection.rendering.arrows.ILineEndStyle;
29 import org.simantics.diagram.connection.rendering.arrows.PlainLineEndStyle;
30 import org.simantics.diagram.connection.segments.Segment;
31 import org.simantics.diagram.connection.splitting.SplittedRouteGraph;
33 import gnu.trove.list.array.TDoubleArrayList;
34 import gnu.trove.map.hash.THashMap;
35 import gnu.trove.map.hash.TObjectIntHashMap;
36 import gnu.trove.set.hash.THashSet;
38 public class RouteGraph implements Serializable {
40 private static final long serialVersionUID = 2004022454972623908L;
42 public static final boolean RETURN_UNMODIFIABLE_COLLECTIONS = false;
43 public static final boolean CHECK_PARAMERS = true;
45 ArrayList<RouteLine> lines = new ArrayList<RouteLine>(4);
46 ArrayList<RouteTerminal> terminals = new ArrayList<RouteTerminal>(4);
47 ArrayList<RouteLine> transientLines = new ArrayList<RouteLine>(4);
49 boolean isSimpleConnection;
50 boolean needsUpdate = false;
52 public void updateTerminals() {
53 boolean changed = false;
54 for(RouteTerminal terminal : terminals)
55 changed |= terminal.updateDynamicPosition();
60 * Adds a route line to the graph.
61 * @param isHorizontal true, if the line is horizontal
62 * @param position y coordinate of the line if horizontal, x coordinate if vertical
63 * @return The new line.
65 public RouteLine addLine(boolean isHorizontal, double position) {
66 RouteLine line = new RouteLine(isHorizontal, position);
72 * Adds a route terminal to the graph.
73 * @param x The location of the terminal.
75 * @param minX The avoidance area of the terminal.
79 * @param allowedDirections Allowed directions.
80 * First four bits tell with which directions
81 * a connection can leave the terminal. The
82 * Fifth bit indicates whether direct lines
83 * can be drawn to the terminal. Directions are
90 * @param style Tells what kind of line end is drawn
92 * @param position a provider for a dynamic position for the terminal or
93 * <code>null</code> if terminal position is not dynamic
94 * @return The new terminal.
96 public RouteTerminal addTerminal(double x, double y,
97 double minX, double minY,
98 double maxX, double maxY,
99 int allowedDirections,
100 ILineEndStyle style, RouteTerminalPosition position) {
101 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, position);
104 public RouteTerminal addTerminal(double x, double y,
105 double minX, double minY,
106 double maxX, double maxY,
107 int allowedDirections,
108 ILineEndStyle style) {
109 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections, style, null, null);
112 public RouteTerminal addTerminal(double x, double y,
113 double minX, double minY,
114 double maxX, double maxY,
115 int allowedDirections,
116 ILineEndStyle style, ILineEndStyle dynamicStyle, RouteTerminalPosition position) {
118 if(allowedDirections > 0x1f)
119 throw new IllegalArgumentException("Illegal allowedDirection flags.");
120 if(minX > x || x > maxX || minY > y || y > maxY)
121 throw new IllegalArgumentException("Illegal position attributes for a terminal, (" + x + ", " + y + ") is outside of (" + minX + ", " + minY + ")x(" + maxX + ", " + maxY + ").");
124 style = PlainLineEndStyle.INSTANCE;
125 RouteTerminal terminal = new RouteTerminal(x, y, minX, minY,
126 maxX, maxY, allowedDirections, false, style, position);
127 terminal.setDynamicStyle(dynamicStyle);
128 terminals.add(terminal);
132 public RouteTerminal addBigTerminal(
133 double minX, double minY,
134 double maxX, double maxY,
135 ILineEndStyle style) {
136 return addBigTerminal(minX, minY, maxX, maxY, style, null);
138 public RouteTerminal addBigTerminal(
139 double minX, double minY,
140 double maxX, double maxY,
141 ILineEndStyle style, ILineEndStyle dynamicStyle) {
143 style = PlainLineEndStyle.INSTANCE;
144 RouteTerminal terminal = new RouteTerminal(
145 0.5*(minX+maxX), 0.5*(minY+maxY),
148 0xf, true, style, null);
149 terminal.setDynamicStyle(dynamicStyle);
151 terminals.add(terminal);
156 * Adds a route terminal to the graph. The avoidance
157 * area is given as a rectangle.
158 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
160 public RouteTerminal addTerminal(double x, double y,
162 int allowedDirections,
163 ILineEndStyle style) {
164 return addTerminal(x, y,
165 bounds.getMinX(), bounds.getMinY(), bounds.getMaxX(), bounds.getMaxY(),
166 allowedDirections, style, null);
170 * Adds a copy of the given terminal to the graph.
172 public RouteTerminal addTerminal(RouteTerminal terminal) {
173 RouteTerminal newTerminal = addTerminal(terminal.x, terminal.y,
174 terminal.getMinX(), terminal.getMinY(),
175 terminal.getMaxX(), terminal.getMaxY(),
176 terminal.getAllowedDirections(), terminal.getStyle(), terminal.getDynamicStyle(), terminal.getDynamicPosition());
177 newTerminal.setData(terminal.getData());
182 * Adds a route terminal to the graph. A default line end style is used.
183 * @see RouteGraph#addTerminal(double, double, double, double, double, double, int, ILineEndStyle)
185 public RouteTerminal addTerminal(double x, double y,
186 double minX, double minY,
187 double maxX, double maxY,
188 int allowedDirections) {
189 return addTerminal(x, y, minX, minY, maxX, maxY, allowedDirections,
190 PlainLineEndStyle.INSTANCE, null);
196 public void link(RouteNode node1, RouteNode node2) {
197 if(node1 instanceof RouteLine) {
198 if(node2 instanceof RouteLine) {
199 link((RouteLine)node1, (RouteLine)node2);
202 link((RouteLine)node1, (RouteTerminal)node2);
206 if(node2 instanceof RouteLine) {
207 link((RouteTerminal)node1, (RouteLine)node2);
210 link((RouteTerminal)node1, (RouteTerminal)node2);
218 public void link(RouteNode ... nodes) {
219 for(int i=1;i<nodes.length;++i)
220 link(nodes[i-1], nodes[i]);
226 public void link(RouteLine node1, RouteLine node2) {
227 new RouteLink(node1, node2);
232 * Links a terminal and a line.
234 public void link(RouteTerminal node1, RouteLine node2) {
237 throw new NullPointerException();
238 if(node1.line != null)
239 throw new IllegalStateException("Terminal is already connected.");
246 * Links a line and a terminal.
248 public void link(RouteLine node1, RouteTerminal node2) {
251 throw new NullPointerException();
252 if(node2.line != null)
253 throw new IllegalStateException("Terminal is already connected.");
260 * Links two terminals.
262 public void link(RouteTerminal node1, RouteTerminal node2) {
265 throw new NullPointerException();
267 throw new NullPointerException();
269 isSimpleConnection = true;
273 void removeTransientRouteLines() {
274 for(RouteLine line : transientLines)
276 transientLines.clear();
280 * Rotates given terminal clockwise by given amount
281 * (also negative numbers are allowed).
283 public void rotate(RouteTerminal terminal, int amount) {
284 terminal.rotate(amount);
289 * Moves the given route line so that its position correspond
290 * to given x or y depending on the orientation of the line.
292 public void setLocation(RouteLine line, double x, double y) {
293 makePersistent(line);
294 line.setLocation(x, y);
299 * Moves the terminal to given location.
301 public void setLocation(RouteTerminal terminal, double x, double y) {
302 terminal.setLocation(x, y);
307 * Updates transient route lines, route link positions
308 * and sorts route points of each route line.
310 public void update() {
312 removeTransientRouteLines();
316 for(RouteLine line : lines)
318 for(RouteTerminal terminal : terminals)
319 if(terminal.hasDirectConnection() && terminal.line != null)
320 terminal.line.hidden = true;
323 if(isSimpleConnection) {
324 RouteTerminal a = terminals.get(0);
325 RouteTerminal b = terminals.get(1);
326 if(a.hasDirectConnection() || b.hasDirectConnection())
328 caseId = SimpleConnectionUtility.simpleConnectionCase(a, b);
329 //System.out.println("caseId = " + caseId);
331 case SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION:
332 case SimpleConnectionUtility.DIRECT_VERTICAL_CONNECTION: {
333 boolean horiz = caseId==SimpleConnectionUtility.DIRECT_HORIZONTAL_CONNECTION;
334 RouteLine line = new RouteLine(horiz, horiz ? a.y : a.x);
338 transientLines.add(line);
341 case SimpleConnectionUtility.ONE_BEND_HORIZONTAL_VERTICAL: {
342 RouteLine line1 = new RouteLine(true, a.y);
343 RouteLine line2 = new RouteLine(false, b.x);
344 new RouteLink(line1, line2);
349 transientLines.add(line1);
350 transientLines.add(line2);
353 case SimpleConnectionUtility.ONE_BEND_VERTICAL_HORIZONTAL: {
354 RouteLine line1 = new RouteLine(false, a.x);
355 RouteLine line2 = new RouteLine(true, b.y);
356 new RouteLink(line1, line2);
361 transientLines.add(line1);
362 transientLines.add(line2);
365 case SimpleConnectionUtility.MORE_BENDS_BBS_DONT_INTERSECT:
366 case SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT: {
368 SimpleConnectionUtility.findRouteLine(terminals.get(0), terminals.get(1),
369 caseId == SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT )
371 terminals.get(0).line = line;
372 terminals.get(1).line = line;
373 transientLines.add(line);
374 routeFromTerminals(caseId==SimpleConnectionUtility.MORE_BENDS_BBS_INTERSECT);
380 caseId = SimpleConnectionUtility.COMPLEX_CONNECTION;
381 routeFromTerminals(false);
384 // Find positions of route points
385 for(RouteLine line : lines)
386 line.setPointPositions();
387 for(RouteLine line : transientLines)
388 line.setPointPositions();
390 // Sort route points in route lines
391 for(RouteLine line : lines) {
394 for(RouteLine line : transientLines) {
399 static class Interval {
400 public final double min;
401 public final double max;
402 public Interval(double min, double max) {
408 class IntervalCache {
409 THashMap<RouteLine, Interval> cache =
410 new THashMap<RouteLine, Interval>();
411 public Interval get(RouteLine line) {
412 Interval result = cache.get(line);
416 result = create(line);
417 cache.put(line, result);
421 private Interval create(RouteLine line) {
422 double min = Double.POSITIVE_INFINITY;
423 double max = Double.NEGATIVE_INFINITY;
425 for(RoutePoint point : line.points) {
427 if(point instanceof RouteLink) {
428 RouteLink link = (RouteLink)point;
430 temp = link.b.position;
432 temp = link.a.position;
435 RouteTerminal terminal = (RouteTerminal)point;
436 if(line.isHorizontal)
446 for(RouteTerminal terminal : terminals) {
447 if(terminal.line == line) {
448 double temp = terminal.approximatePositionToLine();
456 return new Interval(min, max);
460 private void routeFromTerminals(boolean boundingBoxesIntersect) {
461 IntervalCache cache = new IntervalCache();
462 for(RouteTerminal terminal : terminals)
463 if(terminal.line != null) {
464 if(!terminal.hasDirectConnection())
465 terminal.route(transientLines, cache, boundingBoxesIntersect);
470 * Returns a RouteLine near the given point (x,y) (within tolerance).
472 public RouteLine pickLine(double x, double y, double tolerance, int mask) {
475 if(isSimpleConnection && transientLines.isEmpty()) {
476 if(terminals.size() == 2) {
477 if((mask & PICK_TRANSIENT_LINES) == 0)
479 RouteTerminal a = terminals.get(0);
480 RouteTerminal b = terminals.get(1);
481 if(a.hasDirectConnection() || b.hasDirectConnection()) {
482 if(Line2D.ptSegDistSq(a.x, a.y, b.x, b.y, x, y) <= tolerance*tolerance) {
483 RouteLine dummy = new RouteLine(false, y);
484 return dummy; // There are no lines to return
491 if((mask & PICK_PERSISTENT_LINES) != 0)
492 for(RouteLine line : lines)
493 if(line.isNear(x, y, tolerance))
495 if((mask & PICK_TRANSIENT_LINES) != 0)
496 for(RouteLine line : transientLines)
497 if(line.isNear(x, y, tolerance))
499 if((mask & PICK_DIRECT_LINES) != 0) {
500 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
502 return terminal.line;
507 public RouteLine pickLine(double x, double y, double tolerance) {
508 return pickLine(x, y, tolerance, PICK_LINES);
511 private RouteTerminal pickDirectLine(double x, double y, double tolerance) {
512 double toleranceSq = tolerance * tolerance;
513 for(RouteTerminal terminal : terminals)
514 if((terminal.getAllowedDirections()&0x10) != 0) {
516 RouteLine line = terminal.getLine();
519 RoutePoint b = line.getBegin();
520 double distSq = Line2D.ptSegDistSq(terminal.x, terminal.y, b.x, b.y, x, y);
521 if(distSq <= toleranceSq) {
522 //System.out.println("distSq = " + distSq + ", toleranceSq = " + toleranceSq);
525 } catch(NullPointerException e) {
526 //if terminal does not have a line
528 } catch(IndexOutOfBoundsException e) {
529 // if line does not contain points
536 public RouteLineHalf pickLineHalf(double x, double y, double tolerance) {
537 if(isSimpleConnection)
541 RouteLine line = pickLine(x, y, tolerance);
544 RouteLink link = null;
545 RoutePoint begin = line.getBegin();
546 RoutePoint end = line.getEnd();
547 if(line.isHorizontal) {
548 double mx = 0.5*(begin.getX() + end.getX());
550 if(begin instanceof RouteLink)
551 link = (RouteLink)begin;
554 if(end instanceof RouteLink)
555 link = (RouteLink)line.getEnd();
559 double my = 0.5*(begin.getY() + end.getY());
561 if(begin instanceof RouteLink)
562 link = (RouteLink)begin;
565 if(end instanceof RouteLink)
566 link = (RouteLink)end;
571 if(link.getOther(line).isTransient())
573 return new RouteLineHalf(line, link);
576 public Collection<RouteLineHalf> getLineHalves() {
577 return getLineHalves(new ArrayList<RouteLineHalf>());
580 public Collection<RouteLineHalf> getLineHalves(Collection<RouteLineHalf> result) {
581 for(RouteLine line : getAllLines()) {
583 RoutePoint p = line.getBegin();
584 if(p instanceof RouteLink) {
585 RouteLink link = (RouteLink)p;
586 if(!link.getOther(line).isTransient())
587 result.add(new RouteLineHalf(line, link));
591 RoutePoint p = line.getEnd();
592 if(p instanceof RouteLink) {
593 RouteLink link = (RouteLink)p;
594 if(!link.getOther(line).isTransient())
595 result.add(new RouteLineHalf(line, link));
603 * Returns a RoutePoint near the given point (x,y) (within tolerance).
605 public RoutePoint pickPoint(double x, double y, double tolerance, int mask) {
608 if((mask&PICK_TERMINALS) != 0)
609 for(RouteTerminal terminal : terminals)
610 if(terminal.isNear(x, y))
612 if((mask&PICK_INTERIOR_POINTS) != 0) {
613 for(RouteLine line : lines) {
614 for(RoutePoint point : line.points)
615 if(point.isNear(x, y, tolerance))
618 for(RouteLine line : transientLines) {
619 for(RoutePoint point : line.points)
620 if(point.isNear(x, y, tolerance))
627 public RoutePoint pickPoint(double x, double y, double tolerance) {
628 return pickPoint(x, y, tolerance, PICK_POINTS);
631 public static final int PICK_INTERIOR_POINTS = 1;
632 public static final int PICK_TERMINALS = 2;
633 public static final int PICK_POINTS = PICK_INTERIOR_POINTS | PICK_TERMINALS;
635 public static final int PICK_PERSISTENT_LINES = 4;
636 public static final int PICK_TRANSIENT_LINES = 8;
637 public static final int PICK_DIRECT_LINES = 16;
638 public static final int PICK_LINES = PICK_PERSISTENT_LINES | PICK_TRANSIENT_LINES | PICK_DIRECT_LINES;
640 public static final int PICK_ALL = PICK_POINTS | PICK_LINES;
643 * Returns RoutePoint or RouteLine near the given point (x,y) (within tolerance).
645 public Object pick(double x, double y, double tolerance, int mask) {
646 if((mask & PICK_POINTS) != 0) {
647 Object point = pickPoint(x, y, tolerance, mask);
651 /*if((mask & PICK_DIRECT_LINES) != 0) {
652 RouteTerminal terminal = pickDirectLine(x, y, tolerance);
654 return terminal.line.getBegin();
656 if((mask & PICK_LINES) != 0)
657 return pickLine(x, y, tolerance, mask);
662 public Object pick(double x, double y, double tolerance) {
663 return pick(x, y, tolerance, PICK_ALL);
667 * Returns RoutePoint or RouteLine exactly under the given point (x,y).
669 public Object pick(double x, double y) {
670 return pick(x, y, 0.0);
674 * Prints the contents of the route graph to stdout.
676 public void print() {
681 * Prints the contents of the route graph to given print stream.
683 public void print(PrintStream out) {
686 if(isSimpleConnection)
687 out.println("=== SIMPLE CONNECTION ===");
689 out.println("=== COMPLEX CONNECTION ===");
690 for(RouteLine line : lines) {
694 for(RouteLine line : transientLines) {
698 for(RouteTerminal terminal : terminals) {
704 public void makePersistent(RouteLine line) {
705 prepareForModification();
706 if(isSimpleConnection || line.isTransient()) {
707 if(isSimpleConnection) {
708 isSimpleConnection = false;
709 for(RouteTerminal terminal : terminals)
710 terminal.line = line;
711 transientLines.remove(line);
713 Iterator<RoutePoint> it = line.points.iterator();
714 while(it.hasNext()) {
715 RoutePoint point = it.next();
716 if(point instanceof RouteTerminal)
719 line.terminal = null;
720 line.nextTransient = null;
723 line.terminal.line = line;
725 transientLines.remove(line);
727 Iterator<RoutePoint> it = line.points.iterator();
728 while(it.hasNext()) {
729 RoutePoint point = it.next();
730 if(point instanceof RouteTerminal)
733 line.terminal = null;
734 RouteLine temp = line.nextTransient;
735 line.nextTransient = null;
737 } while(line != null);
743 void prepareForModification() {
745 RouteLine line = transientLines.remove(0);
746 line.terminal = null;
748 for(RouteTerminal terminal : terminals)
749 terminal.line = line;
750 isSimpleConnection = false;
755 public double[] getLineLengths(RouteTerminal terminal) {
758 if(lines.size()==0 && transientLines.size()==1)
759 return new double[] { transientLines.get(0).getLength() };
761 RouteLine line = null;
763 for(RouteLine l : transientLines)
764 if(l.isTransient()) {
765 for(RoutePoint p : l.points)
766 if(!(p instanceof RouteLink)) {
771 TDoubleArrayList result = new TDoubleArrayList();
772 THashSet<RouteLine> set = new THashSet<RouteLine>();
776 result.add(line.getLength());
777 for(RoutePoint point : line.points)
778 if(point instanceof RouteLink) {
779 RouteLink link = (RouteLink)point;
780 if(set.add(link.a)) {
784 if(set.add(link.b)) {
791 return result.toArray();
794 public void split(RouteLine rl1, double splitPosition) {
797 boolean isHorizontal = rl1.isHorizontal();
798 if(isSimpleConnection) {
799 isSimpleConnection = false;
801 RouteLine sp = addLine(!isHorizontal, splitPosition);
802 for(RouteTerminal terminal : terminals)
807 else if(caseId < 4) {
808 RouteLine sp = addLine(!isHorizontal, splitPosition);
809 RouteLine l = addLine(isHorizontal, rl1.position);
811 rl1.terminal.line = sp;
812 for(RouteTerminal terminal : terminals)
813 if(terminal != rl1.terminal)
819 prepareForModification();
822 RouteLine rl2 = new RouteLine(isHorizontal, rl1.getPosition());
823 RouteLine sp = new RouteLine(!isHorizontal, splitPosition);
825 ArrayList<RoutePoint> points = rl1.points;
830 int maxPos = points.size();
831 while(minPos != maxPos) {
832 int c = (minPos + maxPos)/2;
834 ? points.get(c).getX() > splitPosition
835 : points.get(c).getY() > splitPosition)
843 for(int i=points.size()-1;i>=splitPos;--i) {
844 RoutePoint point = points.remove(i);
845 if(point instanceof RouteLink) {
846 RouteLink link = (RouteLink)point;
847 link.replace(rl1, rl2);
851 if(rl1.isTransient()) {
852 boolean p1 = rl1.isConnectedToPeristentLine();
853 boolean p2 = rl2.isConnectedToPeristentLine();
855 RouteTerminal terminal = rl1.terminal;
858 transientLines.add(rl2);
864 transientLines.add(rl2);
866 for(RouteTerminal t : terminals)
874 new RouteLink(rl1, sp);
875 new RouteLink(sp, rl2);
880 public boolean merge(RouteLine line) {
883 for(RoutePoint point : line.points) {
884 if(point instanceof RouteLink) {
885 RouteLink link = (RouteLink)point;
886 RouteLine other = link.getOther(line);
887 if(!other.isTransient()) {
888 sum += other.position;
893 return merge(line, sum / count);
897 * Removes given route line and collapses all its neighbor
898 * route lines into one line with given position.
900 public boolean merge(RouteLine line, double position) {
903 if(isSimpleConnection || line.isTransient())
906 if(lines.size() == 1) {
907 if(terminals.size() != 2)
910 isSimpleConnection = true;
911 for(RouteTerminal terminal : terminals)
912 terminal.line = null;
917 ArrayList<RouteLine> nLines = new ArrayList<RouteLine>();
918 for(RoutePoint point : line.points) {
919 /* Because line.terminal == null, there should be
922 * Update 14.2.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
924 if (point instanceof RouteLink) {
925 RouteLine l = ((RouteLink)point).getOther(line);
926 l.points.remove(point);
934 RouteLine merged = nLines.remove(nLines.size()-1);
935 merged.position = position;
936 for(RouteLine l : nLines) {
937 for(RoutePoint point : l.points) {
938 /* Because l.terminal == null, there should be
941 * Update 16.10.2014: With Sulca, there is a constant issue when line.terminal == null but point is RouteTerminal.
943 if (point instanceof RouteLink) {
944 RouteLink link = (RouteLink)point;
945 link.replace(l, merged);
949 THashSet<RouteLine> removedLines = new THashSet<RouteLine>();
950 removedLines.addAll(nLines);
951 lines.removeAll(removedLines);
952 removedLines.add(line);
954 for(RouteTerminal terminal : terminals)
955 if(removedLines.contains(terminal.line))
956 terminal.line = merged;
961 public void deleteCorner(RouteLink link) {
964 RouteLine a = link.getA();
965 RouteLine b = link.getB();
966 if(a.isTransient() || b.isTransient()
967 || a.points.size() != 2 || b.points.size() != 2)
969 RouteLine na=null, nb=null;
970 for(RoutePoint p : a.points) {
971 RouteLink l = (RouteLink)p;
972 if(l.a == a && l.b != b) {
976 else if(l.b == a && l.a != b) {
981 for(RoutePoint p : b.points) {
982 RouteLink l = (RouteLink)p;
983 if(l.a == b && l.b != a) {
987 else if(l.b == b && l.a != a) {
992 if(na == null || nb == null) {
993 System.err.println("Internal error in router.");
1001 if(na.terminal != null)
1002 na.terminal.line = nb;
1003 if(nb.terminal != null)
1004 nb.terminal.line = na;
1008 public boolean connectTerminal(RouteTerminal terminal, double x, double y, double tolerance) {
1009 Object target = pick(x, y, tolerance);
1010 if(target instanceof RouteLine) {
1011 RouteLine line = (RouteLine)target;
1012 RouteTerminal involvedTerminal =
1013 line.isTransient() ? line.terminal : null;
1014 makePersistent(line);
1015 terminal.line = null; // TODO this is a workaround
1017 int lineDir = line.isHorizontal
1018 ? (line.position < terminal.y ? 3 : 1)
1019 : (line.position < terminal.x ? 2 : 0)
1022 if(line.isHorizontal && Math.abs(x - terminal.x) > 30) {
1024 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1025 RouteLine l1 = addLine(true, 0.5*(y+terminal.y));
1026 l2 = addLine(false, x);
1027 link(terminal, l1, l2, line);
1030 l2 = addLine(false, x);
1031 link(terminal, l2, line);
1033 if(involvedTerminal != null)
1034 involvedTerminal.line = l2;
1036 else if(!line.isHorizontal && Math.abs(y - terminal.y) > 30) {
1038 if(Directions.isAllowed(terminal.getAllowedDirections(), lineDir)) {
1039 RouteLine l1 = addLine(false, 0.5*(x+terminal.x));
1040 l2 = addLine(true, y);
1041 link(terminal, l1, l2, line);
1044 l2 = addLine(true, y);
1045 link(terminal, l2, line);
1047 if(involvedTerminal != null)
1048 involvedTerminal.line = l2;
1051 link(terminal, line);
1060 public boolean connectLine(RouteLine sLine, double x, double y, double tolerance) {
1061 Object target = pick(x, y, tolerance);
1062 if(target instanceof RouteLine) {
1063 RouteLine line = (RouteLine)target;
1064 RouteTerminal involvedTerminal =
1065 line.isTransient() ? line.terminal : null;
1066 makePersistent(line);
1067 if(line.isHorizontal == sLine.isHorizontal) {
1068 RouteLine l = addLine(!sLine.isHorizontal,
1069 sLine.isHorizontal ? x : y);
1070 link(sLine, l, line);
1071 if(involvedTerminal != null)
1072 involvedTerminal.line = l;
1076 if(involvedTerminal != null)
1077 involvedTerminal.line = sLine;
1087 * Makes a deep copy of the route graph and stores
1088 * the correspondences between original and copied
1089 * objects into the given map.
1091 public RouteGraph copy(THashMap<Object, Object> map) {
1092 RouteGraph copy = new RouteGraph();
1093 copy.isSimpleConnection = isSimpleConnection;
1094 copy.caseId = caseId;
1095 copy.needsUpdate = needsUpdate;
1096 for(RouteLine line : lines)
1097 copy.lines.add(line.copy(map));
1098 for(RouteLine line : transientLines)
1099 copy.transientLines.add(line.copy(map));
1100 for(RouteTerminal terminal : terminals)
1101 copy.terminals.add(terminal.copy(map));
1106 * Makes a deep copy of the route graph.
1108 public RouteGraph copy() {
1109 THashMap<Object, Object> map = new THashMap<Object, Object>();
1114 * Removes route lines that are conneted to at most
1115 * one other route line or terminal.
1117 public void removeExtraConnections() {
1118 TObjectIntHashMap<RouteLine> counts =
1119 new TObjectIntHashMap<RouteLine>();
1120 removeTransientRouteLines();
1121 for(RouteLine line : lines) {
1123 for(RoutePoint point : line.points)
1124 if(point instanceof RouteLink)
1126 counts.put(line, count);
1128 for(RouteTerminal terminal : terminals)
1129 counts.adjustOrPutValue(terminal.line, 1, 1);
1133 Iterator<RouteLine> it = lines.iterator();
1134 while(it.hasNext()) {
1135 RouteLine line = it.next();
1136 if(counts.get(line) <= 1) {
1137 for(RoutePoint point : line.points)
1138 if(point instanceof RouteLink)
1139 counts.adjustValue(((RouteLink)point).getOther(line), -1);
1150 * Removes a terminal and all route lines that become degenerated by the removal.
1152 public void remove(RouteTerminal terminal) {
1153 terminals.remove(terminal);
1154 removeExtraConnections();
1157 public void disconnect(RouteTerminal terminal) {
1158 terminal.line = null;
1159 removeExtraConnections();
1162 public void remove(RouteLink link) {
1163 link.a.points.remove(link);
1164 link.b.points.remove(link);
1167 public void toggleDirectLines(RouteTerminal terminal) {
1168 terminal.toggleDirectLines();
1173 * Returns all persistent route lines of the route graph.
1175 public Collection<RouteLine> getLines() {
1178 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1179 return Collections.unmodifiableList(lines);
1185 * Returns all transient route lines of the route graph.
1187 public Collection<RouteLine> getTransientLines() {
1190 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1191 return Collections.unmodifiableList(transientLines);
1193 return transientLines;
1197 * Returns all terminals of the route graph.
1199 public Collection<RouteTerminal> getTerminals() {
1200 if(RETURN_UNMODIFIABLE_COLLECTIONS)
1201 return Collections.unmodifiableList(terminals);
1207 * Returns all route lines, both persistent and transient,
1208 * of the route graph.
1210 public Collection<RouteLine> getAllLines() {
1213 ArrayList<RouteLine> allLines = new ArrayList<RouteLine>(lines.size() + transientLines.size());
1214 allLines.addAll(lines);
1215 allLines.addAll(transientLines);
1220 * Returns all route lines, both persistent and transient, of the route
1221 * graph, added to the specified collection. Avoids allocation of new
1222 * {@link ArrayList} compared to {@link #getAllLines()}.
1224 public Collection<RouteLine> getAllLines(Collection<RouteLine> result) {
1226 throw new NullPointerException("null result collection");
1229 result.addAll(lines);
1230 result.addAll(transientLines);
1235 * Returns true, if the route graph is connected and contains no cycles.
1237 public boolean isTree() {
1238 if(isSimpleConnection)
1240 for(RouteTerminal terminal : terminals)
1241 if(terminal.line == null)
1243 THashSet<RouteLine> visited = new THashSet<RouteLine>();
1244 ArrayList<RouteLine> stack = new ArrayList<RouteLine>();
1246 visited.add(lines.get(0));
1247 stack.add(lines.get(0));
1248 while(!stack.isEmpty()) {
1249 RouteLine cur = stack.remove(stack.size()-1);
1250 for(RouteLine n : cur.getPersistentNeighbors()) {
1256 return visited.size() == lines.size() && linkCount == 2*(lines.size()-1);
1260 * Returns if the connection is simple. A connection is simple, if it has just
1261 * two terminals connected together directly without (persistent) route lines.
1263 public boolean isSimpleConnection() {
1264 return isSimpleConnection;
1267 public void replaceBy(RouteGraph rg) {
1268 this.lines = rg.lines;
1269 this.terminals = rg.terminals;
1270 this.transientLines = rg.transientLines;
1271 this.caseId = rg.caseId;
1272 this.isSimpleConnection = rg.isSimpleConnection;
1273 this.needsUpdate = rg.needsUpdate;
1277 private void reset() {
1278 lines = new ArrayList<RouteLine>();
1279 terminals = new ArrayList<RouteTerminal>();
1280 transientLines = new ArrayList<RouteLine>();
1282 isSimpleConnection = false;
1283 needsUpdate = false;
1286 public Rectangle2D getBounds() {
1287 Rectangle2D bounds = new Rectangle2D.Double();
1292 public void getBounds(Rectangle2D bounds) {
1295 double minX = Double.POSITIVE_INFINITY;
1296 double maxX = Double.NEGATIVE_INFINITY;
1297 double minY = Double.POSITIVE_INFINITY;
1298 double maxY = Double.NEGATIVE_INFINITY;
1299 for(RouteLine line : lines) {
1300 double position = line.position;
1301 if(line.isHorizontal) {
1302 minY = Math.min(minY, position);
1303 maxY = Math.max(maxY, position);
1306 minX = Math.min(minX, position);
1307 maxX = Math.max(maxX, position);
1310 for(RouteLine line : transientLines) {
1311 double position = line.position;
1312 if(line.isHorizontal) {
1313 minY = Math.min(minY, position);
1314 maxY = Math.max(maxY, position);
1317 minX = Math.min(minX, position);
1318 maxX = Math.max(maxX, position);
1321 for(RouteTerminal terminal : terminals) {
1322 double x = terminal.x;
1323 double y = terminal.y;
1324 minX = Math.min(minX, x);
1325 maxX = Math.max(maxX, x);
1326 minY = Math.min(minY, y);
1327 maxY = Math.max(maxY, y);
1329 bounds.setFrame(minX, minY, maxX-minX, maxY-minY);
1332 private static void addPathBegin(Path2D path, RoutePoint cur, RouteLine line) {
1333 double x = cur.x, y = cur.y;
1334 if(cur instanceof RouteTerminal) {
1335 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1336 if(line.isHorizontal()) {
1337 if(cur == line.getBegin())
1338 x += style.getLineEndLength(0);
1340 x -= style.getLineEndLength(2);
1343 if(cur == line.getBegin())
1344 y += style.getLineEndLength(1);
1346 y -= style.getLineEndLength(3);
1352 private static final Comparator<RoutePoint> RG_COMP = (o1, o2) -> {
1353 if (o1.getX() < o2.getX())
1355 else if (o1.getX() > o2.getX())
1357 if (o1.getY() < o2.getY())
1359 else if (o1.getY() > o2.getY())
1364 private static void addPathEnd(Path2D path, RoutePoint cur, RouteLine line) {
1365 double x = cur.x, y = cur.y;
1366 if(cur instanceof RouteTerminal) {
1367 ILineEndStyle style = ((RouteTerminal)cur).getRenderStyle();
1368 if(line.isHorizontal()) {
1369 if(cur == line.getBegin())
1370 x += style.getLineEndLength(0);
1372 x -= style.getLineEndLength(2);
1375 if(cur == line.getBegin())
1376 y += style.getLineEndLength(1);
1378 y -= style.getLineEndLength(3);
1384 public void getPath2D(Path2D path) {
1388 if(isSimpleConnection && transientLines.isEmpty()) {
1389 if(terminals.size() == 2) {
1390 RouteTerminal a = terminals.get(0);
1391 RouteTerminal b = terminals.get(1);
1392 if(a.hasDirectConnection() || b.hasDirectConnection()) {
1393 path.moveTo(a.x, a.y);
1394 path.lineTo(b.x, b.y);
1401 Map<RoutePoint, RouteLine> begins =
1402 // new THashMap<RoutePoint, RouteLine>(); //The ordering of the coordinates in the path should be deterministic between scenegraphs
1403 new TreeMap<RoutePoint, RouteLine>(RG_COMP);
1404 for(RouteLine line : lines) {
1407 for(RouteLine line : transientLines) {
1410 for(RouteTerminal terminal : terminals)
1411 if((terminal.getAllowedDirections() & 0x10)!=0 && terminal.line != null) {
1412 begins.remove(terminal.line.getBegin());
1413 drawContinuousPath(path, begins, terminal, terminal.line);
1417 for(RoutePoint begin : begins.keySet().toArray(new RoutePoint[begins.size()])) {
1418 RouteLine curLine = begins.remove(begin);
1419 drawContinuousPath(path, begins, begin, curLine);
1423 private void drawContinuousPath(Path2D path, Map<RoutePoint, RouteLine> begins,
1424 RoutePoint cur, RouteLine curLine) {
1427 addPathBegin(path, cur, curLine);
1430 if(cur != curLine.getEnd())
1431 cur = curLine.getEnd();
1433 cur = curLine.getBegin();
1434 if(begins.remove(cur) != null || !(cur instanceof RouteLink)) {
1435 addPathEnd(path, cur, curLine);
1438 if(cur instanceof RouteLink) {
1439 if(!curLine.isDegenerated() ||
1440 path.getCurrentPoint().getX() != cur.x ||
1441 path.getCurrentPoint().getY() != cur.y)
1442 path.lineTo(cur.x, cur.y);
1443 RouteLink link = (RouteLink)cur;
1444 if(link.a != curLine)
1452 private static void add(Map<RoutePoint, RouteLine> begins,
1454 if(line.points.size() > 1) {
1456 RoutePoint p = line.getBegin();
1457 if(begins.remove(p) == null)
1458 begins.put(p, line);
1461 RoutePoint p = line.getEnd();
1462 if(begins.remove(p) == null)
1463 begins.put(p, line);
1468 public Collection<Segment> getSegments() {
1471 ArrayList<Segment> segments = new ArrayList<Segment>();
1472 for(RouteLine routeLine : lines)
1473 routeLine.collectSegments(segments);
1474 for(RouteLine routeLine : transientLines)
1475 routeLine.collectSegments(segments);
1479 public Segment findNearestSegment(double x, double y) {
1480 Segment nearest = null;
1481 double minDistanceSq = Double.MAX_VALUE;
1483 for (Segment segment : getSegments()) {
1484 RoutePoint p1 = segment.p1;
1485 RoutePoint p2 = segment.p2;
1487 double distanceSq = Line2D.ptSegDistSq(p1.x, p1.y, p2.x, p2.y, x, y);
1488 if (distanceSq < minDistanceSq) {
1489 minDistanceSq = distanceSq;
1496 public Point2D findNearestPoint(double x, double y) {
1497 Segment nearest = findNearestSegment(x, y);
1498 if (nearest == null) return null;
1500 RoutePoint p1 = nearest.p1;
1501 RoutePoint p2 = nearest.p2;
1503 double d = Math.pow(p2.x - p1.x, 2.0) + Math.pow(p2.y - p1.y, 2.0);
1506 return new Point2D.Double(p1.x, p1.y);
1508 double u = ((x - p1.x) * (p2.x - p1.x) + (y - p1.y) * (p2.y - p1.y)) / d;
1510 return new Point2D.Double(p2.x, p2.y);
1511 } else if (u <= 0.0) {
1512 return new Point2D.Double(p1.x, p1.y);
1514 return new Point2D.Double(p2.x * u + p1.x * (1.0-u), (p2.y * u + p1.y * (1.0- u)));
1519 public Path2D getPath2D() {
1520 Path2D result = new Path2D.Double();
1525 public SplittedRouteGraph splitGraph(RouteLine splitLine, double position) {
1526 THashSet<RouteNode> interfaceNodes1 = new THashSet<RouteNode>();
1527 THashSet<RouteLine> lines1 = new THashSet<RouteLine>();
1528 THashSet<RouteTerminal> terminals1 = new THashSet<RouteTerminal>();
1529 THashSet<RouteNode> interfaceNodes2 = new THashSet<RouteNode>();
1530 THashSet<RouteLine> lines2 = new THashSet<RouteLine>();
1531 THashSet<RouteTerminal> terminals2 = new THashSet<RouteTerminal>();
1533 if(splitLine.isTransient()) {
1534 RouteTerminal terminal = splitLine.terminal;
1536 if(splitLine.beginsWithTerminal()) {
1537 lines2.addAll(getLines());
1538 terminals2.addAll(getTerminals());
1539 terminals1.add(terminal);
1540 terminals2.remove(terminal);
1541 interfaceNodes1.add(terminal);
1542 if(isSimpleConnection())
1543 interfaceNodes2.addAll(terminals2);
1545 interfaceNodes2.add(terminal.line);
1548 lines1.addAll(getLines());
1549 terminals1.addAll(getTerminals());
1550 terminals2.add(terminal);
1551 terminals1.remove(terminal);
1552 interfaceNodes2.add(terminal);
1553 if(isSimpleConnection())
1554 interfaceNodes1.addAll(terminals1);
1556 interfaceNodes1.add(terminal.line);
1560 for(RoutePoint rp : splitLine.getPoints()) {
1561 double p = splitLine.isHorizontal ? rp.x : rp.y;
1562 if(rp instanceof RouteLink) {
1563 RouteLink link = (RouteLink)rp;
1564 RouteLine otherLine = link.getA() != splitLine ? link.getA()
1566 if(otherLine.isTransient()) {
1568 interfaceNodes1.add(otherLine.terminal);
1569 terminals1.add(otherLine.terminal);
1572 interfaceNodes2.add(otherLine.terminal);
1573 terminals2.add(otherLine.terminal);
1579 interfaceNodes1.add(otherLine);
1580 traverseGraph(link, otherLine, lines1);
1583 interfaceNodes2.add(otherLine);
1584 traverseGraph(link, otherLine, lines2);
1589 for(RouteTerminal terminal : getTerminals())
1590 if(lines1.contains(terminal.line))
1591 terminals1.add(terminal);
1592 else if(lines2.contains(terminal.line))
1593 terminals2.add(terminal);
1596 return new SplittedRouteGraph(splitLine,
1597 interfaceNodes1, lines1, terminals1,
1598 interfaceNodes2, lines2, terminals2);
1601 private void traverseGraph(RoutePoint previousPoint, RouteLine line,
1602 THashSet<RouteLine> lines) {
1603 if(lines.add(line)) {
1604 for(RoutePoint rp : line.getPoints()) {
1605 if(rp != previousPoint && rp instanceof RouteLink) {
1606 RouteLink link = (RouteLink)rp;
1607 RouteLine otherLine = line != link.getA()
1608 ? link.getA() : link.getB();
1609 if(otherLine.isTransient())
1611 traverseGraph(rp, otherLine, lines);
1617 public void reclaimTransientMemory() {
1618 removeTransientRouteLines();