X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.g2d%2Fsrc%2Forg%2Fsimantics%2Fg2d%2Frouting%2Falgorithm1%2FRouter.java;fp=bundles%2Forg.simantics.g2d%2Fsrc%2Forg%2Fsimantics%2Fg2d%2Frouting%2Falgorithm1%2FRouter.java;h=6622bf9ad44a4972ddb8d4ee2f75cdd010084cae;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm1/Router.java b/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm1/Router.java new file mode 100644 index 000000000..6622bf9ad --- /dev/null +++ b/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm1/Router.java @@ -0,0 +1,253 @@ +/******************************************************************************* + * Copyright (c) 2007, 2010 Association for Decentralized Information Management + * in Industry THTH ry. + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Eclipse Public License v1.0 + * which accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * VTT Technical Research Centre of Finland - initial API and implementation + *******************************************************************************/ +package org.simantics.g2d.routing.algorithm1; + +import gnu.trove.map.hash.TCustomHashMap; +import gnu.trove.strategy.IdentityHashingStrategy; + +import java.awt.geom.AffineTransform; +import java.awt.geom.Path2D; +import java.awt.geom.PathIterator; +import java.awt.geom.Rectangle2D; +import java.util.Arrays; +import java.util.Collection; +import java.util.HashSet; + +import org.simantics.g2d.routing.IGraphModel; +import org.simantics.g2d.routing.IRouter; +import org.simantics.g2d.routing.Terminal; +import org.simantics.g2d.routing.spatial.IRectangleProcedure; +import org.simantics.g2d.routing.spatial.RTree; + +public class Router implements IRouter { + + TCustomHashMap oldObstacles; + TCustomHashMap oldConnections = new TCustomHashMap(IdentityHashingStrategy.INSTANCE); + + static class ConnectionInfo extends Rectangle { + + Rectangle bounds; + int hash; + + public ConnectionInfo(double x0, double y0, double x1, double y1, Rectangle bounds, int hash) { + super(x0, y0, x1, y1); + this.bounds = bounds; + this.hash = hash; + } + + } + + @Override + public void update(IGraphModel model) { + double[] coords = new double[6]; + + RTree rtree = new RTree(); + RTree modifications = null; + if(oldObstacles == null) { + oldObstacles = new TCustomHashMap(IdentityHashingStrategy.INSTANCE); + for(Object obstacle : model.getObstacles()) { + Rectangle2D rect2d = model.getObstacleShape(obstacle); + PenaltyRectangle pRect = new PenaltyRectangle( + rect2d.getMinX(), rect2d.getMinY(), rect2d.getMaxX(), rect2d.getMaxY(), + Penalty.OBSTACLE_PENALTY, Penalty.OBSTACLE_PENALTY + ); + rtree.add(pRect, pRect); + oldObstacles.put(obstacle, pRect); + } + } + else { + modifications = new RTree(); + TCustomHashMap newObstacles = new TCustomHashMap(IdentityHashingStrategy.INSTANCE); + for(Object obstacle : model.getObstacles()) { + Rectangle2D rect2d = model.getObstacleShape(obstacle); + PenaltyRectangle oldRect = oldObstacles.remove(obstacle); + if(oldRect != null && rect2d.getMinX() == oldRect.x0 && rect2d.getMaxX() == oldRect.x1 && + rect2d.getMinY() == oldRect.y0 && rect2d.getMaxY() == oldRect.y1) { + newObstacles.put(obstacle, oldRect); + rtree.add(oldRect, oldRect); + } + else { + PenaltyRectangle pRect = new PenaltyRectangle( + rect2d.getMinX(), rect2d.getMinY(), rect2d.getMaxX(), rect2d.getMaxY(), + Penalty.OBSTACLE_PENALTY, Penalty.OBSTACLE_PENALTY + ); + rtree.add(pRect, pRect); + newObstacles.put(obstacle, pRect); + modifications.add(pRect, pRect); + if(oldRect != null) + modifications.add(oldRect, oldRect); + } + } + oldObstacles = newObstacles; + } + + TCustomHashMap newConnections = new TCustomHashMap(IdentityHashingStrategy.INSTANCE); + Collection connections = model.getConnections(); + if(modifications != null) { + for(Object c : connections) { + ConnectionInfo oldInfo = oldConnections.remove(c); + if(oldInfo != null) + newConnections.put(c, oldInfo); + } + for(ConnectionInfo info : oldConnections.values()) + modifications.add(info.bounds, info); + } + int count = 0; + for(Object c : connections) { + Terminal begin = model.getBeginTerminal(c); + double[] routePoints = model.getRoutePoints(c); + Terminal end = model.getEndTerminal(c); + + int hash = (begin == null ? 0 : begin.hashCode()) + 31 * ((end == null ? 0 : end.hashCode()) + 31 * Arrays.hashCode(routePoints)); + + if(modifications != null) { + ConnectionInfo info = newConnections.get(c); + if(info != null) { + if(hash==info.hash && !modifications.intersects(info)) { + newConnections.put(c, info); + continue; + } + modifications.add(info.bounds, info); + } + } + + ++ count; + + double x0 = Double.POSITIVE_INFINITY; + double y0 = Double.POSITIVE_INFINITY; + double x1 = Double.NEGATIVE_INFINITY; + double y1 = Double.NEGATIVE_INFINITY; + + if(begin != null) { + if(begin.x < x0) x0 = begin.x; + else if(begin.x > x1) x1 = begin.x; + if(begin.y < y0) y0 = begin.x; + else if(begin.y > y1) y1 = begin.x; + } + + if(end != null) { + if(end.x < x0) x0 = end.x; + else if(end.x > x1) x1 = end.x; + if(end.y < y0) y0 = end.x; + else if(end.y > y1) y1 = end.x; + } + + for(int i=0;i x1) x1 = x; + double y = routePoints[i+1]; + if(y < y0) y0 = x; + else if(y > y1) y1 = x; + } + + final HashSet rectangles = new HashSet(); + rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() { + + @Override + public void call(double x0, double y0, double x1, double y1, Object value) { + rectangles.add((PenaltyRectangle)value); + } + + }); + + while(true) { + + Path2D path = new StaticRouter(rectangles).route(begin, routePoints, end); + if(path == null) + break; + + Rectangle2D rect = path.getBounds2D(); + boolean contained = true; + if(rect.getMinX() < x0) { + x0 = rect.getMinX(); + contained = false; + } + if(rect.getMaxX() > x1) { + x1 = rect.getMaxX(); + contained = false; + } + if(rect.getMinY() < y0) { + y0 = rect.getMinY(); + contained = false; + } + if(rect.getMaxY() > y1) { + y1 = rect.getMaxY(); + contained = false; + } + + final boolean[] ff = new boolean[] { true }; + if(!contained) { + rtree.search(new Rectangle(x0, y0, x1, y1), new IRectangleProcedure() { + + @Override + public void call(double x0, double y0, double x1, double y1, Object value) { + if(!rectangles.contains(value)) { + rectangles.add((PenaltyRectangle)value); + ff[0] = false; + } + } + + }); + } + + if(ff[0]) { + model.setPath(c, path); + PathIterator it = path.getPathIterator(new AffineTransform()); + double curX = 0.0, curY = 0.0, newX = 0.0, newY = 0.0; + while(!it.isDone()) { + switch(it.currentSegment(coords)) { + case PathIterator.SEG_MOVETO: + curX = coords[0]; + curY = coords[1]; + break; + case PathIterator.SEG_LINETO: + newX = coords[0]; + newY = coords[1]; + + PenaltyRectangle pRect; + if(newX == curX) { + pRect = new PenaltyRectangle( + curX-Penalty.CONNECTION_MARGINAL, Math.min(curY, newY), curX+Penalty.CONNECTION_MARGINAL, Math.max(curY, newY), + Penalty.CONNECTION_CROSS_PENALTY, Penalty.CONNECTION_SIDE_PENALTY + ); + } + else { + pRect = new PenaltyRectangle( + Math.min(curX, newX), curY-Penalty.CONNECTION_MARGINAL, Math.max(curX, newX), curY+Penalty.CONNECTION_MARGINAL, + Penalty.CONNECTION_SIDE_PENALTY, Penalty.CONNECTION_CROSS_PENALTY + ); + } + rtree.add(pRect, pRect); + + curX = newX; + curY = newY; + } + it.next(); + } + ConnectionInfo info = new ConnectionInfo(x0, y0, x1, y1, Rectangle.of(path.getBounds2D()), hash); + if(modifications != null) + modifications.add(info.bounds, info); + newConnections.put(c, info); + break; + } + } + + + } + + oldConnections = newConnections; + + //System.out.println("updated " + count + "/" + connections.size() + " connections"); + } + +}