+/*******************************************************************************\r
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
+ * in 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.g2d.routing.algorithm1;\r
+\r
+import gnu.trove.map.hash.TCustomHashMap;\r
+import gnu.trove.strategy.IdentityHashingStrategy;\r
+\r
+import java.awt.geom.AffineTransform;\r
+import java.awt.geom.Path2D;\r
+import java.awt.geom.PathIterator;\r
+import java.awt.geom.Rectangle2D;\r
+import java.util.Arrays;\r
+import java.util.Collection;\r
+import java.util.HashSet;\r
+\r
+import org.simantics.g2d.routing.IGraphModel;\r
+import org.simantics.g2d.routing.IRouter;\r
+import org.simantics.g2d.routing.Terminal;\r
+import org.simantics.g2d.routing.spatial.IRectangleProcedure;\r
+import org.simantics.g2d.routing.spatial.RTree;\r
+\r
+public class Router implements IRouter {\r
+ \r
+ TCustomHashMap<Object, PenaltyRectangle> oldObstacles;\r
+ TCustomHashMap<Object, ConnectionInfo> oldConnections = new TCustomHashMap<Object, ConnectionInfo>(IdentityHashingStrategy.INSTANCE);\r
+ \r
+ static class ConnectionInfo extends Rectangle {\r
+\r
+ Rectangle bounds;\r
+ int hash;\r
+ \r
+ public ConnectionInfo(double x0, double y0, double x1, double y1, Rectangle bounds, int hash) {\r
+ super(x0, y0, x1, y1);\r
+ this.bounds = bounds;\r
+ this.hash = hash;\r
+ }\r
+ \r
+ }\r
+ \r
+ @Override\r
+ public void update(IGraphModel model) {\r
+ double[] coords = new double[6];\r
+ \r
+ RTree rtree = new RTree();\r
+ RTree modifications = null;\r
+ if(oldObstacles == null) {\r
+ oldObstacles = new TCustomHashMap<Object, PenaltyRectangle>(IdentityHashingStrategy.INSTANCE);\r
+ for(Object obstacle : model.getObstacles()) {\r
+ Rectangle2D rect2d = model.getObstacleShape(obstacle);\r
+ PenaltyRectangle pRect = new PenaltyRectangle(\r
+ rect2d.getMinX(), rect2d.getMinY(), rect2d.getMaxX(), rect2d.getMaxY(),\r
+ Penalty.OBSTACLE_PENALTY, Penalty.OBSTACLE_PENALTY\r
+ ); \r
+ rtree.add(pRect, pRect);\r
+ oldObstacles.put(obstacle, pRect);\r
+ } \r
+ }\r
+ else {\r
+ modifications = new RTree();\r
+ TCustomHashMap<Object, PenaltyRectangle> newObstacles = new TCustomHashMap<Object, PenaltyRectangle>(IdentityHashingStrategy.INSTANCE); \r
+ for(Object obstacle : model.getObstacles()) {\r
+ Rectangle2D rect2d = model.getObstacleShape(obstacle);\r
+ PenaltyRectangle oldRect = oldObstacles.remove(obstacle);\r
+ if(oldRect != null && rect2d.getMinX() == oldRect.x0 && rect2d.getMaxX() == oldRect.x1 &&\r
+ rect2d.getMinY() == oldRect.y0 && rect2d.getMaxY() == oldRect.y1) {\r
+ newObstacles.put(obstacle, oldRect);\r
+ rtree.add(oldRect, oldRect);\r
+ }\r
+ else {\r
+ PenaltyRectangle pRect = new PenaltyRectangle(\r
+ rect2d.getMinX(), rect2d.getMinY(), rect2d.getMaxX(), rect2d.getMaxY(),\r
+ Penalty.OBSTACLE_PENALTY, Penalty.OBSTACLE_PENALTY\r
+ ); \r
+ rtree.add(pRect, pRect);\r
+ newObstacles.put(obstacle, pRect);\r
+ modifications.add(pRect, pRect);\r
+ if(oldRect != null)\r
+ modifications.add(oldRect, oldRect);\r
+ }\r
+ }\r
+ oldObstacles = newObstacles;\r
+ }\r
+ \r
+ TCustomHashMap<Object, ConnectionInfo> newConnections = new TCustomHashMap<Object, ConnectionInfo>(IdentityHashingStrategy.INSTANCE);\r
+ Collection<Object> connections = model.getConnections();\r
+ if(modifications != null) { \r
+ for(Object c : connections) {\r
+ ConnectionInfo oldInfo = oldConnections.remove(c);\r
+ if(oldInfo != null)\r
+ newConnections.put(c, oldInfo);\r
+ }\r
+ for(ConnectionInfo info : oldConnections.values())\r
+ modifications.add(info.bounds, info);\r
+ }\r
+ int count = 0;\r
+ for(Object c : connections) {\r
+ Terminal begin = model.getBeginTerminal(c);\r
+ double[] routePoints = model.getRoutePoints(c);\r
+ Terminal end = model.getEndTerminal(c); \r
+ \r
+ int hash = (begin == null ? 0 : begin.hashCode()) + 31 * ((end == null ? 0 : end.hashCode()) + 31 * Arrays.hashCode(routePoints));\r
+ \r
+ if(modifications != null) {\r
+ ConnectionInfo info = newConnections.get(c);\r
+ if(info != null) { \r
+ if(hash==info.hash && !modifications.intersects(info)) {\r
+ newConnections.put(c, info);\r
+ continue;\r
+ }\r
+ modifications.add(info.bounds, info);\r
+ }\r
+ }\r
+ \r
+ ++ count;\r
+ \r
+ double x0 = Double.POSITIVE_INFINITY;\r
+ double y0 = Double.POSITIVE_INFINITY;\r
+ double x1 = Double.NEGATIVE_INFINITY;\r
+ double y1 = Double.NEGATIVE_INFINITY;\r
+ \r
+ if(begin != null) {\r
+ if(begin.x < x0) x0 = begin.x;\r
+ else if(begin.x > x1) x1 = begin.x;\r
+ if(begin.y < y0) y0 = begin.x;\r
+ else if(begin.y > y1) y1 = begin.x;\r
+ }\r
+ \r
+ if(end != null) {\r
+ if(end.x < x0) x0 = end.x;\r
+ else if(end.x > x1) x1 = end.x;\r
+ if(end.y < y0) y0 = end.x;\r
+ else if(end.y > y1) y1 = end.x;\r
+ }\r
+ \r
+ for(int i=0;i<routePoints.length;i+=2) {\r
+ double x = routePoints[i];\r
+ if(x < x0) x0 = x;\r
+ else if(x > x1) x1 = x;\r
+ double y = routePoints[i+1];\r
+ if(y < y0) y0 = x;\r
+ else if(y > y1) y1 = x;\r
+ }\r
+ \r
+ final HashSet<PenaltyRectangle> rectangles = new HashSet<PenaltyRectangle>();\r
+ rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() {\r
+\r
+ @Override\r
+ public void call(double x0, double y0, double x1, double y1, Object value) {\r
+ rectangles.add((PenaltyRectangle)value);\r
+ }\r
+ \r
+ });\r
+ \r
+ while(true) { \r
+ \r
+ Path2D path = new StaticRouter(rectangles).route(begin, routePoints, end);\r
+ if(path == null)\r
+ break;\r
+ \r
+ Rectangle2D rect = path.getBounds2D();\r
+ boolean contained = true;\r
+ if(rect.getMinX() < x0) {\r
+ x0 = rect.getMinX();\r
+ contained = false;\r
+ }\r
+ if(rect.getMaxX() > x1) {\r
+ x1 = rect.getMaxX();\r
+ contained = false;\r
+ }\r
+ if(rect.getMinY() < y0) {\r
+ y0 = rect.getMinY();\r
+ contained = false;\r
+ }\r
+ if(rect.getMaxY() > y1) {\r
+ y1 = rect.getMaxY();\r
+ contained = false;\r
+ }\r
+ \r
+ final boolean[] ff = new boolean[] { true };\r
+ if(!contained) {\r
+ rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() {\r
+\r
+ @Override\r
+ public void call(double x0, double y0, double x1, double y1, Object value) {\r
+ if(!rectangles.contains(value)) {\r
+ rectangles.add((PenaltyRectangle)value);\r
+ ff[0] = false;\r
+ }\r
+ }\r
+ \r
+ });\r
+ }\r
+ \r
+ if(ff[0]) {\r
+ model.setPath(c, path);\r
+ PathIterator it = path.getPathIterator(new AffineTransform());\r
+ double curX = 0.0, curY = 0.0, newX = 0.0, newY = 0.0;\r
+ while(!it.isDone()) { \r
+ switch(it.currentSegment(coords)) {\r
+ case PathIterator.SEG_MOVETO:\r
+ curX = coords[0];\r
+ curY = coords[1];\r
+ break;\r
+ case PathIterator.SEG_LINETO:\r
+ newX = coords[0];\r
+ newY = coords[1];\r
+ \r
+ PenaltyRectangle pRect;\r
+ if(newX == curX) {\r
+ pRect = new PenaltyRectangle(\r
+ curX-Penalty.CONNECTION_MARGINAL, Math.min(curY, newY), curX+Penalty.CONNECTION_MARGINAL, Math.max(curY, newY),\r
+ Penalty.CONNECTION_CROSS_PENALTY, Penalty.CONNECTION_SIDE_PENALTY\r
+ ); \r
+ }\r
+ else {\r
+ pRect = new PenaltyRectangle(\r
+ Math.min(curX, newX), curY-Penalty.CONNECTION_MARGINAL, Math.max(curX, newX), curY+Penalty.CONNECTION_MARGINAL, \r
+ Penalty.CONNECTION_SIDE_PENALTY, Penalty.CONNECTION_CROSS_PENALTY\r
+ ); \r
+ }\r
+ rtree.add(pRect, pRect);\r
+ \r
+ curX = newX;\r
+ curY = newY;\r
+ }\r
+ it.next();\r
+ }\r
+ ConnectionInfo info = new ConnectionInfo(x0, y0, x1, y1, Rectangle.of(path.getBounds2D()), hash);\r
+ if(modifications != null)\r
+ modifications.add(info.bounds, info);\r
+ newConnections.put(c, info); \r
+ break;\r
+ }\r
+ }\r
+ \r
+ \r
+ }\r
+ \r
+ oldConnections = newConnections;\r
+\r
+ //System.out.println("updated " + count + "/" + connections.size() + " connections");\r
+ } \r
+\r
+}\r