1 /*******************************************************************************
\r
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
\r
3 * in Industry THTH ry.
\r
4 * All rights reserved. This program and the accompanying materials
\r
5 * are made available under the terms of the Eclipse Public License v1.0
\r
6 * which accompanies this distribution, and is available at
\r
7 * http://www.eclipse.org/legal/epl-v10.html
\r
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.g2d.routing.algorithm1;
\r
14 import gnu.trove.map.hash.TCustomHashMap;
\r
15 import gnu.trove.strategy.IdentityHashingStrategy;
\r
17 import java.awt.geom.AffineTransform;
\r
18 import java.awt.geom.Path2D;
\r
19 import java.awt.geom.PathIterator;
\r
20 import java.awt.geom.Rectangle2D;
\r
21 import java.util.Arrays;
\r
22 import java.util.Collection;
\r
23 import java.util.HashSet;
\r
25 import org.simantics.g2d.routing.IGraphModel;
\r
26 import org.simantics.g2d.routing.IRouter;
\r
27 import org.simantics.g2d.routing.Terminal;
\r
28 import org.simantics.g2d.routing.spatial.IRectangleProcedure;
\r
29 import org.simantics.g2d.routing.spatial.RTree;
\r
31 public class Router implements IRouter {
\r
33 TCustomHashMap<Object, PenaltyRectangle> oldObstacles;
\r
34 TCustomHashMap<Object, ConnectionInfo> oldConnections = new TCustomHashMap<Object, ConnectionInfo>(IdentityHashingStrategy.INSTANCE);
\r
36 static class ConnectionInfo extends Rectangle {
\r
41 public ConnectionInfo(double x0, double y0, double x1, double y1, Rectangle bounds, int hash) {
\r
42 super(x0, y0, x1, y1);
\r
43 this.bounds = bounds;
\r
50 public void update(IGraphModel model) {
\r
51 double[] coords = new double[6];
\r
53 RTree rtree = new RTree();
\r
54 RTree modifications = null;
\r
55 if(oldObstacles == null) {
\r
56 oldObstacles = new TCustomHashMap<Object, PenaltyRectangle>(IdentityHashingStrategy.INSTANCE);
\r
57 for(Object obstacle : model.getObstacles()) {
\r
58 Rectangle2D rect2d = model.getObstacleShape(obstacle);
\r
59 PenaltyRectangle pRect = new PenaltyRectangle(
\r
60 rect2d.getMinX(), rect2d.getMinY(), rect2d.getMaxX(), rect2d.getMaxY(),
\r
61 Penalty.OBSTACLE_PENALTY, Penalty.OBSTACLE_PENALTY
\r
63 rtree.add(pRect, pRect);
\r
64 oldObstacles.put(obstacle, pRect);
\r
68 modifications = new RTree();
\r
69 TCustomHashMap<Object, PenaltyRectangle> newObstacles = new TCustomHashMap<Object, PenaltyRectangle>(IdentityHashingStrategy.INSTANCE);
\r
70 for(Object obstacle : model.getObstacles()) {
\r
71 Rectangle2D rect2d = model.getObstacleShape(obstacle);
\r
72 PenaltyRectangle oldRect = oldObstacles.remove(obstacle);
\r
73 if(oldRect != null && rect2d.getMinX() == oldRect.x0 && rect2d.getMaxX() == oldRect.x1 &&
\r
74 rect2d.getMinY() == oldRect.y0 && rect2d.getMaxY() == oldRect.y1) {
\r
75 newObstacles.put(obstacle, oldRect);
\r
76 rtree.add(oldRect, oldRect);
\r
79 PenaltyRectangle pRect = new PenaltyRectangle(
\r
80 rect2d.getMinX(), rect2d.getMinY(), rect2d.getMaxX(), rect2d.getMaxY(),
\r
81 Penalty.OBSTACLE_PENALTY, Penalty.OBSTACLE_PENALTY
\r
83 rtree.add(pRect, pRect);
\r
84 newObstacles.put(obstacle, pRect);
\r
85 modifications.add(pRect, pRect);
\r
87 modifications.add(oldRect, oldRect);
\r
90 oldObstacles = newObstacles;
\r
93 TCustomHashMap<Object, ConnectionInfo> newConnections = new TCustomHashMap<Object, ConnectionInfo>(IdentityHashingStrategy.INSTANCE);
\r
94 Collection<Object> connections = model.getConnections();
\r
95 if(modifications != null) {
\r
96 for(Object c : connections) {
\r
97 ConnectionInfo oldInfo = oldConnections.remove(c);
\r
99 newConnections.put(c, oldInfo);
\r
101 for(ConnectionInfo info : oldConnections.values())
\r
102 modifications.add(info.bounds, info);
\r
105 for(Object c : connections) {
\r
106 Terminal begin = model.getBeginTerminal(c);
\r
107 double[] routePoints = model.getRoutePoints(c);
\r
108 Terminal end = model.getEndTerminal(c);
\r
110 int hash = (begin == null ? 0 : begin.hashCode()) + 31 * ((end == null ? 0 : end.hashCode()) + 31 * Arrays.hashCode(routePoints));
\r
112 if(modifications != null) {
\r
113 ConnectionInfo info = newConnections.get(c);
\r
114 if(info != null) {
\r
115 if(hash==info.hash && !modifications.intersects(info)) {
\r
116 newConnections.put(c, info);
\r
119 modifications.add(info.bounds, info);
\r
125 double x0 = Double.POSITIVE_INFINITY;
\r
126 double y0 = Double.POSITIVE_INFINITY;
\r
127 double x1 = Double.NEGATIVE_INFINITY;
\r
128 double y1 = Double.NEGATIVE_INFINITY;
\r
130 if(begin != null) {
\r
131 if(begin.x < x0) x0 = begin.x;
\r
132 else if(begin.x > x1) x1 = begin.x;
\r
133 if(begin.y < y0) y0 = begin.x;
\r
134 else if(begin.y > y1) y1 = begin.x;
\r
138 if(end.x < x0) x0 = end.x;
\r
139 else if(end.x > x1) x1 = end.x;
\r
140 if(end.y < y0) y0 = end.x;
\r
141 else if(end.y > y1) y1 = end.x;
\r
144 for(int i=0;i<routePoints.length;i+=2) {
\r
145 double x = routePoints[i];
\r
147 else if(x > x1) x1 = x;
\r
148 double y = routePoints[i+1];
\r
150 else if(y > y1) y1 = x;
\r
153 final HashSet<PenaltyRectangle> rectangles = new HashSet<PenaltyRectangle>();
\r
154 rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() {
\r
157 public void call(double x0, double y0, double x1, double y1, Object value) {
\r
158 rectangles.add((PenaltyRectangle)value);
\r
165 Path2D path = new StaticRouter(rectangles).route(begin, routePoints, end);
\r
169 Rectangle2D rect = path.getBounds2D();
\r
170 boolean contained = true;
\r
171 if(rect.getMinX() < x0) {
\r
172 x0 = rect.getMinX();
\r
175 if(rect.getMaxX() > x1) {
\r
176 x1 = rect.getMaxX();
\r
179 if(rect.getMinY() < y0) {
\r
180 y0 = rect.getMinY();
\r
183 if(rect.getMaxY() > y1) {
\r
184 y1 = rect.getMaxY();
\r
188 final boolean[] ff = new boolean[] { true };
\r
190 rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() {
\r
193 public void call(double x0, double y0, double x1, double y1, Object value) {
\r
194 if(!rectangles.contains(value)) {
\r
195 rectangles.add((PenaltyRectangle)value);
\r
204 model.setPath(c, path);
\r
205 PathIterator it = path.getPathIterator(new AffineTransform());
\r
206 double curX = 0.0, curY = 0.0, newX = 0.0, newY = 0.0;
\r
207 while(!it.isDone()) {
\r
208 switch(it.currentSegment(coords)) {
\r
209 case PathIterator.SEG_MOVETO:
\r
213 case PathIterator.SEG_LINETO:
\r
217 PenaltyRectangle pRect;
\r
219 pRect = new PenaltyRectangle(
\r
220 curX-Penalty.CONNECTION_MARGINAL, Math.min(curY, newY), curX+Penalty.CONNECTION_MARGINAL, Math.max(curY, newY),
\r
221 Penalty.CONNECTION_CROSS_PENALTY, Penalty.CONNECTION_SIDE_PENALTY
\r
225 pRect = new PenaltyRectangle(
\r
226 Math.min(curX, newX), curY-Penalty.CONNECTION_MARGINAL, Math.max(curX, newX), curY+Penalty.CONNECTION_MARGINAL,
\r
227 Penalty.CONNECTION_SIDE_PENALTY, Penalty.CONNECTION_CROSS_PENALTY
\r
230 rtree.add(pRect, pRect);
\r
237 ConnectionInfo info = new ConnectionInfo(x0, y0, x1, y1, Rectangle.of(path.getBounds2D()), hash);
\r
238 if(modifications != null)
\r
239 modifications.add(info.bounds, info);
\r
240 newConnections.put(c, info);
\r
248 oldConnections = newConnections;
\r
250 //System.out.println("updated " + count + "/" + connections.size() + " connections");
\r