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

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