X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.g2d%2Fsrc%2Forg%2Fsimantics%2Fg2d%2Frouting%2Falgorithm2%2FRouter3.java;fp=bundles%2Forg.simantics.g2d%2Fsrc%2Forg%2Fsimantics%2Fg2d%2Frouting%2Falgorithm2%2FRouter3.java;h=7ee89a20f00704415b6084013eb7b4f38a002a44;hb=0ae2b770234dfc3cbb18bd38f324125cf0faca07;hp=1bceae469d210b1b6171f93777de098a3ce9568d;hpb=24e2b34260f219f0d1644ca7a138894980e25b14;p=simantics%2Fplatform.git diff --git a/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router3.java b/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router3.java index 1bceae469..7ee89a20f 100644 --- a/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router3.java +++ b/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router3.java @@ -1,283 +1,283 @@ -/******************************************************************************* - * 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.algorithm2; - -import gnu.trove.map.hash.TObjectIntHashMap; - -import java.awt.geom.AffineTransform; -import java.awt.geom.Path2D; -import java.awt.geom.PathIterator; -import java.awt.geom.Rectangle2D; -import java.util.ArrayList; -import java.util.Collection; - -import org.simantics.g2d.routing.Constants; -import org.simantics.g2d.routing.IConnection; -import org.simantics.g2d.routing.IConnection.Connector; -import org.simantics.g2d.routing.IRouter2; - -public class Router3 implements IRouter2 { - - LocalRouter localRouter; - - public Router3(boolean roundCorners) { - this.localRouter = new LocalRouter(roundCorners); - } - - private Path2D route(double beginX, double beginY, int sDir, Rectangle2D beginObstacle, - double endX, double endY, int tDir, Rectangle2D endObstacle) { - localRouter.sx = beginX; - localRouter.sy = beginY; - if(beginObstacle == null) { - localRouter.aMinX = beginX; - localRouter.aMinY = beginY; - localRouter.aMaxX = beginX; - localRouter.aMaxY = beginY; - } - else { - localRouter.aMinX = beginObstacle.getMinX(); - localRouter.aMinY = beginObstacle.getMinY(); - localRouter.aMaxX = beginObstacle.getMaxX(); - localRouter.aMaxY = beginObstacle.getMaxY(); - } - localRouter.sourceDirection = sDir; - - localRouter.tx = endX; - localRouter.ty = endY; - if(endObstacle == null) { - localRouter.bMinX = endX; - localRouter.bMinY = endY; - localRouter.bMaxX = endX; - localRouter.bMaxY = endY; - } - else { - localRouter.bMinX = endObstacle.getMinX(); - localRouter.bMinY = endObstacle.getMinY(); - localRouter.bMaxX = endObstacle.getMaxX(); - localRouter.bMaxY = endObstacle.getMaxY(); - } - localRouter.targetDirection = tDir; - - localRouter.route(); - - return localRouter.path; - } - - @Override - public void route(IConnection connection) { -// System.out.println("route"); - - Collection segments = connection.getSegments(); - if(segments.size() == 1) - for(Object seg : segments) { - Connector begin = connection.getBegin(seg); - Connector end = connection.getEnd(seg); - - double bestLength = Double.POSITIVE_INFINITY; - Path2D bestPath = null; - - for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections]) - for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) { - Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle, - end.x, end.y, tDir, end.parentObstacle); - - double length = pathCost(path); - if(length < bestLength) { - bestLength = length; - bestPath = localRouter.path; - } - } - - if(bestPath != null) - connection.setPath(seg, bestPath); - } - else { - - SegmentInfo[] sInfos = new SegmentInfo[segments.size()]; - TObjectIntHashMap connectorIds = new TObjectIntHashMap(); - int sId = 0; - int cId = 0; - for(Object seg : segments) { - Connector begin = connection.getBegin(seg); - Connector end = connection.getEnd(seg); - - SegmentInfo sInfo = new SegmentInfo(); - sInfo.segment = seg; - if(connectorIds.contains(begin)) - sInfo.begin = connectorIds.get(begin); - else { - sInfo.begin = cId; - connectorIds.put(begin, cId); - cId += 4; - } - if(connectorIds.contains(end)) - sInfo.end = connectorIds.get(end); - else { - sInfo.end = cId; - connectorIds.put(end, cId); - cId += 4; - } - - for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections]) - for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) { - Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle, - end.x, end.y, tDir, end.parentObstacle); - - sInfo.candidates.add(new SegmentCandidate( - path, pathCost(path), - sDir, tDir - )); - } - - sInfos[sId++] = sInfo; - } - - bestCost = Double.POSITIVE_INFINITY; - bestPaths = new Path2D[sId]; - findBestCandidate(0, sInfos, new Path2D[sId], new int[cId], 0.0); - //System.out.println("cost: " + bestCost); - for(int i=0;i= bestCost) - return; - if(seg < sInfos.length) { - for(SegmentCandidate sCand : sInfos[seg].candidates) { - chosen[seg] = sCand.path; - int sId = sInfos[seg].begin + sCand.sDir; - int tId = sInfos[seg].end + sCand.tDir; - double nCost = cost + sCand.localCost; - if(++dirCounts[sId] > 1) - nCost += 10.0; - nCost += 2.0 * (dirCounts[sId ^ 1] + dirCounts[sId ^ 3]); - if(++dirCounts[tId] > 1) - nCost += 10.0; - nCost += 2.0 * (dirCounts[tId ^ 1] + dirCounts[tId ^ 3]); - for(int i=0;i candidates = new ArrayList(4); - } - - static class SegmentCandidate { - Path2D path; - double localCost; - int sDir; - int tDir; - - public SegmentCandidate(Path2D path, double localCost, int sDir, int tDir) { - this.path = path; - this.localCost = localCost; - this.sDir = sDir; - this.tDir = tDir; - } - - } - - final static AffineTransform identity = new AffineTransform(); - - static int intersections(Path2D path1, Path2D path2) { - int count = 0; - PathIterator it1 = path1.getPathIterator(identity); - double begin1X = 0.0, begin1Y = 0.0, end1X = 0.0, end1Y = 0.0; - double begin2X = 0.0, begin2Y = 0.0, end2X = 0.0, end2Y = 0.0; - double[] temp = new double[6]; - while(!it1.isDone()) { - int t1 = it1.currentSegment(temp); - if(t1 == PathIterator.SEG_MOVETO) { - end1X = temp[0]; - end1Y = temp[1]; - } - else if(t1 == PathIterator.SEG_LINETO) { - begin1X = end1X; - begin1Y = end1Y; - end1X = temp[0]; - end1Y = temp[1]; - - double min1X, min1Y, max1X, max1Y; - if(begin1X < end1X) { min1X = begin1X; max1X = end1X; } - else { max1X = begin1X; min1X = end1X; } - if(begin1Y < end1Y) { min1Y = begin1Y; max1Y = end1Y; } - else { max1Y = begin1Y; min1Y = end1Y; } - - PathIterator it2 = path2.getPathIterator(identity); - while(!it2.isDone()) { - int t2 = it2.currentSegment(temp); - if(t2 == PathIterator.SEG_MOVETO) { - end2X = temp[0]; - end2Y = temp[1]; - } - else if(t2 == PathIterator.SEG_LINETO) { - begin2X = end2X; - begin2Y = end2Y; - end2X = temp[0]; - end2Y = temp[1]; - - double min2X, min2Y, max2X, max2Y; - if(begin2X < end2X) { min2X = begin2X; max2X = end2X; } - else { max2X = begin2X; min2X = end2X; } - if(begin2Y < end2Y) { min2Y = begin2Y; max2Y = end2Y; } - else { max2Y = begin2Y; min2Y = end2Y; } - - if( ((min1X < min2X && max2X < max1X) || (min2X < min1X && max1X < max2X)) && - ((min1Y < min2Y && max2Y < max1Y) || (min2Y < min1Y && max1Y < max2Y)) ) - ++ count; - } - it2.next(); - } - } - it1.next(); - } - return count; - } - - final static AffineTransform IDENTITY = new AffineTransform(); - - static double pathCost(Path2D path) { - double length = 0.0; - PathIterator it = path.getPathIterator(IDENTITY); - double[] temp = new double[6]; - double x=0.0, y=0.0; - double bendCount = 0.0; - while(!it.isDone()) { - bendCount += 1.0; - if(it.currentSegment(temp) != PathIterator.SEG_MOVETO) - length += Math.abs(x - temp[0] + y - temp[1]); - x = temp[0]; - y = temp[1]; - it.next(); - } - //return length * (6.0 + bendCount); - return bendCount - 1.0 / length; - } -} +/******************************************************************************* + * 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.algorithm2; + +import gnu.trove.map.hash.TObjectIntHashMap; + +import java.awt.geom.AffineTransform; +import java.awt.geom.Path2D; +import java.awt.geom.PathIterator; +import java.awt.geom.Rectangle2D; +import java.util.ArrayList; +import java.util.Collection; + +import org.simantics.g2d.routing.Constants; +import org.simantics.g2d.routing.IConnection; +import org.simantics.g2d.routing.IConnection.Connector; +import org.simantics.g2d.routing.IRouter2; + +public class Router3 implements IRouter2 { + + LocalRouter localRouter; + + public Router3(boolean roundCorners) { + this.localRouter = new LocalRouter(roundCorners); + } + + private Path2D route(double beginX, double beginY, int sDir, Rectangle2D beginObstacle, + double endX, double endY, int tDir, Rectangle2D endObstacle) { + localRouter.sx = beginX; + localRouter.sy = beginY; + if(beginObstacle == null) { + localRouter.aMinX = beginX; + localRouter.aMinY = beginY; + localRouter.aMaxX = beginX; + localRouter.aMaxY = beginY; + } + else { + localRouter.aMinX = beginObstacle.getMinX(); + localRouter.aMinY = beginObstacle.getMinY(); + localRouter.aMaxX = beginObstacle.getMaxX(); + localRouter.aMaxY = beginObstacle.getMaxY(); + } + localRouter.sourceDirection = sDir; + + localRouter.tx = endX; + localRouter.ty = endY; + if(endObstacle == null) { + localRouter.bMinX = endX; + localRouter.bMinY = endY; + localRouter.bMaxX = endX; + localRouter.bMaxY = endY; + } + else { + localRouter.bMinX = endObstacle.getMinX(); + localRouter.bMinY = endObstacle.getMinY(); + localRouter.bMaxX = endObstacle.getMaxX(); + localRouter.bMaxY = endObstacle.getMaxY(); + } + localRouter.targetDirection = tDir; + + localRouter.route(); + + return localRouter.path; + } + + @Override + public void route(IConnection connection) { +// System.out.println("route"); + + Collection segments = connection.getSegments(); + if(segments.size() == 1) + for(Object seg : segments) { + Connector begin = connection.getBegin(seg); + Connector end = connection.getEnd(seg); + + double bestLength = Double.POSITIVE_INFINITY; + Path2D bestPath = null; + + for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections]) + for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) { + Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle, + end.x, end.y, tDir, end.parentObstacle); + + double length = pathCost(path); + if(length < bestLength) { + bestLength = length; + bestPath = localRouter.path; + } + } + + if(bestPath != null) + connection.setPath(seg, bestPath); + } + else { + + SegmentInfo[] sInfos = new SegmentInfo[segments.size()]; + TObjectIntHashMap connectorIds = new TObjectIntHashMap(); + int sId = 0; + int cId = 0; + for(Object seg : segments) { + Connector begin = connection.getBegin(seg); + Connector end = connection.getEnd(seg); + + SegmentInfo sInfo = new SegmentInfo(); + sInfo.segment = seg; + if(connectorIds.contains(begin)) + sInfo.begin = connectorIds.get(begin); + else { + sInfo.begin = cId; + connectorIds.put(begin, cId); + cId += 4; + } + if(connectorIds.contains(end)) + sInfo.end = connectorIds.get(end); + else { + sInfo.end = cId; + connectorIds.put(end, cId); + cId += 4; + } + + for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections]) + for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) { + Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle, + end.x, end.y, tDir, end.parentObstacle); + + sInfo.candidates.add(new SegmentCandidate( + path, pathCost(path), + sDir, tDir + )); + } + + sInfos[sId++] = sInfo; + } + + bestCost = Double.POSITIVE_INFINITY; + bestPaths = new Path2D[sId]; + findBestCandidate(0, sInfos, new Path2D[sId], new int[cId], 0.0); + //System.out.println("cost: " + bestCost); + for(int i=0;i= bestCost) + return; + if(seg < sInfos.length) { + for(SegmentCandidate sCand : sInfos[seg].candidates) { + chosen[seg] = sCand.path; + int sId = sInfos[seg].begin + sCand.sDir; + int tId = sInfos[seg].end + sCand.tDir; + double nCost = cost + sCand.localCost; + if(++dirCounts[sId] > 1) + nCost += 10.0; + nCost += 2.0 * (dirCounts[sId ^ 1] + dirCounts[sId ^ 3]); + if(++dirCounts[tId] > 1) + nCost += 10.0; + nCost += 2.0 * (dirCounts[tId ^ 1] + dirCounts[tId ^ 3]); + for(int i=0;i candidates = new ArrayList(4); + } + + static class SegmentCandidate { + Path2D path; + double localCost; + int sDir; + int tDir; + + public SegmentCandidate(Path2D path, double localCost, int sDir, int tDir) { + this.path = path; + this.localCost = localCost; + this.sDir = sDir; + this.tDir = tDir; + } + + } + + final static AffineTransform identity = new AffineTransform(); + + static int intersections(Path2D path1, Path2D path2) { + int count = 0; + PathIterator it1 = path1.getPathIterator(identity); + double begin1X = 0.0, begin1Y = 0.0, end1X = 0.0, end1Y = 0.0; + double begin2X = 0.0, begin2Y = 0.0, end2X = 0.0, end2Y = 0.0; + double[] temp = new double[6]; + while(!it1.isDone()) { + int t1 = it1.currentSegment(temp); + if(t1 == PathIterator.SEG_MOVETO) { + end1X = temp[0]; + end1Y = temp[1]; + } + else if(t1 == PathIterator.SEG_LINETO) { + begin1X = end1X; + begin1Y = end1Y; + end1X = temp[0]; + end1Y = temp[1]; + + double min1X, min1Y, max1X, max1Y; + if(begin1X < end1X) { min1X = begin1X; max1X = end1X; } + else { max1X = begin1X; min1X = end1X; } + if(begin1Y < end1Y) { min1Y = begin1Y; max1Y = end1Y; } + else { max1Y = begin1Y; min1Y = end1Y; } + + PathIterator it2 = path2.getPathIterator(identity); + while(!it2.isDone()) { + int t2 = it2.currentSegment(temp); + if(t2 == PathIterator.SEG_MOVETO) { + end2X = temp[0]; + end2Y = temp[1]; + } + else if(t2 == PathIterator.SEG_LINETO) { + begin2X = end2X; + begin2Y = end2Y; + end2X = temp[0]; + end2Y = temp[1]; + + double min2X, min2Y, max2X, max2Y; + if(begin2X < end2X) { min2X = begin2X; max2X = end2X; } + else { max2X = begin2X; min2X = end2X; } + if(begin2Y < end2Y) { min2Y = begin2Y; max2Y = end2Y; } + else { max2Y = begin2Y; min2Y = end2Y; } + + if( ((min1X < min2X && max2X < max1X) || (min2X < min1X && max1X < max2X)) && + ((min1Y < min2Y && max2Y < max1Y) || (min2Y < min1Y && max1Y < max2Y)) ) + ++ count; + } + it2.next(); + } + } + it1.next(); + } + return count; + } + + final static AffineTransform IDENTITY = new AffineTransform(); + + static double pathCost(Path2D path) { + double length = 0.0; + PathIterator it = path.getPathIterator(IDENTITY); + double[] temp = new double[6]; + double x=0.0, y=0.0; + double bendCount = 0.0; + while(!it.isDone()) { + bendCount += 1.0; + if(it.currentSegment(temp) != PathIterator.SEG_MOVETO) + length += Math.abs(x - temp[0] + y - temp[1]); + x = temp[0]; + y = temp[1]; + it.next(); + } + //return length * (6.0 + bendCount); + return bendCount - 1.0 / length; + } +}