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