src/libavoid/graph.cpp

   1 /*
   2  * vim: ts=4 sw=4 et tw=0 wm=0
   3  *
   4  * libavoid - Fast, Incremental, Object-avoiding Line Router
   5  *
   6  * Copyright (C) 2004-2009  Monash University
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  * See the file LICENSE.LGPL distributed with the library.
  13  *
  14  * Licensees holding a valid commercial license may use this file in
  15  * accordance with the commercial license agreement provided with the
  16  * library.
  17  *
  18  * This library is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  21  *
  22  * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
  23 */
  24
  25
  26 #include <cmath>
  27
  28 #include "libavoid/debug.h"
  29 #include "libavoid/graph.h"
  30 #include "libavoid/connector.h"
  31 #include "libavoid/geometry.h"
  32 #include "libavoid/timer.h"
  33 #include "libavoid/vertices.h"
  34 #include "libavoid/router.h"
  35 #include "libavoid/assertions.h"
  36
  37
  38 using std::pair;
  39
  40 namespace Avoid {
  41
  42
  43 EdgeInf::EdgeInf(VertInf *v1, VertInf *v2, const bool orthogonal)
  44     : lstPrev(NULL),
  45       lstNext(NULL),
  46       _blocker(0),
  47       _router(NULL),
  48       _added(false),
  49       _visible(false),
  50       _orthogonal(orthogonal),
  51       _v1(v1),
  52       _v2(v2),
  53       _dist(-1)
  54 {
  55     // Not passed NULL values.
  56     COLA_ASSERT(v1 && v2);
  57
  58     // We are in the same instance
  59     COLA_ASSERT(_v1->_router == _v2->_router);
  60     _router = _v1->_router;
  61
  62     _conns.clear();
  63 }
  64
  65
  66 EdgeInf::~EdgeInf()
  67 {
  68     if (_added)
  69     {
  70         makeInactive();
  71     }
  72 }
  73
  74
  75 // Gives an order value between 0 and 3 for the point c, given the last
  76 // segment was from a to b.  Returns the following value:
  77 //    0 : Point c is directly backwards from point b.
  78 //    1 : Point c is a left-hand 90 degree turn.
  79 //    2 : Point c is a right-hand 90 degree turn.
  80 //    3 : Point c is straight ahead (collinear).
  81 //
  82 static inline int orthogTurnOrder(const Point& a, const Point& b,
  83         const Point& c)
  84 {
  85     // We should only be calling this with orthogonal points,
  86     COLA_ASSERT((c.x == b.x) || (c.y == b.y));
  87     COLA_ASSERT((a.x == b.x) || (a.y == b.y));
  88
  89     int direction = vecDir(a, b, c);
  90
  91     if (direction > 0)
  92     {
  93         // Counterclockwise := left
  94         return 1;
  95     }
  96     else if (direction < 0)
  97     {
  98         // Clockwise := right
  99         return 2;
 100     }
 101
 102     if (b.x == c.x)
 103     {
 104         if ( ((a.y < b.y) && (c.y < b.y)) ||
 105              ((a.y > b.y) && (c.y > b.y)) )
 106         {
 107             // Behind.
 108             return 0;
 109         }
 110     }
 111     else
 112     {
 113         if ( ((a.x < b.x) && (c.x < b.x)) ||
 114              ((a.x > b.x) && (c.x > b.x)) )
 115         {
 116             // Behind.
 117             return 0;
 118         }
 119     }
 120
 121     // Ahead.
 122     return 3;
 123 }
 124
 125
 126 // Returns a less than operation for a set exploration order for orthogonal
 127 // searching.  Forward, then left, then right.  Or if there is no previous
 128 // point, then the order is north, east, south, then west.
 129 // Note: This method assumes the two Edges that share a common point.
 130 bool EdgeInf::rotationLessThan(const VertInf *lastV, const EdgeInf *rhs) const
 131 {
 132     if ((_v1 == rhs->_v1) && (_v2 == rhs->_v2))
 133     {
 134         // Effectively the same visibility edge, so they are equal.
 135         return false;
 136     }
 137     VertInf *lhsV = NULL, *rhsV = NULL, *commonV = NULL;
 138
 139     // Determine common Point and the comparison point on the left- and
 140     // the right-hand-side.
 141     if (_v1 == rhs->_v1)
 142     {
 143         commonV = _v1;
 144         lhsV = _v2;
 145         rhsV = rhs->_v2;
 146     }
 147     else if (_v1 == rhs->_v2)
 148     {
 149         commonV = _v1;
 150         lhsV = _v2;
 151         rhsV = rhs->_v1;
 152     }
 153     else if (_v2 == rhs->_v1)
 154     {
 155         commonV = _v2;
 156         lhsV = _v1;
 157         rhsV = rhs->_v2;
 158     }
 159     else if (_v2 == rhs->_v2)
 160     {
 161         commonV = _v2;
 162         lhsV = _v1;
 163         rhsV = rhs->_v1;
 164     }
 165
 166     const Point& lhsPt = lhsV->point;
 167     const Point& rhsPt = rhsV->point;
 168     const Point& commonPt = commonV->point;
 169
 170     // If no lastPt, use one directly to the left;
 171     Point lastPt = (lastV) ? lastV->point : Point(commonPt.x - 10,  commonPt.y);
 172
 173     int lhsVal = orthogTurnOrder(lastPt, commonPt, lhsPt);
 174     int rhsVal = orthogTurnOrder(lastPt, commonPt, rhsPt);
 175
 176     return lhsVal < rhsVal;
 177 }
 178
 179
 180 void EdgeInf::makeActive(void)
 181 {
 182     COLA_ASSERT(_added == false);
 183
 184     if (_orthogonal)
 185     {
 186         COLA_ASSERT(_visible);
 187         _router->visOrthogGraph.addEdge(this);
 188         _pos1 = _v1->orthogVisList.insert(_v1->orthogVisList.begin(), this);
 189         _v1->orthogVisListSize++;
 190         _pos2 = _v2->orthogVisList.insert(_v2->orthogVisList.begin(), this);
 191         _v2->orthogVisListSize++;
 192     }
 193     else
 194     {
 195         if (_visible)
 196         {
 197             _router->visGraph.addEdge(this);
 198             _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
 199             _v1->visListSize++;
 200             _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
 201             _v2->visListSize++;
 202         }
 203         else // if (invisible)
 204         {
 205             _router->invisGraph.addEdge(this);
 206             _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
 207             _v1->invisListSize++;
 208             _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
 209             _v2->invisListSize++;
 210         }
 211     }
 212     _added = true;
 213 }
 214
 215
 216 void EdgeInf::makeInactive(void)
 217 {
 218     COLA_ASSERT(_added == true);
 219
 220     if (_orthogonal)
 221     {
 222         COLA_ASSERT(_visible);
 223         _router->visOrthogGraph.removeEdge(this);
 224         _v1->orthogVisList.erase(_pos1);
 225         _v1->orthogVisListSize--;
 226         _v2->orthogVisList.erase(_pos2);
 227         _v2->orthogVisListSize--;
 228     }
 229     else
 230     {
 231         if (_visible)
 232         {
 233             _router->visGraph.removeEdge(this);
 234             _v1->visList.erase(_pos1);
 235             _v1->visListSize--;
 236             _v2->visList.erase(_pos2);
 237             _v2->visListSize--;
 238         }
 239         else // if (invisible)
 240         {
 241             _router->invisGraph.removeEdge(this);
 242             _v1->invisList.erase(_pos1);
 243             _v1->invisListSize--;
 244             _v2->invisList.erase(_pos2);
 245             _v2->invisListSize--;
 246         }
 247     }
 248     _blocker = 0;
 249     _conns.clear();
 250     _added = false;
 251 }
 252
 253
 254 void EdgeInf::setDist(double dist)
 255 {
 256     //COLA_ASSERT(dist != 0);
 257
 258     if (_added && !_visible)
 259     {
 260         makeInactive();
 261         COLA_ASSERT(!_added);
 262     }
 263     if (!_added)
 264     {
 265         _visible = true;
 266         makeActive();
 267     }
 268     _dist = dist;
 269     _blocker = 0;
 270 }
 271
 272
 273 bool EdgeInf::added(void)
 274 {
 275     return _added;
 276 }
 277
 278
 279 void EdgeInf::alertConns(void)
 280 {
 281     FlagList::iterator finish = _conns.end();
 282     for (FlagList::iterator i = _conns.begin(); i != finish; ++i)
 283     {
 284         *(*i) = true;
 285     }
 286     _conns.clear();
 287 }
 288
 289
 290 void EdgeInf::addConn(bool *flag)
 291 {
 292     _conns.push_back(flag);
 293 }
 294
 295
 296 void EdgeInf::addCycleBlocker(void)
 297 {
 298     // Needs to be in invisibility graph.
 299     addBlocker(-1);
 300 }
 301
 302
 303 void EdgeInf::addBlocker(int b)
 304 {
 305     COLA_ASSERT(_router->InvisibilityGrph);
 306
 307     if (_added && _visible)
 308     {
 309         makeInactive();
 310         COLA_ASSERT(!_added);
 311     }
 312     if (!_added)
 313     {
 314         _visible = false;
 315         makeActive();
 316     }
 317     _dist = 0;
 318     _blocker = b;
 319 }
 320
 321
 322 pair<VertID, VertID> EdgeInf::ids(void)
 323 {
 324     return std::make_pair(_v1->id, _v2->id);
 325 }
 326
 327
 328 pair<Point, Point> EdgeInf::points(void)
 329 {
 330     return std::make_pair(_v1->point, _v2->point);
 331 }
 332
 333
 334 void EdgeInf::db_print(void)
 335 {
 336     db_printf("Edge(");
 337     _v1->id.db_print();
 338     db_printf(",");
 339     _v2->id.db_print();
 340     db_printf(")\n");
 341 }
 342
 343
 344 void EdgeInf::checkVis(void)
 345 {
 346     if (_added && !_visible)
 347     {
 348         db_printf("\tChecking visibility for existing invisibility edge..."
 349                 "\n\t\t");
 350         db_print();
 351     }
 352     else if (_added && _visible)
 353     {
 354         db_printf("\tChecking visibility for existing visibility edge..."
 355                 "\n\t\t");
 356         db_print();
 357     }
 358
 359     int blocker = 0;
 360     bool cone1 = true;
 361     bool cone2 = true;
 362
 363     VertInf *i = _v1;
 364     VertInf *j = _v2;
 365     const VertID& iID = i->id;
 366     const VertID& jID = j->id;
 367     const Point& iPoint = i->point;
 368     const Point& jPoint = j->point;
 369
 370     _router->st_checked_edges++;
 371
 372     if (iID.isShape)
 373     {
 374         cone1 = inValidRegion(_router->IgnoreRegions, i->shPrev->point,
 375                 iPoint, i->shNext->point, jPoint);
 376     }
 377     else if (_router->IgnoreRegions == false)
 378     {
 379         // If Ignoring regions then this case is already caught by
 380         // the invalid regions, so only check it when not ignoring
 381         // regions.
 382         ShapeSet& ss = _router->contains[iID];
 383
 384         if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
 385         {
 386             db_printf("1: Edge of bounding shape\n");
 387             // Don't even check this edge, it should be zero,
 388             // since a point in a shape can't see it's corners
 389             cone1 = false;
 390         }
 391     }
 392
 393     if (cone1)
 394     {
 395         // If outside the first cone, don't even bother checking.
 396         if (jID.isShape)
 397         {
 398             cone2 = inValidRegion(_router->IgnoreRegions, j->shPrev->point,
 399                     jPoint, j->shNext->point, iPoint);
 400         }
 401         else if (_router->IgnoreRegions == false)
 402         {
 403             // If Ignoring regions then this case is already caught by
 404             // the invalid regions, so only check it when not ignoring
 405             // regions.
 406             ShapeSet& ss = _router->contains[jID];
 407
 408             if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
 409             {
 410                 db_printf("2: Edge of bounding shape\n");
 411                 // Don't even check this edge, it should be zero,
 412                 // since a point in a shape can't see it's corners
 413                 cone2 = false;
 414             }
 415         }
 416     }
 417
 418     if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
 419     {
 420
 421         // if i and j see each other, add edge
 422         db_printf("\tSetting visibility edge... \n\t\t");
 423         db_print();
 424
 425         double d = euclideanDist(iPoint, jPoint);
 426
 427         setDist(d);
 428
 429     }
 430     else if (_router->InvisibilityGrph)
 431     {
 432 #if 0
 433         db_printf("%d, %d, %d\n", cone1, cone2, blocker);
 434         db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x,
 435                 (int) iInfo.point.y, (int) jInfo.point.x,
 436                 (int) jInfo.point.y);
 437 #endif
 438
 439         // if i and j can't see each other, add blank edge
 440         db_printf("\tSetting invisibility edge... \n\t\t");
 441         db_print();
 442         addBlocker(blocker);
 443     }
 444 }
 445
 446
 447 int EdgeInf::firstBlocker(void)
 448 {
 449     ShapeSet ss = ShapeSet();
 450
 451     Point& pti = _v1->point;
 452     Point& ptj = _v2->point;
 453     VertID& iID = _v1->id;
 454     VertID& jID = _v2->id;
 455
 456     ContainsMap &contains = _router->contains;
 457     if (!(iID.isShape))
 458     {
 459         ss.insert(contains[iID].begin(), contains[iID].end());
 460     }
 461     if (!(jID.isShape))
 462     {
 463         ss.insert(contains[jID].begin(), contains[jID].end());
 464     }
 465
 466     VertInf *last = _router->vertices.end();
 467     unsigned int lastId = 0;
 468     bool seenIntersectionAtEndpoint = false;
 469     for (VertInf *k = _router->vertices.shapesBegin(); k != last; )
 470     {
 471         VertID kID = k->id;
 472         if (k->id == dummyOrthogID)
 473         {
 474             // Don't include orthogonal dummy vertices.
 475             k = k->lstNext;
 476             continue;
 477         }
 478         if (kID.objID != lastId)
 479         {
 480             if ((ss.find(kID.objID) != ss.end()))
 481             {
 482                 unsigned int shapeID = kID.objID;
 483                 db_printf("Endpoint is inside shape %u so ignore shape "
 484                         "edges.\n", kID.objID);
 485                 // One of the endpoints is inside this shape so ignore it.
 486                 while ((k != last) && (k->id.objID == shapeID))
 487                 {
 488                     // And skip the other vertices from this shape.
 489                     k = k->lstNext;
 490                 }
 491                 continue;
 492             }
 493             seenIntersectionAtEndpoint = false;
 494             lastId = kID.objID;
 495         }
 496         Point& kPoint = k->point;
 497         Point& kPrevPoint = k->shPrev->point;
 498         if (segmentShapeIntersect(pti, ptj, kPrevPoint, kPoint,
 499                     seenIntersectionAtEndpoint))
 500         {
 501             ss.clear();
 502             return kID.objID;
 503         }
 504         k = k->lstNext;
 505     }
 506     ss.clear();
 507     return 0;
 508 }
 509
 510
 511 bool EdgeInf::isBetween(VertInf *i, VertInf *j)
 512 {
 513     if ( ((i == _v1) && (j == _v2)) ||
 514          ((i == _v2) && (j == _v1)) )
 515     {
 516         return true;
 517     }
 518     return false;
 519 }
 520
 521
 522     // Returns true if this edge is a vertical or horizontal line segment.
 523 bool EdgeInf::isOrthogonal(void) const
 524 {
 525     return ((_v1->point.x == _v2->point.x) ||
 526             (_v1->point.y == _v2->point.y));
 527 }
 528
 529
 530 VertInf *EdgeInf::otherVert(VertInf *vert)
 531 {
 532     COLA_ASSERT((vert == _v1) || (vert == _v2));
 533
 534     if (vert == _v1)
 535     {
 536         return _v2;
 537     }
 538     return _v1;
 539 }
 540
 541
 542 EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
 543 {
 544     // This is for polyline routing, so check we're not
 545     // considering orthogonal vertices.
 546     COLA_ASSERT(i->id != dummyOrthogID);
 547     COLA_ASSERT(j->id != dummyOrthogID);
 548
 549     Router *router = i->_router;
 550     EdgeInf *edge = NULL;
 551
 552     if (knownNew)
 553     {
 554         COLA_ASSERT(existingEdge(i, j) == NULL);
 555         edge = new EdgeInf(i, j);
 556     }
 557     else
 558     {
 559         edge = existingEdge(i, j);
 560         if (edge == NULL)
 561         {
 562             edge = new EdgeInf(i, j);
 563         }
 564     }
 565     edge->checkVis();
 566     if (!(edge->_added) && !(router->InvisibilityGrph))
 567     {
 568         delete edge;
 569         edge = NULL;
 570     }
 571
 572     return edge;
 573 }
 574
 575
 576     // XXX: This function is ineffecient, and shouldn't even really be
 577     //      required.
 578 EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
 579 {
 580     VertInf *selected = NULL;
 581
 582     // Look through poly-line visibility edges.
 583     selected = (i->visListSize <= j->visListSize) ? i : j;
 584     EdgeInfList& visList = selected->visList;
 585     EdgeInfList::const_iterator finish = visList.end();
 586     for (EdgeInfList::const_iterator edge = visList.begin(); edge != finish;
 587             ++edge)
 588     {
 589         if ((*edge)->isBetween(i, j))
 590         {
 591             return (*edge);
 592         }
 593     }
 594
 595     // Look through orthogonal visbility edges.
 596     selected = (i->orthogVisListSize <= j->orthogVisListSize) ? i : j;
 597     EdgeInfList& orthogVisList = selected->orthogVisList;
 598     finish = orthogVisList.end();
 599     for (EdgeInfList::const_iterator edge = orthogVisList.begin();
 600             edge != finish; ++edge)
 601     {
 602         if ((*edge)->isBetween(i, j))
 603         {
 604             return (*edge);
 605         }
 606     }
 607
 608     // Look through poly-line invisbility edges.
 609     selected = (i->invisListSize <= j->invisListSize) ? i : j;
 610     EdgeInfList& invisList = selected->invisList;
 611     finish = invisList.end();
 612     for (EdgeInfList::const_iterator edge = invisList.begin(); edge != finish;
 613             ++edge)
 614     {
 615         if ((*edge)->isBetween(i, j))
 616         {
 617             return (*edge);
 618         }
 619     }
 620
 621     return NULL;
 622 }
 623
 624
 625 //===========================================================================
 626
 627
 628 EdgeList::EdgeList(bool orthogonal)
 629     : _orthogonal(orthogonal),
 630       _firstEdge(NULL),
 631       _lastEdge(NULL),
 632       _count(0)
 633 {
 634 }
 635
 636
 637 EdgeList::~EdgeList()
 638 {
 639     clear();
 640 }
 641
 642
 643 void EdgeList::clear(void)
 644 {
 645     while (_firstEdge)
 646     {
 647         delete _firstEdge;
 648     }
 649     COLA_ASSERT(_count == 0);
 650     _lastEdge = NULL;
 651 }
 652
 653
 654 int EdgeList::size(void) const
 655 {
 656     return _count;
 657 }
 658
 659
 660 void EdgeList::addEdge(EdgeInf *edge)
 661 {
 662     COLA_ASSERT(!_orthogonal || edge->isOrthogonal());
 663
 664     if (_firstEdge == NULL)
 665     {
 666         COLA_ASSERT(_lastEdge == NULL);
 667
 668         _lastEdge = edge;
 669         _firstEdge = edge;
 670
 671         edge->lstPrev = NULL;
 672         edge->lstNext = NULL;
 673     }
 674     else
 675     {
 676         COLA_ASSERT(_lastEdge != NULL);
 677
 678         _lastEdge->lstNext = edge;
 679         edge->lstPrev = _lastEdge;
 680
 681         _lastEdge = edge;
 682
 683         edge->lstNext = NULL;
 684     }
 685     _count++;
 686 }
 687
 688
 689 void EdgeList::removeEdge(EdgeInf *edge)
 690 {
 691     if (edge->lstPrev)
 692     {
 693         edge->lstPrev->lstNext = edge->lstNext;
 694     }
 695     if (edge->lstNext)
 696     {
 697         edge->lstNext->lstPrev = edge->lstPrev;
 698     }
 699     if (edge == _lastEdge)
 700     {
 701         _lastEdge = edge->lstPrev;
 702         if (edge == _firstEdge)
 703         {
 704             _firstEdge = NULL;
 705         }
 706     }
 707     else if (edge == _firstEdge)
 708     {
 709         _firstEdge = edge->lstNext;
 710     }
 711
 712
 713     edge->lstPrev = NULL;
 714     edge->lstNext = NULL;
 715
 716     _count--;
 717 }
 718
 719
 720 EdgeInf *EdgeList::begin(void)
 721 {
 722     return _firstEdge;
 723 }
 724
 725
 726 EdgeInf *EdgeList::end(void)
 727 {
 728     return NULL;
 729 }
 730
 731
 732 }
 733
 734