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 "math.h"
31 //#define ORTHOGONAL_ROUTING
33 namespace Avoid {
36 Router::Router()
37 : PartialTime(false)
38 // Algorithm options:
39 , UseAStarSearch(true)
40 , IgnoreRegions(true)
41 , SelectiveReroute(true)
42 , IncludeEndpoints(true)
43 , UseLeesAlgorithm(false)
44 , InvisibilityGrph(true)
45 , ConsolidateMoves(false)
46 , PartialFeedback(false)
47 // Instrumentation:
48 , st_checked_edges(0)
49 #ifdef LINEDEBUG
50 , avoid_screen(NULL)
51 #endif
52 { }
57 void Router::addShape(ShapeRef *shape)
58 {
59 unsigned int pid = shape->id();
60 Polygn poly = shape->poly();
62 adjustContainsWithAdd(poly, pid);
64 // o Check all visibility edges to see if this one shape
65 // blocks them.
66 newBlockingShape(&poly, pid);
68 #ifdef ORTHOGONAL_ROUTING
69 Region::addShape(shape);
70 #endif
72 // o Calculate visibility for the new vertices.
73 if (UseLeesAlgorithm)
74 {
75 shapeVisSweep(shape);
76 }
77 else
78 {
79 shapeVis(shape);
80 }
81 callbackAllInvalidConnectors();
82 }
85 void Router::delShape(ShapeRef *shape)
86 {
87 unsigned int pid = shape->id();
89 // o Remove entries related to this shape's vertices
90 shape->removeFromGraph();
92 if (SelectiveReroute)
93 {
94 markConnectors(shape);
95 }
97 adjustContainsWithDel(pid);
99 #ifdef ORTHOGONAL_ROUTING
100 Region::removeShape(shape);
101 #endif
103 delete shape;
105 // o Check all edges that were blocked by this shape.
106 if (InvisibilityGrph)
107 {
108 checkAllBlockedEdges(pid);
109 }
110 else
111 {
112 // check all edges not in graph
113 checkAllMissingEdges();
114 }
115 callbackAllInvalidConnectors();
116 }
119 void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
120 {
121 unsigned int pid = shape->id();
122 bool notPartialTime = !(PartialFeedback && PartialTime);
124 // o Remove entries related to this shape's vertices
125 shape->removeFromGraph();
127 if (SelectiveReroute && (notPartialTime || first_move))
128 {
129 markConnectors(shape);
130 }
132 adjustContainsWithDel(pid);
134 #ifdef ORTHOGONAL_ROUTING
135 Region::removeShape(shape);
136 #endif
138 shape->setNewPoly(*newPoly);
140 adjustContainsWithAdd(*newPoly, pid);
142 // o Check all edges that were blocked by this shape.
143 if (InvisibilityGrph)
144 {
145 checkAllBlockedEdges(pid);
146 }
147 else
148 {
149 // check all edges not in graph
150 checkAllMissingEdges();
151 }
153 #ifdef ORTHOGONAL_ROUTING
154 Region::addShape(shape);
155 #endif
157 // o Check all visibility edges to see if this one shape
158 // blocks them.
159 if (notPartialTime)
160 {
161 newBlockingShape(newPoly, pid);
162 }
164 // o Calculate visibility for the new vertices.
165 if (UseLeesAlgorithm)
166 {
167 shapeVisSweep(shape);
168 }
169 else
170 {
171 shapeVis(shape);
172 }
173 callbackAllInvalidConnectors();
174 }
178 //----------------------------------------------------------------------------
180 // XXX: attachedShapes and attachedConns both need to be rewritten
181 // for constant time lookup of attached objects once this info
182 // is stored better within libavoid. Also they shouldn't need to
183 // be friends of ConnRef.
185 // Returns a list of connector Ids of all the connectors of type
186 // 'type' attached to the shape with the ID 'shapeId'.
187 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
188 const unsigned int type)
189 {
190 ConnRefList::iterator fin = connRefs.end();
191 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
193 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
194 conns.push_back((*i)->_srcId);
195 }
196 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
197 conns.push_back((*i)->_dstId);
198 }
199 }
200 }
203 // Returns a list of shape Ids of all the shapes attached to the
204 // shape with the ID 'shapeId' with connection type 'type'.
205 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
206 const unsigned int type)
207 {
208 ConnRefList::iterator fin = connRefs.end();
209 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
210 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
211 if ((*i)->_srcId != 0)
212 {
213 // Only if there is a shape attached to the other end.
214 shapes.push_back((*i)->_srcId);
215 }
216 }
217 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
218 if ((*i)->_dstId != 0)
219 {
220 // Only if there is a shape attached to the other end.
221 shapes.push_back((*i)->_dstId);
222 }
223 }
224 }
225 }
228 // It's intended this function is called after shape movement has
229 // happened to alert connectors that they need to be rerouted.
230 void Router::callbackAllInvalidConnectors(void)
231 {
232 ConnRefList::iterator fin = connRefs.end();
233 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
234 (*i)->handleInvalid();
235 }
236 }
239 void Router::newBlockingShape(Polygn *poly, int pid)
240 {
241 // o Check all visibility edges to see if this one shape
242 // blocks them.
243 EdgeInf *finish = visGraph.end();
244 for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
245 {
246 EdgeInf *tmp = iter;
247 iter = iter->lstNext;
249 if (tmp->getDist() != 0)
250 {
251 pair<VertID, VertID> ids(tmp->ids());
252 VertID eID1 = ids.first;
253 VertID eID2 = ids.second;
254 pair<Point, Point> points(tmp->points());
255 Point e1 = points.first;
256 Point e2 = points.second;
257 bool blocked = false;
259 bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
260 bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
261 if (ep_in_poly1 || ep_in_poly2)
262 {
263 // Don't check edges that have a connector endpoint
264 // and are inside the shape being added.
265 continue;
266 }
268 for (int pt_i = 0; pt_i < poly->pn; pt_i++)
269 {
270 int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
271 if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
272 {
273 blocked = true;
274 break;
275 }
276 }
277 if (blocked)
278 {
279 db_printf("\tRemoving newly blocked edge (by shape %3d)"
280 "... \n\t\t", pid);
281 tmp->alertConns();
282 tmp->db_print();
283 if (InvisibilityGrph)
284 {
285 tmp->addBlocker(pid);
286 }
287 else
288 {
289 delete tmp;
290 }
291 }
292 }
293 }
294 }
297 void Router::checkAllBlockedEdges(int pid)
298 {
299 assert(InvisibilityGrph);
301 for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
302 {
303 EdgeInf *tmp = iter;
304 iter = iter->lstNext;
306 if (tmp->_blocker == -1)
307 {
308 tmp->alertConns();
309 tmp->checkVis();
310 }
311 else if (tmp->_blocker == pid)
312 {
313 tmp->checkVis();
314 }
315 }
316 }
319 void Router::checkAllMissingEdges(void)
320 {
321 assert(!InvisibilityGrph);
323 VertInf *first = NULL;
325 if (IncludeEndpoints)
326 {
327 first = vertices.connsBegin();
328 }
329 else
330 {
331 first = vertices.shapesBegin();
332 }
334 VertInf *pend = vertices.end();
335 for (VertInf *i = first; i != pend; i = i->lstNext)
336 {
337 VertID iID = i->id;
339 // Check remaining, earlier vertices
340 for (VertInf *j = first ; j != i; j = j->lstNext)
341 {
342 VertID jID = j->id;
343 if (!(iID.isShape) && (iID.objID != jID.objID))
344 {
345 // Don't keep visibility between edges of different conns
346 continue;
347 }
349 // See if the edge is already there?
350 bool found = (EdgeInf::existingEdge(i, j) != NULL);
352 if (!found)
353 {
354 // Didn't already exist, check.
355 bool knownNew = true;
356 EdgeInf::checkEdgeVisibility(i, j, knownNew);
357 }
358 }
359 }
360 }
363 void Router::generateContains(VertInf *pt)
364 {
365 contains[pt->id].clear();
367 ShapeRefList::iterator finish = shapeRefs.end();
368 for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
369 {
370 Polygn poly = copyPoly(*i);
371 if (inPoly(poly, pt->point))
372 {
373 contains[pt->id].insert((*i)->id());
374 }
375 freePoly(poly);
376 }
377 }
380 void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape)
381 {
382 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
383 k = k->lstNext)
384 {
385 if (inPoly(poly, k->point))
386 {
387 contains[k->id].insert(p_shape);
388 }
389 }
390 }
393 void Router::adjustContainsWithDel(const int p_shape)
394 {
395 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
396 k = k->lstNext)
397 {
398 contains[k->id].erase(p_shape);
399 }
400 }
403 #define MIN(a, b) (((a) <= (b)) ? (a) : (b))
404 #define MAX(a, b) (((a) >= (b)) ? (a) : (b))
406 #ifdef SELECTIVE_DEBUG
407 static double AngleAFromThreeSides(const double a, const double b,
408 const double c)
409 {
410 // returns angle A, the angle opposite from side a, in radians
411 return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
412 }
413 #endif
415 void Router::markConnectors(ShapeRef *shape)
416 {
417 assert(SelectiveReroute);
419 ConnRefList::iterator end = connRefs.end();
420 for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
421 {
422 ConnRef *conn = (*it);
424 if (conn->_route.pn == 0)
425 {
426 // Ignore uninitialised connectors.
427 continue;
428 }
430 Point start = conn->_route.ps[0];
431 Point end = conn->_route.ps[conn->_route.pn - 1];
433 double conndist = conn->_route_dist;
435 double estdist;
436 double e1, e2;
438 VertInf *beginV = shape->firstVert();
439 VertInf *endV = shape->lastVert()->lstNext;
440 for (VertInf *i = beginV; i != endV; i = i->lstNext)
441 {
442 const Point& p1 = i->point;
443 const Point& p2 = i->shNext->point;
445 double offy;
446 double a;
447 double b;
448 double c;
449 double d;
451 double min;
452 double max;
454 if (p1.y == p2.y)
455 {
456 // Standard case
457 offy = p1.y;
458 a = start.x;
459 b = start.y - offy;
460 c = end.x;
461 d = end.y - offy;
463 min = MIN(p1.x, p2.x);
464 max = MAX(p1.x, p2.x);
465 }
466 else if (p1.x == p2.x)
467 {
468 // Other Standard case
469 offy = p1.x;
470 a = start.y;
471 b = start.x - offy;
472 c = end.y;
473 d = end.x - offy;
475 min = MIN(p1.y, p2.y);
476 max = MAX(p1.y, p2.y);
477 }
478 else
479 {
480 // Need to do rotation
481 Point n_p2 = { p2.x - p1.x, p2.y - p1.y };
482 Point n_start = { start.x - p1.x, start.y - p1.y };
483 Point n_end = { end.x - p1.x, end.y - p1.y };
484 //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
485 //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
486 //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
488 double theta = 0 - atan2(n_p2.y, n_p2.x);
489 //printf("theta = %.2f\n", theta * (180 / PI));
491 Point r_p1 = {0, 0};
492 Point r_p2 = n_p2;
493 start = n_start;
494 end = n_end;
496 double cosv = cos(theta);
497 double sinv = sin(theta);
499 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
500 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
501 start.x = cosv * n_start.x - sinv * n_start.y;
502 start.y = cosv * n_start.y + sinv * n_start.x;
503 end.x = cosv * n_end.x - sinv * n_end.y;
504 end.y = cosv * n_end.y + sinv * n_end.x;
505 //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
506 //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
507 //printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
509 if (((int) r_p2.y) != 0)
510 {
511 printf("r_p2.y: %f != 0\n", r_p2.y);
512 abort();
513 }
514 // This might be slightly off.
515 r_p2.y = 0;
517 offy = r_p1.y;
518 a = start.x;
519 b = start.y - offy;
520 c = end.x;
521 d = end.y - offy;
523 min = MIN(r_p1.x, r_p2.x);
524 max = MAX(r_p1.x, r_p2.x);
526 }
528 double x;
529 if ((b + d) == 0)
530 {
531 db_printf("WARNING: (b + d) == 0\n");
532 d = d * -1;
533 }
535 if ((b == 0) && (d == 0))
536 {
537 db_printf("WARNING: b == d == 0\n");
538 if (((a < min) && (c < min)) ||
539 ((a > max) && (c > max)))
540 {
541 // It's going to get adjusted.
542 x = a;
543 }
544 else
545 {
546 continue;
547 }
548 }
549 else
550 {
551 x = ((b*c) + (a*d)) / (b + d);
552 }
554 //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
555 //printf("x = %.1f\n", x);
557 // XXX: Use MAX and MIN
558 x = (x < min) ? min : x;
559 x = (x > max) ? max : x;
561 //printf("x = %.1f\n", x);
563 Point xp;
564 if (p1.x == p2.x)
565 {
566 xp.x = offy;
567 xp.y = x;
568 }
569 else
570 {
571 xp.x = x;
572 xp.y = offy;
573 }
574 //printf("(%.1f, %.1f)\n", xp.x, xp.y);
576 e1 = dist(start, xp);
577 e2 = dist(xp, end);
578 estdist = e1 + e2;
581 //printf("is %.1f < %.1f\n", estdist, conndist);
582 if (estdist < conndist)
583 {
584 #ifdef SELECTIVE_DEBUG
585 //double angle = AngleAFromThreeSides(dist(start, end),
586 // e1, e2);
587 printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
588 conn->_id, estdist, conndist);
589 #endif
590 conn->_needs_reroute_flag = true;
591 break;
592 }
594 }
595 }
596 }
599 void Router::printInfo(void)
600 {
601 FILE *fp = stdout;
602 fprintf(fp, "\nVisibility Graph info:\n");
603 fprintf(fp, "----------------------\n");
605 unsigned int currshape = 0;
606 int st_shapes = 0;
607 int st_vertices = 0;
608 int st_endpoints = 0;
609 int st_valid_shape_visedges = 0;
610 int st_valid_endpt_visedges = 0;
611 int st_invalid_visedges = 0;
612 VertInf *finish = vertices.end();
613 for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
614 {
615 VertID pID = t->id;
617 if ((pID.isShape) && (pID.objID != currshape))
618 {
619 currshape = pID.objID;
620 st_shapes++;
621 }
622 if (pID.isShape)
623 {
624 st_vertices++;
625 }
626 else
627 {
628 // The shape 0 ones are temporary and not considered.
629 st_endpoints++;
630 }
631 }
632 for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
633 t = t->lstNext)
634 {
635 std::pair<VertID, VertID> idpair = t->ids();
637 if (!(idpair.first.isShape) || !(idpair.second.isShape))
638 {
639 st_valid_endpt_visedges++;
640 }
641 else
642 {
643 st_valid_shape_visedges++;
644 }
645 }
646 for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
647 t = t->lstNext)
648 {
649 st_invalid_visedges++;
650 }
651 fprintf(fp, "Number of shapes: %d\n", st_shapes);
652 fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
653 st_vertices + st_endpoints, st_vertices, st_endpoints);
654 fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
655 "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
656 st_valid_endpt_visedges, st_valid_shape_visedges +
657 st_valid_endpt_visedges, st_valid_shape_visedges,
658 st_valid_endpt_visedges, st_invalid_visedges);
659 fprintf(fp, "----------------------\n");
660 fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
661 fprintf(fp, "----------------------\n");
663 fprintf(fp, "ADDS: "); timers.Print(tmAdd);
664 fprintf(fp, "DELS: "); timers.Print(tmDel);
665 fprintf(fp, "MOVS: "); timers.Print(tmMov);
666 fprintf(fp, "***S: "); timers.Print(tmSev);
667 fprintf(fp, "PTHS: "); timers.Print(tmPth);
668 fprintf(fp, "\n");
669 }
672 }