-/*******************************************************************************\r
- * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
- * in Industry THTH ry.\r
- * All rights reserved. This program and the accompanying materials\r
- * are made available under the terms of the Eclipse Public License v1.0\r
- * which accompanies this distribution, and is available at\r
- * http://www.eclipse.org/legal/epl-v10.html\r
- *\r
- * Contributors:\r
- * VTT Technical Research Centre of Finland - initial API and implementation\r
- *******************************************************************************/\r
-package org.simantics.g2d.routing.algorithm2;\r
-\r
-import gnu.trove.map.hash.TObjectIntHashMap;\r
-\r
-import java.awt.geom.AffineTransform;\r
-import java.awt.geom.Path2D;\r
-import java.awt.geom.PathIterator;\r
-import java.awt.geom.Rectangle2D;\r
-import java.util.ArrayList;\r
-import java.util.Collection;\r
-\r
-import org.simantics.g2d.routing.Constants;\r
-import org.simantics.g2d.routing.IConnection;\r
-import org.simantics.g2d.routing.IConnection.Connector;\r
-import org.simantics.g2d.routing.IRouter2;\r
-\r
-public class Router3 implements IRouter2 {\r
-\r
- LocalRouter localRouter;\r
-\r
- public Router3(boolean roundCorners) {\r
- this.localRouter = new LocalRouter(roundCorners);\r
- }\r
-\r
- private Path2D route(double beginX, double beginY, int sDir, Rectangle2D beginObstacle,\r
- double endX, double endY, int tDir, Rectangle2D endObstacle) {\r
- localRouter.sx = beginX;\r
- localRouter.sy = beginY;\r
- if(beginObstacle == null) {\r
- localRouter.aMinX = beginX;\r
- localRouter.aMinY = beginY;\r
- localRouter.aMaxX = beginX;\r
- localRouter.aMaxY = beginY;\r
- }\r
- else {\r
- localRouter.aMinX = beginObstacle.getMinX();\r
- localRouter.aMinY = beginObstacle.getMinY();\r
- localRouter.aMaxX = beginObstacle.getMaxX();\r
- localRouter.aMaxY = beginObstacle.getMaxY();\r
- }\r
- localRouter.sourceDirection = sDir;\r
-\r
- localRouter.tx = endX;\r
- localRouter.ty = endY;\r
- if(endObstacle == null) {\r
- localRouter.bMinX = endX;\r
- localRouter.bMinY = endY;\r
- localRouter.bMaxX = endX;\r
- localRouter.bMaxY = endY;\r
- }\r
- else {\r
- localRouter.bMinX = endObstacle.getMinX();\r
- localRouter.bMinY = endObstacle.getMinY();\r
- localRouter.bMaxX = endObstacle.getMaxX();\r
- localRouter.bMaxY = endObstacle.getMaxY();\r
- }\r
- localRouter.targetDirection = tDir;\r
-\r
- localRouter.route();\r
-\r
- return localRouter.path;\r
- }\r
-\r
- @Override\r
- public void route(IConnection connection) {\r
-// System.out.println("route");\r
-\r
- Collection<?> segments = connection.getSegments();\r
- if(segments.size() == 1)\r
- for(Object seg : segments) {\r
- Connector begin = connection.getBegin(seg);\r
- Connector end = connection.getEnd(seg);\r
-\r
- double bestLength = Double.POSITIVE_INFINITY;\r
- Path2D bestPath = null;\r
-\r
- for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])\r
- for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {\r
- Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,\r
- end.x, end.y, tDir, end.parentObstacle);\r
-\r
- double length = pathCost(path);\r
- if(length < bestLength) {\r
- bestLength = length;\r
- bestPath = localRouter.path;\r
- }\r
- }\r
-\r
- if(bestPath != null)\r
- connection.setPath(seg, bestPath);\r
- }\r
- else {\r
-\r
- SegmentInfo[] sInfos = new SegmentInfo[segments.size()];\r
- TObjectIntHashMap<Connector> connectorIds = new TObjectIntHashMap<Connector>();\r
- int sId = 0;\r
- int cId = 0;\r
- for(Object seg : segments) {\r
- Connector begin = connection.getBegin(seg);\r
- Connector end = connection.getEnd(seg);\r
-\r
- SegmentInfo sInfo = new SegmentInfo();\r
- sInfo.segment = seg;\r
- if(connectorIds.contains(begin))\r
- sInfo.begin = connectorIds.get(begin);\r
- else {\r
- sInfo.begin = cId;\r
- connectorIds.put(begin, cId);\r
- cId += 4;\r
- }\r
- if(connectorIds.contains(end))\r
- sInfo.end = connectorIds.get(end);\r
- else {\r
- sInfo.end = cId;\r
- connectorIds.put(end, cId);\r
- cId += 4;\r
- }\r
-\r
- for(int sDir : Constants.POSSIBLE_DIRECTIONS[begin.allowedDirections])\r
- for(int tDir : Constants.POSSIBLE_DIRECTIONS[end.allowedDirections]) {\r
- Path2D path = route(begin.x, begin.y, sDir, begin.parentObstacle,\r
- end.x, end.y, tDir, end.parentObstacle);\r
-\r
- sInfo.candidates.add(new SegmentCandidate(\r
- path, pathCost(path),\r
- sDir, tDir\r
- ));\r
- }\r
-\r
- sInfos[sId++] = sInfo;\r
- }\r
-\r
- bestCost = Double.POSITIVE_INFINITY;\r
- bestPaths = new Path2D[sId];\r
- findBestCandidate(0, sInfos, new Path2D[sId], new int[cId], 0.0);\r
- //System.out.println("cost: " + bestCost);\r
- for(int i=0;i<sId;++i) {\r
- connection.setPath(sInfos[i].segment, bestPaths[i]);\r
- }\r
- }\r
- }\r
-\r
- double bestCost;\r
- Path2D[] bestPaths;\r
-\r
- void findBestCandidate(int seg, SegmentInfo[] sInfos, Path2D[] chosen, int[] dirCounts, double cost) {\r
- if(cost >= bestCost)\r
- return;\r
- if(seg < sInfos.length) {\r
- for(SegmentCandidate sCand : sInfos[seg].candidates) {\r
- chosen[seg] = sCand.path;\r
- int sId = sInfos[seg].begin + sCand.sDir;\r
- int tId = sInfos[seg].end + sCand.tDir;\r
- double nCost = cost + sCand.localCost;\r
- if(++dirCounts[sId] > 1)\r
- nCost += 10.0;\r
- nCost += 2.0 * (dirCounts[sId ^ 1] + dirCounts[sId ^ 3]);\r
- if(++dirCounts[tId] > 1)\r
- nCost += 10.0;\r
- nCost += 2.0 * (dirCounts[tId ^ 1] + dirCounts[tId ^ 3]);\r
- for(int i=0;i<seg;++i)\r
- nCost += 10.0*intersections(chosen[i], sCand.path);\r
- findBestCandidate(seg+1, sInfos, chosen, dirCounts, nCost);\r
- --dirCounts[sId];\r
- --dirCounts[tId];\r
- }\r
- }\r
- else {\r
- bestCost = cost;\r
- System.arraycopy(chosen, 0, bestPaths, 0, seg);\r
- }\r
- }\r
-\r
- static class SegmentInfo {\r
- Object segment;\r
- int begin;\r
- int end;\r
- ArrayList<SegmentCandidate> candidates = new ArrayList<SegmentCandidate>(4);\r
- }\r
-\r
- static class SegmentCandidate {\r
- Path2D path;\r
- double localCost;\r
- int sDir;\r
- int tDir;\r
-\r
- public SegmentCandidate(Path2D path, double localCost, int sDir, int tDir) {\r
- this.path = path;\r
- this.localCost = localCost;\r
- this.sDir = sDir;\r
- this.tDir = tDir;\r
- }\r
-\r
- }\r
-\r
- final static AffineTransform identity = new AffineTransform();\r
-\r
- static int intersections(Path2D path1, Path2D path2) {\r
- int count = 0;\r
- PathIterator it1 = path1.getPathIterator(identity);\r
- double begin1X = 0.0, begin1Y = 0.0, end1X = 0.0, end1Y = 0.0;\r
- double begin2X = 0.0, begin2Y = 0.0, end2X = 0.0, end2Y = 0.0;\r
- double[] temp = new double[6];\r
- while(!it1.isDone()) {\r
- int t1 = it1.currentSegment(temp);\r
- if(t1 == PathIterator.SEG_MOVETO) {\r
- end1X = temp[0];\r
- end1Y = temp[1];\r
- }\r
- else if(t1 == PathIterator.SEG_LINETO) {\r
- begin1X = end1X;\r
- begin1Y = end1Y;\r
- end1X = temp[0];\r
- end1Y = temp[1];\r
-\r
- double min1X, min1Y, max1X, max1Y;\r
- if(begin1X < end1X) { min1X = begin1X; max1X = end1X; }\r
- else { max1X = begin1X; min1X = end1X; }\r
- if(begin1Y < end1Y) { min1Y = begin1Y; max1Y = end1Y; }\r
- else { max1Y = begin1Y; min1Y = end1Y; }\r
-\r
- PathIterator it2 = path2.getPathIterator(identity);\r
- while(!it2.isDone()) {\r
- int t2 = it2.currentSegment(temp);\r
- if(t2 == PathIterator.SEG_MOVETO) {\r
- end2X = temp[0];\r
- end2Y = temp[1];\r
- }\r
- else if(t2 == PathIterator.SEG_LINETO) {\r
- begin2X = end2X;\r
- begin2Y = end2Y;\r
- end2X = temp[0];\r
- end2Y = temp[1];\r
-\r
- double min2X, min2Y, max2X, max2Y;\r
- if(begin2X < end2X) { min2X = begin2X; max2X = end2X; }\r
- else { max2X = begin2X; min2X = end2X; }\r
- if(begin2Y < end2Y) { min2Y = begin2Y; max2Y = end2Y; }\r
- else { max2Y = begin2Y; min2Y = end2Y; }\r
-\r
- if( ((min1X < min2X && max2X < max1X) || (min2X < min1X && max1X < max2X)) &&\r
- ((min1Y < min2Y && max2Y < max1Y) || (min2Y < min1Y && max1Y < max2Y)) )\r
- ++ count;\r
- }\r
- it2.next();\r
- }\r
- }\r
- it1.next();\r
- }\r
- return count;\r
- }\r
-\r
- final static AffineTransform IDENTITY = new AffineTransform();\r
-\r
- static double pathCost(Path2D path) {\r
- double length = 0.0;\r
- PathIterator it = path.getPathIterator(IDENTITY);\r
- double[] temp = new double[6];\r
- double x=0.0, y=0.0;\r
- double bendCount = 0.0;\r
- while(!it.isDone()) {\r
- bendCount += 1.0;\r
- if(it.currentSegment(temp) != PathIterator.SEG_MOVETO)\r
- length += Math.abs(x - temp[0] + y - temp[1]);\r
- x = temp[0];\r
- y = temp[1];\r
- it.next();\r
- }\r
- //return length * (6.0 + bendCount);\r
- return bendCount - 1.0 / length;\r
- }\r
-}\r
+/*******************************************************************************
+ * 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<Connector> connectorIds = new TObjectIntHashMap<Connector>();
+ 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<sId;++i) {
+ connection.setPath(sInfos[i].segment, bestPaths[i]);
+ }
+ }
+ }
+
+ double bestCost;
+ Path2D[] bestPaths;
+
+ void findBestCandidate(int seg, SegmentInfo[] sInfos, Path2D[] chosen, int[] dirCounts, double cost) {
+ if(cost >= 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<seg;++i)
+ nCost += 10.0*intersections(chosen[i], sCand.path);
+ findBestCandidate(seg+1, sInfos, chosen, dirCounts, nCost);
+ --dirCounts[sId];
+ --dirCounts[tId];
+ }
+ }
+ else {
+ bestCost = cost;
+ System.arraycopy(chosen, 0, bestPaths, 0, seg);
+ }
+ }
+
+ static class SegmentInfo {
+ Object segment;
+ int begin;
+ int end;
+ ArrayList<SegmentCandidate> candidates = new ArrayList<SegmentCandidate>(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;
+ }
+}
Code Review / simantics / platform.git / blobdiff