src/libavoid/router.cpp

   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 */
  22
  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"
  30
  31
  32 namespace Avoid {
  33
  34
  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 { }
  51
  52
  53
  54
  55 void Router::addShape(ShapeRef *shape)
  56 {
  57     unsigned int pid = shape->id();
  58     Polygn poly = shape->poly();
  59
  60     adjustContainsWithAdd(poly, pid);
  61
  62     // o  Check all visibility edges to see if this one shape
  63     //    blocks them.
  64     newBlockingShape(&poly, pid);
  65
  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 }
  77
  78
  79 void Router::delShape(ShapeRef *shape)
  80 {
  81     unsigned int pid = shape->id();
  82
  83     // o  Remove entries related to this shape's vertices
  84     shape->removeFromGraph();
  85
  86     if (SelectiveReroute)
  87     {
  88         markConnectors(shape);
  89     }
  90
  91     adjustContainsWithDel(pid);
  92
  93     delete shape;
  94
  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 }
 107
 108
 109 ShapeRef *Router::moveShape(ShapeRef *oldShape, Polygn *newPoly, const bool first_move)
 110 {
 111     unsigned int pid = oldShape->id();
 112
 113     // o  Remove entries related to this shape's vertices
 114     oldShape->removeFromGraph();
 115
 116     if (SelectiveReroute && (!(PartialFeedback && PartialTime) || first_move))
 117     {
 118         markConnectors(oldShape);
 119     }
 120
 121     adjustContainsWithDel(pid);
 122
 123     delete oldShape;
 124     oldShape = NULL;
 125
 126     adjustContainsWithAdd(*newPoly, pid);
 127
 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     }
 138
 139     ShapeRef *newShape = new ShapeRef(this, pid, *newPoly);
 140
 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     }
 147
 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();
 158
 159     return newShape;
 160 }
 161
 162
 163
 164 //----------------------------------------------------------------------------
 165
 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.
 170
 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) {
 178
 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 }
 187
 188
 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 }
 212
 213
 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 }
 223
 224
 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;
 234
 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;
 244
 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             }
 253
 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 }
 281
 282
 283 void Router::checkAllBlockedEdges(int pid)
 284 {
 285     assert(InvisibilityGrph);
 286
 287     for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
 288     {
 289         EdgeInf *tmp = iter;
 290         iter = iter->lstNext;
 291
 292         if (tmp->hasBlocker(pid))
 293         {
 294             tmp->checkVis();
 295         }
 296     }
 297 }
 298
 299
 300 void Router::checkAllMissingEdges(void)
 301 {
 302     assert(!InvisibilityGrph);
 303
 304     VertInf *first = NULL;
 305
 306     if (IncludeEndpoints)
 307     {
 308         first = vertices.connsBegin();
 309     }
 310     else
 311     {
 312         first = vertices.shapesBegin();
 313     }
 314
 315     VertInf *pend = vertices.end();
 316     for (VertInf *i = first; i != pend; i = i->lstNext)
 317     {
 318         VertID iID = i->id;
 319
 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             }
 329
 330             // See if the edge is already there?
 331             bool found = (EdgeInf::existingEdge(i, j) != NULL);
 332
 333             if (!found)
 334             {
 335                 // Didn't already exist, check.
 336                 bool knownNew = true;
 337                 EdgeInf::checkEdgeVisibility(i, j, knownNew);
 338             }
 339         }
 340     }
 341 }
 342
 343
 344 void Router::generateContains(VertInf *pt)
 345 {
 346     contains[pt->id].clear();
 347
 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 }
 359
 360
 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 }
 372
 373
 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 }
 382
 383
 384 #define MIN(a, b) (((a) <= (b)) ? (a) : (b))
 385 #define MAX(a, b) (((a) >= (b)) ? (a) : (b))
 386
 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
 395
 396 void Router::markConnectors(ShapeRef *shape)
 397 {
 398     assert(SelectiveReroute);
 399
 400     ConnRefList::iterator end = connRefs.end();
 401     for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
 402     {
 403         ConnRef *conn = (*it);
 404
 405         if (conn->_route.pn == 0)
 406         {
 407             // Ignore uninitialised connectors.
 408             continue;
 409         }
 410
 411         Point start = conn->_route.ps[0];
 412         Point end = conn->_route.ps[conn->_route.pn - 1];
 413
 414         double conndist = conn->_route_dist;
 415
 416         double estdist;
 417         double e1, e2;
 418
 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;
 425
 426             double offy;
 427             double a;
 428             double b;
 429             double c;
 430             double d;
 431
 432             double min;
 433             double max;
 434
 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;
 443
 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;
 455
 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);
 468
 469                 double theta = 0 - atan2(n_p2.y, n_p2.x);
 470                 //printf("theta = %.2f\n", theta * (180 / PI));
 471
 472                 Point r_p1 = {0, 0};
 473                 Point r_p2 = n_p2;
 474                 start = n_start;
 475                 end = n_end;
 476
 477                 double cosv = cos(theta);
 478                 double sinv = sin(theta);
 479
 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);
 489
 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;
 497
 498                 offy = r_p1.y;
 499                 a = start.x;
 500                 b = start.y - offy;
 501                 c = end.x;
 502                 d = end.y - offy;
 503
 504                 min = MIN(r_p1.x, r_p2.x);
 505                 max = MAX(r_p1.x, r_p2.x);
 506
 507             }
 508
 509             double x;
 510             if ((b + d) == 0)
 511             {
 512                 db_printf("WARNING: (b + d) == 0\n");
 513                 d = d * -1;
 514             }
 515
 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             }
 534
 535             //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
 536             //printf("x = %.1f\n", x);
 537
 538             // XXX: Use MAX and MIN
 539             x = (x < min) ? min : x;
 540             x = (x > max) ? max : x;
 541
 542             //printf("x = %.1f\n", x);
 543
 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);
 556
 557             e1 = dist(start, xp);
 558             e2 = dist(xp, end);
 559             estdist = e1 + e2;
 560
 561
 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             }
 574
 575         }
 576     }
 577 }
 578
 579
 580 void Router::printInfo(void)
 581 {
 582     FILE *fp = stdout;
 583     fprintf(fp, "\nVisibility Graph info:\n");
 584     fprintf(fp, "----------------------\n");
 585
 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;
 597
 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();
 617
 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");
 643
 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 }
 651
 652
 653 }
 654