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 <cstdlib>
24 #include "libavoid/shape.h"
25 #include "libavoid/router.h"
26 #include "libavoid/visibility.h"
27 #include "libavoid/connector.h"
28 #include "libavoid/polyutil.h"
29 #include "libavoid/debug.h"
30 #include "libavoid/region.h"
31 #include "math.h"
33 //#define ORTHOGONAL_ROUTING
35 namespace Avoid {
38 static const unsigned int infoAdd = 1;
39 static const unsigned int infoDel = 2;
40 static const unsigned int infoMov = 3;
43 class MoveInfo {
44 public:
45 MoveInfo(ShapeRef *s, Polygn *p, bool fM)
46 : shape(s)
47 , newPoly(copyPoly(*p))
48 , firstMove(fM)
49 { }
50 ~MoveInfo()
51 {
52 freePoly(newPoly);
53 }
54 ShapeRef *shape;
55 Polygn newPoly;
56 bool firstMove;
57 };
61 Router::Router()
62 : PartialTime(false)
63 , SimpleRouting(false)
64 , segmt_penalty(0)
65 , angle_penalty(0)
66 , crossing_penalty(200)
67 // Algorithm options:
68 , UseAStarSearch(true)
69 , IgnoreRegions(true)
70 , SelectiveReroute(true)
71 , IncludeEndpoints(true)
72 , UseLeesAlgorithm(false)
73 , InvisibilityGrph(true)
74 , ConsolidateMoves(true)
75 , PartialFeedback(false)
76 // Instrumentation:
77 , st_checked_edges(0)
78 #ifdef LINEDEBUG
79 , avoid_screen(NULL)
80 #endif
81 { }
86 void Router::addShape(ShapeRef *shape)
87 {
88 unsigned int pid = shape->id();
89 Polygn poly = shape->poly();
91 adjustContainsWithAdd(poly, pid);
93 // o Check all visibility edges to see if this one shape
94 // blocks them.
95 newBlockingShape(&poly, pid);
97 #ifdef ORTHOGONAL_ROUTING
98 Region::addShape(shape);
99 #endif
101 // o Calculate visibility for the new vertices.
102 if (UseLeesAlgorithm)
103 {
104 shapeVisSweep(shape);
105 }
106 else
107 {
108 shapeVis(shape);
109 }
110 callbackAllInvalidConnectors();
111 }
114 void Router::delShape(ShapeRef *shape)
115 {
116 unsigned int pid = shape->id();
118 // Delete items that are queued in the movList.
119 for (MoveInfoList::iterator it = moveList.begin(); it != moveList.end(); )
120 {
121 if ((*it)->shape->id() == pid)
122 {
123 MoveInfoList::iterator doomed = it;
124 ++it;
125 moveList.erase(doomed);
126 }
127 else
128 {
129 ++it;
130 }
131 }
133 // o Remove entries related to this shape's vertices
134 shape->removeFromGraph();
136 if (SelectiveReroute)
137 {
138 markConnectors(shape);
139 }
141 adjustContainsWithDel(pid);
143 #ifdef ORTHOGONAL_ROUTING
144 Region::removeShape(shape);
145 #endif
147 delete shape;
149 // o Check all edges that were blocked by this shape.
150 if (InvisibilityGrph)
151 {
152 checkAllBlockedEdges(pid);
153 }
154 else
155 {
156 // check all edges not in graph
157 checkAllMissingEdges();
158 }
159 callbackAllInvalidConnectors();
160 }
163 void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
164 {
165 // Sanely cope with the case where the user requests moving the same
166 // shape multiple times before rerouting connectors.
167 bool alreadyThere = false;
168 unsigned int id = shape->id();
169 MoveInfoList::iterator finish = moveList.end();
170 for (MoveInfoList::iterator it = moveList.begin(); it != finish; ++it)
171 {
172 if ((*it)->shape->id() == id)
173 {
174 if (!SimpleRouting)
175 {
176 fprintf(stderr,
177 "warning: multiple moves requested for shape %d.\n",
178 (int) id);
179 }
180 // Just update the MoveInfo with the second polygon, but
181 // leave the firstMove setting alone.
182 (*it)->newPoly = copyPoly(*newPoly);
183 alreadyThere = true;
184 }
185 }
187 if (!alreadyThere)
188 {
189 MoveInfo *moveInfo = new MoveInfo(shape, newPoly, first_move);
190 moveList.push_back(moveInfo);
191 }
193 if (!ConsolidateMoves)
194 {
195 processMoves();
196 }
197 }
200 void Router::processMoves(void)
201 {
202 // If SimpleRouting, then don't update yet.
203 if (moveList.empty() || SimpleRouting)
204 {
205 return;
206 }
208 MoveInfoList::iterator curr;
209 MoveInfoList::iterator finish = moveList.end();
210 for (curr = moveList.begin(); curr != finish; ++curr)
211 {
212 MoveInfo *moveInf = *curr;
213 ShapeRef *shape = moveInf->shape;
214 Polygn *newPoly = &(moveInf->newPoly);
215 bool first_move = moveInf->firstMove;
217 unsigned int pid = shape->id();
218 bool notPartialTime = !(PartialFeedback && PartialTime);
220 // o Remove entries related to this shape's vertices
221 shape->removeFromGraph();
223 if (SelectiveReroute && (notPartialTime || first_move))
224 {
225 markConnectors(shape);
226 }
228 adjustContainsWithDel(pid);
230 #ifdef ORTHOGONAL_ROUTING
231 Region::removeShape(shape);
232 #endif
234 shape->setNewPoly(*newPoly);
236 adjustContainsWithAdd(*newPoly, pid);
238 // Ignore this shape for visibility.
239 // XXX: We don't really need to do this if we're not using Partial
240 // Feedback. Without this the blocked edges still route
241 // around the shape until it leaves the connector.
242 shape->makeInactive();
244 }
246 if (InvisibilityGrph)
247 {
248 for (curr = moveList.begin(); curr != finish; ++curr)
249 {
250 MoveInfo *moveInf = *curr;
251 ShapeRef *shape = moveInf->shape;
252 unsigned int pid = shape->id();
254 // o Check all edges that were blocked by this shape.
255 checkAllBlockedEdges(pid);
256 }
257 }
258 else
259 {
260 // check all edges not in graph
261 checkAllMissingEdges();
262 }
264 while ( ! moveList.empty() )
265 {
266 MoveInfo *moveInf = moveList.front();
267 ShapeRef *shape = moveInf->shape;
268 Polygn *newPoly = &(moveInf->newPoly);
270 unsigned int pid = shape->id();
271 bool notPartialTime = !(PartialFeedback && PartialTime);
273 // Restore this shape for visibility.
274 shape->makeActive();
276 #ifdef ORTHOGONAL_ROUTING
277 Region::addShape(shape);
278 #endif
280 // o Check all visibility edges to see if this one shape
281 // blocks them.
282 if (notPartialTime)
283 {
284 newBlockingShape(newPoly, pid);
285 }
287 // o Calculate visibility for the new vertices.
288 if (UseLeesAlgorithm)
289 {
290 shapeVisSweep(shape);
291 }
292 else
293 {
294 shapeVis(shape);
295 }
297 moveList.pop_front();
298 delete moveInf;
299 }
300 callbackAllInvalidConnectors();
301 }
304 //----------------------------------------------------------------------------
306 // XXX: attachedShapes and attachedConns both need to be rewritten
307 // for constant time lookup of attached objects once this info
308 // is stored better within libavoid. Also they shouldn't need to
309 // be friends of ConnRef.
311 // Returns a list of connector Ids of all the connectors of type
312 // 'type' attached to the shape with the ID 'shapeId'.
313 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
314 const unsigned int type)
315 {
316 ConnRefList::iterator fin = connRefs.end();
317 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
319 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
320 conns.push_back((*i)->_id);
321 }
322 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
323 conns.push_back((*i)->_id);
324 }
325 }
326 }
329 // Returns a list of shape Ids of all the shapes attached to the
330 // shape with the ID 'shapeId' with connection type 'type'.
331 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
332 const unsigned int type)
333 {
334 ConnRefList::iterator fin = connRefs.end();
335 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
336 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
337 if ((*i)->_srcId != 0)
338 {
339 // Only if there is a shape attached to the other end.
340 shapes.push_back((*i)->_srcId);
341 }
342 }
343 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
344 if ((*i)->_dstId != 0)
345 {
346 // Only if there is a shape attached to the other end.
347 shapes.push_back((*i)->_dstId);
348 }
349 }
350 }
351 }
354 // It's intended this function is called after shape movement has
355 // happened to alert connectors that they need to be rerouted.
356 void Router::callbackAllInvalidConnectors(void)
357 {
358 ConnRefList::iterator fin = connRefs.end();
359 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
360 (*i)->handleInvalid();
361 }
362 }
365 void Router::newBlockingShape(Polygn *poly, int pid)
366 {
367 // o Check all visibility edges to see if this one shape
368 // blocks them.
369 EdgeInf *finish = visGraph.end();
370 for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
371 {
372 EdgeInf *tmp = iter;
373 iter = iter->lstNext;
375 if (tmp->getDist() != 0)
376 {
377 std::pair<VertID, VertID> ids(tmp->ids());
378 VertID eID1 = ids.first;
379 VertID eID2 = ids.second;
380 std::pair<Point, Point> points(tmp->points());
381 Point e1 = points.first;
382 Point e2 = points.second;
383 bool blocked = false;
385 bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
386 bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
387 if (ep_in_poly1 || ep_in_poly2)
388 {
389 // Don't check edges that have a connector endpoint
390 // and are inside the shape being added.
391 continue;
392 }
394 for (int pt_i = 0; pt_i < poly->pn; pt_i++)
395 {
396 int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
397 if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
398 {
399 blocked = true;
400 break;
401 }
402 }
403 if (blocked)
404 {
405 db_printf("\tRemoving newly blocked edge (by shape %3d)"
406 "... \n\t\t", pid);
407 tmp->alertConns();
408 tmp->db_print();
409 if (InvisibilityGrph)
410 {
411 tmp->addBlocker(pid);
412 }
413 else
414 {
415 delete tmp;
416 }
417 }
418 }
419 }
420 }
423 void Router::checkAllBlockedEdges(int pid)
424 {
425 assert(InvisibilityGrph);
427 for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
428 {
429 EdgeInf *tmp = iter;
430 iter = iter->lstNext;
432 if (tmp->_blocker == -1)
433 {
434 tmp->alertConns();
435 tmp->checkVis();
436 }
437 else if (tmp->_blocker == pid)
438 {
439 tmp->checkVis();
440 }
441 }
442 }
445 void Router::checkAllMissingEdges(void)
446 {
447 assert(!InvisibilityGrph);
449 VertInf *first = NULL;
451 if (IncludeEndpoints)
452 {
453 first = vertices.connsBegin();
454 }
455 else
456 {
457 first = vertices.shapesBegin();
458 }
460 VertInf *pend = vertices.end();
461 for (VertInf *i = first; i != pend; i = i->lstNext)
462 {
463 VertID iID = i->id;
465 // Check remaining, earlier vertices
466 for (VertInf *j = first ; j != i; j = j->lstNext)
467 {
468 VertID jID = j->id;
469 if (!(iID.isShape) && (iID.objID != jID.objID))
470 {
471 // Don't keep visibility between edges of different conns
472 continue;
473 }
475 // See if the edge is already there?
476 bool found = (EdgeInf::existingEdge(i, j) != NULL);
478 if (!found)
479 {
480 // Didn't already exist, check.
481 bool knownNew = true;
482 EdgeInf::checkEdgeVisibility(i, j, knownNew);
483 }
484 }
485 }
486 }
489 void Router::generateContains(VertInf *pt)
490 {
491 contains[pt->id].clear();
493 ShapeRefList::iterator finish = shapeRefs.end();
494 for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
495 {
496 Polygn poly = copyPoly(*i);
497 if (inPoly(poly, pt->point))
498 {
499 contains[pt->id].insert((*i)->id());
500 }
501 freePoly(poly);
502 }
503 }
506 void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape)
507 {
508 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
509 k = k->lstNext)
510 {
511 if (inPoly(poly, k->point))
512 {
513 contains[k->id].insert(p_shape);
514 }
515 }
516 }
519 void Router::adjustContainsWithDel(const int p_shape)
520 {
521 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
522 k = k->lstNext)
523 {
524 contains[k->id].erase(p_shape);
525 }
526 }
529 #ifdef SELECTIVE_DEBUG
530 static double AngleAFromThreeSides(const double a, const double b,
531 const double c)
532 {
533 // returns angle A, the angle opposite from side a, in radians
534 return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
535 }
536 #endif
538 void Router::markConnectors(ShapeRef *shape)
539 {
540 assert(SelectiveReroute);
542 ConnRefList::iterator end = connRefs.end();
543 for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
544 {
545 ConnRef *conn = (*it);
547 if (conn->_route.pn == 0)
548 {
549 // Ignore uninitialised connectors.
550 continue;
551 }
552 else if (conn->_needs_reroute_flag)
553 {
554 // Already marked, so skip.
555 continue;
556 }
558 Point start = conn->_route.ps[0];
559 Point end = conn->_route.ps[conn->_route.pn - 1];
561 double conndist = conn->_route_dist;
563 double estdist;
564 double e1, e2;
566 VertInf *beginV = shape->firstVert();
567 VertInf *endV = shape->lastVert()->lstNext;
568 for (VertInf *i = beginV; i != endV; i = i->lstNext)
569 {
570 const Point& p1 = i->point;
571 const Point& p2 = i->shNext->point;
573 double offy;
574 double a;
575 double b;
576 double c;
577 double d;
579 double min;
580 double max;
582 if (p1.y == p2.y)
583 {
584 // Standard case
585 offy = p1.y;
586 a = start.x;
587 b = start.y - offy;
588 c = end.x;
589 d = end.y - offy;
591 min = std::min(p1.x, p2.x);
592 max = std::max(p1.x, p2.x);
593 }
594 else if (p1.x == p2.x)
595 {
596 // Other Standard case
597 offy = p1.x;
598 a = start.y;
599 b = start.x - offy;
600 c = end.y;
601 d = end.x - offy;
603 min = std::min(p1.y, p2.y);
604 max = std::max(p1.y, p2.y);
605 }
606 else
607 {
608 // Need to do rotation
609 Point n_p2(p2.x - p1.x, p2.y - p1.y);
610 Point n_start(start.x - p1.x, start.y - p1.y);
611 Point n_end(end.x - p1.x, end.y - p1.y);
612 //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
613 //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
614 //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
616 double theta = 0 - atan2(n_p2.y, n_p2.x);
617 //printf("theta = %.2f\n", theta * (180 / PI));
619 Point r_p1(0, 0);
620 Point r_p2 = n_p2;
621 start = n_start;
622 end = n_end;
624 double cosv = cos(theta);
625 double sinv = sin(theta);
627 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
628 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
629 start.x = cosv * n_start.x - sinv * n_start.y;
630 start.y = cosv * n_start.y + sinv * n_start.x;
631 end.x = cosv * n_end.x - sinv * n_end.y;
632 end.y = cosv * n_end.y + sinv * n_end.x;
633 //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
634 //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
635 //printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
637 if (((int) r_p2.y) != 0)
638 {
639 printf("r_p2.y: %f != 0\n", r_p2.y);
640 std::abort();
641 }
642 // This might be slightly off.
643 r_p2.y = 0;
645 offy = r_p1.y;
646 a = start.x;
647 b = start.y - offy;
648 c = end.x;
649 d = end.y - offy;
651 min = std::min(r_p1.x, r_p2.x);
652 max = std::max(r_p1.x, r_p2.x);
654 }
656 double x;
657 if ((b + d) == 0)
658 {
659 db_printf("WARNING: (b + d) == 0\n");
660 d = d * -1;
661 }
663 if ((b == 0) && (d == 0))
664 {
665 db_printf("WARNING: b == d == 0\n");
666 if (((a < min) && (c < min)) ||
667 ((a > max) && (c > max)))
668 {
669 // It's going to get adjusted.
670 x = a;
671 }
672 else
673 {
674 continue;
675 }
676 }
677 else
678 {
679 x = ((b*c) + (a*d)) / (b + d);
680 }
682 //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
683 //printf("x = %.1f\n", x);
685 x = std::max(min, x);
686 x = std::min(max, x);
688 //printf("x = %.1f\n", x);
690 Point xp;
691 if (p1.x == p2.x)
692 {
693 xp.x = offy;
694 xp.y = x;
695 }
696 else
697 {
698 xp.x = x;
699 xp.y = offy;
700 }
701 //printf("(%.1f, %.1f)\n", xp.x, xp.y);
703 e1 = dist(start, xp);
704 e2 = dist(xp, end);
705 estdist = e1 + e2;
708 //printf("is %.1f < %.1f\n", estdist, conndist);
709 if (estdist < conndist)
710 {
711 #ifdef SELECTIVE_DEBUG
712 //double angle = AngleAFromThreeSides(dist(start, end),
713 // e1, e2);
714 printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
715 conn->_id, estdist, conndist);
716 #endif
717 conn->_needs_reroute_flag = true;
718 break;
719 }
721 }
722 }
723 }
726 void Router::printInfo(void)
727 {
728 FILE *fp = stdout;
729 fprintf(fp, "\nVisibility Graph info:\n");
730 fprintf(fp, "----------------------\n");
732 unsigned int currshape = 0;
733 int st_shapes = 0;
734 int st_vertices = 0;
735 int st_endpoints = 0;
736 int st_valid_shape_visedges = 0;
737 int st_valid_endpt_visedges = 0;
738 int st_invalid_visedges = 0;
739 VertInf *finish = vertices.end();
740 for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
741 {
742 VertID pID = t->id;
744 if ((pID.isShape) && (pID.objID != currshape))
745 {
746 currshape = pID.objID;
747 st_shapes++;
748 }
749 if (pID.isShape)
750 {
751 st_vertices++;
752 }
753 else
754 {
755 // The shape 0 ones are temporary and not considered.
756 st_endpoints++;
757 }
758 }
759 for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
760 t = t->lstNext)
761 {
762 std::pair<VertID, VertID> idpair = t->ids();
764 if (!(idpair.first.isShape) || !(idpair.second.isShape))
765 {
766 st_valid_endpt_visedges++;
767 }
768 else
769 {
770 st_valid_shape_visedges++;
771 }
772 }
773 for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
774 t = t->lstNext)
775 {
776 st_invalid_visedges++;
777 }
778 fprintf(fp, "Number of shapes: %d\n", st_shapes);
779 fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
780 st_vertices + st_endpoints, st_vertices, st_endpoints);
781 fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
782 "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
783 st_valid_endpt_visedges, st_valid_shape_visedges +
784 st_valid_endpt_visedges, st_valid_shape_visedges,
785 st_valid_endpt_visedges, st_invalid_visedges);
786 fprintf(fp, "----------------------\n");
787 fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
788 fprintf(fp, "----------------------\n");
790 fprintf(fp, "ADDS: "); timers.Print(tmAdd);
791 fprintf(fp, "DELS: "); timers.Print(tmDel);
792 fprintf(fp, "MOVS: "); timers.Print(tmMov);
793 fprintf(fp, "***S: "); timers.Print(tmSev);
794 fprintf(fp, "PTHS: "); timers.Print(tmPth);
795 fprintf(fp, "\n");
796 }
799 }