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