1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 *
6 * Copyright (C) 2009 Monash University
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 * See the file LICENSE.LGPL distributed with the library.
13 *
14 * Licensees holding a valid commercial license may use this file in
15 * accordance with the commercial license agreement provided with the
16 * library.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21 *
22 * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
23 */
26 #include <cstdlib>
27 #include <cfloat>
28 #include <cmath>
29 #include <set>
30 #include <list>
31 #include <algorithm>
33 #include "libavoid/router.h"
34 #include "libavoid/geomtypes.h"
35 #include "libavoid/shape.h"
36 #include "libavoid/orthogonal.h"
37 #include "libavoid/connector.h"
38 #include "libavoid/vpsc.h"
39 #include "libavoid/assertions.h"
41 #ifdef LIBAVOID_SDL
42 #include <SDL_gfxPrimitives.h>
43 #endif
46 namespace Avoid {
49 static const double CHANNEL_MAX = 100000000;
51 static const size_t XDIM = 0;
52 static const size_t YDIM = 1;
55 class ShiftSegment
56 {
57 public:
58 // For shiftable segments.
59 ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
60 bool isSBend, const size_t dim, double minLim, double maxLim)
61 : connRef(conn),
62 indexLow(low),
63 indexHigh(high),
64 sBend(isSBend),
65 fixed(false),
66 dimension(dim),
67 variable(NULL),
68 minSpaceLimit(minLim),
69 maxSpaceLimit(maxLim)
70 {
71 }
72 // For fixed segments.
73 ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
74 const size_t dim)
75 : connRef(conn),
76 indexLow(low),
77 indexHigh(high),
78 sBend(false),
79 fixed(true),
80 dimension(dim),
81 variable(NULL)
82 {
83 // This has no space to shift.
84 minSpaceLimit = lowPoint()[dim];
85 maxSpaceLimit = lowPoint()[dim];
86 }
87 Point& lowPoint(void)
88 {
89 return connRef->displayRoute().ps[indexLow];
90 }
91 Point& highPoint(void)
92 {
93 return connRef->displayRoute().ps[indexHigh];
94 }
95 const Point& lowPoint(void) const
96 {
97 return connRef->displayRoute().ps[indexLow];
98 }
99 const Point& highPoint(void) const
100 {
101 return connRef->displayRoute().ps[indexHigh];
102 }
103 const int fixedOrder(bool& isFixed) const
104 {
105 if (fixed)
106 {
107 isFixed = true;
108 return 0;
109 }
110 if (lowC())
111 {
112 return 1;
113 }
114 else if (highC())
115 {
116 return -1;
117 }
118 return 0;
119 }
120 const int order(void) const
121 {
122 if (lowC())
123 {
124 return -1;
125 }
126 else if (highC())
127 {
128 return 1;
129 }
130 return 0;
131 }
132 bool operator<(const ShiftSegment& rhs) const
133 {
134 const Point& lowPt = lowPoint();
135 const Point& rhsLowPt = rhs.lowPoint();
137 if (lowPt[dimension] != rhsLowPt[dimension])
138 {
139 return lowPt[dimension] < rhsLowPt[dimension];
140 }
141 return this < &rhs;
142 }
143 // This counts segments that are colliear and share an endpoint as
144 // overlapping. This allows them to be nudged apart where possible.
145 bool overlapsWith(const ShiftSegment& rhs, const size_t dim) const
146 {
147 size_t altDim = (dim + 1) % 2;
148 const Point& lowPt = lowPoint();
149 const Point& highPt = highPoint();
150 const Point& rhsLowPt = rhs.lowPoint();
151 const Point& rhsHighPt = rhs.highPoint();
152 if ( (lowPt[altDim] <= rhsHighPt[altDim]) &&
153 (rhsLowPt[altDim] <= highPt[altDim]))
154 {
155 if ( (minSpaceLimit <= rhs.maxSpaceLimit) &&
156 (rhs.minSpaceLimit <= maxSpaceLimit))
157 {
158 return true;
159 }
160 }
161 return false;
162 }
164 ConnRef *connRef;
165 size_t indexLow;
166 size_t indexHigh;
167 bool sBend;
168 bool fixed;
169 size_t dimension;
170 Variable *variable;
171 double minSpaceLimit;
172 double maxSpaceLimit;
173 private:
174 const bool lowC(void) const
175 {
176 // This is true if this is a cBend and its adjoining points
177 // are at lower positions.
178 if (!sBend && !fixed && (minSpaceLimit == lowPoint()[dimension]))
179 {
180 return true;
181 }
182 return false;
183 }
184 const bool highC(void) const
185 {
186 // This is true if this is a cBend and its adjoining points
187 // are at higher positions.
188 if (!sBend && !fixed && (maxSpaceLimit == lowPoint()[dimension]))
189 {
190 return true;
191 }
192 return false;
193 }
194 };
195 typedef std::list<ShiftSegment> ShiftSegmentList;
197 bool cmpShiftSegment(const ShiftSegment& u, const ShiftSegment& v)
198 {
199 return u < v;
200 }
203 struct Node;
204 struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
206 typedef std::set<Node*,CmpNodePos> NodeSet;
207 struct Node
208 {
209 ShapeRef *v;
210 VertInf *c;
211 ShiftSegment *ss;
212 double pos;
213 double min[2], max[2];
214 Node *firstAbove, *firstBelow;
215 NodeSet::iterator iter;
217 Node(ShapeRef *v, const double p)
218 : v(v),
219 c(NULL),
220 ss(NULL),
221 pos(p),
222 firstAbove(NULL),
223 firstBelow(NULL)
224 {
225 //COLA_ASSERT(r->width()<1e40);
226 v->polygon().getBoundingRect(&min[0], &min[1], &max[0], &max[1]);
227 }
228 Node(VertInf *c, const double p)
229 : v(NULL),
230 c(c),
231 ss(NULL),
232 pos(p),
233 firstAbove(NULL),
234 firstBelow(NULL)
235 {
236 min[0] = max[0] = c->point.x;
237 min[1] = max[1] = c->point.y;
238 }
239 Node(ShiftSegment *ss, const double p)
240 : v(NULL),
241 c(NULL),
242 ss(ss),
243 pos(p),
244 firstAbove(NULL),
245 firstBelow(NULL)
246 {
247 // These values shouldn't ever be used, so they don't matter.
248 min[0] = max[0] = min[1] = max[1] = 0;
249 }
250 ~Node()
251 {
252 }
253 // Find the first Node above in the scanline that is a shape edge,
254 // and does not have an open or close event at this position (meaning
255 // it is just about to be removed).
256 double firstObstacleAbove(size_t dim)
257 {
258 Node *curr = firstAbove;
259 while (curr && (curr->ss || (curr->max[dim] > pos)))
260 {
261 curr = curr->firstAbove;
262 }
264 if (curr)
265 {
266 return curr->max[dim];
267 }
268 return -DBL_MAX;
269 }
270 // Find the first Node below in the scanline that is a shape edge,
271 // and does not have an open or close event at this position (meaning
272 // it is just about to be removed).
273 double firstObstacleBelow(size_t dim)
274 {
275 Node *curr = firstBelow;
276 while (curr && (curr->ss || (curr->min[dim] < pos)))
277 {
278 curr = curr->firstBelow;
279 }
281 if (curr)
282 {
283 return curr->min[dim];
284 }
285 return DBL_MAX;
286 }
287 // Mark all connector segments above in the scanline as being able
288 // to see to this shape edge.
289 void markShiftSegmentsAbove(size_t dim)
290 {
291 Node *curr = firstAbove;
292 while (curr && (curr->ss || (curr->pos > min[dim])))
293 {
294 if (curr->ss && (curr->pos <= min[dim]))
295 {
296 curr->ss->maxSpaceLimit =
297 std::min(min[dim], curr->ss->maxSpaceLimit);
298 }
299 curr = curr->firstAbove;
300 }
301 }
302 // Mark all connector segments below in the scanline as being able
303 // to see to this shape edge.
304 void markShiftSegmentsBelow(size_t dim)
305 {
306 Node *curr = firstBelow;
307 while (curr && (curr->ss || (curr->pos < max[dim])))
308 {
309 if (curr->ss && (curr->pos >= max[dim]))
310 {
311 curr->ss->minSpaceLimit =
312 std::max(max[dim], curr->ss->minSpaceLimit);
313 }
314 curr = curr->firstBelow;
315 }
316 }
317 bool findFirstPointAboveAndBelow(const size_t dim, double& firstAbovePos,
318 double& firstBelowPos, double& lastAbovePos, double& lastBelowPos)
319 {
320 bool clearVisibility = true;
321 firstAbovePos = -DBL_MAX;
322 firstBelowPos = DBL_MAX;
323 // We start looking left from the right side of the shape,
324 // and vice versa.
325 lastAbovePos = max[dim];
326 lastBelowPos = min[dim];
328 // Find the first blocking edge above this point. Don't count the
329 // edges as we are travelling out of shapes we are inside, but then
330 // mark clearVisibility as false.
331 Node *curr = firstAbove;
332 while (curr && (curr->max[dim] > min[dim]))
333 {
334 lastAbovePos = std::min(curr->min[dim], lastAbovePos);
335 if ((curr->max[dim] >= min[dim]) && (curr->max[dim] <= max[dim]))
336 {
337 lastAbovePos = std::min(curr->max[dim], lastAbovePos);
338 }
339 lastBelowPos = std::max(curr->max[dim], lastBelowPos);
340 clearVisibility = false;
341 curr = curr->firstAbove;
342 }
343 if (curr)
344 {
345 firstAbovePos = curr->max[dim];
346 }
347 while (curr)
348 {
349 // There might be a larger shape after this one in the ordering.
350 if (curr->max[dim] < min[dim])
351 {
352 firstAbovePos = std::max(curr->max[dim], firstAbovePos);
353 }
354 curr = curr->firstAbove;
355 }
357 // Find the first blocking edge below this point. Don't count the
358 // edges as we are travelling out of shapes we are inside, but then
359 // mark clearVisibility as false.
360 curr = firstBelow;
361 while (curr && (curr->min[dim] < max[dim]))
362 {
363 lastBelowPos = std::max(curr->max[dim], lastBelowPos);
364 if ((curr->min[dim] >= min[dim]) && (curr->min[dim] <= max[dim]))
365 {
366 lastBelowPos = std::max(curr->min[dim], lastBelowPos);
367 }
368 lastAbovePos = std::min(curr->min[dim], lastAbovePos);
369 clearVisibility = false;
370 curr = curr->firstBelow;
371 }
372 if (curr)
373 {
374 firstBelowPos = curr->min[dim];
375 }
376 while (curr)
377 {
378 // There might be a larger shape after this one in the ordering.
379 if (curr->min[dim] > max[dim])
380 {
381 firstBelowPos = std::min(curr->min[dim], firstBelowPos);
382 }
383 curr = curr->firstBelow;
384 }
386 return clearVisibility;
387 }
388 double firstPointAbove(size_t dim)
389 {
390 Node *curr = firstAbove;
391 while (curr && (curr->max[dim] >= pos))
392 {
393 curr = curr->firstAbove;
394 }
396 if (curr)
397 {
398 return curr->max[dim];
399 }
400 return -DBL_MAX;
401 }
402 double firstPointBelow(size_t dim)
403 {
404 Node *curr = firstBelow;
405 while (curr && (curr->min[dim] <= pos))
406 {
407 curr = curr->firstBelow;
408 }
410 if (curr)
411 {
412 return curr->min[dim];
413 }
414 return DBL_MAX;
415 }
416 // This is a bit inefficient, but we won't need to do it once we have
417 // connection points.
418 bool isInsideShape(size_t dimension)
419 {
420 for (Node *curr = firstBelow; curr; curr = curr->firstBelow)
421 {
422 if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
423 {
424 return true;
425 }
426 }
427 for (Node *curr = firstAbove; curr; curr = curr->firstAbove)
428 {
429 if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
430 {
431 return true;
432 }
433 }
434 return false;
435 }
436 };
439 bool CmpNodePos::operator() (const Node* u, const Node* v) const
440 {
441 if (u->pos != v->pos)
442 {
443 return u->pos < v->pos;
444 }
446 // Use the pointers to the base objects to differentiate them.
447 void *up = (u->v) ? (void *) u->v :
448 ((u->c) ? (void *) u->c : (void *) u->ss);
449 void *vp = (v->v) ? (void *) v->v :
450 ((v->c) ? (void *) v->c : (void *) v->ss);
451 return up < vp;
452 }
455 // Note: Open must come first.
456 typedef enum {
457 Open = 1,
458 SegOpen = 2,
459 ConnPoint = 3,
460 SegClose = 4,
461 Close = 5
462 } EventType;
465 struct Event
466 {
467 Event(EventType t, Node *v, double p)
468 : type(t),
469 v(v),
470 pos(p)
471 {};
472 EventType type;
473 Node *v;
474 double pos;
475 };
477 Event **events;
480 // Used for quicksort. Must return <0, 0, or >0.
481 int compare_events(const void *a, const void *b)
482 {
483 Event *ea = *(Event**) a;
484 Event *eb = *(Event**) b;
485 if (ea->pos != eb->pos)
486 {
487 return (ea->pos < eb->pos) ? -1 : 1;
488 }
489 if (ea->type != eb->type)
490 {
491 return ea->type - eb->type;
492 }
493 COLA_ASSERT(ea->v != eb->v);
494 return ea->v - eb->v;
495 }
498 // Returns a bitfield of the direction of visibility (in this dimension)
499 // made up of ConnDirDown (for visibility towards lower position values)
500 // and ConnDirUp (for visibility towards higher position values).
501 //
502 static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim)
503 {
504 if (dim == XDIM) // X-dimension
505 {
506 unsigned int dirs = v->visDirections & (ConnDirLeft | ConnDirRight);
507 if (dirs == (ConnDirLeft | ConnDirRight))
508 {
509 return (ConnDirDown | ConnDirUp);
510 }
511 else if (dirs == ConnDirLeft)
512 {
513 return ConnDirDown;
514 }
515 else if (dirs == ConnDirRight)
516 {
517 return ConnDirUp;
518 }
519 }
520 else if (dim == YDIM) // Y-dimension
521 {
522 unsigned int dirs = v->visDirections & (ConnDirDown | ConnDirUp);
523 if (dirs == (ConnDirDown | ConnDirUp))
524 {
525 return (ConnDirDown | ConnDirUp);
526 }
527 else if (dirs == ConnDirDown)
528 {
529 // For libavoid the Y-axis points downwards, so in terms of
530 // smaller or larger position values, Down is Up and vice versa.
531 return ConnDirUp;
532 }
533 else if (dirs == ConnDirUp)
534 {
535 // For libavoid the Y-axis points downwards, so in terms of
536 // smaller or larger position values, Down is Up and vice versa.
537 return ConnDirDown;
538 }
539 }
541 // Can occur for ConnDirNone visibility.
542 return ConnDirNone;
543 }
546 struct PosVertInf
547 {
548 PosVertInf(double p, VertInf *vI, ConnDirFlags d = ConnDirNone)
549 : pos(p),
550 vert(vI),
551 dir(d)
552 {
553 }
555 bool operator<(const PosVertInf& rhs) const
556 {
557 if (pos != rhs.pos)
558 {
559 return pos < rhs.pos;
560 }
561 return vert < rhs.vert;
562 }
564 double pos;
565 VertInf *vert;
567 // A bitfield marking the direction of visibility (in this dimension)
568 // made up of ConnDirDown (for visibility towards lower position values)
569 // and ConnDirUp (for visibility towards higher position values).
570 //
571 ConnDirFlags dir;
572 };
575 struct CmpVertInf
576 {
577 bool operator()(const VertInf* u, const VertInf* v) const
578 {
579 // Comparator for VertSet, an ordered set of VertInf pointers.
580 // It is assumed vertical sets of points will all have the same
581 // x position and horizontal sets all share a y position, so this
582 // method can be used to sort both these sets.
583 COLA_ASSERT((u->point.x == v->point.x) || (u->point.y == v->point.y));
584 if (u->point.x != v->point.x)
585 {
586 return u->point.x < v->point.x;
587 }
588 else if (u->point.y != v->point.y)
589 {
590 return u->point.y < v->point.y;
591 }
592 return u < v;
593 }
594 };
597 typedef std::set<VertInf *, CmpVertInf> VertSet;
599 // A set of points to break the line segment,
600 // along with vertices for these points.
601 typedef std::set<PosVertInf> BreakpointSet;
603 // Temporary structure used to store the possible horizontal visibility
604 // lines arising from the vertical sweep.
605 class LineSegment
606 {
607 public:
608 LineSegment(const double& b, const double& f, const double& p,
609 bool ss = false, VertInf *bvi = NULL, VertInf *fvi = NULL)
610 : begin(b),
611 finish(f),
612 pos(p),
613 shapeSide(false)
614 {
615 COLA_ASSERT(begin < finish);
617 if (bvi)
618 {
619 vertInfs.insert(bvi);
620 }
621 if (fvi)
622 {
623 vertInfs.insert(fvi);
624 }
625 }
626 LineSegment(const double& bf, const double& p, VertInf *bfvi = NULL)
627 : begin(bf),
628 finish(bf),
629 pos(p),
630 shapeSide(false)
631 {
632 if (bfvi)
633 {
634 vertInfs.insert(bfvi);
635 }
636 }
638 // Order by begin, pos, finish.
639 bool operator<(const LineSegment& rhs) const
640 {
641 if (begin != rhs.begin)
642 {
643 return begin < rhs.begin;
644 }
645 if (pos != rhs.pos)
646 {
647 return pos < rhs.pos;
648 }
649 if (finish != rhs.finish)
650 {
651 return finish < rhs.finish;
652 }
653 COLA_ASSERT(shapeSide == rhs.shapeSide);
654 return false;
655 }
657 bool overlaps(const LineSegment& rhs) const
658 {
659 if ((begin == rhs.begin) && (pos == rhs.pos) &&
660 (finish == rhs.finish))
661 {
662 // Lines are exactly equal.
663 return true;
664 }
666 if (pos == rhs.pos)
667 {
668 if (((begin >= rhs.begin) && (begin <= rhs.finish)) ||
669 ((rhs.begin >= begin) && (rhs.begin <= finish)) )
670 {
671 // They are colinear and overlap by some amount.
672 return true;
673 }
674 }
675 return false;
676 }
678 void mergeVertInfs(const LineSegment& segment)
679 {
680 begin = std::min(begin, segment.begin);
681 finish = std::max(finish, segment.finish);
682 vertInfs.insert(segment.vertInfs.begin(), segment.vertInfs.end());
683 }
685 VertInf *beginVertInf(void) const
686 {
687 if (vertInfs.empty())
688 {
689 return NULL;
690 }
691 return *vertInfs.begin();
692 }
693 VertInf *finishVertInf(void) const
694 {
695 if (vertInfs.empty())
696 {
697 return NULL;
698 }
699 return *vertInfs.rbegin();
700 }
702 VertInf *commitPositionX(Router *router, double posX)
703 {
704 VertInf *found = NULL;
705 for (VertSet::iterator v = vertInfs.begin();
706 v != vertInfs.end(); ++v)
707 {
708 if ((*v)->point.x == posX)
709 {
710 found = *v;
711 break;
712 }
713 }
714 if (!found)
715 {
716 found = new VertInf(router, dummyOrthogID, Point(posX, pos));
717 vertInfs.insert(found);
718 }
719 return found;
720 }
721 // Set begin endpoint vertex if none has been assigned.
722 void commitBegin(Router *router, VertInf *vert = NULL)
723 {
724 if (vert)
725 {
726 vertInfs.insert(vert);
727 }
729 if (vertInfs.empty() ||
730 ((*vertInfs.begin())->point.x != begin))
731 {
732 vertInfs.insert(new
733 VertInf(router, dummyOrthogID, Point(begin, pos)));
734 }
735 }
737 // Set begin endpoint vertex if none has been assigned.
738 void commitFinish(Router *router, VertInf *vert = NULL)
739 {
740 if (vert)
741 {
742 vertInfs.insert(vert);
743 }
745 if (vertInfs.empty() ||
746 ((*vertInfs.rbegin())->point.x != finish))
747 {
748 vertInfs.insert(new
749 VertInf(router, dummyOrthogID, Point(finish, pos)));
750 }
751 }
753 // Converts a section of the points list to a set of breakPoints.
754 // Returns the first of the intersection points occuring at finishPos.
755 VertSet::iterator addSegmentsUpTo(Router *router, double finishPos)
756 {
757 VertSet::iterator firstIntersectionPt = vertInfs.end();
758 for (VertSet::iterator vert = vertInfs.begin();
759 vert != vertInfs.end(); ++vert)
760 {
761 if ((*vert)->point.x > finishPos)
762 {
763 // We're done.
764 break;
765 }
767 breakPoints.insert(PosVertInf((*vert)->point.x, (*vert),
768 getPosVertInfDirection(*vert, XDIM)));
770 if ((firstIntersectionPt == vertInfs.end()) &&
771 ((*vert)->point.x == finishPos))
772 {
773 firstIntersectionPt = vert;
774 }
775 }
776 // Returns the first of the intersection points at finishPos.
777 return firstIntersectionPt;
778 }
780 // Add visibility edge(s) for this segment. There may be multiple if
781 // one of the endpoints is shared by multiple connector endpoints.
782 void addEdgeHorizontal(Router *router)
783 {
784 commitBegin(router);
785 commitFinish(router);
787 addSegmentsUpTo(router, finish);
788 }
790 // Add visibility edge(s) for this segment up until an intersection.
791 // Then, move the segment beginning to the intersection point, so we
792 // later only consider the remainder of the segment.
793 // There may be multiple segments added to the graph if the beginning
794 // endpoint of the segment is shared by multiple connector endpoints.
795 VertSet addEdgeHorizontalTillIntersection(Router *router,
796 LineSegment& vertLine)
797 {
798 VertSet intersectionSet;
800 commitBegin(router);
802 // Does a vertex already exist for this point.
803 commitPositionX(router, vertLine.pos);
805 // Generate segments and set end iterator to the first point
806 // at the intersection position.
807 VertSet::iterator restBegin = addSegmentsUpTo(router, vertLine.pos);
809 // Add the intersections points to intersectionSet.
810 VertSet::iterator restEnd = restBegin;
811 while ((restEnd != vertInfs.end()) &&
812 (*restEnd)->point.x == vertLine.pos)
813 {
814 ++restEnd;
815 }
816 intersectionSet.insert(restBegin, restEnd);
818 // Adjust segment to remove processed portion.
819 begin = vertLine.pos;
820 vertInfs.erase(vertInfs.begin(), restBegin);
822 return intersectionSet;
823 }
825 // Insert vertical breakpoints.
826 void insertBreakpointsBegin(Router *router, LineSegment& vertLine)
827 {
828 VertInf *vert = NULL;
829 if (pos == vertLine.begin && vertLine.beginVertInf())
830 {
831 vert = vertLine.beginVertInf();
832 }
833 else if (pos == vertLine.finish && vertLine.finishVertInf())
834 {
835 vert = vertLine.finishVertInf();
836 }
837 commitBegin(router, vert);
839 for (VertSet::iterator v = vertInfs.begin();
840 v != vertInfs.end(); ++v)
841 {
842 if ((*v)->point.x == begin)
843 {
844 vertLine.breakPoints.insert(PosVertInf(pos, *v,
845 getPosVertInfDirection(*v, YDIM)));
846 }
847 }
848 }
850 // Insert vertical breakpoints.
851 void insertBreakpointsFinish(Router *router, LineSegment& vertLine)
852 {
853 VertInf *vert = NULL;
854 if (pos == vertLine.begin && vertLine.beginVertInf())
855 {
856 vert = vertLine.beginVertInf();
857 }
858 else if (pos == vertLine.finish && vertLine.finishVertInf())
859 {
860 vert = vertLine.finishVertInf();
861 }
862 commitFinish(router, vert);
864 for (VertSet::iterator v = vertInfs.begin();
865 v != vertInfs.end(); ++v)
866 {
867 if ((*v)->point.x == finish)
868 {
869 vertLine.breakPoints.insert(PosVertInf(pos, *v,
870 getPosVertInfDirection(*v, YDIM)));
871 }
872 }
873 }
874 void generateVisibilityEdgesFromBreakpointSet(Router *router, size_t dim)
875 {
876 if ((breakPoints.begin())->pos != begin)
877 {
878 if (!beginVertInf())
879 {
880 Point point(pos, pos);
881 point[dim] = begin;
882 // Add begin point if it didn't intersect another line.
883 VertInf *vert = new VertInf(router, dummyOrthogID, point);
884 breakPoints.insert(PosVertInf(begin, vert));
885 }
886 }
887 if ((breakPoints.rbegin())->pos != finish)
888 {
889 if (!finishVertInf())
890 {
891 Point point(pos, pos);
892 point[dim] = finish;
893 // Add finish point if it didn't intersect another line.
894 VertInf *vert = new VertInf(router, dummyOrthogID, point);
895 breakPoints.insert(PosVertInf(finish, vert));
896 }
897 }
899 const bool orthogonal = true;
900 BreakpointSet::iterator vert, last;
901 for (vert = last = breakPoints.begin(); vert != breakPoints.end();)
902 {
903 BreakpointSet::iterator firstPrev = last;
904 while (last->vert->point[dim] != vert->vert->point[dim])
905 {
906 COLA_ASSERT(vert != last);
907 // Assert points are not at the same position.
908 COLA_ASSERT(vert->vert->point != last->vert->point);
910 if ( !(vert->vert->id.isShape || last->vert->id.isShape))
911 {
912 // Here we have a pair of two endpoints that are both
913 // connector endpoints and both are inside a shape.
915 // Give vert visibility back to the first non-connector
916 // endpoint vertex (i.e., the side of the shape).
917 BreakpointSet::iterator side = last;
918 while (!side->vert->id.isShape)
919 {
920 if (side == breakPoints.begin())
921 {
922 break;
923 }
924 --side;
925 }
926 bool canSeeDown = (vert->dir & ConnDirDown);
927 if (canSeeDown && side->vert->id.isShape)
928 {
929 EdgeInf *edge = new
930 EdgeInf(side->vert, vert->vert, orthogonal);
931 edge->setDist(vert->vert->point[dim] -
932 side->vert->point[dim]);
933 }
935 // Give last visibility back to the first non-connector
936 // endpoint vertex (i.e., the side of the shape).
937 side = vert;
938 while ((side != breakPoints.end()) &&
939 !side->vert->id.isShape)
940 {
941 ++side;
942 }
943 bool canSeeUp = (last->dir & ConnDirUp);
944 if (canSeeUp && (side != breakPoints.end()))
945 {
946 EdgeInf *edge = new
947 EdgeInf(last->vert, side->vert, orthogonal);
948 edge->setDist(side->vert->point[dim] -
949 last->vert->point[dim]);
950 }
951 }
953 // The normal case.
954 //
955 // Note: It's okay to give two connector endpoints visbility
956 // here since we only consider the partner endpoint as a
957 // candidate while searching if it is the other endpoint of
958 // the connector in question.
959 //
960 bool generateEdge = true;
961 if (!last->vert->id.isShape && !(last->dir & ConnDirUp))
962 {
963 generateEdge = false;
964 }
965 else if (!vert->vert->id.isShape && !(vert->dir & ConnDirDown))
966 {
967 generateEdge = false;
968 }
969 if (generateEdge)
970 {
971 EdgeInf *edge =
972 new EdgeInf(last->vert, vert->vert, orthogonal);
973 edge->setDist(vert->vert->point[dim] -
974 last->vert->point[dim]);
975 }
977 ++last;
978 }
980 ++vert;
982 if ((vert != breakPoints.end()) &&
983 (last->vert->point[dim] == vert->vert->point[dim]))
984 {
985 // Still looking at same pair, just reset prev number pointer.
986 last = firstPrev;
987 }
988 else
989 {
990 // vert has moved to the beginning of a number number group.
991 // Last is now in the right place, so do nothing.
992 }
993 }
994 }
996 double begin;
997 double finish;
998 double pos;
999 bool shapeSide;
1001 VertSet vertInfs;
1002 BreakpointSet breakPoints;
1003 private:
1004 // MSVC wants to generate the assignment operator and the default
1005 // constructor, but fails. Therefore we declare them private and
1006 // don't implement them.
1007 LineSegment & operator=(LineSegment const &);
1008 LineSegment();
1009 };
1011 typedef std::list<LineSegment> SegmentList;
1013 class SegmentListWrapper
1014 {
1015 public:
1016 LineSegment *insert(LineSegment segment)
1017 {
1018 SegmentList::iterator found = _list.end();
1019 for (SegmentList::iterator curr = _list.begin();
1020 curr != _list.end(); ++curr)
1021 {
1022 if (curr->overlaps(segment))
1023 {
1024 if (found != _list.end())
1025 {
1026 // This is not the first segment that overlaps,
1027 // so we need to merge and then delete an existing
1028 // segment.
1029 curr->mergeVertInfs(*found);
1030 _list.erase(found);
1031 found = curr;
1032 }
1033 else
1034 {
1035 // This is the first overlapping segment, so just
1036 // merge the new segment with this one.
1037 curr->mergeVertInfs(segment);
1038 found = curr;
1039 }
1040 }
1041 }
1043 if (found == _list.end())
1044 {
1045 // Add this line.
1046 _list.push_back(segment);
1047 return &(_list.back());
1048 }
1050 return &(*found);
1051 }
1052 SegmentList& list(void)
1053 {
1054 return _list;
1055 }
1056 private:
1057 SegmentList _list;
1058 };
1061 // Given a router instance and a set of possible horizontal segments, and a
1062 // possible vertical visibility segment, compute and add edges to the
1063 // orthogonal visibility graph for all the visibility edges.
1064 static void intersectSegments(Router *router, SegmentList& segments,
1065 LineSegment& vertLine)
1066 {
1067 COLA_ASSERT(vertLine.beginVertInf() == NULL);
1068 COLA_ASSERT(vertLine.finishVertInf() == NULL);
1069 for (SegmentList::iterator it = segments.begin(); it != segments.end(); )
1070 {
1071 LineSegment& horiLine = *it;
1073 bool inVertSegRegion = ((vertLine.begin <= horiLine.pos) &&
1074 (vertLine.finish >= horiLine.pos));
1076 if (horiLine.finish < vertLine.pos)
1077 {
1078 // Add horizontal visibility segment.
1079 horiLine.addEdgeHorizontal(router);
1081 size_t dim = XDIM; // x-dimension
1082 horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
1084 // We've now swept past this horizontal segment, so delete.
1085 it = segments.erase(it);
1086 continue;
1087 }
1088 else if (horiLine.begin > vertLine.pos)
1089 {
1090 // We've yet to reach this segment in the sweep, so ignore.
1091 ++it;
1092 continue;
1093 }
1094 else if (horiLine.begin == vertLine.pos)
1095 {
1096 if (inVertSegRegion)
1097 {
1098 horiLine.insertBreakpointsBegin(router, vertLine);
1099 }
1100 }
1101 else if (horiLine.finish == vertLine.pos)
1102 {
1103 if (inVertSegRegion)
1104 {
1105 // Add horizontal visibility segment.
1106 horiLine.addEdgeHorizontal(router);
1108 horiLine.insertBreakpointsFinish(router, vertLine);
1110 size_t dim = XDIM; // x-dimension
1111 horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
1113 // And we've now finished with the segment, so delete.
1114 it = segments.erase(it);
1115 continue;
1116 }
1117 }
1118 else
1119 {
1120 COLA_ASSERT(horiLine.begin < vertLine.pos);
1121 COLA_ASSERT(horiLine.finish > vertLine.pos);
1123 if (inVertSegRegion)
1124 {
1125 // Add horizontal visibility segment.
1126 VertSet intersectionVerts =
1127 horiLine.addEdgeHorizontalTillIntersection(
1128 router, vertLine);
1130 for (VertSet::iterator v = intersectionVerts.begin();
1131 v != intersectionVerts.end(); ++v)
1132 {
1133 vertLine.breakPoints.insert(PosVertInf(horiLine.pos, *v,
1134 getPosVertInfDirection(*v, YDIM)));
1135 }
1136 }
1137 }
1138 ++it;
1139 }
1141 // Split breakPoints set into visibility segments.
1142 size_t dimension = YDIM; // y-dimension
1143 vertLine.generateVisibilityEdgesFromBreakpointSet(router, dimension);
1144 }
1147 // Processes an event for the vertical sweep used for computing the static
1148 // orthogonal visibility graph. This adds possible visibility sgments to
1149 // the segments list.
1150 // The first pass is adding the event to the scanline, the second is for
1151 // processing the event and the third for removing it from the scanline.
1152 static void processEventVert(Router *router, NodeSet& scanline,
1153 SegmentListWrapper& segments, Event *e, unsigned int pass)
1154 {
1155 Node *v = e->v;
1157 if ( ((pass == 1) && (e->type == Open)) ||
1158 ((pass == 2) && (e->type == ConnPoint)) )
1159 {
1160 std::pair<NodeSet::iterator, bool> result = scanline.insert(v);
1161 v->iter = result.first;
1162 COLA_ASSERT(result.second);
1164 NodeSet::iterator it = v->iter;
1165 // Work out neighbours
1166 if (it != scanline.begin())
1167 {
1168 Node *u = *(--it);
1169 v->firstAbove = u;
1170 u->firstBelow = v;
1171 }
1172 it = v->iter;
1173 if (++it != scanline.end())
1174 {
1175 Node *u = *it;
1176 v->firstBelow = u;
1177 u->firstAbove = v;
1178 }
1179 }
1181 if (pass == 2)
1182 {
1183 if ((e->type == Open) || (e->type == Close))
1184 {
1185 // Shape edge positions.
1186 double minShape = v->min[0];
1187 double maxShape = v->max[0];
1188 // As far as we can see.
1189 double minLimit, maxLimit;
1190 double minLimitMax, maxLimitMin;
1191 v->findFirstPointAboveAndBelow(0, minLimit, maxLimit,
1192 minLimitMax, maxLimitMin);
1194 // Only difference between Open and Close is whether the line
1195 // segments are at the top or bottom of the shape. Decide here.
1196 double lineY = (e->type == Open) ? v->min[1] : v->max[1];
1198 if (minLimitMax >= maxLimitMin)
1199 {
1200 // Insert possible visibility segments.
1201 VertInf *vI1 = new VertInf(router, dummyOrthogID,
1202 Point(minShape, lineY));
1203 VertInf *vI2 = new VertInf(router, dummyOrthogID,
1204 Point(maxShape, lineY));
1206 // There are no overlapping shapes, so give full visibility.
1207 if (minLimit < minShape)
1208 {
1209 segments.insert(LineSegment(minLimit, minShape, lineY,
1210 true, NULL, vI1));
1211 }
1212 segments.insert(LineSegment(minShape, maxShape, lineY,
1213 true, vI1, vI2));
1214 if (maxShape < maxLimit)
1215 {
1216 segments.insert(LineSegment(maxShape, maxLimit, lineY,
1217 true, vI2, NULL));
1218 }
1219 }
1220 else
1221 {
1222 if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
1223 {
1224 segments.insert(LineSegment(minLimit, minLimitMax, lineY,
1225 true, NULL, NULL));
1226 }
1227 if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
1228 {
1229 segments.insert(LineSegment(maxLimitMin, maxLimit, lineY,
1230 true, NULL, NULL));
1231 }
1232 }
1233 }
1234 else if (e->type == ConnPoint)
1235 {
1236 // Connection point.
1237 VertInf *centreVert = e->v->c;
1238 Point& cp = centreVert->point;
1240 // As far as we can see.
1241 double minLimit = v->firstPointAbove(0);
1242 double maxLimit = v->firstPointBelow(0);
1243 bool inShape = v->isInsideShape(0);
1245 LineSegment *line1 = NULL, *line2 = NULL;
1246 if (!inShape || (centreVert->visDirections & ConnDirLeft))
1247 {
1248 line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos,
1249 true, NULL, centreVert));
1250 }
1251 if (!inShape || (centreVert->visDirections & ConnDirRight))
1252 {
1253 line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos,
1254 true, centreVert, NULL));
1255 }
1256 if (!line1 && !line2)
1257 {
1258 // Add a point segment for the centre point.
1259 segments.insert(LineSegment(cp.x, e->pos, centreVert));
1260 }
1262 if (!inShape)
1263 {
1264 // This is not contained within a shape so add a normal
1265 // visibility graph point here too (since paths won't route
1266 // *through* connector endpoint vertices).
1267 if (line1 || line2)
1268 {
1269 VertInf *cent = new VertInf(router, dummyOrthogID, cp);
1270 if (line1)
1271 {
1272 line1->vertInfs.insert(cent);
1273 }
1274 if (line2)
1275 {
1276 line2->vertInfs.insert(cent);
1277 }
1278 }
1279 }
1280 }
1281 }
1283 if ( ((pass == 3) && (e->type == Close)) ||
1284 ((pass == 2) && (e->type == ConnPoint)) )
1285 {
1286 // Clean up neighbour pointers.
1287 Node *l = v->firstAbove, *r = v->firstBelow;
1288 if (l != NULL)
1289 {
1290 l->firstBelow = v->firstBelow;
1291 }
1292 if (r != NULL)
1293 {
1294 r->firstAbove = v->firstAbove;
1295 }
1297 if (e->type == ConnPoint)
1298 {
1299 scanline.erase(v->iter);
1300 delete v;
1301 }
1302 else // if (e->type == Close)
1303 {
1304 size_t result;
1305 result = scanline.erase(v);
1306 COLA_ASSERT(result == 1);
1307 delete v;
1308 }
1309 }
1310 }
1313 // Processes an event for the vertical sweep used for computing the static
1314 // orthogonal visibility graph. This adds possible visibility sgments to
1315 // the segments list.
1316 // The first pass is adding the event to the scanline, the second is for
1317 // processing the event and the third for removing it from the scanline.
1318 static void processEventHori(Router *router, NodeSet& scanline,
1319 SegmentListWrapper& segments, Event *e, unsigned int pass)
1320 {
1321 Node *v = e->v;
1323 if ( ((pass == 1) && (e->type == Open)) ||
1324 ((pass == 2) && (e->type == ConnPoint)) )
1325 {
1326 std::pair<NodeSet::iterator, bool> result = scanline.insert(v);
1327 v->iter = result.first;
1328 COLA_ASSERT(result.second);
1330 NodeSet::iterator it = v->iter;
1331 // Work out neighbours
1332 if (it != scanline.begin())
1333 {
1334 Node *u = *(--it);
1335 v->firstAbove = u;
1336 u->firstBelow = v;
1337 }
1338 it = v->iter;
1339 if (++it != scanline.end())
1340 {
1341 Node *u = *it;
1342 v->firstBelow = u;
1343 u->firstAbove = v;
1344 }
1345 }
1347 if (pass == 2)
1348 {
1349 if ((e->type == Open) || (e->type == Close))
1350 {
1351 // Shape edge positions.
1352 double minShape = v->min[1];
1353 double maxShape = v->max[1];
1354 // As far as we can see.
1355 double minLimit, maxLimit;
1356 double minLimitMax, maxLimitMin;
1357 v->findFirstPointAboveAndBelow(1, minLimit, maxLimit,
1358 minLimitMax, maxLimitMin);
1360 // Only difference between Open and Close is whether the line
1361 // segments are at the left or right of the shape. Decide here.
1362 double lineX = (e->type == Open) ? v->min[0] : v->max[0];
1364 if (minLimitMax >= maxLimitMin)
1365 {
1366 LineSegment vertSeg = LineSegment(minLimit, maxLimit, lineX);
1367 segments.insert(vertSeg);
1368 }
1369 else
1370 {
1371 if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
1372 {
1373 LineSegment vertSeg =
1374 LineSegment(minLimit, minLimitMax, lineX);
1375 segments.insert(vertSeg);
1376 }
1377 if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
1378 {
1379 LineSegment vertSeg =
1380 LineSegment(maxLimitMin, maxLimit, lineX);
1381 segments.insert(vertSeg);
1382 }
1383 }
1384 }
1385 else if (e->type == ConnPoint)
1386 {
1387 // Connection point.
1388 VertInf *centreVert = e->v->c;
1389 Point& cp = centreVert->point;
1391 // As far as we can see.
1392 double minLimit = v->firstPointAbove(1);
1393 double maxLimit = v->firstPointBelow(1);
1394 bool inShape = v->isInsideShape(1);
1396 if (!inShape || (centreVert->visDirections & ConnDirUp))
1397 {
1398 segments.insert(LineSegment(minLimit, cp.y, e->pos));
1399 }
1400 if (!inShape || (centreVert->visDirections & ConnDirDown))
1401 {
1402 segments.insert(LineSegment(cp.y, maxLimit, e->pos));
1403 }
1404 }
1405 }
1407 if ( ((pass == 3) && (e->type == Close)) ||
1408 ((pass == 2) && (e->type == ConnPoint)) )
1409 {
1410 // Clean up neighbour pointers.
1411 Node *l = v->firstAbove, *r = v->firstBelow;
1412 if (l != NULL)
1413 {
1414 l->firstBelow = v->firstBelow;
1415 }
1416 if (r != NULL)
1417 {
1418 r->firstAbove = v->firstAbove;
1419 }
1421 if (e->type == ConnPoint)
1422 {
1423 scanline.erase(v->iter);
1424 delete v;
1425 }
1426 else // if (e->type == Close)
1427 {
1428 size_t result;
1429 result = scanline.erase(v);
1430 COLA_ASSERT(result == 1);
1431 delete v;
1432 }
1433 }
1434 }
1437 extern void generateStaticOrthogonalVisGraph(Router *router)
1438 {
1439 const size_t n = router->shapeRefs.size();
1440 const unsigned cpn = router->vertices.connsSize();
1441 // Set up the events for the vertical sweep.
1442 size_t totalEvents = (2 * n) + cpn;
1443 events = new Event*[totalEvents];
1444 unsigned ctr = 0;
1445 ShapeRefList::iterator shRefIt = router->shapeRefs.begin();
1446 for (unsigned i = 0; i < n; i++)
1447 {
1448 ShapeRef *shRef = *shRefIt;
1449 double minX, minY, maxX, maxY;
1450 shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
1451 double midX = minX + ((maxX - minX) / 2);
1452 Node *v = new Node(shRef, midX);
1453 events[ctr++] = new Event(Open, v, minY);
1454 events[ctr++] = new Event(Close, v, maxY);
1456 ++shRefIt;
1457 }
1458 for (VertInf *curr = router->vertices.connsBegin();
1459 curr && (curr != router->vertices.shapesBegin());
1460 curr = curr->lstNext)
1461 {
1462 Point& point = curr->point;
1464 Node *v = new Node(curr, point.x);
1465 events[ctr++] = new Event(ConnPoint, v, point.y);
1466 }
1467 qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
1469 // Process the vertical sweep.
1470 // We do multiple passes over sections of the list so we can add relevant
1471 // entries to the scanline that might follow, before process them.
1472 SegmentListWrapper segments;
1473 NodeSet scanline;
1474 double thisPos = (totalEvents > 0) ? events[0]->pos : 0;
1475 unsigned int posStartIndex = 0;
1476 unsigned int posFinishIndex = 0;
1477 for (unsigned i = 0; i <= totalEvents; ++i)
1478 {
1479 // If we have finished the current scanline or all events, then we
1480 // process the events on the current scanline in a couple of passes.
1481 if ((i == totalEvents) || (events[i]->pos != thisPos))
1482 {
1483 posFinishIndex = i;
1484 for (int pass = 2; pass <= 3; ++pass)
1485 {
1486 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
1487 {
1488 processEventVert(router, scanline, segments,
1489 events[j], pass);
1490 }
1491 }
1493 if (i == totalEvents)
1494 {
1495 // We have cleaned up, so we can now break out of loop.
1496 break;
1497 }
1499 thisPos = events[i]->pos;
1500 posStartIndex = i;
1501 }
1503 // Do the first sweep event handling -- building the correct
1504 // structure of the scanline.
1505 const int pass = 1;
1506 processEventVert(router, scanline, segments, events[i], pass);
1507 }
1508 COLA_ASSERT(scanline.size() == 0);
1509 for (unsigned i = 0; i < totalEvents; ++i)
1510 {
1511 delete events[i];
1512 }
1514 segments.list().sort();
1516 // Set up the events for the horizontal sweep.
1517 SegmentListWrapper vertSegments;
1518 ctr = 0;
1519 shRefIt = router->shapeRefs.begin();
1520 for (unsigned i = 0; i < n; i++)
1521 {
1522 ShapeRef *shRef = *shRefIt;
1523 double minX, minY, maxX, maxY;
1524 shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
1525 double midY = minY + ((maxY - minY) / 2);
1526 Node *v = new Node(shRef, midY);
1527 events[ctr++] = new Event(Open, v, minX);
1528 events[ctr++] = new Event(Close, v, maxX);
1530 ++shRefIt;
1531 }
1532 for (VertInf *curr = router->vertices.connsBegin();
1533 curr && (curr != router->vertices.shapesBegin());
1534 curr = curr->lstNext)
1535 {
1536 Point& point = curr->point;
1538 Node *v = new Node(curr, point.y);
1539 events[ctr++] = new Event(ConnPoint, v, point.x);
1540 }
1541 qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
1543 // Process the horizontal sweep
1544 thisPos = (totalEvents > 0) ? events[0]->pos : 0;
1545 posStartIndex = 0;
1546 posFinishIndex = 0;
1547 for (unsigned i = 0; i <= totalEvents; ++i)
1548 {
1549 // If we have finished the current scanline or all events, then we
1550 // process the events on the current scanline in a couple of passes.
1551 if ((i == totalEvents) || (events[i]->pos != thisPos))
1552 {
1553 posFinishIndex = i;
1554 for (int pass = 2; pass <= 3; ++pass)
1555 {
1556 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
1557 {
1558 processEventHori(router, scanline, vertSegments,
1559 events[j], pass);
1560 }
1561 }
1563 // Process the merged line segments.
1564 vertSegments.list().sort();
1565 for (SegmentList::iterator curr = vertSegments.list().begin();
1566 curr != vertSegments.list().end(); ++curr)
1567 {
1568 intersectSegments(router, segments.list(), *curr);
1569 }
1570 vertSegments.list().clear();
1572 if (i == totalEvents)
1573 {
1574 // We have cleaned up, so we can now break out of loop.
1575 break;
1576 }
1578 thisPos = events[i]->pos;
1579 posStartIndex = i;
1580 }
1582 // Do the first sweep event handling -- building the correct
1583 // structure of the scanline.
1584 const int pass = 1;
1585 processEventHori(router, scanline, vertSegments, events[i], pass);
1586 }
1587 COLA_ASSERT(scanline.size() == 0);
1588 for (unsigned i = 0; i < totalEvents; ++i)
1589 {
1590 delete events[i];
1591 }
1592 delete [] events;
1594 // Add portions of the horizontal line that are after the final vertical
1595 // position we considered.
1596 for (SegmentList::iterator it = segments.list().begin();
1597 it != segments.list().end(); )
1598 {
1599 LineSegment& horiLine = *it;
1601 horiLine.addEdgeHorizontal(router);
1603 size_t dim = XDIM; // x-dimension
1604 horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
1606 it = segments.list().erase(it);
1607 }
1608 }
1611 //============================================================================
1612 // Path Adjustment code
1613 //============================================================================
1618 // Processes sweep events used to determine each horizontal and vertical
1619 // line segment in a connector's channel of visibility.
1620 // Four calls to this function are made at each position by the scanline:
1621 // 1) Handle all Close event processing.
1622 // 2) Remove Close event objects from the scanline.
1623 // 3) Add Open event objects to the scanline.
1624 // 4) Handle all Open event processing.
1625 //
1626 static void processShiftEvent(Router *router, NodeSet& scanline,
1627 ShiftSegmentList& segments, Event *e, size_t dim,
1628 unsigned int pass)
1629 {
1630 Node *v = e->v;
1632 if ( ((pass == 3) && (e->type == Open)) ||
1633 ((pass == 3) && (e->type == SegOpen)) )
1634 {
1635 std::pair<NodeSet::iterator, bool> result = scanline.insert(v);
1636 v->iter = result.first;
1637 COLA_ASSERT(result.second);
1639 NodeSet::iterator it = v->iter;
1640 // Work out neighbours
1641 if (it != scanline.begin())
1642 {
1643 Node *u = *(--it);
1644 v->firstAbove = u;
1645 u->firstBelow = v;
1646 }
1647 it = v->iter;
1648 if (++it != scanline.end())
1649 {
1650 Node *u = *it;
1651 v->firstBelow = u;
1652 u->firstAbove = v;
1653 }
1654 }
1656 if ( ((pass == 4) && (e->type == Open)) ||
1657 ((pass == 4) && (e->type == SegOpen)) ||
1658 ((pass == 1) && (e->type == SegClose)) ||
1659 ((pass == 1) && (e->type == Close)) )
1660 {
1661 if (v->ss)
1662 {
1663 // As far as we can see.
1664 double minLimit = v->firstObstacleAbove(dim);
1665 double maxLimit = v->firstObstacleBelow(dim);
1667 v->ss->minSpaceLimit =
1668 std::max(minLimit, v->ss->minSpaceLimit);
1669 v->ss->maxSpaceLimit =
1670 std::min(maxLimit, v->ss->maxSpaceLimit);
1671 }
1672 else
1673 {
1674 v->markShiftSegmentsAbove(dim);
1675 v->markShiftSegmentsBelow(dim);
1676 }
1677 }
1679 if ( ((pass == 2) && (e->type == SegClose)) ||
1680 ((pass == 2) && (e->type == Close)) )
1681 {
1682 // Clean up neighbour pointers.
1683 Node *l = v->firstAbove, *r = v->firstBelow;
1684 if (l != NULL)
1685 {
1686 l->firstBelow = v->firstBelow;
1687 }
1688 if (r != NULL)
1689 {
1690 r->firstAbove = v->firstAbove;
1691 }
1693 size_t result;
1694 result = scanline.erase(v);
1695 COLA_ASSERT(result == 1);
1696 delete v;
1697 }
1698 }
1701 static void buildOrthogonalChannelInfo(Router *router,
1702 const size_t dim, ShiftSegmentList& segmentList)
1703 {
1704 if (router->routingPenalty(segmentPenalty) == 0)
1705 {
1706 // This code assumes the routes are pretty optimal, so we don't
1707 // do this adjustment if the routes have no segment penalty.
1708 return;
1709 }
1711 size_t altDim = (dim + 1) % 2;
1712 // For each connector.
1713 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1714 curr != router->connRefs.end(); ++curr)
1715 {
1716 if ((*curr)->routingType() != ConnType_Orthogonal)
1717 {
1718 continue;
1719 }
1720 Polygon& displayRoute = (*curr)->displayRoute();
1721 // Determine all line segments that we are interested in shifting.
1722 // We don't consider the first or last segment of a path.
1723 for (size_t i = 1; i < displayRoute.size(); ++i)
1724 {
1725 if (displayRoute.ps[i - 1][dim] == displayRoute.ps[i][dim])
1726 {
1727 // It's a segment in the dimension we are processing,
1728 size_t indexLow = i - 1;
1729 size_t indexHigh = i;
1730 if (displayRoute.ps[i - 1][altDim] > displayRoute.ps[i][altDim])
1731 {
1732 indexLow = i;
1733 indexHigh = i - 1;
1734 }
1735 COLA_ASSERT(displayRoute.at(indexLow)[altDim] <
1736 displayRoute.at(indexHigh)[altDim]);
1738 if ((i == 1) || ((i + 1) == displayRoute.size()))
1739 {
1740 // The first and last segment of a connector can't be
1741 // shifted. We call them fixed segments. Note: this
1742 // will change if we later allow connection channels.
1743 segmentList.push_back(
1744 ShiftSegment(*curr, indexLow, indexHigh, dim));
1745 continue;
1746 }
1748 // The segment probably has space to be shifted.
1749 double minLim = -CHANNEL_MAX;
1750 double maxLim = CHANNEL_MAX;
1751 bool isSBend = false;
1753 double prevPos = displayRoute.ps[i - 2][dim];
1754 double nextPos = displayRoute.ps[i + 1][dim];
1755 if (((prevPos < displayRoute.ps[i][dim]) &&
1756 (nextPos > displayRoute.ps[i][dim]))
1757 ||
1758 ((prevPos > displayRoute.ps[i][dim]) &&
1759 (nextPos < displayRoute.ps[i][dim])) )
1760 {
1761 isSBend = true;
1763 // Determine limits if the s-bend is not due to an
1764 // obstacle. In this case we need to limit the channel
1765 // to the span of the adjoining segments to this one.
1766 if ((prevPos < displayRoute.ps[i][dim]) &&
1767 (nextPos > displayRoute.ps[i][dim]))
1768 {
1769 minLim = std::max(minLim, prevPos);
1770 maxLim = std::min(maxLim, nextPos);
1771 }
1772 else
1773 {
1774 minLim = std::max(minLim, nextPos);
1775 maxLim = std::min(maxLim, prevPos);
1776 }
1777 }
1778 else
1779 {
1780 // isCBend: Both adjoining segments are in the same
1781 // direction. We indicate this for later by setting
1782 // the maxLim or minLim to the segment position.
1783 if (prevPos < displayRoute.ps[i][dim])
1784 {
1785 minLim = displayRoute.ps[i][dim];
1786 }
1787 else
1788 {
1789 maxLim = displayRoute.ps[i][dim];
1790 }
1791 }
1793 segmentList.push_back(ShiftSegment(*curr, indexLow,
1794 indexHigh, isSBend, dim, minLim, maxLim));
1795 }
1796 }
1797 }
1798 if (segmentList.empty())
1799 {
1800 // There are no segments, so we can just return now.
1801 return;
1802 }
1804 // Do a sweep and shift these segments.
1805 const size_t n = router->shapeRefs.size();
1806 const size_t cpn = segmentList.size();
1807 // Set up the events for the sweep.
1808 size_t totalEvents = 2 * (n + cpn);
1809 events = new Event*[totalEvents];
1810 unsigned ctr = 0;
1811 ShapeRefList::iterator shRefIt = router->shapeRefs.begin();
1812 for (unsigned i = 0; i < n; i++)
1813 {
1814 ShapeRef *shRef = *shRefIt;
1815 Point min, max;
1816 shRef->polygon().getBoundingRect(&min.x, &min.y, &max.x, &max.y);
1817 double mid = min[dim] + ((max[dim] - min[dim]) / 2);
1818 Node *v = new Node(shRef, mid);
1819 events[ctr++] = new Event(Open, v, min[altDim]);
1820 events[ctr++] = new Event(Close, v, max[altDim]);
1822 ++shRefIt;
1823 }
1824 for (ShiftSegmentList::iterator curr = segmentList.begin();
1825 curr != segmentList.end(); ++curr)
1826 {
1827 const Point& lowPt = curr->lowPoint();
1828 const Point& highPt = curr->highPoint();
1830 COLA_ASSERT(lowPt[dim] == highPt[dim]);
1831 COLA_ASSERT(lowPt[altDim] < highPt[altDim]);
1832 Node *v = new Node(&(*curr), lowPt[dim]);
1833 events[ctr++] = new Event(SegOpen, v, lowPt[altDim]);
1834 events[ctr++] = new Event(SegClose, v, highPt[altDim]);
1835 }
1836 qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
1838 // Process the sweep.
1839 // We do multiple passes over sections of the list so we can add relevant
1840 // entries to the scanline that might follow, before process them.
1841 NodeSet scanline;
1842 double thisPos = (totalEvents > 0) ? events[0]->pos : 0;
1843 unsigned int posStartIndex = 0;
1844 unsigned int posFinishIndex = 0;
1845 for (unsigned i = 0; i <= totalEvents; ++i)
1846 {
1847 // If we have finished the current scanline or all events, then we
1848 // process the events on the current scanline in a couple of passes.
1849 if ((i == totalEvents) || (events[i]->pos != thisPos))
1850 {
1851 posFinishIndex = i;
1852 for (int pass = 2; pass <= 4; ++pass)
1853 {
1854 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
1855 {
1856 processShiftEvent(router, scanline, segmentList, events[j],
1857 dim, pass);
1858 }
1859 }
1861 if (i == totalEvents)
1862 {
1863 // We have cleaned up, so we can now break out of loop.
1864 break;
1865 }
1867 thisPos = events[i]->pos;
1868 posStartIndex = i;
1869 }
1871 // Do the first sweep event handling -- building the correct
1872 // structure of the scanline.
1873 const int pass = 1;
1874 processShiftEvent(router, scanline, segmentList, events[i],
1875 dim, pass);
1876 }
1877 COLA_ASSERT(scanline.size() == 0);
1878 for (unsigned i = 0; i < totalEvents; ++i)
1879 {
1880 delete events[i];
1881 }
1882 delete [] events;
1883 }
1886 static void simplifyOrthogonalRoutes(Router *router)
1887 {
1888 // Simplify routes.
1889 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1890 curr != router->connRefs.end(); ++curr)
1891 {
1892 if ((*curr)->routingType() != ConnType_Orthogonal)
1893 {
1894 continue;
1895 }
1896 (*curr)->set_route((*curr)->displayRoute().simplify());
1897 }
1898 }
1901 static void buildOrthogonalNudgingOrderInfo(Router *router,
1902 PtOrderMap& pointOrders)
1903 {
1904 // Simplify routes.
1905 simplifyOrthogonalRoutes(router);
1907 int crossingsN = 0;
1909 // Do segment splitting.
1910 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1911 curr != router->connRefs.end(); ++curr)
1912 {
1913 if ((*curr)->routingType() != ConnType_Orthogonal)
1914 {
1915 continue;
1916 }
1917 ConnRef *conn = *curr;
1919 for (ConnRefList::const_iterator curr2 = router->connRefs.begin();
1920 curr2 != router->connRefs.end(); ++curr2)
1921 {
1922 if ((*curr2)->routingType() != ConnType_Orthogonal)
1923 {
1924 continue;
1925 }
1926 ConnRef *conn2 = *curr2;
1928 if (conn == conn2)
1929 {
1930 continue;
1931 }
1933 Avoid::Polygon& route = conn->displayRoute();
1934 Avoid::Polygon& route2 = conn2->displayRoute();
1935 splitBranchingSegments(route2, true, route);
1936 }
1937 }
1939 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1940 curr != router->connRefs.end(); ++curr)
1941 {
1942 if ((*curr)->routingType() != ConnType_Orthogonal)
1943 {
1944 continue;
1945 }
1946 ConnRef *conn = *curr;
1948 for (ConnRefList::const_iterator curr2 = curr;
1949 curr2 != router->connRefs.end(); ++curr2)
1950 {
1951 if ((*curr2)->routingType() != ConnType_Orthogonal)
1952 {
1953 continue;
1954 }
1955 ConnRef *conn2 = *curr2;
1957 if (conn == conn2)
1958 {
1959 continue;
1960 }
1962 Avoid::Polygon& route = conn->displayRoute();
1963 Avoid::Polygon& route2 = conn2->displayRoute();
1964 bool checkForBranchingSegments = false;
1965 int crossings = 0;
1966 for (size_t i = 1; i < route.size(); ++i)
1967 {
1968 const bool finalSegment = ((i + 1) == route.size());
1969 crossings += countRealCrossings(route2, true, route, i,
1970 checkForBranchingSegments, finalSegment, NULL,
1971 &pointOrders, conn2, conn).first;
1972 }
1973 if (crossings > 0)
1974 {
1975 crossingsN += crossings;
1976 }
1977 }
1978 }
1980 // Sort the point orders.
1981 PtOrderMap::iterator finish = pointOrders.end();
1982 for (PtOrderMap::iterator it = pointOrders.begin(); it != finish; ++it)
1983 {
1984 //const VertID& ptID = it->first;
1985 PtOrder& order = it->second;
1987 for (size_t dim = XDIM; dim <= YDIM; ++dim)
1988 {
1989 order.sort(dim);
1990 }
1991 }
1992 }
1995 class CmpLineOrder
1996 {
1997 public:
1998 CmpLineOrder(PtOrderMap& ord, const size_t dim)
1999 : orders(ord),
2000 dimension(dim)
2001 {
2002 }
2003 bool operator()(const ShiftSegment& lhs, const ShiftSegment& rhs,
2004 bool *comparable = NULL) const
2005 {
2006 if (comparable)
2007 {
2008 *comparable = true;
2009 }
2010 Point lhsLow = lhs.lowPoint();
2011 Point rhsLow = rhs.lowPoint();
2012 #ifndef NDEBUG
2013 const Point& lhsHigh = lhs.highPoint();
2014 const Point& rhsHigh = rhs.highPoint();
2015 #endif
2016 size_t altDim = (dimension + 1) % 2;
2018 COLA_ASSERT(lhsLow[dimension] == lhsHigh[dimension]);
2019 COLA_ASSERT(rhsLow[dimension] == rhsHigh[dimension]);
2021 if (lhsLow[dimension] != rhsLow[dimension])
2022 {
2023 return lhsLow[dimension] < rhsLow[dimension];
2024 }
2026 // If one of these is fixed, then determine order based on
2027 // fixed segment, that is, order so the fixed segment doesn't
2028 // block movement.
2029 bool oneIsFixed = false;
2030 const int lhsFixedOrder = lhs.fixedOrder(oneIsFixed);
2031 const int rhsFixedOrder = rhs.fixedOrder(oneIsFixed);
2032 if (oneIsFixed && (lhsFixedOrder != rhsFixedOrder))
2033 {
2034 return lhsFixedOrder < rhsFixedOrder;
2035 }
2037 // C-bends that did not have a clear order with s-bends might
2038 // not have a good ordering here, so compare their order in
2039 // terms of C-bend direction and S-bends and use that if it
2040 // differs for the two segments.
2041 const int lhsOrder = lhs.order();
2042 const int rhsOrder = rhs.order();
2043 if (lhsOrder != rhsOrder)
2044 {
2045 return lhsOrder < rhsOrder;
2046 }
2048 // Need to index using the original point into the map, so find it.
2049 Point& unchanged = (lhsLow[altDim] > rhsLow[altDim]) ?
2050 lhsLow : rhsLow;
2052 PtOrder& lowOrder = orders[unchanged];
2053 int lhsPos = lowOrder.positionFor(lhs.connRef, dimension);
2054 int rhsPos = lowOrder.positionFor(rhs.connRef, dimension);
2055 if ((lhsPos == -1) || (rhsPos == -1))
2056 {
2057 // A value for rhsPos or lhsPos mean the points are not directly
2058 // comparable, meaning they are at the same position but cannot
2059 // overlap (they are just collinear. The relative order for
2060 // these segments is not important since we do not constrain
2061 // them against each other.
2062 //COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false);
2063 // We do need to be consistent though.
2064 if (comparable)
2065 {
2066 *comparable = false;
2067 }
2068 return lhsLow[altDim] < rhsLow[altDim];
2069 }
2071 return lhsPos < rhsPos;
2072 }
2074 PtOrderMap& orders;
2075 const size_t dimension;
2076 };
2079 // We can use the normaal sort algorithm for lists since it is not possible
2080 // to comapre all elements, but there will be an ordering defined between
2081 // most of the elements. Hence we order these, using insertion sort, and
2082 // the case of them not being able to be compared is handled by not setting
2083 // up any constraints between such segments when doing the nudging.
2084 //
2085 static ShiftSegmentList linesort(ShiftSegmentList origList,
2086 CmpLineOrder& comparison)
2087 {
2088 ShiftSegmentList resultList;
2090 while (!origList.empty())
2091 {
2092 // Get and remove the first element from the origList.
2093 ShiftSegment segment = origList.front();
2094 origList.pop_front();
2096 // Find the insertion point in the resultList.
2097 ShiftSegmentList::iterator curr;
2098 for (curr = resultList.begin(); curr != resultList.end(); ++curr)
2099 {
2100 bool comparable = false;
2101 bool lessThan = comparison(segment, *curr, &comparable);
2103 if (comparable && lessThan)
2104 {
2105 // If it is comparable and lessThan, then we have found the
2106 // insertion point.
2107 break;
2108 }
2109 }
2111 // Insert the element into the reultList at the required point.
2112 resultList.insert(curr, segment);
2113 }
2115 return resultList;
2116 }
2119 typedef std::list<ShiftSegment *> ShiftSegmentPtrList;
2122 static void nudgeOrthogonalRoutes(Router *router, size_t dimension,
2123 PtOrderMap& pointOrders, ShiftSegmentList& segmentList)
2124 {
2125 // Do the actual nudging.
2126 ShiftSegmentList currentRegion;
2127 while (!segmentList.empty())
2128 {
2129 // Take a reference segment
2130 ShiftSegment& currentSegment = segmentList.front();
2131 // Then, find the segments that overlap this one.
2132 currentRegion.clear();
2133 currentRegion.push_back(currentSegment);
2134 segmentList.erase(segmentList.begin());
2135 for (ShiftSegmentList::iterator curr = segmentList.begin();
2136 curr != segmentList.end(); )
2137 {
2138 bool overlaps = false;
2139 for (ShiftSegmentList::iterator curr2 = currentRegion.begin();
2140 curr2 != currentRegion.end(); ++curr2)
2141 {
2142 if (curr->overlapsWith(*curr2, dimension))
2143 {
2144 overlaps = true;
2145 break;
2146 }
2147 }
2148 if (overlaps)
2149 {
2150 currentRegion.push_back(*curr);
2151 segmentList.erase(curr);
2152 // Consider segments from the beginning, since we mave have
2153 // since passed segments that overlap with the new set.
2154 curr = segmentList.begin();
2155 }
2156 else
2157 {
2158 ++curr;
2159 }
2160 }
2161 CmpLineOrder lineSortComp(pointOrders, dimension);
2162 currentRegion = linesort(currentRegion, lineSortComp);
2164 if (currentRegion.size() == 1)
2165 {
2166 // Save creating the solver instance if there is just one
2167 // immovable segment.
2168 if (!currentRegion.front().sBend)
2169 {
2170 continue;
2171 }
2172 }
2174 // Process these segments.
2175 Variables vs;
2176 Constraints cs;
2177 ShiftSegmentPtrList prevVars;
2178 // IDs:
2179 const int freeID = 0;
2180 const int fixedID = 1;
2181 // Weights:
2182 double freeWeight = 0.00001;
2183 double strongWeight = 0.001;
2184 double fixedWeight = 100000;
2185 //printf("-------------------------------------------------------\n");
2186 //printf("Nudge -- size: %d\n", (int) currentRegion.size());
2187 for (ShiftSegmentList::iterator currSegment = currentRegion.begin();
2188 currSegment != currentRegion.end(); ++currSegment)
2189 {
2190 Point& lowPt = currSegment->lowPoint();
2192 // Create a solver variable for the position of this segment.
2193 int varID = freeID;
2194 double idealPos = lowPt[dimension];
2195 double weight = freeWeight;
2196 if (currSegment->sBend)
2197 {
2198 COLA_ASSERT(currSegment->minSpaceLimit > -CHANNEL_MAX);
2199 COLA_ASSERT(currSegment->maxSpaceLimit < CHANNEL_MAX);
2201 // For s-bends, take the middle as ideal.
2202 idealPos = currSegment->minSpaceLimit +
2203 ((currSegment->maxSpaceLimit -
2204 currSegment->minSpaceLimit) / 2);
2205 }
2206 else if (currSegment->fixed)
2207 {
2208 // Fixed segments shouldn't get moved.
2209 weight = fixedWeight;
2210 varID = fixedID;
2211 }
2212 else
2213 {
2214 // Set a higher weight for c-bends to stop them sometimes
2215 // getting pushed out into channels by more-free connectors
2216 // to the "inner" side of them.
2217 weight = strongWeight;
2218 }
2219 currSegment->variable = new Variable(varID, idealPos, weight);
2220 vs.push_back(currSegment->variable);
2221 size_t index = vs.size() - 1;
2222 //printf("line %.15f pos: %g min: %g max: %g\n",
2223 // lowPt[dimension], idealPos, currSegment->minSpaceLimit,
2224 // currSegment->maxSpaceLimit);
2226 // Constrain position in relation to previously seen segments,
2227 // if necessary (i.e. when they could overlap).
2228 for (ShiftSegmentPtrList::iterator prevVarIt = prevVars.begin();
2229 prevVarIt != prevVars.end(); )
2230 {
2231 ShiftSegment *prevSeg = *prevVarIt;
2232 Variable *prevVar = prevSeg->variable;
2234 if (currSegment->overlapsWith(*prevSeg, dimension) &&
2235 (!(currSegment->fixed) || !(prevSeg->fixed)))
2236 {
2237 // If there is a previous segment to the left that
2238 // could overlap this in the shift direction, then
2239 // constrain the two segments to be separated.
2240 // Though don't add the constraint if both the
2241 // segments are fixed in place.
2242 cs.push_back(new Constraint(prevVar, vs[index],
2243 router->orthogonalNudgeDistance()));
2244 prevVarIt = prevVars.erase(prevVarIt);
2245 }
2246 else
2247 {
2248 ++prevVarIt;
2249 }
2250 }
2252 if (!currSegment->fixed)
2253 {
2254 // If this segment sees a channel boundary to its left,
2255 // then constrain its placement as such.
2256 if (currSegment->minSpaceLimit > -CHANNEL_MAX)
2257 {
2258 vs.push_back(new Variable(fixedID,
2259 currSegment->minSpaceLimit, fixedWeight));
2260 cs.push_back(new Constraint(vs[vs.size() - 1], vs[index],
2261 0.0));
2262 }
2264 // If this segment sees a channel boundary to its right,
2265 // then constrain its placement as such.
2266 if (currSegment->maxSpaceLimit < CHANNEL_MAX)
2267 {
2268 vs.push_back(new Variable(fixedID,
2269 currSegment->maxSpaceLimit, fixedWeight));
2270 cs.push_back(new Constraint(vs[index], vs[vs.size() - 1],
2271 0.0));
2272 }
2273 }
2274 prevVars.push_back(&(*currSegment));
2275 }
2276 #if 0
2277 for(unsigned i=0;i<vs.size();i++) {
2278 printf("-vs[%d]=%f\n",i,vs[i]->desiredPosition);
2279 }
2280 #endif
2281 IncSolver f(vs,cs);
2282 f.solve();
2283 bool satisfied = true;
2284 for (size_t i = 0; i < vs.size(); ++i)
2285 {
2286 if (vs[i]->id == fixedID)
2287 {
2288 if (fabs(vs[i]->finalPosition - vs[i]->desiredPosition) > 0.01)
2289 {
2290 satisfied = false;
2291 break;
2292 }
2293 }
2294 }
2295 if (satisfied)
2296 {
2297 for (ShiftSegmentList::iterator currSegment = currentRegion.begin();
2298 currSegment != currentRegion.end(); ++currSegment)
2299 {
2300 Point& lowPt = currSegment->lowPoint();
2301 Point& highPt = currSegment->highPoint();
2302 double newPos = currSegment->variable->finalPosition;
2303 //printf("Pos: %X, %g\n", (int) currSegment->connRef, newPos);
2304 lowPt[dimension] = newPos;
2305 highPt[dimension] = newPos;
2306 }
2307 }
2308 #if 0
2309 for(unsigned i=0;i<vs.size();i++) {
2310 printf("+vs[%d]=%f\n",i,vs[i]->finalPosition);
2311 }
2312 #endif
2313 for_each(vs.begin(),vs.end(),delete_object());
2314 for_each(cs.begin(),cs.end(),delete_object());
2315 }
2316 }
2319 extern void improveOrthogonalRoutes(Router *router)
2320 {
2321 router->timers.Register(tmOrthogNudge, timerStart);
2322 for (size_t dimension = 0; dimension < 2; ++dimension)
2323 {
2324 // Build nudging info.
2325 // XXX: We need to build the point orders separately in each
2326 // dimension since things move. There is probably a more
2327 // efficient way to do this.
2328 PtOrderMap pointOrders;
2329 buildOrthogonalNudgingOrderInfo(router, pointOrders);
2331 // Simplify routes.
2332 simplifyOrthogonalRoutes(router);
2334 // Do the centring and nudging.
2335 ShiftSegmentList segLists;
2336 buildOrthogonalChannelInfo(router, dimension, segLists);
2337 nudgeOrthogonalRoutes(router, dimension, pointOrders, segLists);
2338 }
2339 router->timers.Stop();
2340 }
2343 }