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 , segmt_penalty(0)
63 , angle_penalty(0)
64 , crossing_penalty(200)
65 // Algorithm options:
66 , UseAStarSearch(true)
67 , IgnoreRegions(true)
68 , SelectiveReroute(true)
69 , IncludeEndpoints(true)
70 , UseLeesAlgorithm(false)
71 , InvisibilityGrph(true)
72 , ConsolidateMoves(true)
73 , PartialFeedback(false)
74 // Instrumentation:
75 , st_checked_edges(0)
76 #ifdef LINEDEBUG
77 , avoid_screen(NULL)
78 #endif
79 { }
84 void Router::addShape(ShapeRef *shape)
85 {
86 unsigned int pid = shape->id();
87 Polygn poly = shape->poly();
89 adjustContainsWithAdd(poly, pid);
91 // o Check all visibility edges to see if this one shape
92 // blocks them.
93 newBlockingShape(&poly, pid);
95 #ifdef ORTHOGONAL_ROUTING
96 Region::addShape(shape);
97 #endif
99 // o Calculate visibility for the new vertices.
100 if (UseLeesAlgorithm)
101 {
102 shapeVisSweep(shape);
103 }
104 else
105 {
106 shapeVis(shape);
107 }
108 callbackAllInvalidConnectors();
109 }
112 void Router::delShape(ShapeRef *shape)
113 {
114 unsigned int pid = shape->id();
116 // o Remove entries related to this shape's vertices
117 shape->removeFromGraph();
119 if (SelectiveReroute)
120 {
121 markConnectors(shape);
122 }
124 adjustContainsWithDel(pid);
126 #ifdef ORTHOGONAL_ROUTING
127 Region::removeShape(shape);
128 #endif
130 delete shape;
132 // o Check all edges that were blocked by this shape.
133 if (InvisibilityGrph)
134 {
135 checkAllBlockedEdges(pid);
136 }
137 else
138 {
139 // check all edges not in graph
140 checkAllMissingEdges();
141 }
142 callbackAllInvalidConnectors();
143 }
146 void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
147 {
148 // Sanely cope with the case where the user requests moving the same
149 // shape multiple times before rerouting connectors.
150 bool alreadyThere = false;
151 unsigned int id = shape->id();
152 MoveInfoList::iterator finish = moveList.end();
153 for (MoveInfoList::iterator it = moveList.begin(); it != finish; ++it)
154 {
155 if ((*it)->shape->id() == id)
156 {
157 fprintf(stderr,
158 "warning: multiple moves requested for shape %d.\n",
159 (int) id);
160 // Just update the MoveInfo with the second polygon, but
161 // leave the firstMove setting alone.
162 (*it)->newPoly = copyPoly(*newPoly);
163 alreadyThere = true;
164 }
165 }
167 if (!alreadyThere)
168 {
169 MoveInfo *moveInfo = new MoveInfo(shape, newPoly, first_move);
170 moveList.push_back(moveInfo);
171 }
173 if (!ConsolidateMoves)
174 {
175 processMoves();
176 }
177 }
180 void Router::processMoves(void)
181 {
182 if (moveList.empty())
183 {
184 return;
185 }
187 MoveInfoList::iterator curr;
188 MoveInfoList::iterator finish = moveList.end();
189 for (curr = moveList.begin(); curr != finish; ++curr)
190 {
191 MoveInfo *moveInf = *curr;
192 ShapeRef *shape = moveInf->shape;
193 Polygn *newPoly = &(moveInf->newPoly);
194 bool first_move = moveInf->firstMove;
196 unsigned int pid = shape->id();
197 bool notPartialTime = !(PartialFeedback && PartialTime);
199 // o Remove entries related to this shape's vertices
200 shape->removeFromGraph();
202 if (SelectiveReroute && (notPartialTime || first_move))
203 {
204 markConnectors(shape);
205 }
207 adjustContainsWithDel(pid);
209 #ifdef ORTHOGONAL_ROUTING
210 Region::removeShape(shape);
211 #endif
213 shape->setNewPoly(*newPoly);
215 adjustContainsWithAdd(*newPoly, pid);
217 // Ignore this shape for visibility.
218 // XXX: We don't really need to do this if we're not using Partial
219 // Feedback. Without this the blocked edges still route
220 // around the shape until it leaves the connector.
221 shape->makeInactive();
223 }
225 if (InvisibilityGrph)
226 {
227 for (curr = moveList.begin(); curr != finish; ++curr)
228 {
229 MoveInfo *moveInf = *curr;
230 ShapeRef *shape = moveInf->shape;
231 unsigned int pid = shape->id();
233 // o Check all edges that were blocked by this shape.
234 checkAllBlockedEdges(pid);
235 }
236 }
237 else
238 {
239 // check all edges not in graph
240 checkAllMissingEdges();
241 }
243 while ( ! moveList.empty() )
244 {
245 MoveInfo *moveInf = moveList.front();
246 ShapeRef *shape = moveInf->shape;
247 Polygn *newPoly = &(moveInf->newPoly);
249 unsigned int pid = shape->id();
250 bool notPartialTime = !(PartialFeedback && PartialTime);
252 // Restore this shape for visibility.
253 shape->makeActive();
255 #ifdef ORTHOGONAL_ROUTING
256 Region::addShape(shape);
257 #endif
259 // o Check all visibility edges to see if this one shape
260 // blocks them.
261 if (notPartialTime)
262 {
263 newBlockingShape(newPoly, pid);
264 }
266 // o Calculate visibility for the new vertices.
267 if (UseLeesAlgorithm)
268 {
269 shapeVisSweep(shape);
270 }
271 else
272 {
273 shapeVis(shape);
274 }
276 moveList.pop_front();
277 delete moveInf;
278 }
279 callbackAllInvalidConnectors();
280 }
283 //----------------------------------------------------------------------------
285 // XXX: attachedShapes and attachedConns both need to be rewritten
286 // for constant time lookup of attached objects once this info
287 // is stored better within libavoid. Also they shouldn't need to
288 // be friends of ConnRef.
290 // Returns a list of connector Ids of all the connectors of type
291 // 'type' attached to the shape with the ID 'shapeId'.
292 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
293 const unsigned int type)
294 {
295 ConnRefList::iterator fin = connRefs.end();
296 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
298 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
299 conns.push_back((*i)->_id);
300 }
301 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
302 conns.push_back((*i)->_id);
303 }
304 }
305 }
308 // Returns a list of shape Ids of all the shapes attached to the
309 // shape with the ID 'shapeId' with connection type 'type'.
310 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
311 const unsigned int type)
312 {
313 ConnRefList::iterator fin = connRefs.end();
314 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
315 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
316 if ((*i)->_srcId != 0)
317 {
318 // Only if there is a shape attached to the other end.
319 shapes.push_back((*i)->_srcId);
320 }
321 }
322 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
323 if ((*i)->_dstId != 0)
324 {
325 // Only if there is a shape attached to the other end.
326 shapes.push_back((*i)->_dstId);
327 }
328 }
329 }
330 }
333 // It's intended this function is called after shape movement has
334 // happened to alert connectors that they need to be rerouted.
335 void Router::callbackAllInvalidConnectors(void)
336 {
337 ConnRefList::iterator fin = connRefs.end();
338 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
339 (*i)->handleInvalid();
340 }
341 }
344 void Router::newBlockingShape(Polygn *poly, int pid)
345 {
346 // o Check all visibility edges to see if this one shape
347 // blocks them.
348 EdgeInf *finish = visGraph.end();
349 for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
350 {
351 EdgeInf *tmp = iter;
352 iter = iter->lstNext;
354 if (tmp->getDist() != 0)
355 {
356 std::pair<VertID, VertID> ids(tmp->ids());
357 VertID eID1 = ids.first;
358 VertID eID2 = ids.second;
359 std::pair<Point, Point> points(tmp->points());
360 Point e1 = points.first;
361 Point e2 = points.second;
362 bool blocked = false;
364 bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
365 bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
366 if (ep_in_poly1 || ep_in_poly2)
367 {
368 // Don't check edges that have a connector endpoint
369 // and are inside the shape being added.
370 continue;
371 }
373 for (int pt_i = 0; pt_i < poly->pn; pt_i++)
374 {
375 int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
376 if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
377 {
378 blocked = true;
379 break;
380 }
381 }
382 if (blocked)
383 {
384 db_printf("\tRemoving newly blocked edge (by shape %3d)"
385 "... \n\t\t", pid);
386 tmp->alertConns();
387 tmp->db_print();
388 if (InvisibilityGrph)
389 {
390 tmp->addBlocker(pid);
391 }
392 else
393 {
394 delete tmp;
395 }
396 }
397 }
398 }
399 }
402 void Router::checkAllBlockedEdges(int pid)
403 {
404 assert(InvisibilityGrph);
406 for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
407 {
408 EdgeInf *tmp = iter;
409 iter = iter->lstNext;
411 if (tmp->_blocker == -1)
412 {
413 tmp->alertConns();
414 tmp->checkVis();
415 }
416 else if (tmp->_blocker == pid)
417 {
418 tmp->checkVis();
419 }
420 }
421 }
424 void Router::checkAllMissingEdges(void)
425 {
426 assert(!InvisibilityGrph);
428 VertInf *first = NULL;
430 if (IncludeEndpoints)
431 {
432 first = vertices.connsBegin();
433 }
434 else
435 {
436 first = vertices.shapesBegin();
437 }
439 VertInf *pend = vertices.end();
440 for (VertInf *i = first; i != pend; i = i->lstNext)
441 {
442 VertID iID = i->id;
444 // Check remaining, earlier vertices
445 for (VertInf *j = first ; j != i; j = j->lstNext)
446 {
447 VertID jID = j->id;
448 if (!(iID.isShape) && (iID.objID != jID.objID))
449 {
450 // Don't keep visibility between edges of different conns
451 continue;
452 }
454 // See if the edge is already there?
455 bool found = (EdgeInf::existingEdge(i, j) != NULL);
457 if (!found)
458 {
459 // Didn't already exist, check.
460 bool knownNew = true;
461 EdgeInf::checkEdgeVisibility(i, j, knownNew);
462 }
463 }
464 }
465 }
468 void Router::generateContains(VertInf *pt)
469 {
470 contains[pt->id].clear();
472 ShapeRefList::iterator finish = shapeRefs.end();
473 for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
474 {
475 Polygn poly = copyPoly(*i);
476 if (inPoly(poly, pt->point))
477 {
478 contains[pt->id].insert((*i)->id());
479 }
480 freePoly(poly);
481 }
482 }
485 void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape)
486 {
487 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
488 k = k->lstNext)
489 {
490 if (inPoly(poly, k->point))
491 {
492 contains[k->id].insert(p_shape);
493 }
494 }
495 }
498 void Router::adjustContainsWithDel(const int p_shape)
499 {
500 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
501 k = k->lstNext)
502 {
503 contains[k->id].erase(p_shape);
504 }
505 }
508 #define MIN(a, b) (((a) <= (b)) ? (a) : (b))
509 #define MAX(a, b) (((a) >= (b)) ? (a) : (b))
511 #ifdef SELECTIVE_DEBUG
512 static double AngleAFromThreeSides(const double a, const double b,
513 const double c)
514 {
515 // returns angle A, the angle opposite from side a, in radians
516 return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
517 }
518 #endif
520 void Router::markConnectors(ShapeRef *shape)
521 {
522 assert(SelectiveReroute);
524 ConnRefList::iterator end = connRefs.end();
525 for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
526 {
527 ConnRef *conn = (*it);
529 if (conn->_route.pn == 0)
530 {
531 // Ignore uninitialised connectors.
532 continue;
533 }
534 else if (conn->_needs_reroute_flag)
535 {
536 // Already marked, so skip.
537 continue;
538 }
540 Point start = conn->_route.ps[0];
541 Point end = conn->_route.ps[conn->_route.pn - 1];
543 double conndist = conn->_route_dist;
545 double estdist;
546 double e1, e2;
548 VertInf *beginV = shape->firstVert();
549 VertInf *endV = shape->lastVert()->lstNext;
550 for (VertInf *i = beginV; i != endV; i = i->lstNext)
551 {
552 const Point& p1 = i->point;
553 const Point& p2 = i->shNext->point;
555 double offy;
556 double a;
557 double b;
558 double c;
559 double d;
561 double min;
562 double max;
564 if (p1.y == p2.y)
565 {
566 // Standard case
567 offy = p1.y;
568 a = start.x;
569 b = start.y - offy;
570 c = end.x;
571 d = end.y - offy;
573 min = MIN(p1.x, p2.x);
574 max = MAX(p1.x, p2.x);
575 }
576 else if (p1.x == p2.x)
577 {
578 // Other Standard case
579 offy = p1.x;
580 a = start.y;
581 b = start.x - offy;
582 c = end.y;
583 d = end.x - offy;
585 min = MIN(p1.y, p2.y);
586 max = MAX(p1.y, p2.y);
587 }
588 else
589 {
590 // Need to do rotation
591 Point n_p2(p2.x - p1.x, p2.y - p1.y);
592 Point n_start(start.x - p1.x, start.y - p1.y);
593 Point n_end(end.x - p1.x, end.y - p1.y);
594 //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
595 //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
596 //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
598 double theta = 0 - atan2(n_p2.y, n_p2.x);
599 //printf("theta = %.2f\n", theta * (180 / PI));
601 Point r_p1(0, 0);
602 Point r_p2 = n_p2;
603 start = n_start;
604 end = n_end;
606 double cosv = cos(theta);
607 double sinv = sin(theta);
609 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
610 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
611 start.x = cosv * n_start.x - sinv * n_start.y;
612 start.y = cosv * n_start.y + sinv * n_start.x;
613 end.x = cosv * n_end.x - sinv * n_end.y;
614 end.y = cosv * n_end.y + sinv * n_end.x;
615 //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
616 //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
617 //printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
619 if (((int) r_p2.y) != 0)
620 {
621 printf("r_p2.y: %f != 0\n", r_p2.y);
622 abort();
623 }
624 // This might be slightly off.
625 r_p2.y = 0;
627 offy = r_p1.y;
628 a = start.x;
629 b = start.y - offy;
630 c = end.x;
631 d = end.y - offy;
633 min = MIN(r_p1.x, r_p2.x);
634 max = MAX(r_p1.x, r_p2.x);
636 }
638 double x;
639 if ((b + d) == 0)
640 {
641 db_printf("WARNING: (b + d) == 0\n");
642 d = d * -1;
643 }
645 if ((b == 0) && (d == 0))
646 {
647 db_printf("WARNING: b == d == 0\n");
648 if (((a < min) && (c < min)) ||
649 ((a > max) && (c > max)))
650 {
651 // It's going to get adjusted.
652 x = a;
653 }
654 else
655 {
656 continue;
657 }
658 }
659 else
660 {
661 x = ((b*c) + (a*d)) / (b + d);
662 }
664 //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
665 //printf("x = %.1f\n", x);
667 // XXX: Use MAX and MIN
668 x = (x < min) ? min : x;
669 x = (x > max) ? max : x;
671 //printf("x = %.1f\n", x);
673 Point xp;
674 if (p1.x == p2.x)
675 {
676 xp.x = offy;
677 xp.y = x;
678 }
679 else
680 {
681 xp.x = x;
682 xp.y = offy;
683 }
684 //printf("(%.1f, %.1f)\n", xp.x, xp.y);
686 e1 = dist(start, xp);
687 e2 = dist(xp, end);
688 estdist = e1 + e2;
691 //printf("is %.1f < %.1f\n", estdist, conndist);
692 if (estdist < conndist)
693 {
694 #ifdef SELECTIVE_DEBUG
695 //double angle = AngleAFromThreeSides(dist(start, end),
696 // e1, e2);
697 printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
698 conn->_id, estdist, conndist);
699 #endif
700 conn->_needs_reroute_flag = true;
701 break;
702 }
704 }
705 }
706 }
709 void Router::printInfo(void)
710 {
711 FILE *fp = stdout;
712 fprintf(fp, "\nVisibility Graph info:\n");
713 fprintf(fp, "----------------------\n");
715 unsigned int currshape = 0;
716 int st_shapes = 0;
717 int st_vertices = 0;
718 int st_endpoints = 0;
719 int st_valid_shape_visedges = 0;
720 int st_valid_endpt_visedges = 0;
721 int st_invalid_visedges = 0;
722 VertInf *finish = vertices.end();
723 for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
724 {
725 VertID pID = t->id;
727 if ((pID.isShape) && (pID.objID != currshape))
728 {
729 currshape = pID.objID;
730 st_shapes++;
731 }
732 if (pID.isShape)
733 {
734 st_vertices++;
735 }
736 else
737 {
738 // The shape 0 ones are temporary and not considered.
739 st_endpoints++;
740 }
741 }
742 for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
743 t = t->lstNext)
744 {
745 std::pair<VertID, VertID> idpair = t->ids();
747 if (!(idpair.first.isShape) || !(idpair.second.isShape))
748 {
749 st_valid_endpt_visedges++;
750 }
751 else
752 {
753 st_valid_shape_visedges++;
754 }
755 }
756 for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
757 t = t->lstNext)
758 {
759 st_invalid_visedges++;
760 }
761 fprintf(fp, "Number of shapes: %d\n", st_shapes);
762 fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
763 st_vertices + st_endpoints, st_vertices, st_endpoints);
764 fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
765 "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
766 st_valid_endpt_visedges, st_valid_shape_visedges +
767 st_valid_endpt_visedges, st_valid_shape_visedges,
768 st_valid_endpt_visedges, st_invalid_visedges);
769 fprintf(fp, "----------------------\n");
770 fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
771 fprintf(fp, "----------------------\n");
773 fprintf(fp, "ADDS: "); timers.Print(tmAdd);
774 fprintf(fp, "DELS: "); timers.Print(tmDel);
775 fprintf(fp, "MOVS: "); timers.Print(tmMov);
776 fprintf(fp, "***S: "); timers.Print(tmSev);
777 fprintf(fp, "PTHS: "); timers.Print(tmPth);
778 fprintf(fp, "\n");
779 }
782 }