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
23 */
24
25
26 #include <iostream>
27 #include <cstdlib>
28
29 #include "libavoid/vertices.h"
30 #include "libavoid/geometry.h"
31 #include "libavoid/graph.h" // For alertConns
32 #include "libavoid/debug.h"
33 #include "libavoid/router.h"
34 #include "libavoid/assertions.h"
35 #include "libavoid/connend.h"
36
37 using std::ostream;
38
39
40 namespace Avoid {
41
42
VertID()43 VertID::VertID()
44 {
45 }
46
47
VertID(unsigned int id,unsigned short n,VertIDProps p)48 VertID::VertID(unsigned int id, unsigned short n, VertIDProps p)
49 : objID(id),
50 vn(n),
51 props(p)
52 {
53 }
54
55
VertID(const VertID & other)56 VertID::VertID(const VertID& other)
57 : objID(other.objID),
58 vn(other.vn),
59 props(other.props)
60 {
61 }
62
63
operator =(const VertID & rhs)64 VertID& VertID::operator= (const VertID& rhs)
65 {
66 // Gracefully handle self assignment
67 //if (this == &rhs) return *this;
68
69 objID = rhs.objID;
70 vn = rhs.vn;
71 props = rhs.props;
72
73 return *this;
74 }
75
76
operator ==(const VertID & rhs) const77 bool VertID::operator==(const VertID& rhs) const
78 {
79 if ((objID != rhs.objID) || (vn != rhs.vn))
80 {
81 return false;
82 }
83 return true;
84 }
85
86
operator !=(const VertID & rhs) const87 bool VertID::operator!=(const VertID& rhs) const
88 {
89 if ((objID != rhs.objID) || (vn != rhs.vn))
90 {
91 return true;
92 }
93 return false;
94 }
95
96
operator <(const VertID & rhs) const97 bool VertID::operator<(const VertID& rhs) const
98 {
99 if ((objID < rhs.objID) ||
100 ((objID == rhs.objID) && (vn < rhs.vn)))
101 {
102 return true;
103 }
104 return false;
105 }
106
107
operator +(const int & rhs) const108 VertID VertID::operator+(const int& rhs) const
109 {
110 return VertID(objID, vn + rhs, props);
111 }
112
113
operator -(const int & rhs) const114 VertID VertID::operator-(const int& rhs) const
115 {
116 return VertID(objID, vn - rhs, props);
117 }
118
119
operator ++(int)120 VertID& VertID::operator++(int)
121 {
122 vn += 1;
123 return *this;
124 }
125
126
print(FILE * file) const127 void VertID::print(FILE *file) const
128 {
129 fprintf(file, "[%u,%d, p=%u]", objID, vn, (unsigned int) props);
130 }
131
db_print(void) const132 void VertID::db_print(void) const
133 {
134 db_printf("[%u,%d, p=%u]", objID, vn, (unsigned int) props);
135 }
136
137
138 const unsigned short VertID::src = 1;
139 const unsigned short VertID::tar = 2;
140
141 // Property flags:
142 const unsigned short VertID::PROP_ConnPoint = 1;
143 const unsigned short VertID::PROP_OrthShapeEdge = 2;
144 const unsigned short VertID::PROP_ConnectionPin = 4;
145 const unsigned short VertID::PROP_ConnCheckpoint = 8;
146 const unsigned short VertID::PROP_DummyPinHelper = 16;
147
148
operator <<(ostream & os,const VertID & vID)149 ostream& operator<<(ostream& os, const VertID& vID)
150 {
151 return os << '[' << vID.objID << ',' << vID.vn << ']';
152 }
153
154
155
VertInf(Router * router,const VertID & vid,const Point & vpoint,const bool addToRouter)156 VertInf::VertInf(Router *router, const VertID& vid, const Point& vpoint,
157 const bool addToRouter)
158 : _router(router),
159 id(vid),
160 point(vpoint),
161 lstPrev(nullptr),
162 lstNext(nullptr),
163 shPrev(nullptr),
164 shNext(nullptr),
165 visListSize(0),
166 orthogVisListSize(0),
167 invisListSize(0),
168 pathNext(nullptr),
169 m_orthogonalPartner(nullptr),
170 m_treeRoot(nullptr),
171 visDirections(ConnDirNone),
172 orthogVisPropFlags(0)
173 {
174 point.id = vid.objID;
175 point.vn = vid.vn;
176
177 if (addToRouter)
178 {
179 _router->vertices.addVertex(this);
180 }
181 }
182
183
~VertInf()184 VertInf::~VertInf()
185 {
186 COLA_ASSERT(orphaned());
187 }
188
189
hasNeighbour(VertInf * target,bool orthogonal) const190 EdgeInf *VertInf::hasNeighbour(VertInf *target, bool orthogonal) const
191 {
192 const EdgeInfList& visEdgeList = (orthogonal) ? orthogVisList : visList;
193 EdgeInfList::const_iterator finish = visEdgeList.end();
194 for (EdgeInfList::const_iterator edge = visEdgeList.begin(); edge != finish; ++edge)
195 {
196 if ((*edge)->otherVert(this) == target)
197 {
198 return *edge;
199 }
200 }
201 return nullptr;
202 }
203
Reset(const VertID & vid,const Point & vpoint)204 void VertInf::Reset(const VertID& vid, const Point& vpoint)
205 {
206 id = vid;
207 point = vpoint;
208 point.id = id.objID;
209 point.vn = id.vn;
210 }
211
212
Reset(const Point & vpoint)213 void VertInf::Reset(const Point& vpoint)
214 {
215 point = vpoint;
216 point.id = id.objID;
217 point.vn = id.vn;
218 }
219
220
221 // Returns true if this vertex is not involved in any (in)visibility graphs.
orphaned(void)222 bool VertInf::orphaned(void)
223 {
224 return (visList.empty() && invisList.empty() && orthogVisList.empty());
225 }
226
227
removeFromGraph(const bool isConnVert)228 void VertInf::removeFromGraph(const bool isConnVert)
229 {
230 if (isConnVert)
231 {
232 COLA_ASSERT(id.isConnPt());
233 }
234
235 // For each vertex.
236 EdgeInfList::const_iterator finish = visList.end();
237 EdgeInfList::const_iterator edge;
238 while ((edge = visList.begin()) != finish)
239 {
240 // Remove each visibility edge
241 (*edge)->alertConns();
242 delete (*edge);
243 }
244
245 finish = orthogVisList.end();
246 while ((edge = orthogVisList.begin()) != finish)
247 {
248 // Remove each orthogonal visibility edge.
249 (*edge)->alertConns();
250 delete (*edge);
251 }
252
253 finish = invisList.end();
254 while ((edge = invisList.begin()) != finish)
255 {
256 // Remove each invisibility edge
257 delete (*edge);
258 }
259 }
260
261
orphan(void)262 void VertInf::orphan(void)
263 {
264 // For each vertex.
265 EdgeInfList::const_iterator finish = visList.end();
266 EdgeInfList::const_iterator edge;
267 while ((edge = visList.begin()) != finish)
268 {
269 // Remove each visibility edge
270 (*edge)->makeInactive();
271 }
272
273 finish = orthogVisList.end();
274 while ((edge = orthogVisList.begin()) != finish)
275 {
276 // Remove each orthogonal visibility edge.
277 (*edge)->makeInactive();
278 }
279
280 finish = invisList.end();
281 while ((edge = invisList.begin()) != finish)
282 {
283 // Remove each invisibility edge
284 (*edge)->makeInactive();
285 }
286 }
287
288 // Returns the direction of this vertex relative to the other specified vertex.
289 //
directionFrom(const VertInf * other) const290 ConnDirFlags VertInf::directionFrom(const VertInf *other) const
291 {
292 double epsilon = 0.000001;
293 Point thisPoint = point;
294 Point otherPoint = other->point;
295 Point diff = thisPoint - otherPoint;
296
297 ConnDirFlags directions = ConnDirNone;
298 if (diff.y > epsilon)
299 {
300 directions |= ConnDirUp;
301 }
302 if (diff.y < -epsilon)
303 {
304 directions |= ConnDirDown;
305 }
306 if (diff.x > epsilon)
307 {
308 directions |= ConnDirRight;
309 }
310 if (diff.x < -epsilon)
311 {
312 directions |= ConnDirLeft;
313 }
314 return directions;
315 }
316
317 // Given a set of directions, mark visibility edges in all other directions
318 // as being invalid so they get ignored during the search.
319 //
setVisibleDirections(const ConnDirFlags directions)320 void VertInf::setVisibleDirections(const ConnDirFlags directions)
321 {
322 for (EdgeInfList::const_iterator edge = visList.begin();
323 edge != visList.end(); ++edge)
324 {
325 if (directions == ConnDirAll)
326 {
327 (*edge)->setDisabled(false);
328 }
329 else
330 {
331 VertInf *otherVert = (*edge)->otherVert(this);
332 ConnDirFlags direction = otherVert->directionFrom(this);
333 bool visible = (direction & directions);
334 (*edge)->setDisabled(!visible);
335 }
336 }
337
338 for (EdgeInfList::const_iterator edge = orthogVisList.begin();
339 edge != orthogVisList.end(); ++edge)
340 {
341 if (directions == ConnDirAll)
342 {
343 (*edge)->setDisabled(false);
344 }
345 else
346 {
347 VertInf *otherVert = (*edge)->otherVert(this);
348 ConnDirFlags direction = otherVert->directionFrom(this);
349 bool visible = (direction & directions);
350 (*edge)->setDisabled(!visible);
351 }
352 }
353 }
354
355 // Number of points in path from end back to start, or zero if no path exists.
356 //
pathLeadsBackTo(const VertInf * start) const357 unsigned int VertInf::pathLeadsBackTo(const VertInf *start) const
358 {
359 unsigned int pathlen = 1;
360 for (const VertInf *i = this; i != start; i = i->pathNext)
361 {
362 if ((pathlen > 1) && (i == this))
363 {
364 // We have a circular path, so path not found.
365 return 0;
366 }
367
368 pathlen++;
369 if (i == nullptr)
370 {
371 // Path not found.
372 return 0;
373 }
374
375 // Check we don't have an apparent infinite connector path.
376 COLA_ASSERT(pathlen < 20000);
377 }
378 return pathlen;
379 }
380
makeTreeRootPointer(VertInf * root)381 VertInf **VertInf::makeTreeRootPointer(VertInf *root)
382 {
383 m_treeRoot = (VertInf **) malloc(sizeof(VertInf *));
384 *m_treeRoot = root;
385 return m_treeRoot;
386 }
387
treeRoot(void) const388 VertInf *VertInf::treeRoot(void) const
389 {
390 return (m_treeRoot) ? *m_treeRoot : nullptr;
391 }
392
treeRootPointer(void) const393 VertInf **VertInf::treeRootPointer(void) const
394 {
395 return m_treeRoot;
396 }
397
clearTreeRootPointer(void)398 void VertInf::clearTreeRootPointer(void)
399 {
400 m_treeRoot = nullptr;
401 }
402
setTreeRootPointer(VertInf ** pointer)403 void VertInf::setTreeRootPointer(VertInf **pointer)
404 {
405 m_treeRoot = pointer;
406 }
407
setSPTFRoot(VertInf * root)408 void VertInf::setSPTFRoot(VertInf *root)
409 {
410 // Use the m_treeRoot instance var, but as just a normal VertInf pointer.
411 m_treeRoot = (VertInf **) root;
412 }
413
414
sptfRoot(void) const415 VertInf *VertInf::sptfRoot(void) const
416 {
417 // Use the m_treeRoot instance var, but as just a normal VertInf pointer.
418 return (VertInf *) m_treeRoot;
419 }
420
421
directVis(VertInf * src,VertInf * dst)422 bool directVis(VertInf *src, VertInf *dst)
423 {
424 ShapeSet ss = ShapeSet();
425
426 Point& p = src->point;
427 Point& q = dst->point;
428
429 VertID& pID = src->id;
430 VertID& qID = dst->id;
431
432 // We better be part of the same instance of libavoid.
433 Router *router = src->_router;
434 COLA_ASSERT(router == dst->_router);
435
436 ContainsMap& contains = router->contains;
437 if (pID.isConnPt())
438 {
439 ss.insert(contains[pID].begin(), contains[pID].end());
440 }
441 if (qID.isConnPt())
442 {
443 ss.insert(contains[qID].begin(), contains[qID].end());
444 }
445
446 // The "beginning" should be the first shape vertex, rather
447 // than an endpoint, which are also stored in "vertices".
448 VertInf *endVert = router->vertices.end();
449 for (VertInf *k = router->vertices.shapesBegin(); k != endVert;
450 k = k->lstNext)
451 {
452 if ((ss.find(k->id.objID) == ss.end()))
453 {
454 if (segmentIntersect(p, q, k->point, k->shNext->point))
455 {
456 return false;
457 }
458 }
459 }
460 return true;
461 }
462
463
VertInfList()464 VertInfList::VertInfList()
465 : _firstShapeVert(nullptr),
466 _firstConnVert(nullptr),
467 _lastShapeVert(nullptr),
468 _lastConnVert(nullptr),
469 _shapeVertices(0),
470 _connVertices(0)
471 {
472 }
473
474
475 #define checkVertInfListConditions() \
476 do { \
477 COLA_ASSERT((!_firstConnVert && (_connVertices == 0)) || \
478 ((_firstConnVert->lstPrev == nullptr) && (_connVertices > 0))); \
479 COLA_ASSERT((!_firstShapeVert && (_shapeVertices == 0)) || \
480 ((_firstShapeVert->lstPrev == nullptr) && (_shapeVertices > 0))); \
481 COLA_ASSERT(!_lastShapeVert || (_lastShapeVert->lstNext == nullptr)); \
482 COLA_ASSERT(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
483 COLA_ASSERT((!_firstConnVert && !_lastConnVert) || \
484 (_firstConnVert && _lastConnVert) ); \
485 COLA_ASSERT((!_firstShapeVert && !_lastShapeVert) || \
486 (_firstShapeVert && _lastShapeVert) ); \
487 COLA_ASSERT(!_firstShapeVert || !(_firstShapeVert->id.isConnPt())); \
488 COLA_ASSERT(!_lastShapeVert || !(_lastShapeVert->id.isConnPt())); \
489 COLA_ASSERT(!_firstConnVert || _firstConnVert->id.isConnPt()); \
490 COLA_ASSERT(!_lastConnVert || _lastConnVert->id.isConnPt()); \
491 } while(0)
492
493
addVertex(VertInf * vert)494 void VertInfList::addVertex(VertInf *vert)
495 {
496 checkVertInfListConditions();
497 COLA_ASSERT(vert->lstPrev == nullptr);
498 COLA_ASSERT(vert->lstNext == nullptr);
499
500 if (vert->id.isConnPt())
501 {
502 // A Connector vertex
503 if (_firstConnVert)
504 {
505 // Join with previous front
506 vert->lstNext = _firstConnVert;
507 _firstConnVert->lstPrev = vert;
508
509 // Make front
510 _firstConnVert = vert;
511 }
512 else
513 {
514 // Make front and back
515 _firstConnVert = vert;
516 _lastConnVert = vert;
517
518 // Link to front of shapes list
519 vert->lstNext = _firstShapeVert;
520 }
521 _connVertices++;
522 }
523 else // if (vert->id.shape > 0)
524 {
525 // A Shape vertex
526 if (_lastShapeVert)
527 {
528 // Join with previous back
529 vert->lstPrev = _lastShapeVert;
530 _lastShapeVert->lstNext = vert;
531
532 // Make back
533 _lastShapeVert = vert;
534 }
535 else
536 {
537 // Make first and last
538 _firstShapeVert = vert;
539 _lastShapeVert = vert;
540
541 // Join with conns list
542 if (_lastConnVert)
543 {
544 COLA_ASSERT(_lastConnVert->lstNext == nullptr);
545
546 _lastConnVert->lstNext = vert;
547 }
548 }
549 _shapeVertices++;
550 }
551 checkVertInfListConditions();
552 }
553
554
555 // Removes a vertex from the list and returns a pointer to the vertex
556 // following the removed one.
removeVertex(VertInf * vert)557 VertInf *VertInfList::removeVertex(VertInf *vert)
558 {
559 if (vert == nullptr)
560 {
561 return nullptr;
562 }
563 // Conditions for correct data structure
564 checkVertInfListConditions();
565
566 VertInf *following = vert->lstNext;
567
568 if (vert->id.isConnPt())
569 {
570 // A Connector vertex
571 if (vert == _firstConnVert)
572 {
573
574 if (vert == _lastConnVert)
575 {
576 _firstConnVert = nullptr;
577 _lastConnVert = nullptr;
578 }
579 else
580 {
581 // Set new first
582 _firstConnVert = _firstConnVert->lstNext;
583
584 if (_firstConnVert)
585 {
586 // Set previous
587 _firstConnVert->lstPrev = nullptr;
588 }
589 }
590 }
591 else if (vert == _lastConnVert)
592 {
593 // Set new last
594 _lastConnVert = _lastConnVert->lstPrev;
595
596 // Make last point to shapes list
597 _lastConnVert->lstNext = _firstShapeVert;
598 }
599 else
600 {
601 vert->lstNext->lstPrev = vert->lstPrev;
602 vert->lstPrev->lstNext = vert->lstNext;
603 }
604 _connVertices--;
605 }
606 else // if (vert->id.shape > 0)
607 {
608 // A Shape vertex
609 if (vert == _lastShapeVert)
610 {
611 // Set new last
612 _lastShapeVert = _lastShapeVert->lstPrev;
613
614 if (vert == _firstShapeVert)
615 {
616 _firstShapeVert = nullptr;
617 if (_lastConnVert)
618 {
619 _lastConnVert->lstNext = nullptr;
620 }
621 }
622
623 if (_lastShapeVert)
624 {
625 _lastShapeVert->lstNext = nullptr;
626 }
627 }
628 else if (vert == _firstShapeVert)
629 {
630 // Set new first
631 _firstShapeVert = _firstShapeVert->lstNext;
632
633 // Correct the last conn vertex
634 if (_lastConnVert)
635 {
636 _lastConnVert->lstNext = _firstShapeVert;
637 }
638
639 if (_firstShapeVert)
640 {
641 _firstShapeVert->lstPrev = nullptr;
642 }
643 }
644 else
645 {
646 vert->lstNext->lstPrev = vert->lstPrev;
647 vert->lstPrev->lstNext = vert->lstNext;
648 }
649 _shapeVertices--;
650 }
651 vert->lstPrev = nullptr;
652 vert->lstNext = nullptr;
653
654 checkVertInfListConditions();
655
656 return following;
657 }
658
659
getVertexByID(const VertID & id)660 VertInf *VertInfList::getVertexByID(const VertID& id)
661 {
662 VertID searchID = id;
663 if (searchID.vn == kUnassignedVertexNumber)
664 {
665 unsigned int topbit = ((unsigned int) 1) << 31;
666 if (searchID.objID & topbit)
667 {
668 searchID.objID = searchID.objID & ~topbit;
669 searchID.vn = VertID::src;
670 }
671 else
672 {
673 searchID.vn = VertID::tar;
674 }
675 }
676 VertInf *last = end();
677 for (VertInf *curr = connsBegin(); curr != last; curr = curr->lstNext)
678 {
679 if (curr->id == searchID)
680 {
681 return curr;
682 }
683 }
684 return nullptr;
685 }
686
687
getVertexByPos(const Point & p)688 VertInf *VertInfList::getVertexByPos(const Point& p)
689 {
690 VertInf *last = end();
691 for (VertInf *curr = shapesBegin(); curr != last; curr = curr->lstNext)
692 {
693 if (curr->point == p)
694 {
695 return curr;
696 }
697 }
698 return nullptr;
699 }
700
701
shapesBegin(void)702 VertInf *VertInfList::shapesBegin(void)
703 {
704 return _firstShapeVert;
705 }
706
707
connsBegin(void)708 VertInf *VertInfList::connsBegin(void)
709 {
710 if (_firstConnVert)
711 {
712 return _firstConnVert;
713 }
714 // No connector vertices
715 return _firstShapeVert;
716 }
717
718
end(void)719 VertInf *VertInfList::end(void)
720 {
721 return nullptr;
722 }
723
724
connsSize(void) const725 unsigned int VertInfList::connsSize(void) const
726 {
727 return _connVertices;
728 }
729
730
shapesSize(void) const731 unsigned int VertInfList::shapesSize(void) const
732 {
733 return _shapeVertices;
734 }
735
736
737 }
738
739
740