1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.g2d.routing.algorithm1;
14 import java.awt.geom.Path2D;
15 import java.util.ArrayList;
16 import java.util.Arrays;
17 import java.util.Collection;
18 import java.util.Comparator;
19 import java.util.HashMap;
20 import java.util.PriorityQueue;
22 import org.simantics.g2d.routing.ConnectionDirectionUtil;
23 import org.simantics.g2d.routing.Constants;
24 import org.simantics.g2d.routing.Terminal;
25 import org.simantics.g2d.routing.algorithm1.StopSet.IStopProcedure;
26 import org.simantics.g2d.routing.algorithm1.StopSet.Line;
27 import org.simantics.g2d.routing.algorithm1.StopSet.Stop;
29 public class StaticRouter {
31 StopSet[] stopSets = new StopSet[4];
34 public StaticRouter(Collection<PenaltyRectangle> rectangles) {
35 for(int i=0;i<4;++i) {
36 Direction dir = Direction.directions[i];
37 Collection<Stop> stops= new ArrayList<Stop>(rectangles.size());
38 for(PenaltyRectangle rectangle : rectangles)
39 stops.add(new Stop((i&1) == 0 ? rectangle.xPenalty : rectangle.yPenalty,
40 dir.minSide(rectangle),
41 dir.maxSide(rectangle),
42 dir.front(rectangle)));
43 stopSets[i] = new StopSet(stops);
47 /*public StaticRouter(Collection<Rectangle2D> rectangles,
48 Collection<Path2D> paths) {
49 stopSets = new StopSet[4];
50 Collection<Rectangle> horizontalLines = new ArrayList<Rectangle>();
51 Collection<Rectangle> verticalLines = new ArrayList<Rectangle>();
53 for(Path2D path : paths) {
54 PathIterator it = path.getPathIterator(null);
57 double[] cur = new double[2];
58 it.currentSegment(cur);
60 if(old[1] == cur[1]) {
61 horizontalLines.add(new Rectangle(
62 Math.min(cur[0], old[0]),
63 cur[1]-CONNECTION_MARGINAL,
64 Math.max(cur[0], old[0]),
65 cur[1]+CONNECTION_MARGINAL
69 verticalLines.add(new Rectangle(
70 cur[0]-CONNECTION_MARGINAL,
71 Math.min(cur[1], old[1]),
72 cur[0]+CONNECTION_MARGINAL,
73 Math.max(cur[1], old[1])
82 for(int i=0;i<4;++i) {
83 Direction dir = Direction.directions[i];
84 Collection<Stop> stops= new ArrayList<Stop>(rectangles.size()+
85 horizontalLines.size()+
86 verticalLines.size());
87 for(Rectangle2D rectangle : rectangles)
88 stops.add(new Stop(obstaclePenalty,
89 dir.minSide(rectangle),
90 dir.maxSide(rectangle),
91 dir.front(rectangle)));
92 for(Rectangle rectangle : horizontalLines)
93 stops.add(new Stop((i&1)==0 ? connectionSidePenalty : connectionCrossPenalty,
94 dir.minSide(rectangle),
95 dir.maxSide(rectangle),
96 dir.front(rectangle)));
97 for(Rectangle rectangle : verticalLines)
98 stops.add(new Stop((i&1)==1 ? connectionSidePenalty : connectionCrossPenalty,
99 dir.minSide(rectangle),
100 dir.maxSide(rectangle),
101 dir.front(rectangle)));
102 stopSets[i] = new StopSet(stops);
106 static class Continuation implements Comparable<Continuation> {
115 double minTurnDistance;
119 public Continuation(Direction direction, double min, double max,
120 double front, int pos, Line line, RoutePencil parent, double penalty,
121 double minTurnDistance, double targetX, double targetY) {
122 this.direction = direction;
128 this.parent = parent;
129 this.penalty = penalty;
130 this.minTurnDistance = minTurnDistance;
131 calcDistance(targetX, targetY);
135 public int compareTo(Continuation o) {
136 if(priority < o.priority)
138 if(priority > o.priority)
140 if(distance < o.distance)
142 if(distance > o.distance)
148 public int hashCode() {
149 final int prime = 31;
150 int result = direction.getId();
152 temp = Double.doubleToLongBits(front);
153 result = prime * result + (int) (temp ^ (temp >>> 32));
154 temp = Double.doubleToLongBits(max);
155 result = prime * result + (int) (temp ^ (temp >>> 32));
156 temp = Double.doubleToLongBits(min);
157 result = prime * result + (int) (temp ^ (temp >>> 32));
162 public boolean equals(Object obj) {
167 if (getClass() != obj.getClass())
169 Continuation other = (Continuation) obj;
170 if (direction == null) {
171 if (other.direction != null)
173 } else if (direction!=other.direction)
175 if (Double.doubleToLongBits(front) != Double
176 .doubleToLongBits(other.front))
178 if (Double.doubleToLongBits(max) != Double
179 .doubleToLongBits(other.max))
181 if (Double.doubleToLongBits(min) != Double
182 .doubleToLongBits(other.min))
187 void calcDistance(double x, double y) {
190 distance = parent.distanceConstant;
191 switch(direction.getId()) {
193 if(front > parent.x1)
194 distance += parent.distanceX*parent.x1 + (front-parent.x1);
196 distance += parent.distanceX*front;
197 distance += Math.abs(x-front);
199 distance += parent.distanceY*min + (min - y);
201 distance += parent.distanceY*max + (y - max);
203 distance += parent.distanceY*y;
205 case Constants.SOUTH:
206 if(front > parent.y1)
207 distance += parent.distanceY*parent.y1 + (front-parent.y1);
209 distance += parent.distanceY*front;
210 distance += Math.abs(y-front);
212 distance += parent.distanceX*min + (min - x);
214 distance += parent.distanceX*max + (x - max);
216 distance += parent.distanceX*x;
219 if(-front < parent.x0)
220 distance += parent.distanceX*parent.x0 + (parent.x0+front);
222 distance += parent.distanceX*(-front);
223 distance += Math.abs(x+front);
225 distance += parent.distanceY*min + (min - y);
227 distance += parent.distanceY*max + (y - max);
229 distance += parent.distanceY*y;
231 case Constants.NORTH:
232 if(-front < parent.y0)
233 distance += parent.distanceY*parent.y0 + (parent.y0+front);
235 distance += parent.distanceY*(-front);
236 distance += Math.abs(y+front);
238 distance += parent.distanceX*min + (min - x);
240 distance += parent.distanceX*max + (x - max);
242 distance += parent.distanceX*x;
249 static class Cost implements Comparable<Cost> {
253 public Cost(double penalty, double distance) {
254 this.penalty = penalty;
255 this.distance = distance;
259 public int compareTo(Cost o) {
260 if(penalty < o.penalty)
262 if(penalty > o.penalty)
264 if(distance < o.distance)
266 if(distance > o.distance)
273 PriorityQueue<Continuation> queue = new PriorityQueue<Continuation>();
274 double targetX, targetY;
275 RoutePencil[] targets;
277 RoutePencil[] solutions = new RoutePencil[4];
278 int requiredSolutionCount;
279 double bPenalty = Double.POSITIVE_INFINITY;
280 double bDistance = Double.POSITIVE_INFINITY;
281 Cost[] sortedCosts = new Cost[4];
282 HashMap<Continuation, Continuation> continuations = new HashMap<Continuation, Continuation>();
285 double targetX, double targetY,
286 RoutePencil[] targets, int targetDirs,
287 int requiredSolutionCount) {
288 this.targetX = targetX;
289 this.targetY = targetY;
290 this.targets = targets;
291 this.targetDirs = targetDirs;
292 this.requiredSolutionCount = requiredSolutionCount;
294 double minPenalty = Double.MAX_VALUE;
295 for(RoutePencil target : targets)
296 if(target.penalty < minPenalty)
297 minPenalty = target.penalty;
299 for(RoutePencil target : targets)
300 target.penalty -= minPenalty;
303 void calcPriority(Continuation cont) {
304 cont.priority = cont.penalty;
305 double tDir = cont.direction.getDir(targetX, targetY);
306 double tSide = cont.direction.getSide(targetX, targetY);
307 if(tDir >= cont.front) {
308 if(tSide < cont.min || tSide > cont.max)
309 cont.priority += Penalty.BEND_PENALTY;
312 cont.priority += 2*Penalty.BEND_PENALTY;
315 void prime(Direction dir, double min, double max, double front, double minTurnDistance) {
316 Continuation cont = new Continuation(dir, min, max, front, 0, null,
317 dir.createPencil(front, front, min, max, 0.0, null), 0.0, minTurnDistance,
319 addContinutation(cont);
322 void prime(RoutePencil pencil) {
323 Direction dir = pencil.direction;
324 Continuation cont = new Continuation(
329 0, null, pencil, pencil.penalty, 0.0,
331 addContinutation(cont);
336 while(!queue.isEmpty() && count < 10000) {
337 Continuation cont = queue.remove();
338 if(cont.priority > bPenalty ||
339 (cont.priority == bPenalty && cont.distance >= bDistance)) {
340 //System.out.println("solution found, next priority would be " + cont.priority);
343 doContinuation(cont);
348 void addContinutation(Continuation cont) {
349 Continuation old = continuations.get(cont);
351 if(old.priority < cont.priority)
353 if(old.priority == cont.priority && old.distance <= cont.distance)
356 continuations.put(cont, cont);
361 void addBend(RoutePencil pencil) {
362 //System.out.println(pencil + " (" + pencil.x0 + " " + pencil.y0 + " " + pencil.x1 + " " + pencil.y1 + ")");
363 boolean foundSolution = false;
364 for(RoutePencil target : targets)
365 if(pencil.intersects(target)) {
366 int dir = target.direction.getId();
367 if(dir==pencil.direction.getId())
370 double penalty = pencil.penalty + target.penalty;
371 if(dir != pencil.direction.getId())
372 penalty += Penalty.BEND_PENALTY;
373 if(solutions[dir] == null || solutions[dir].penalty > penalty) {
374 //System.out.println("Solution by penalty");
375 solutions[dir] = new RoutePencil(targetX, targetY, targetX, targetY, penalty,
376 Direction.directions[dir], pencil);
377 foundSolution = true;
379 else if(solutions[dir].penalty == penalty) {
380 RoutePencil sol = new RoutePencil(targetX, targetY, targetX, targetY, penalty,
381 Direction.directions[dir], pencil);
382 double d1 = sol.distance();
383 double d2 = solutions[dir].distance();
384 //System.out.println("Solution by distance " + d1 + " " + d2);
386 solutions[dir] = sol;
387 foundSolution = true;
391 ; /*System.out.println("Ignored solution: " +
392 "penalty=" + penalty +
393 ", pencil.penalty=" + pencil.penalty +
394 ", distance=" + pencil.distance() +
395 ", better=" + solutions[dir].penalty);*/
400 solutions[i] == null ? Penalty.INFINITE_COST
401 : new Cost(solutions[i].penalty, solutions[i].distance());
402 Arrays.sort(sortedCosts);
403 bPenalty = sortedCosts[requiredSolutionCount-1].penalty;
404 bDistance = sortedCosts[requiredSolutionCount-1].distance;
408 Direction left = pencil.direction.turnLeft();
409 double front = left.back(pencil);
410 if(front < Double.POSITIVE_INFINITY) {
411 Continuation leftCont = new Continuation(left,
412 left.minSide(pencil),
413 left.maxSide(pencil),
415 0, null, pencil, pencil.penalty+Penalty.BEND_PENALTY, 0.0,
417 addContinutation(leftCont);
422 Direction right = pencil.direction.turnRight();
423 double front = right.back(pencil);
424 if(front < Double.POSITIVE_INFINITY) {
425 Continuation rightCont = new Continuation(right,
426 right.minSide(pencil),
427 right.maxSide(pencil),
429 0, null, pencil, pencil.penalty+Penalty.BEND_PENALTY, 0.0,
431 addContinutation(rightCont);
438 void doContinuation(final Continuation cont) {
439 //System.out.println("cont " + cont.parent + " -> " + cont.direction.getId() + " x=(" + cont.min + ", " + cont.max + ") y=" + cont.front);
440 IStopProcedure proc = new IStopProcedure() {
443 public void blockEnd(double y) {
444 double front = cont.front + cont.minTurnDistance;
445 //System.out.println(cont.minTurnDistance);
447 addBend(cont.direction.createPencil(front, y, cont.min, cont.max, cont.penalty, cont.parent));
451 public void continuation(double min, double max, int pos, Line line) {
452 double newPenalty = cont.penalty;
453 double newMinTurnDistance;
455 Penalty penalty = line.penalty[pos];
456 if(penalty != null) {
457 newPenalty += penalty.penalty;
458 newMinTurnDistance = Math.max(penalty.minDistance,
459 cont.minTurnDistance - line.y + cont.front);
462 newMinTurnDistance = Math.max(0.0,
463 cont.minTurnDistance - line.y + cont.front);
464 Continuation newCont = new Continuation(cont.direction,
466 pos, line, cont.parent, newPenalty, newMinTurnDistance,
468 addContinutation(newCont);
472 if(cont.line != null)
473 StopSet.continueStop(cont.pos, cont.line, cont.min, cont.max, proc);
475 StopSet ss = stopSets[cont.direction.getId()];
476 ss.findStops(cont.min, cont.max, cont.front, proc);
480 static double makeFinite(double x) {
481 if(x == Double.POSITIVE_INFINITY)
483 if(x == Double.NEGATIVE_INFINITY)
488 class TargetFinder implements IStopProcedure {
490 Collection<RoutePencil> targets;
497 public TargetFinder(Direction dir, double dd, double side, double penalty,
499 Collection<RoutePencil> targets) {
503 this.targets = targets;
504 this.penalty = penalty;
505 this.minDistance = minDistance;
509 public void blockEnd(double y) {
510 if(y >= dd+minDistance)
511 targets.add(dir.createPencil(dd+minDistance,
512 y, side, side, penalty, null));
516 public void continuation(double min, double max,
517 int pos, Line line) {
518 Penalty p = line.penalty[pos];
519 if(p.penalty >= Penalty.OBSTACLE_PENALTY.penalty)
521 StopSet.continueStop(pos, line, side, side,
522 new TargetFinder(dir, line.y, side,
523 Math.max(p.minDistance, minDistance-line.y+dd),
524 penalty+p.penalty, targets));
528 public void addTargets(final Collection<RoutePencil> targets,
529 final double x, final double y, double minDist, int dirId) {
530 final Direction dir = Direction.directions[dirId];
531 final double side = dir.getSide(x,y);
532 final double dd = dir.getDir(x, y);
533 stopSets[dirId].findStops(side, side, dd,
534 new TargetFinder(dir, dd, side, 0.0, minDist, targets));
537 public Path2D route(Terminal begin, double[] points, Terminal end) {
539 /* Handle begin==null (end==null) case by taking the first (last)
540 * route point as terminal
544 if(points.length < 2)
546 begin = new Terminal(points[0], points[1], 0x1, Terminal.ZEROS, null);
547 points = Arrays.copyOfRange(points, 2, points.length);
550 if(points.length < 2)
552 end = new Terminal(points[points.length-2], points[points.length-1], 0xf, Terminal.ZEROS, null);
553 points = Arrays.copyOf(points, points.length-2);
557 double dx = end.x - begin.x;
558 double dy = end.y - begin.y;
559 if(dx < begin.minDist[0]+end.minDist[2]+20.0 && -dx < begin.minDist[2]+end.minDist[0]+20.0 &&
560 dy < begin.minDist[1]+end.minDist[3]+20.0 && -dy < begin.minDist[3]+end.minDist[1]+20.0 ) {
561 if((begin.directions & Constants.EAST_FLAG) == Constants.EAST_FLAG &&
562 (end.directions & Constants.WEST_FLAG) == Constants.WEST_FLAG && dx > 0.0) {
563 Path2D path = new Path2D.Double();
564 path.moveTo(begin.x, begin.y);
565 path.lineTo(0.5 * (begin.x + end.x), begin.y);
566 path.lineTo(0.5 * (begin.x + end.x), end.y);
567 path.lineTo(end.x, end.y);
570 else if((begin.directions & Constants.WEST_FLAG) == Constants.WEST_FLAG &&
571 (end.directions & Constants.EAST_FLAG) == Constants.EAST_FLAG && dx < 0.0) {
572 Path2D path = new Path2D.Double();
573 path.moveTo(begin.x, begin.y);
574 path.lineTo(0.5 * (begin.x + end.x), begin.y);
575 path.lineTo(0.5 * (begin.x + end.x), end.y);
576 path.lineTo(end.x, end.y);
579 else if((begin.directions & Constants.SOUTH_FLAG) == Constants.SOUTH_FLAG &&
580 (end.directions & Constants.NORTH_FLAG) == Constants.NORTH_FLAG && dy > 0.0) {
581 Path2D path = new Path2D.Double();
582 path.moveTo(begin.x, begin.y);
583 path.lineTo(begin.x, 0.5 * (begin.y + end.y));
584 path.lineTo(end.x, 0.5 * (begin.y + end.y));
585 path.lineTo(end.x, end.y);
588 else if((begin.directions & Constants.NORTH_FLAG) == Constants.NORTH_FLAG &&
589 (end.directions & Constants.SOUTH_FLAG) == Constants.SOUTH_FLAG && dy < 0.0) {
590 Path2D path = new Path2D.Double();
591 path.moveTo(begin.x, begin.y);
592 path.lineTo(begin.x, 0.5 * (begin.y + end.y));
593 path.lineTo(end.x, 0.5 * (begin.y + end.y));
594 path.lineTo(end.x, end.y);
603 SingleRoute oldRoute = null;
604 for(int p=0;p<=points.length;p+=2) {
606 * Create SingleRoute-class and targets
609 if(p==points.length) {
610 Collection<RoutePencil> targets = new ArrayList<RoutePencil>(1);
612 if((end.directions & (1 << i)) != 0)
613 addTargets(targets, end.x, end.y, end.minDist[i], i);
614 route = new SingleRoute(end.x, end.y, targets.toArray(new RoutePencil[targets.size()]),
615 ConnectionDirectionUtil.reverseDirections(end.directions), 1);
618 double x = points[p];
619 double y = points[p+1];
620 Collection<RoutePencil> targets = new ArrayList<RoutePencil>(4);
622 addTargets(targets, x, y, 0.0, i);
623 //targets[i] = new RoutePencil(x, y, x, y, 0.0, Direction.directions[i], null);
624 route = new SingleRoute(x, y, targets.toArray(new RoutePencil[targets.size()]), 0xf, 1);
630 if(oldRoute == null) {
632 if((begin.directions & (1 << i)) != 0) {
633 Direction dir = Direction.directions[i];
634 double side = dir.getSide(begin.x, begin.y);
635 double dd = dir.getDir(begin.x, begin.y);
636 route.prime(dir, side, side, dd, begin.minDist[i]);
641 if(oldRoute.solutions[i] != null)
642 route.prime(oldRoute.solutions[i]);
650 System.out.println("Stage " + (p/2));
652 if(route.solutions[i] != null)
653 System.out.println(" " + i + ": " + route.solutions[i] +
654 ", penalty: " + route.solutions[i].penalty +
655 ", distance: " + route.solutions[i].distance());
661 * Choose the best path
663 RoutePencil[] solutions = oldRoute.solutions;
664 Arrays.sort(solutions, solutionComparator);
665 if(solutions[0] == null)
667 return solutions[0].createPath(end.x, end.y);
670 final static Comparator<RoutePencil> solutionComparator = new Comparator<RoutePencil>() {
673 public int compare(RoutePencil o1, RoutePencil o2) {
682 if(o1.penalty < o2.penalty)
684 if(o1.penalty > o2.penalty)
686 double d1 = o1.distance();
687 double d2 = o2.distance();