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"
32 namespace Avoid {
35 Router::Router()
36 : PartialTime(false)
37 // Algorithm options:
38 , UseAStarSearch(true)
39 , IgnoreRegions(true)
40 , SelectiveReroute(true)
41 , IncludeEndpoints(true)
42 , UseLeesAlgorithm(false)
43 , InvisibilityGrph(true)
44 , PartialFeedback(false)
45 // Instrumentation:
46 , st_checked_edges(0)
47 #ifdef LINEDEBUG
48 , avoid_screen(NULL)
49 #endif
50 { }
55 void Router::addShape(ShapeRef *shape)
56 {
57 unsigned int pid = shape->id();
58 Polygn poly = shape->poly();
60 adjustContainsWithAdd(poly, pid);
62 // o Check all visibility edges to see if this one shape
63 // blocks them.
64 newBlockingShape(&poly, pid);
66 // o Calculate visibility for the new vertices.
67 if (UseLeesAlgorithm)
68 {
69 shapeVisSweep(shape);
70 }
71 else
72 {
73 shapeVis(shape);
74 }
75 callbackAllInvalidConnectors();
76 }
79 void Router::delShape(ShapeRef *shape)
80 {
81 unsigned int pid = shape->id();
83 // o Remove entries related to this shape's vertices
84 shape->removeFromGraph();
86 if (SelectiveReroute)
87 {
88 markConnectors(shape);
89 }
91 adjustContainsWithDel(pid);
93 delete shape;
95 // o Check all edges that were blocked by this shape.
96 if (InvisibilityGrph)
97 {
98 checkAllBlockedEdges(pid);
99 }
100 else
101 {
102 // check all edges not in graph
103 checkAllMissingEdges();
104 }
105 callbackAllInvalidConnectors();
106 }
109 ShapeRef *Router::moveShape(ShapeRef *oldShape, Polygn *newPoly, const bool first_move)
110 {
111 unsigned int pid = oldShape->id();
113 // o Remove entries related to this shape's vertices
114 oldShape->removeFromGraph();
116 if (SelectiveReroute && (!(PartialFeedback && PartialTime) || first_move))
117 {
118 markConnectors(oldShape);
119 }
121 adjustContainsWithDel(pid);
123 delete oldShape;
124 oldShape = NULL;
126 adjustContainsWithAdd(*newPoly, pid);
128 // o Check all edges that were blocked by this shape.
129 if (InvisibilityGrph)
130 {
131 checkAllBlockedEdges(pid);
132 }
133 else
134 {
135 // check all edges not in graph
136 checkAllMissingEdges();
137 }
139 ShapeRef *newShape = new ShapeRef(this, pid, *newPoly);
141 // o Check all visibility edges to see if this one shape
142 // blocks them.
143 if (!(PartialFeedback && PartialTime))
144 {
145 newBlockingShape(newPoly, pid);
146 }
148 // o Calculate visibility for the new vertices.
149 if (UseLeesAlgorithm)
150 {
151 shapeVisSweep(newShape);
152 }
153 else
154 {
155 shapeVis(newShape);
156 }
157 callbackAllInvalidConnectors();
159 return newShape;
160 }
164 //----------------------------------------------------------------------------
166 // XXX: attachedShapes and attachedConns both need to be rewritten
167 // for constant time lookup of attached objects once this info
168 // is stored better within libavoid. Also they shouldn't need to
169 // be friends of ConnRef.
171 // Returns a list of connector Ids of all the connectors of type
172 // 'type' attached to the shape with the ID 'shapeId'.
173 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
174 const unsigned int type)
175 {
176 ConnRefList::iterator fin = connRefs.end();
177 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
179 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
180 conns.push_back((*i)->_srcId);
181 }
182 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
183 conns.push_back((*i)->_dstId);
184 }
185 }
186 }
189 // Returns a list of shape Ids of all the shapes attached to the
190 // shape with the ID 'shapeId' with connection type 'type'.
191 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
192 const unsigned int type)
193 {
194 ConnRefList::iterator fin = connRefs.end();
195 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
196 if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
197 if ((*i)->_srcId != 0)
198 {
199 // Only if there is a shape attached to the other end.
200 shapes.push_back((*i)->_srcId);
201 }
202 }
203 else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
204 if ((*i)->_dstId != 0)
205 {
206 // Only if there is a shape attached to the other end.
207 shapes.push_back((*i)->_dstId);
208 }
209 }
210 }
211 }
214 // It's intended this function is called after shape movement has
215 // happened to alert connectors that they need to be rerouted.
216 void Router::callbackAllInvalidConnectors(void)
217 {
218 ConnRefList::iterator fin = connRefs.end();
219 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
220 (*i)->handleInvalid();
221 }
222 }
225 void Router::newBlockingShape(Polygn *poly, int pid)
226 {
227 // o Check all visibility edges to see if this one shape
228 // blocks them.
229 EdgeInf *finish = visGraph.end();
230 for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
231 {
232 EdgeInf *tmp = iter;
233 iter = iter->lstNext;
235 if (tmp->getDist() != 0)
236 {
237 pair<VertID, VertID> ids(tmp->ids());
238 VertID eID1 = ids.first;
239 VertID eID2 = ids.second;
240 pair<Point, Point> points(tmp->points());
241 Point e1 = points.first;
242 Point e2 = points.second;
243 bool blocked = false;
245 bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
246 bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
247 if (ep_in_poly1 || ep_in_poly2)
248 {
249 // Don't check edges that have a connector endpoint
250 // and are inside the shape being added.
251 continue;
252 }
254 for (int pt_i = 0; pt_i < poly->pn; pt_i++)
255 {
256 int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
257 if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
258 {
259 blocked = true;
260 break;
261 }
262 }
263 if (blocked)
264 {
265 db_printf("\tRemoving newly blocked edge (by shape %3d)"
266 "... \n\t\t", pid);
267 tmp->alertConns();
268 tmp->db_print();
269 if (InvisibilityGrph)
270 {
271 tmp->addBlocker(pid);
272 }
273 else
274 {
275 delete tmp;
276 }
277 }
278 }
279 }
280 }
283 void Router::checkAllBlockedEdges(int pid)
284 {
285 assert(InvisibilityGrph);
287 for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
288 {
289 EdgeInf *tmp = iter;
290 iter = iter->lstNext;
292 if (tmp->hasBlocker(pid))
293 {
294 tmp->checkVis();
295 }
296 }
297 }
300 void Router::checkAllMissingEdges(void)
301 {
302 assert(!InvisibilityGrph);
304 VertInf *first = NULL;
306 if (IncludeEndpoints)
307 {
308 first = vertices.connsBegin();
309 }
310 else
311 {
312 first = vertices.shapesBegin();
313 }
315 VertInf *pend = vertices.end();
316 for (VertInf *i = first; i != pend; i = i->lstNext)
317 {
318 VertID iID = i->id;
320 // Check remaining, earlier vertices
321 for (VertInf *j = first ; j != i; j = j->lstNext)
322 {
323 VertID jID = j->id;
324 if (!(iID.isShape) && (iID.objID != jID.objID))
325 {
326 // Don't keep visibility between edges of different conns
327 continue;
328 }
330 // See if the edge is already there?
331 bool found = (EdgeInf::existingEdge(i, j) != NULL);
333 if (!found)
334 {
335 // Didn't already exist, check.
336 bool knownNew = true;
337 EdgeInf::checkEdgeVisibility(i, j, knownNew);
338 }
339 }
340 }
341 }
344 void Router::generateContains(VertInf *pt)
345 {
346 contains[pt->id].clear();
348 ShapeRefList::iterator finish = shapeRefs.end();
349 for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
350 {
351 Polygn poly = copyPoly(*i);
352 if (inPoly(poly, pt->point))
353 {
354 contains[pt->id].insert((*i)->id());
355 }
356 freePoly(poly);
357 }
358 }
361 void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape)
362 {
363 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
364 k = k->lstNext)
365 {
366 if (inPoly(poly, k->point))
367 {
368 contains[k->id].insert(p_shape);
369 }
370 }
371 }
374 void Router::adjustContainsWithDel(const int p_shape)
375 {
376 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
377 k = k->lstNext)
378 {
379 contains[k->id].erase(p_shape);
380 }
381 }
384 #define MIN(a, b) (((a) <= (b)) ? (a) : (b))
385 #define MAX(a, b) (((a) >= (b)) ? (a) : (b))
387 #ifdef SELECTIVE_DEBUG
388 static double AngleAFromThreeSides(const double a, const double b,
389 const double c)
390 {
391 // returns angle A, the angle opposite from side a, in radians
392 return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
393 }
394 #endif
396 void Router::markConnectors(ShapeRef *shape)
397 {
398 assert(SelectiveReroute);
400 ConnRefList::iterator end = connRefs.end();
401 for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
402 {
403 ConnRef *conn = (*it);
405 if (conn->_route.pn == 0)
406 {
407 // Ignore uninitialised connectors.
408 continue;
409 }
411 Point start = conn->_route.ps[0];
412 Point end = conn->_route.ps[conn->_route.pn - 1];
414 double conndist = conn->_route_dist;
416 double estdist;
417 double e1, e2;
419 VertInf *beginV = shape->firstVert();
420 VertInf *endV = shape->lastVert()->lstNext;
421 for (VertInf *i = beginV; i != endV; i = i->lstNext)
422 {
423 const Point& p1 = i->point;
424 const Point& p2 = i->shNext->point;
426 double offy;
427 double a;
428 double b;
429 double c;
430 double d;
432 double min;
433 double max;
435 if (p1.y == p2.y)
436 {
437 // Standard case
438 offy = p1.y;
439 a = start.x;
440 b = start.y - offy;
441 c = end.x;
442 d = end.y - offy;
444 min = MIN(p1.x, p2.x);
445 max = MAX(p1.x, p2.x);
446 }
447 else if (p1.x == p2.x)
448 {
449 // Other Standard case
450 offy = p1.x;
451 a = start.y;
452 b = start.x - offy;
453 c = end.y;
454 d = end.x - offy;
456 min = MIN(p1.y, p2.y);
457 max = MAX(p1.y, p2.y);
458 }
459 else
460 {
461 // Need to do rotation
462 Point n_p2 = { p2.x - p1.x, p2.y - p1.y };
463 Point n_start = { start.x - p1.x, start.y - p1.y };
464 Point n_end = { end.x - p1.x, end.y - p1.y };
465 //printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
466 //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
467 //printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
469 double theta = 0 - atan2(n_p2.y, n_p2.x);
470 //printf("theta = %.2f\n", theta * (180 / PI));
472 Point r_p1 = {0, 0};
473 Point r_p2 = n_p2;
474 start = n_start;
475 end = n_end;
477 double cosv = cos(theta);
478 double sinv = sin(theta);
480 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
481 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
482 start.x = cosv * n_start.x - sinv * n_start.y;
483 start.y = cosv * n_start.y + sinv * n_start.x;
484 end.x = cosv * n_end.x - sinv * n_end.y;
485 end.y = cosv * n_end.y + sinv * n_end.x;
486 //printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
487 //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
488 //printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
490 if (((int) r_p2.y) != 0)
491 {
492 printf("r_p2.y: %f != 0\n", r_p2.y);
493 abort();
494 }
495 // This might be slightly off.
496 r_p2.y = 0;
498 offy = r_p1.y;
499 a = start.x;
500 b = start.y - offy;
501 c = end.x;
502 d = end.y - offy;
504 min = MIN(r_p1.x, r_p2.x);
505 max = MAX(r_p1.x, r_p2.x);
507 }
509 double x;
510 if ((b + d) == 0)
511 {
512 db_printf("WARNING: (b + d) == 0\n");
513 d = d * -1;
514 }
516 if ((b == 0) && (d == 0))
517 {
518 db_printf("WARNING: b == d == 0\n");
519 if (((a < min) && (c < min)) ||
520 ((a > max) && (c > max)))
521 {
522 // It's going to get adjusted.
523 x = a;
524 }
525 else
526 {
527 continue;
528 }
529 }
530 else
531 {
532 x = ((b*c) + (a*d)) / (b + d);
533 }
535 //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
536 //printf("x = %.1f\n", x);
538 // XXX: Use MAX and MIN
539 x = (x < min) ? min : x;
540 x = (x > max) ? max : x;
542 //printf("x = %.1f\n", x);
544 Point xp;
545 if (p1.x == p2.x)
546 {
547 xp.x = offy;
548 xp.y = x;
549 }
550 else
551 {
552 xp.x = x;
553 xp.y = offy;
554 }
555 //printf("(%.1f, %.1f)\n", xp.x, xp.y);
557 e1 = dist(start, xp);
558 e2 = dist(xp, end);
559 estdist = e1 + e2;
562 //printf("is %.1f < %.1f\n", estdist, conndist);
563 if (estdist < conndist)
564 {
565 #ifdef SELECTIVE_DEBUG
566 //double angle = AngleAFromThreeSides(dist(start, end),
567 // e1, e2);
568 printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
569 conn->_id, estdist, conndist);
570 #endif
571 conn->_needs_reroute_flag = true;
572 break;
573 }
575 }
576 }
577 }
580 void Router::printInfo(void)
581 {
582 FILE *fp = stdout;
583 fprintf(fp, "\nVisibility Graph info:\n");
584 fprintf(fp, "----------------------\n");
586 unsigned int currshape = 0;
587 int st_shapes = 0;
588 int st_vertices = 0;
589 int st_endpoints = 0;
590 int st_valid_shape_visedges = 0;
591 int st_valid_endpt_visedges = 0;
592 int st_invalid_visedges = 0;
593 VertInf *finish = vertices.end();
594 for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
595 {
596 VertID pID = t->id;
598 if ((pID.isShape) && (pID.objID != currshape))
599 {
600 currshape = pID.objID;
601 st_shapes++;
602 }
603 if (pID.isShape)
604 {
605 st_vertices++;
606 }
607 else
608 {
609 // The shape 0 ones are temporary and not considered.
610 st_endpoints++;
611 }
612 }
613 for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
614 t = t->lstNext)
615 {
616 std::pair<VertID, VertID> idpair = t->ids();
618 if (!(idpair.first.isShape) || !(idpair.second.isShape))
619 {
620 st_valid_endpt_visedges++;
621 }
622 else
623 {
624 st_valid_shape_visedges++;
625 }
626 }
627 for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
628 t = t->lstNext)
629 {
630 st_invalid_visedges++;
631 }
632 fprintf(fp, "Number of shapes: %d\n", st_shapes);
633 fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
634 st_vertices + st_endpoints, st_vertices, st_endpoints);
635 fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
636 "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
637 st_valid_endpt_visedges, st_valid_shape_visedges +
638 st_valid_endpt_visedges, st_valid_shape_visedges,
639 st_valid_endpt_visedges, st_invalid_visedges);
640 fprintf(fp, "----------------------\n");
641 fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
642 fprintf(fp, "----------------------\n");
644 fprintf(fp, "ADDS: "); timers.Print(tmAdd);
645 fprintf(fp, "DELS: "); timers.Print(tmDel);
646 fprintf(fp, "MOVS: "); timers.Print(tmMov);
647 fprintf(fp, "***S: "); timers.Print(tmSev);
648 fprintf(fp, "PTHS: "); timers.Print(tmPth);
649 fprintf(fp, "\n");
650 }
653 }