src/libavoid/vertices.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-2005  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/geometry.h"
  24 #include "libavoid/graph.h"  // For alertConns
  25 #include "libavoid/debug.h"
  26
  27
  28
  29 namespace Avoid {
  30
  31
  32 ContainsMap contains;
  33
  34
  35 VertID::VertID()
  36 {
  37 }
  38
  39
  40 VertID::VertID(unsigned int id, bool s, int n)
  41     : objID(id)
  42     , isShape(s)
  43     , vn(n)
  44 {
  45 }
  46
  47
  48 VertID::VertID(const VertID& other)
  49     : objID(other.objID)
  50     , isShape(other.isShape)
  51     , vn(other.vn)
  52 {
  53 }
  54
  55
  56 VertID& VertID::operator= (const VertID& rhs)
  57 {
  58     // Gracefully handle self assignment
  59     //if (this == &rhs) return *this;
  60
  61     objID = rhs.objID;
  62     isShape = rhs.isShape;
  63     vn = rhs.vn;
  64
  65     return *this;
  66 }
  67
  68
  69 bool VertID::operator==(const VertID& rhs) const
  70 {
  71     if ((objID != rhs.objID) || (vn != rhs.vn))
  72     {
  73         return false;
  74     }
  75     assert(isShape == rhs.isShape);
  76     return true;
  77 }
  78
  79
  80 bool VertID::operator!=(const VertID& rhs) const
  81 {
  82     if ((objID != rhs.objID) || (vn != rhs.vn))
  83     {
  84         return true;
  85     }
  86     assert(isShape == rhs.isShape);
  87     return false;
  88 }
  89
  90
  91 bool VertID::operator<(const VertID& rhs) const
  92 {
  93     if ((objID < rhs.objID) ||
  94             ((objID == rhs.objID) && (vn < rhs.vn)))
  95     {
  96         return true;
  97     }
  98     return false;
  99 }
 100
 101
 102 VertID VertID::operator+(const int& rhs) const
 103 {
 104     return VertID(objID, isShape, vn + rhs);
 105 }
 106
 107
 108 VertID VertID::operator-(const int& rhs) const
 109 {
 110     return VertID(objID, isShape, vn - rhs);
 111 }
 112
 113
 114 VertID& VertID::operator++(int)
 115 {
 116     vn += 1;
 117     return *this;
 118 }
 119
 120
 121 void VertID::print(FILE *file) const
 122 {
 123     fprintf(file, "[%u,%d]", objID, vn);
 124 }
 125
 126
 127 void VertID::db_print(void) const
 128 {
 129     db_printf("[%u,%d]", objID, vn);
 130 }
 131
 132
 133 const int VertID::src = 1;
 134 const int VertID::tar = 2;
 135
 136
 137 VertInf::VertInf(const VertID& vid, const Point& vpoint)
 138     : id(vid)
 139     , point(vpoint)
 140     , lstPrev(NULL)
 141     , lstNext(NULL)
 142     , shPrev(NULL)
 143     , shNext(NULL)
 144     , visListSize(0)
 145     , invisListSize(0)
 146     , pathNext(NULL)
 147     , pathDist(0)
 148 {
 149 }
 150
 151
 152 void VertInf::Reset(const Point& vpoint)
 153 {
 154     point = vpoint;
 155 }
 156
 157
 158 void VertInf::removeFromGraph(const bool isConnVert)
 159 {
 160     if (isConnVert)
 161     {
 162         assert(!(id.isShape));
 163     }
 164
 165     VertInf *tmp = this;
 166
 167     // For each vertex.
 168     EdgeInfList& visList = tmp->visList;
 169     EdgeInfList::iterator finish = visList.end();
 170     EdgeInfList::iterator edge;
 171     while ((edge = visList.begin()) != finish)
 172     {
 173         // Remove each visibility edge
 174         (*edge)->alertConns();
 175         delete (*edge);
 176     }
 177
 178     EdgeInfList& invisList = tmp->invisList;
 179     finish = invisList.end();
 180     while ((edge = invisList.begin()) != finish)
 181     {
 182         // Remove each invisibility edge
 183         delete (*edge);
 184     }
 185 }
 186
 187
 188 bool directVis(VertInf *src, VertInf *dst)
 189 {
 190     ShapeSet ss = ShapeSet();
 191
 192     Point& p = src->point;
 193     Point& q = dst->point;
 194
 195     VertID& pID = src->id;
 196     VertID& qID = dst->id;
 197
 198     if (!(pID.isShape))
 199     {
 200         ss.insert(contains[pID].begin(), contains[pID].end());
 201     }
 202     if (!(qID.isShape))
 203     {
 204         ss.insert(contains[qID].begin(), contains[qID].end());
 205     }
 206
 207     // The "beginning" should be the first shape vertex, rather
 208     // than an endpoint, which are also stored in "vertices".
 209     VertInf *endVert = vertices.end();
 210     for (VertInf *k = vertices.shapesBegin(); k != endVert; k = k->lstNext)
 211     {
 212         if ((ss.find(k->id.objID) == ss.end()))
 213         {
 214             if (segmentIntersect(p, q, k->point, k->shNext->point))
 215             {
 216                 return false;
 217             }
 218         }
 219     }
 220     return true;
 221 }
 222
 223
 224 VertInfList::VertInfList()
 225     : _firstShapeVert(NULL)
 226     , _firstConnVert(NULL)
 227     , _lastShapeVert(NULL)
 228     , _lastConnVert(NULL)
 229     , _shapeVertices(0)
 230     , _connVertices(0)
 231 {
 232 }
 233
 234
 235 #define checkVertInfListConditions() \
 236         do { \
 237             assert((!_firstConnVert && (_connVertices == 0)) || \
 238                     ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \
 239             assert((!_firstShapeVert && (_shapeVertices == 0)) || \
 240                     ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \
 241             assert(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
 242             assert(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
 243             assert((!_firstConnVert && !_lastConnVert) || \
 244                     (_firstConnVert &&  _lastConnVert) ); \
 245             assert((!_firstShapeVert && !_lastShapeVert) || \
 246                     (_firstShapeVert &&  _lastShapeVert) ); \
 247             assert(!_firstShapeVert || _firstShapeVert->id.isShape); \
 248             assert(!_lastShapeVert || _lastShapeVert->id.isShape); \
 249             assert(!_firstConnVert || !(_firstConnVert->id.isShape)); \
 250             assert(!_lastConnVert || !(_lastConnVert->id.isShape)); \
 251         } while(0)
 252
 253
 254 void VertInfList::addVertex(VertInf *vert)
 255 {
 256     checkVertInfListConditions();
 257     assert(vert->lstPrev == NULL);
 258     assert(vert->lstNext == NULL);
 259
 260     if (!(vert->id.isShape))
 261     {
 262         // A Connector vertex
 263         if (_firstConnVert)
 264         {
 265             // Join with previous front
 266             vert->lstNext = _firstConnVert;
 267             _firstConnVert->lstPrev = vert;
 268
 269             // Make front
 270             _firstConnVert = vert;
 271         }
 272         else
 273         {
 274             // Make front and back
 275             _firstConnVert = vert;
 276             _lastConnVert = vert;
 277
 278             // Link to front of shapes list
 279             vert->lstNext = _firstShapeVert;
 280         }
 281         _connVertices++;
 282     }
 283     else // if (vert->id.shape > 0)
 284     {
 285         // A Shape vertex
 286         if (_lastShapeVert)
 287         {
 288             // Join with previous back
 289             vert->lstPrev = _lastShapeVert;
 290             _lastShapeVert->lstNext = vert;
 291
 292             // Make back
 293             _lastShapeVert = vert;
 294         }
 295         else
 296         {
 297             // Make first and last
 298             _firstShapeVert = vert;
 299             _lastShapeVert = vert;
 300
 301             // Join with conns list
 302             if (_lastConnVert)
 303             {
 304                 assert (_lastConnVert->lstNext == NULL);
 305
 306                 _lastConnVert->lstNext = vert;
 307             }
 308         }
 309         _shapeVertices++;
 310     }
 311     checkVertInfListConditions();
 312 }
 313
 314
 315 void VertInfList::removeVertex(VertInf *vert)
 316 {
 317     // Conditions for correct data structure
 318     checkVertInfListConditions();
 319
 320     if (!(vert->id.isShape))
 321     {
 322         // A Connector vertex
 323         if (vert == _firstConnVert)
 324         {
 325
 326             if (vert == _lastConnVert)
 327             {
 328                 _firstConnVert = NULL;
 329                 _lastConnVert = NULL;
 330             }
 331             else
 332             {
 333                 // Set new first
 334                 _firstConnVert = _firstConnVert->lstNext;
 335
 336                 if (_firstConnVert)
 337                 {
 338                     // Set previous
 339                     _firstConnVert->lstPrev = NULL;
 340                 }
 341             }
 342         }
 343         else if (vert == _lastConnVert)
 344         {
 345             // Set new last
 346             _lastConnVert = _lastConnVert->lstPrev;
 347
 348             // Make last point to shapes list
 349             _lastConnVert->lstNext = _firstShapeVert;
 350         }
 351         else
 352         {
 353             vert->lstNext->lstPrev = vert->lstPrev;
 354             vert->lstPrev->lstNext = vert->lstNext;
 355         }
 356         _connVertices--;
 357     }
 358     else // if (vert->id.shape > 0)
 359     {
 360         // A Shape vertex
 361         if (vert == _lastShapeVert)
 362         {
 363             // Set new last
 364             _lastShapeVert = _lastShapeVert->lstPrev;
 365
 366             if (vert == _firstShapeVert)
 367             {
 368                 _firstShapeVert = NULL;
 369                 if (_lastConnVert)
 370                 {
 371                     _lastConnVert->lstNext = NULL;
 372                 }
 373             }
 374
 375             if (_lastShapeVert)
 376             {
 377                 _lastShapeVert->lstNext = NULL;
 378             }
 379         }
 380         else if (vert == _firstShapeVert)
 381         {
 382             // Set new first
 383             _firstShapeVert = _firstShapeVert->lstNext;
 384
 385             // Correct the last conn vertex
 386             if (_lastConnVert)
 387             {
 388                 _lastConnVert->lstNext = _firstShapeVert;
 389             }
 390
 391             if (_firstShapeVert)
 392             {
 393                 _firstShapeVert->lstPrev = NULL;
 394             }
 395         }
 396         else
 397         {
 398             vert->lstNext->lstPrev = vert->lstPrev;
 399             vert->lstPrev->lstNext = vert->lstNext;
 400         }
 401         _shapeVertices--;
 402     }
 403     vert->lstPrev = NULL;
 404     vert->lstNext = NULL;
 405
 406     checkVertInfListConditions();
 407 }
 408
 409
 410 VertInf *VertInfList::shapesBegin(void)
 411 {
 412     return _firstShapeVert;
 413 }
 414
 415
 416 VertInf *VertInfList::connsBegin(void)
 417 {
 418     if (_firstConnVert)
 419     {
 420         return _firstConnVert;
 421     }
 422     // No connector vertices
 423     return _firstShapeVert;
 424 }
 425
 426
 427 VertInf *VertInfList::end(void)
 428 {
 429     return NULL;
 430 }
 431
 432
 433 VertInfList vertices;
 434
 435
 436 }
 437
 438