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  * 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/debug.h"
  24 #include "libavoid/graph.h"
  25 #include "libavoid/connector.h"
  26 #include "libavoid/geometry.h"
  27 #include "libavoid/polyutil.h"
  28 #include "libavoid/timer.h"
  29 #include "libavoid/vertices.h"
  30 #include "libavoid/router.h"
  31
  32 #include <math.h>
  33
  34 using std::pair;
  35
  36 namespace Avoid {
  37
  38
  39 EdgeInf::EdgeInf(VertInf *v1, VertInf *v2)
  40     : lstPrev(NULL)
  41     , lstNext(NULL)
  42     , _blocker(0)
  43     , _router(NULL)
  44     , _added(false)
  45     , _visible(false)
  46     , _v1(v1)
  47     , _v2(v2)
  48     , _dist(-1)
  49 {
  50     // Not passed NULL values.
  51     assert(v1 && v2);
  52
  53     // We are in the same instance
  54     assert(_v1->_router == _v2->_router);
  55     _router = _v1->_router;
  56
  57     _conns.clear();
  58 }
  59
  60
  61 EdgeInf::~EdgeInf()
  62 {
  63     if (_added)
  64     {
  65         makeInactive();
  66     }
  67 }
  68
  69
  70 void EdgeInf::makeActive(void)
  71 {
  72     assert(_added == false);
  73
  74     if (_visible)
  75     {
  76         _router->visGraph.addEdge(this);
  77         _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
  78         _v1->visListSize++;
  79         _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
  80         _v2->visListSize++;
  81     }
  82     else // if (invisible)
  83     {
  84         _router->invisGraph.addEdge(this);
  85         _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
  86         _v1->invisListSize++;
  87         _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
  88         _v2->invisListSize++;
  89     }
  90     _added = true;
  91 }
  92
  93
  94 void EdgeInf::makeInactive(void)
  95 {
  96     assert(_added == true);
  97
  98     if (_visible)
  99     {
 100         _router->visGraph.removeEdge(this);
 101         _v1->visList.erase(_pos1);
 102         _v1->visListSize--;
 103         _v2->visList.erase(_pos2);
 104         _v2->visListSize--;
 105     }
 106     else // if (invisible)
 107     {
 108         _router->invisGraph.removeEdge(this);
 109         _v1->invisList.erase(_pos1);
 110         _v1->invisListSize--;
 111         _v2->invisList.erase(_pos2);
 112         _v2->invisListSize--;
 113     }
 114     _blocker = 0;
 115     _conns.clear();
 116     _added = false;
 117 }
 118
 119
 120 void EdgeInf::setDist(double dist)
 121 {
 122     //assert(dist != 0);
 123
 124     if (_added && !_visible)
 125     {
 126         makeInactive();
 127     }
 128     if (!_added)
 129     {
 130         _visible = true;
 131         makeActive();
 132     }
 133     _dist = dist;
 134     _blocker = 0;
 135 }
 136
 137
 138 void EdgeInf::alertConns(void)
 139 {
 140     FlagList::iterator finish = _conns.end();
 141     for (FlagList::iterator i = _conns.begin(); i != finish; ++i)
 142     {
 143         *(*i) = true;
 144     }
 145     _conns.clear();
 146 }
 147
 148
 149 void EdgeInf::addConn(bool *flag)
 150 {
 151     _conns.push_back(flag);
 152 }
 153
 154
 155 void EdgeInf::addCycleBlocker(void)
 156 {
 157     // Needs to be in invisibility graph.
 158     addBlocker(-1);
 159 }
 160
 161
 162 void EdgeInf::addBlocker(int b)
 163 {
 164     assert(_router->InvisibilityGrph);
 165
 166     if (_added && _visible)
 167     {
 168         makeInactive();
 169     }
 170     if (!_added)
 171     {
 172         _visible = false;
 173         makeActive();
 174     }
 175     _dist = 0;
 176     _blocker = b;
 177 }
 178
 179
 180 pair<VertID, VertID> EdgeInf::ids(void)
 181 {
 182     return std::make_pair(_v1->id, _v2->id);
 183 }
 184
 185
 186 pair<Point, Point> EdgeInf::points(void)
 187 {
 188     return std::make_pair(_v1->point, _v2->point);
 189 }
 190
 191
 192 void EdgeInf::db_print(void)
 193 {
 194     db_printf("Edge(");
 195     _v1->id.db_print();
 196     db_printf(",");
 197     _v2->id.db_print();
 198     db_printf(")\n");
 199 }
 200
 201
 202 void EdgeInf::checkVis(void)
 203 {
 204     if (_added && !_visible)
 205     {
 206         db_printf("\tChecking visibility for existing invisibility edge..."
 207                 "\n\t\t");
 208         db_print();
 209     }
 210     else if (_added && _visible)
 211     {
 212         db_printf("\tChecking visibility for existing visibility edge..."
 213                 "\n\t\t");
 214         db_print();
 215     }
 216
 217     int blocker = 0;
 218     bool cone1 = true;
 219     bool cone2 = true;
 220
 221     VertInf *i = _v1;
 222     VertInf *j = _v2;
 223     const VertID& iID = i->id;
 224     const VertID& jID = j->id;
 225     const Point& iPoint = i->point;
 226     const Point& jPoint = j->point;
 227
 228     _router->st_checked_edges++;
 229
 230     if (iID.isShape)
 231     {
 232         cone1 = inValidRegion(_router->IgnoreRegions, i->shPrev->point,
 233                 iPoint, i->shNext->point, jPoint);
 234     }
 235     else
 236     {
 237         ShapeSet& ss = _router->contains[iID];
 238
 239         if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
 240         {
 241             db_printf("1: Edge of bounding shape\n");
 242             // Don't even check this edge, it should be zero,
 243             // since a point in a shape can't see it's corners
 244             cone1 = false;
 245         }
 246     }
 247
 248     if (cone1)
 249     {
 250         // If outside the first cone, don't even bother checking.
 251         if (jID.isShape)
 252         {
 253             cone2 = inValidRegion(_router->IgnoreRegions, j->shPrev->point,
 254                     jPoint, j->shNext->point, iPoint);
 255         }
 256         else
 257         {
 258             ShapeSet& ss = _router->contains[jID];
 259
 260             if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
 261             {
 262                 db_printf("2: Edge of bounding shape\n");
 263                 // Don't even check this edge, it should be zero,
 264                 // since a point in a shape can't see it's corners
 265                 cone2 = false;
 266             }
 267         }
 268     }
 269
 270     if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
 271     {
 272
 273         // if i and j see each other, add edge
 274         db_printf("\tSetting visibility edge... \n\t\t");
 275         db_print();
 276
 277         double d = dist(iPoint, jPoint);
 278
 279         setDist(d);
 280
 281     }
 282     else if (_router->InvisibilityGrph)
 283     {
 284 #if 0
 285         db_printf("%d, %d, %d\n", cone1, cone2, blocker);
 286         db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x,
 287                 (int) iInfo.point.y, (int) jInfo.point.x,
 288                 (int) jInfo.point.y);
 289 #endif
 290
 291         // if i and j can't see each other, add blank edge
 292         db_printf("\tSetting invisibility edge... \n\t\t");
 293         db_print();
 294         addBlocker(blocker);
 295     }
 296 }
 297
 298
 299 int EdgeInf::firstBlocker(void)
 300 {
 301     ShapeSet ss = ShapeSet();
 302
 303     Point& pti = _v1->point;
 304     Point& ptj = _v2->point;
 305     VertID& iID = _v1->id;
 306     VertID& jID = _v2->id;
 307
 308     ContainsMap &contains = _router->contains;
 309     if (!(iID.isShape))
 310     {
 311         ss.insert(contains[iID].begin(), contains[iID].end());
 312     }
 313     if (!(jID.isShape))
 314     {
 315         ss.insert(contains[jID].begin(), contains[jID].end());
 316     }
 317
 318     VertInf *last = _router->vertices.end();
 319     for (VertInf *k = _router->vertices.shapesBegin(); k != last; )
 320     {
 321         VertID kID = k->id;
 322         if ((ss.find(kID.objID) != ss.end()))
 323         {
 324             unsigned int shapeID = kID.objID;
 325             db_printf("Endpoint is inside shape %u so ignore shape edges.\n",
 326                     kID.objID);
 327             // One of the endpoints is inside this shape so ignore it.
 328             while ((k != last) && (k->id.objID == shapeID))
 329             {
 330                 // And skip the other vertices from this shape.
 331                 k = k->lstNext;
 332             }
 333             continue;
 334         }
 335         Point& kPoint = k->point;
 336         Point& kPrevPoint = k->shPrev->point;
 337
 338         if (segmentIntersect(pti, ptj, kPrevPoint, kPoint))
 339         {
 340             ss.clear();
 341             return kID.objID;
 342         }
 343         k = k->lstNext;
 344     }
 345     ss.clear();
 346     return 0;
 347 }
 348
 349
 350 bool EdgeInf::isBetween(VertInf *i, VertInf *j)
 351 {
 352     if ( ((i == _v1) && (j == _v2)) ||
 353          ((i == _v2) && (j == _v1)) )
 354     {
 355         return true;
 356     }
 357     return false;
 358 }
 359
 360
 361 VertInf *EdgeInf::otherVert(VertInf *vert)
 362 {
 363     assert((vert == _v1) || (vert == _v2));
 364
 365     if (vert == _v1)
 366     {
 367         return _v2;
 368     }
 369     return _v1;
 370 }
 371
 372
 373 EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
 374 {
 375     Router *router = i->_router;
 376     EdgeInf *edge = NULL;
 377
 378     if (knownNew)
 379     {
 380         assert(existingEdge(i, j) == NULL);
 381         edge = new EdgeInf(i, j);
 382     }
 383     else
 384     {
 385         edge = existingEdge(i, j);
 386         if (edge == NULL)
 387         {
 388             edge = new EdgeInf(i, j);
 389         }
 390     }
 391     edge->checkVis();
 392     if (!(edge->_added) && !(router->InvisibilityGrph))
 393     {
 394         delete edge;
 395         edge = NULL;
 396     }
 397
 398     return edge;
 399 }
 400
 401
 402 EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
 403 {
 404     VertInf *selected = NULL;
 405
 406     if (i->visListSize <= j->visListSize)
 407     {
 408         selected = i;
 409     }
 410     else
 411     {
 412         selected = j;
 413     }
 414
 415     EdgeInfList& visList = selected->visList;
 416     EdgeInfList::iterator finish = visList.end();
 417     for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
 418             ++edge)
 419     {
 420         if ((*edge)->isBetween(i, j))
 421         {
 422             return (*edge);
 423         }
 424     }
 425
 426     if (i->invisListSize <= j->invisListSize)
 427     {
 428         selected = i;
 429     }
 430     else
 431     {
 432         selected = j;
 433     }
 434
 435     EdgeInfList& invisList = selected->invisList;
 436     finish = invisList.end();
 437     for (EdgeInfList::iterator edge = invisList.begin(); edge != finish;
 438             ++edge)
 439     {
 440         if ((*edge)->isBetween(i, j))
 441         {
 442             return (*edge);
 443         }
 444     }
 445
 446     return NULL;
 447 }
 448
 449
 450 //===========================================================================
 451
 452
 453 EdgeList::EdgeList()
 454     : _firstEdge(NULL)
 455     , _lastEdge(NULL)
 456     , _count(0)
 457 {
 458 }
 459
 460
 461 void EdgeList::addEdge(EdgeInf *edge)
 462 {
 463     if (_firstEdge == NULL)
 464     {
 465         assert(_lastEdge == NULL);
 466
 467         _lastEdge = edge;
 468         _firstEdge = edge;
 469
 470         edge->lstPrev = NULL;
 471         edge->lstNext = NULL;
 472     }
 473     else
 474     {
 475         assert(_lastEdge != NULL);
 476
 477         _lastEdge->lstNext = edge;
 478         edge->lstPrev = _lastEdge;
 479
 480         _lastEdge = edge;
 481
 482         edge->lstNext = NULL;
 483     }
 484     _count++;
 485 }
 486
 487
 488 void EdgeList::removeEdge(EdgeInf *edge)
 489 {
 490     if (edge->lstPrev)
 491     {
 492         edge->lstPrev->lstNext = edge->lstNext;
 493     }
 494     if (edge->lstNext)
 495     {
 496         edge->lstNext->lstPrev = edge->lstPrev;
 497     }
 498     if (edge == _lastEdge)
 499     {
 500         _lastEdge = edge->lstPrev;
 501         if (edge == _firstEdge)
 502         {
 503             _firstEdge = NULL;
 504         }
 505     }
 506     else if (edge == _firstEdge)
 507     {
 508         _firstEdge = edge->lstNext;
 509     }
 510
 511
 512     edge->lstPrev = NULL;
 513     edge->lstNext = NULL;
 514
 515     _count--;
 516 }
 517
 518
 519 EdgeInf *EdgeList::begin(void)
 520 {
 521     return _firstEdge;
 522 }
 523
 524
 525 EdgeInf *EdgeList::end(void)
 526 {
 527     return NULL;
 528 }
 529
 530
 531 }
 532
 533