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 //#define ORTHOGONAL_ROUTING
  32
  33 namespace Avoid {
  34
  35
  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 { }
  53
  54
  55
  56
  57 void Router::addShape(ShapeRef *shape)
  58 {
  59     unsigned int pid = shape->id();
  60     Polygn poly = shape->poly();
  61
  62     adjustContainsWithAdd(poly, pid);
  63
  64     // o  Check all visibility edges to see if this one shape
  65     //    blocks them.
  66     newBlockingShape(&poly, pid);
  67
  68 #ifdef ORTHOGONAL_ROUTING
  69     Region::addShape(shape);
  70 #endif
  71
  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 }
  83
  84
  85 void Router::delShape(ShapeRef *shape)
  86 {
  87     unsigned int pid = shape->id();
  88
  89     // o  Remove entries related to this shape's vertices
  90     shape->removeFromGraph();
  91
  92     if (SelectiveReroute)
  93     {
  94         markConnectors(shape);
  95     }
  96
  97     adjustContainsWithDel(pid);
  98
  99 #ifdef ORTHOGONAL_ROUTING
 100     Region::removeShape(shape);
 101 #endif
 102
 103     delete shape;
 104
 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 }
 117
 118
 119 void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
 120 {
 121     unsigned int pid = shape->id();
 122     bool notPartialTime = !(PartialFeedback && PartialTime);
 123
 124     // o  Remove entries related to this shape's vertices
 125     shape->removeFromGraph();
 126
 127     if (SelectiveReroute && (notPartialTime || first_move))
 128     {
 129         markConnectors(shape);
 130     }
 131
 132     adjustContainsWithDel(pid);
 133
 134 #ifdef ORTHOGONAL_ROUTING
 135     Region::removeShape(shape);
 136 #endif
 137
 138     shape->setNewPoly(*newPoly);
 139
 140     adjustContainsWithAdd(*newPoly, pid);
 141
 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     }
 152
 153 #ifdef ORTHOGONAL_ROUTING
 154     Region::addShape(shape);
 155 #endif
 156
 157     // o  Check all visibility edges to see if this one shape
 158     //    blocks them.
 159     if (notPartialTime)
 160     {
 161         newBlockingShape(newPoly, pid);
 162     }
 163
 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 }
 175
 176
 177
 178 //----------------------------------------------------------------------------
 179
 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.
 184
 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) {
 192
 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 }
 201
 202
 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 }
 226
 227
 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 }
 237
 238
 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;
 248
 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;
 258
 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             }
 267
 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 }
 295
 296
 297 void Router::checkAllBlockedEdges(int pid)
 298 {
 299     assert(InvisibilityGrph);
 300
 301     for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
 302     {
 303         EdgeInf *tmp = iter;
 304         iter = iter->lstNext;
 305
 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 }
 317
 318
 319 void Router::checkAllMissingEdges(void)
 320 {
 321     assert(!InvisibilityGrph);
 322
 323     VertInf *first = NULL;
 324
 325     if (IncludeEndpoints)
 326     {
 327         first = vertices.connsBegin();
 328     }
 329     else
 330     {
 331         first = vertices.shapesBegin();
 332     }
 333
 334     VertInf *pend = vertices.end();
 335     for (VertInf *i = first; i != pend; i = i->lstNext)
 336     {
 337         VertID iID = i->id;
 338
 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             }
 348
 349             // See if the edge is already there?
 350             bool found = (EdgeInf::existingEdge(i, j) != NULL);
 351
 352             if (!found)
 353             {
 354                 // Didn't already exist, check.
 355                 bool knownNew = true;
 356                 EdgeInf::checkEdgeVisibility(i, j, knownNew);
 357             }
 358         }
 359     }
 360 }
 361
 362
 363 void Router::generateContains(VertInf *pt)
 364 {
 365     contains[pt->id].clear();
 366
 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 }
 378
 379
 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 }
 391
 392
 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 }
 401
 402
 403 #define MIN(a, b) (((a) <= (b)) ? (a) : (b))
 404 #define MAX(a, b) (((a) >= (b)) ? (a) : (b))
 405
 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
 414
 415 void Router::markConnectors(ShapeRef *shape)
 416 {
 417     assert(SelectiveReroute);
 418
 419     ConnRefList::iterator end = connRefs.end();
 420     for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
 421     {
 422         ConnRef *conn = (*it);
 423
 424         if (conn->_route.pn == 0)
 425         {
 426             // Ignore uninitialised connectors.
 427             continue;
 428         }
 429
 430         Point start = conn->_route.ps[0];
 431         Point end = conn->_route.ps[conn->_route.pn - 1];
 432
 433         double conndist = conn->_route_dist;
 434
 435         double estdist;
 436         double e1, e2;
 437
 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;
 444
 445             double offy;
 446             double a;
 447             double b;
 448             double c;
 449             double d;
 450
 451             double min;
 452             double max;
 453
 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;
 462
 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;
 474
 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);
 487
 488                 double theta = 0 - atan2(n_p2.y, n_p2.x);
 489                 //printf("theta = %.2f\n", theta * (180 / PI));
 490
 491                 Point r_p1 = {0, 0};
 492                 Point r_p2 = n_p2;
 493                 start = n_start;
 494                 end = n_end;
 495
 496                 double cosv = cos(theta);
 497                 double sinv = sin(theta);
 498
 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);
 508
 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;
 516
 517                 offy = r_p1.y;
 518                 a = start.x;
 519                 b = start.y - offy;
 520                 c = end.x;
 521                 d = end.y - offy;
 522
 523                 min = MIN(r_p1.x, r_p2.x);
 524                 max = MAX(r_p1.x, r_p2.x);
 525
 526             }
 527
 528             double x;
 529             if ((b + d) == 0)
 530             {
 531                 db_printf("WARNING: (b + d) == 0\n");
 532                 d = d * -1;
 533             }
 534
 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             }
 553
 554             //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
 555             //printf("x = %.1f\n", x);
 556
 557             // XXX: Use MAX and MIN
 558             x = (x < min) ? min : x;
 559             x = (x > max) ? max : x;
 560
 561             //printf("x = %.1f\n", x);
 562
 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);
 575
 576             e1 = dist(start, xp);
 577             e2 = dist(xp, end);
 578             estdist = e1 + e2;
 579
 580
 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             }
 593
 594         }
 595     }
 596 }
 597
 598
 599 void Router::printInfo(void)
 600 {
 601     FILE *fp = stdout;
 602     fprintf(fp, "\nVisibility Graph info:\n");
 603     fprintf(fp, "----------------------\n");
 604
 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;
 616
 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();
 636
 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");
 662
 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 }
 670
 671
 672 }
 673