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