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=1bceae469d210b1b6171f93777de098a3ce9568d;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;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
new file mode 100644
index 000000000..1bceae469
--- /dev/null
+++ b/bundles/org.simantics.g2d/src/org/simantics/g2d/routing/algorithm2/Router3.java
@@ -0,0 +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<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;
+    }
+}