1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 * Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 *
21 */
23 #include "libavoid/shape.h"
24 #include "libavoid/router.h"
25 #include "libavoid/visibility.h"
26 #include "libavoid/connector.h"
27 #include "libavoid/polyutil.h"
28 #include "libavoid/debug.h"
29 #include "libavoid/region.h"
30 #include "math.h"
32 //#define ORTHOGONAL_ROUTING
34 namespace Avoid {
37 static const unsigned int infoAdd = 1;
38 static const unsigned int infoDel = 2;
39 static const unsigned int infoMov = 3;
42 class MoveInfo {
43 public:
44 MoveInfo(ShapeRef *s, Polygn *p, bool fM)
45 : shape(s)
46 , newPoly(copyPoly(*p))
47 , firstMove(fM)
48 { }
49 ~MoveInfo()
50 {
51 freePoly(newPoly);
52 }
53 ShapeRef *shape;
54 Polygn newPoly;
55 bool firstMove;
56 };
60 Router::Router()
61 : PartialTime(false)
62 , SimpleRouting(false)
63 , segmt_penalty(0)
64 , angle_penalty(0)
65 , crossing_penalty(200)
66 // Algorithm options:
67 , UseAStarSearch(true)
68 , IgnoreRegions(true)
69 , SelectiveReroute(true)
70 , IncludeEndpoints(true)
71 , UseLeesAlgorithm(false)
72 , InvisibilityGrph(true)
73 , ConsolidateMoves(true)
74 , PartialFeedback(false)
75 // Instrumentation:
76 , st_checked_edges(0)
77 #ifdef LINEDEBUG
78 , avoid_screen(NULL)
79 #endif
80 { }
85 void Router::addShape(ShapeRef *shape)
86 {
87 unsigned int pid = shape->id();
88 Polygn poly = shape->poly();
90 adjustContainsWithAdd(poly, pid);
92 // o Check all visibility edges to see if this one shape
93 // blocks them.
94 newBlockingShape(&poly, pid);
96 #ifdef ORTHOGONAL_ROUTING
97 Region::addShape(shape);
98 #endif
100 // o Calculate visibility for the new vertices.
101 if (UseLeesAlgorithm)
102 {
103 shapeVisSweep(shape);
104 }
105 else
106 {
107 shapeVis(shape);
108 }
109 callbackAllInvalidConnectors();
110 }
113 void Router::delShape(ShapeRef *shape)
114 {
115 unsigned int pid = shape->id();
117 // Delete items that are queued in the movList.
118 for (MoveInfoList::iterator it = moveList.begin(); it != moveList.end(); )
119 {
120 if ((*it)->shape->id() == pid)
121 {
122 MoveInfoList::iterator doomed = it;
123 ++it;
124 moveList.erase(doomed);
125 }
126 else
127 {
128 ++it;
129 }
130 }
132 // o Remove entries related to this shape's vertices
133 shape->removeFromGraph();
135 if (SelectiveReroute)
136 {
137 markConnectors(shape);
138 }
140 adjustContainsWithDel(pid);
142 #ifdef ORTHOGONAL_ROUTING
143 Region::removeShape(shape);
144 #endif
146 delete shape;
148 // o Check all edges that were blocked by this shape.
149 if (InvisibilityGrph)
150 {
151 checkAllBlockedEdges(pid);
152 }
153 else
154 {
155 // check all edges not in graph
156 checkAllMissingEdges();
157 }
158 callbackAllInvalidConnectors();
159 }
162 void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
163 {
164 // Sanely cope with the case where the user requests moving the same
165 // shape multiple times before rerouting connectors.
166 bool alreadyThere = false;
167 unsigned int id = shape->id();
168 MoveInfoList::iterator finish = moveList.end();
169 for (MoveInfoList::iterator it = moveList.begin(); it != finish; ++it)
170 {
171 if ((*it)->shape->id() == id)
172 {
173 if (!SimpleRouting)
174 {
175 fprintf(stderr,
176 "warning: multiple moves requested for shape %d.\n",
177 (int) id);
178 }
179 // Just update the MoveInfo with the second polygon, but
180 // leave the firstMove setting alone.
181 (*it)->newPoly = copyPoly(*newPoly);
182 alreadyThere = true;
183 }
184 }
186 if (!alreadyThere)
187 {
188 MoveInfo *moveInfo = new MoveInfo(shape, newPoly, first_move);
189 moveList.push_back(moveInfo);
190 }
192 if (!ConsolidateMoves)
193 {
194 processMoves();
195 }
196 }
199 void Router::processMoves(void)
200 {
201 // If SimpleRouting, then don't update yet.
202 if (moveList.empty() || SimpleRouting)
203 {
204 return;
205 }
207 MoveInfoList::iterator curr;
208 MoveInfoList::iterator finish = moveList.end();
209 for (curr = moveList.begin(); curr != finish; ++curr)
210 {
211 MoveInfo *moveInf = *curr;
212 ShapeRef *shape = moveInf->shape;
213 Polygn *newPoly = &(moveInf->newPoly);
214 bool first_move = moveInf->firstMove;
216 unsigned int pid = shape->id();
217 bool notPartialTime = !(PartialFeedback && PartialTime);
219 // o Remove entries related to this shape's vertices
220 shape->removeFromGraph();
222 if (SelectiveReroute && (notPartialTime || first_move))
223 {
224 markConnectors(shape);
225 }
227 adjustContainsWithDel(pid);
229 #ifdef ORTHOGONAL_ROUTING
230 Region::removeShape(shape);
231 #endif
233 shape->setNewPoly(*newPoly);
235 adjustContainsWithAdd(*newPoly, pid);
237 // Ignore this shape for visibility.
238 // XXX: We don't really need to do this if we're not using Partial
239 // Feedback. Without this the blocked edges still route
240 // around the shape until it leaves the connector.
241 shape->makeInactive();
243 }
245 if (InvisibilityGrph)
246 {
247 for (curr = moveList.begin(); curr != finish; ++curr)
248 {
249 MoveInfo *moveInf = *curr;
250 ShapeRef *shape = moveInf->shape;
251 unsigned int pid = shape->id();
253 // o Check all edges that were blocked by this shape.
254 checkAllBlockedEdges(pid);
255 }
256 }
257 else
258 {
259 // check all edges not in graph
260 checkAllMissingEdges();
261 }
263 while ( ! moveList.empty() )
264 {
265 MoveInfo *moveInf = moveList.front();
266 ShapeRef *shape = moveInf->shape;
267 Polygn *newPoly = &(moveInf->newPoly);
269 unsigned int pid = shape->id();
270 bool notPartialTime = !(PartialFeedback && PartialTime);
272 // Restore this shape for visibility.
273 shape->makeActive();
275 #ifdef ORTHOGONAL_ROUTING
276 Region::addShape(shape);
277 #endif
279 // o Check all visibility edges to see if this one shape
280 // blocks them.
281 if (notPartialTime)
282 {
283 newBlockingShape(newPoly, pid);
284 }
286 // o Calculate visibility for the new vertices.
287 if (UseLeesAlgorithm)
288 {
289 shapeVisSweep(shape);
290 }
291 else
292 {
293 shapeVis(shape);
294 }
296 moveList.pop_front();
297 delete moveInf;
298 }
299 callbackAllInvalidConnectors();
300 }
303 //----------------------------------------------------------------------------
305 // XXX: attachedShapes and attachedConns both need to be rewritten
306 // for constant time lookup of attached objects once this info
307 // is stored better within libavoid. Also they shouldn't need to
308 // be friends of ConnRef.
310 // Returns a list of connector Ids of all the connectors of type
311 // 'type' attached to the shape with the ID 'shapeId'.
312 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
313 const unsigned int type)
314 {
315 ConnRefList::iterator fin = connRefs.end();
316 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
318 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
319 conns.push_back((*i)->_id);
320 }
321 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
322 conns.push_back((*i)->_id);
323 }
324 }
325 }
328 // Returns a list of shape Ids of all the shapes attached to the
329 // shape with the ID 'shapeId' with connection type 'type'.
330 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
331 const unsigned int type)
332 {
333 ConnRefList::iterator fin = connRefs.end();
334 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
335 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
336 if ((*i)->_srcId != 0)
337 {
338 // Only if there is a shape attached to the other end.
339 shapes.push_back((*i)->_srcId);
340 }
341 }
342 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
343 if ((*i)->_dstId != 0)
344 {
345 // Only if there is a shape attached to the other end.
346 shapes.push_back((*i)->_dstId);
347 }
348 }
349 }
350 }
353 // It's intended this function is called after shape movement has
354 // happened to alert connectors that they need to be rerouted.
355 void Router::callbackAllInvalidConnectors(void)
356 {
357 ConnRefList::iterator fin = connRefs.end();
358 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
359 (*i)->handleInvalid();
360 }
361 }
364 void Router::newBlockingShape(Polygn *poly, int pid)
365 {
366 // o Check all visibility edges to see if this one shape
367 // blocks them.
368 EdgeInf *finish = visGraph.end();
369 for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
370 {
371 EdgeInf *tmp = iter;
372 iter = iter->lstNext;
374 if (tmp->getDist() != 0)
375 {
376 std::pair<VertID, VertID> ids(tmp->ids());
377 VertID eID1 = ids.first;
378 VertID eID2 = ids.second;
379 std::pair<Point, Point> points(tmp->points());
380 Point e1 = points.first;
381 Point e2 = points.second;
382 bool blocked = false;
384 bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
385 bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
386 if (ep_in_poly1 || ep_in_poly2)
387 {
388 // Don't check edges that have a connector endpoint
389 // and are inside the shape being added.
390 continue;
391 }
393 for (int pt_i = 0; pt_i < poly->pn; pt_i++)
394 {
395 int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
396 if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
397 {
398 blocked = true;
399 break;
400 }
401 }
402 if (blocked)
403 {
404 db_printf("\tRemoving newly blocked edge (by shape %3d)"
405 "... \n\t\t", pid);
406 tmp->alertConns();
407 tmp->db_print();
408 if (InvisibilityGrph)
409 {
410 tmp->addBlocker(pid);
411 }
412 else
413 {
414 delete tmp;
415 }
416 }
417 }
418 }
419 }
422 void Router::checkAllBlockedEdges(int pid)
423 {
424 assert(InvisibilityGrph);
426 for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
427 {
428 EdgeInf *tmp = iter;
429 iter = iter->lstNext;
431 if (tmp->_blocker == -1)
432 {
433 tmp->alertConns();
434 tmp->checkVis();
435 }
436 else if (tmp->_blocker == pid)
437 {
438 tmp->checkVis();
439 }
440 }
441 }
444 void Router::checkAllMissingEdges(void)
445 {
446 assert(!InvisibilityGrph);
448 VertInf *first = NULL;
450 if (IncludeEndpoints)
451 {
452 first = vertices.connsBegin();
453 }
454 else
455 {
456 first = vertices.shapesBegin();
457 }
459 VertInf *pend = vertices.end();
460 for (VertInf *i = first; i != pend; i = i->lstNext)
461 {
462 VertID iID = i->id;
464 // Check remaining, earlier vertices
465 for (VertInf *j = first ; j != i; j = j->lstNext)
466 {
467 VertID jID = j->id;
468 if (!(iID.isShape) && (iID.objID != jID.objID))
469 {
470 // Don't keep visibility between edges of different conns
471 continue;
472 }
474 // See if the edge is already there?
475 bool found = (EdgeInf::existingEdge(i, j) != NULL);
477 if (!found)
478 {
479 // Didn't already exist, check.
480 bool knownNew = true;
481 EdgeInf::checkEdgeVisibility(i, j, knownNew);
482 }
483 }
484 }
485 }
488 void Router::generateContains(VertInf *pt)
489 {
490 contains[pt->id].clear();
492 ShapeRefList::iterator finish = shapeRefs.end();
493 for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
494 {
495 Polygn poly = copyPoly(*i);
496 if (inPoly(poly, pt->point))
497 {
498 contains[pt->id].insert((*i)->id());
499 }
500 freePoly(poly);
501 }
502 }
505 void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape)
506 {
507 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
508 k = k->lstNext)
509 {
510 if (inPoly(poly, k->point))
511 {
512 contains[k->id].insert(p_shape);
513 }
514 }
515 }
518 void Router::adjustContainsWithDel(const int p_shape)
519 {
520 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
521 k = k->lstNext)
522 {
523 contains[k->id].erase(p_shape);
524 }
525 }
528 #ifdef SELECTIVE_DEBUG
529 static double AngleAFromThreeSides(const double a, const double b,
530 const double c)
531 {
532 // returns angle A, the angle opposite from side a, in radians
533 return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
534 }
535 #endif
537 void Router::markConnectors(ShapeRef *shape)
538 {
539 assert(SelectiveReroute);
541 ConnRefList::iterator end = connRefs.end();
542 for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
543 {
544 ConnRef *conn = (*it);
546 if (conn->_route.pn == 0)
547 {
548 // Ignore uninitialised connectors.
549 continue;
550 }
551 else if (conn->_needs_reroute_flag)
552 {
553 // Already marked, so skip.
554 continue;
555 }
557 Point start = conn->_route.ps[0];
558 Point end = conn->_route.ps[conn->_route.pn - 1];
560 double conndist = conn->_route_dist;
562 double estdist;
563 double e1, e2;
565 VertInf *beginV = shape->firstVert();
566 VertInf *endV = shape->lastVert()->lstNext;
567 for (VertInf *i = beginV; i != endV; i = i->lstNext)
568 {
569 const Point& p1 = i->point;
570 const Point& p2 = i->shNext->point;
572 double offy;
573 double a;
574 double b;
575 double c;
576 double d;
578 double min;
579 double max;
581 if (p1.y == p2.y)
582 {
583 // Standard case
584 offy = p1.y;
585 a = start.x;
586 b = start.y - offy;
587 c = end.x;
588 d = end.y - offy;
590 min = std::min(p1.x, p2.x);
591 max = std::max(p1.x, p2.x);
592 }
593 else if (p1.x == p2.x)
594 {
595 // Other Standard case
596 offy = p1.x;
597 a = start.y;
598 b = start.x - offy;
599 c = end.y;
600 d = end.x - offy;
602 min = std::min(p1.y, p2.y);
603 max = std::max(p1.y, p2.y);
604 }
605 else
606 {
607 // Need to do rotation
608 Point n_p2(p2.x - p1.x, p2.y - p1.y);
609 Point n_start(start.x - p1.x, start.y - p1.y);
610 Point n_end(end.x - p1.x, end.y - p1.y);
611 //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
612 //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
613 //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
615 double theta = 0 - atan2(n_p2.y, n_p2.x);
616 //printf("theta = %.2f\n", theta * (180 / PI));
618 Point r_p1(0, 0);
619 Point r_p2 = n_p2;
620 start = n_start;
621 end = n_end;
623 double cosv = cos(theta);
624 double sinv = sin(theta);
626 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
627 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
628 start.x = cosv * n_start.x - sinv * n_start.y;
629 start.y = cosv * n_start.y + sinv * n_start.x;
630 end.x = cosv * n_end.x - sinv * n_end.y;
631 end.y = cosv * n_end.y + sinv * n_end.x;
632 //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
633 //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
634 //printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
636 if (((int) r_p2.y) != 0)
637 {
638 printf("r_p2.y: %f != 0\n", r_p2.y);
639 abort();
640 }
641 // This might be slightly off.
642 r_p2.y = 0;
644 offy = r_p1.y;
645 a = start.x;
646 b = start.y - offy;
647 c = end.x;
648 d = end.y - offy;
650 min = std::min(r_p1.x, r_p2.x);
651 max = std::max(r_p1.x, r_p2.x);
653 }
655 double x;
656 if ((b + d) == 0)
657 {
658 db_printf("WARNING: (b + d) == 0\n");
659 d = d * -1;
660 }
662 if ((b == 0) && (d == 0))
663 {
664 db_printf("WARNING: b == d == 0\n");
665 if (((a < min) && (c < min)) ||
666 ((a > max) && (c > max)))
667 {
668 // It's going to get adjusted.
669 x = a;
670 }
671 else
672 {
673 continue;
674 }
675 }
676 else
677 {
678 x = ((b*c) + (a*d)) / (b + d);
679 }
681 //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
682 //printf("x = %.1f\n", x);
684 x = std::max(min, x);
685 x = std::min(max, x);
687 //printf("x = %.1f\n", x);
689 Point xp;
690 if (p1.x == p2.x)
691 {
692 xp.x = offy;
693 xp.y = x;
694 }
695 else
696 {
697 xp.x = x;
698 xp.y = offy;
699 }
700 //printf("(%.1f, %.1f)\n", xp.x, xp.y);
702 e1 = dist(start, xp);
703 e2 = dist(xp, end);
704 estdist = e1 + e2;
707 //printf("is %.1f < %.1f\n", estdist, conndist);
708 if (estdist < conndist)
709 {
710 #ifdef SELECTIVE_DEBUG
711 //double angle = AngleAFromThreeSides(dist(start, end),
712 // e1, e2);
713 printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
714 conn->_id, estdist, conndist);
715 #endif
716 conn->_needs_reroute_flag = true;
717 break;
718 }
720 }
721 }
722 }
725 void Router::printInfo(void)
726 {
727 FILE *fp = stdout;
728 fprintf(fp, "\nVisibility Graph info:\n");
729 fprintf(fp, "----------------------\n");
731 unsigned int currshape = 0;
732 int st_shapes = 0;
733 int st_vertices = 0;
734 int st_endpoints = 0;
735 int st_valid_shape_visedges = 0;
736 int st_valid_endpt_visedges = 0;
737 int st_invalid_visedges = 0;
738 VertInf *finish = vertices.end();
739 for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
740 {
741 VertID pID = t->id;
743 if ((pID.isShape) && (pID.objID != currshape))
744 {
745 currshape = pID.objID;
746 st_shapes++;
747 }
748 if (pID.isShape)
749 {
750 st_vertices++;
751 }
752 else
753 {
754 // The shape 0 ones are temporary and not considered.
755 st_endpoints++;
756 }
757 }
758 for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
759 t = t->lstNext)
760 {
761 std::pair<VertID, VertID> idpair = t->ids();
763 if (!(idpair.first.isShape) || !(idpair.second.isShape))
764 {
765 st_valid_endpt_visedges++;
766 }
767 else
768 {
769 st_valid_shape_visedges++;
770 }
771 }
772 for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
773 t = t->lstNext)
774 {
775 st_invalid_visedges++;
776 }
777 fprintf(fp, "Number of shapes: %d\n", st_shapes);
778 fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
779 st_vertices + st_endpoints, st_vertices, st_endpoints);
780 fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
781 "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
782 st_valid_endpt_visedges, st_valid_shape_visedges +
783 st_valid_endpt_visedges, st_valid_shape_visedges,
784 st_valid_endpt_visedges, st_invalid_visedges);
785 fprintf(fp, "----------------------\n");
786 fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
787 fprintf(fp, "----------------------\n");
789 fprintf(fp, "ADDS: "); timers.Print(tmAdd);
790 fprintf(fp, "DELS: "); timers.Print(tmDel);
791 fprintf(fp, "MOVS: "); timers.Print(tmMov);
792 fprintf(fp, "***S: "); timers.Print(tmSev);
793 fprintf(fp, "PTHS: "); timers.Print(tmPth);
794 fprintf(fp, "\n");
795 }
798 }