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=50fb1c937dc71692af8615ec21ae98fcb5d7aea5;hb=0ae2b770234dfc3cbb18bd38f324125cf0faca07;hp=6622bf9ad44a4972ddb8d4ee2f75cdd010084cae;hpb=24e2b34260f219f0d1644ca7a138894980e25b14;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 index 6622bf9ad..50fb1c937 100644 --- 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 @@ -1,253 +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"); - } - -} +/******************************************************************************* + * 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"); + } + +}