bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm1/Router.java

   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
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.g2d.routing.algorithm1;\r
  13 \r
  14 import gnu.trove.map.hash.TCustomHashMap;\r
  15 import gnu.trove.strategy.IdentityHashingStrategy;\r
  16 \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
  24 \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
  30 \r
  31 public class Router implements IRouter {\r
  32         \r
  33         TCustomHashMap<Object, PenaltyRectangle> oldObstacles;\r
  34         TCustomHashMap<Object, ConnectionInfo> oldConnections = new TCustomHashMap<Object, ConnectionInfo>(IdentityHashingStrategy.INSTANCE);\r
  35         \r
  36         static class ConnectionInfo extends Rectangle {\r
  37 \r
  38                 Rectangle bounds;\r
  39                 int hash;\r
  40                 \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
  44                         this.hash = hash;\r
  45                 }\r
  46                 \r
  47         }\r
  48         \r
  49         @Override\r
  50         public void update(IGraphModel model) {\r
  51                 double[] coords = new double[6];\r
  52                 \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
  62                                         ); \r
  63                                 rtree.add(pRect, pRect);\r
  64                                 oldObstacles.put(obstacle, pRect);\r
  65                         }               \r
  66                 }\r
  67                 else {\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
  77                                 }\r
  78                                 else {\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
  82                                                 ); \r
  83                                         rtree.add(pRect, pRect);\r
  84                                         newObstacles.put(obstacle, pRect);\r
  85                                         modifications.add(pRect, pRect);\r
  86                                         if(oldRect != null)\r
  87                                                 modifications.add(oldRect, oldRect);\r
  88                                 }\r
  89                         }\r
  90                         oldObstacles = newObstacles;\r
  91                 }\r
  92                 \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
  98                                 if(oldInfo != null)\r
  99                                         newConnections.put(c, oldInfo);\r
 100                         }\r
 101                         for(ConnectionInfo info : oldConnections.values())\r
 102                                 modifications.add(info.bounds, info);\r
 103                 }\r
 104                 int count = 0;\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
 109                         \r
 110                         int hash = (begin == null ? 0 : begin.hashCode()) + 31 * ((end == null ? 0 : end.hashCode()) + 31 * Arrays.hashCode(routePoints));\r
 111                         \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
 117                                                 continue;\r
 118                                         }\r
 119                                         modifications.add(info.bounds, info);\r
 120                                 }\r
 121                         }\r
 122                         \r
 123                         ++ count;\r
 124                         \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
 129                         \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
 135                         }\r
 136                         \r
 137                         if(end != null) {\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
 142                         }\r
 143                         \r
 144                         for(int i=0;i<routePoints.length;i+=2) {\r
 145                                 double x = routePoints[i];\r
 146                                 if(x < x0) x0 = x;\r
 147                                 else if(x > x1) x1 = x;\r
 148                                 double y = routePoints[i+1];\r
 149                                 if(y < y0) y0 = x;\r
 150                                 else if(y > y1) y1 = x;\r
 151                         }\r
 152                         \r
 153                         final HashSet<PenaltyRectangle> rectangles = new HashSet<PenaltyRectangle>();\r
 154                         rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() {\r
 155 \r
 156                                 @Override\r
 157                                 public void call(double x0, double y0, double x1, double y1, Object value) {\r
 158                                         rectangles.add((PenaltyRectangle)value);\r
 159                                 }\r
 160                                 \r
 161                         });\r
 162                         \r
 163                         while(true) {                           \r
 164                                 \r
 165                                 Path2D path = new StaticRouter(rectangles).route(begin, routePoints, end);\r
 166                                 if(path == null)\r
 167                                         break;\r
 168                                 \r
 169                                 Rectangle2D rect = path.getBounds2D();\r
 170                                 boolean contained = true;\r
 171                                 if(rect.getMinX() < x0) {\r
 172                                         x0 = rect.getMinX();\r
 173                                         contained = false;\r
 174                                 }\r
 175                                 if(rect.getMaxX() > x1) {\r
 176                                         x1 = rect.getMaxX();\r
 177                                         contained = false;\r
 178                                 }\r
 179                                 if(rect.getMinY() < y0) {\r
 180                                         y0 = rect.getMinY();\r
 181                                         contained = false;\r
 182                                 }\r
 183                                 if(rect.getMaxY() > y1) {\r
 184                                         y1 = rect.getMaxY();\r
 185                                         contained = false;\r
 186                                 }\r
 187                                 \r
 188                                 final boolean[] ff = new boolean[] { true };\r
 189                                 if(!contained) {\r
 190                                         rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() {\r
 191 \r
 192                                                 @Override\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
 196                                                                 ff[0] = false;\r
 197                                                         }\r
 198                                                 }\r
 199                                                 \r
 200                                         });\r
 201                                 }\r
 202                                 \r
 203                                 if(ff[0]) {\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
 210                                                         curX = coords[0];\r
 211                                                         curY = coords[1];\r
 212                                                         break;\r
 213                                                 case PathIterator.SEG_LINETO:\r
 214                                                         newX = coords[0];\r
 215                                                         newY = coords[1];\r
 216                                                         \r
 217                                                         PenaltyRectangle pRect;\r
 218                                                         if(newX == curX) {\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
 222                                                                         );                                                              \r
 223                                                         }\r
 224                                                         else {\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
 228                                                                         );      \r
 229                                                         }\r
 230                                                         rtree.add(pRect, pRect);\r
 231                                                         \r
 232                                                         curX = newX;\r
 233                                                         curY = newY;\r
 234                                                 }\r
 235                                                 it.next();\r
 236                                         }\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
 241                                         break;\r
 242                                 }\r
 243                         }\r
 244                         \r
 245                 \r
 246                 }\r
 247                 \r
 248                 oldConnections = newConnections;\r
 249 \r
 250                 //System.out.println("updated " + count + "/" + connections.size() + " connections");\r
 251         }       \r
 252 \r
 253 }\r