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 <mjwybrow@users.sourceforge.net>
23 */
26 #include <cmath>
28 #include "libavoid/debug.h"
29 #include "libavoid/graph.h"
30 #include "libavoid/connector.h"
31 #include "libavoid/geometry.h"
32 #include "libavoid/timer.h"
33 #include "libavoid/vertices.h"
34 #include "libavoid/router.h"
35 #include "libavoid/assertions.h"
38 using std::pair;
40 namespace Avoid {
43 EdgeInf::EdgeInf(VertInf *v1, VertInf *v2, const bool orthogonal)
44 : lstPrev(NULL),
45 lstNext(NULL),
46 _blocker(0),
47 _router(NULL),
48 _added(false),
49 _visible(false),
50 _orthogonal(orthogonal),
51 _v1(v1),
52 _v2(v2),
53 _dist(-1)
54 {
55 // Not passed NULL values.
56 COLA_ASSERT(v1 && v2);
58 // We are in the same instance
59 COLA_ASSERT(_v1->_router == _v2->_router);
60 _router = _v1->_router;
62 _conns.clear();
63 }
66 EdgeInf::~EdgeInf()
67 {
68 if (_added)
69 {
70 makeInactive();
71 }
72 }
75 // Gives an order value between 0 and 3 for the point c, given the last
76 // segment was from a to b. Returns the following value:
77 // 0 : Point c is directly backwards from point b.
78 // 1 : Point c is a left-hand 90 degree turn.
79 // 2 : Point c is a right-hand 90 degree turn.
80 // 3 : Point c is straight ahead (collinear).
81 //
82 static inline int orthogTurnOrder(const Point& a, const Point& b,
83 const Point& c)
84 {
85 // We should only be calling this with orthogonal points,
86 COLA_ASSERT((c.x == b.x) || (c.y == b.y));
87 COLA_ASSERT((a.x == b.x) || (a.y == b.y));
89 int direction = vecDir(a, b, c);
91 if (direction > 0)
92 {
93 // Counterclockwise := left
94 return 1;
95 }
96 else if (direction < 0)
97 {
98 // Clockwise := right
99 return 2;
100 }
102 if (b.x == c.x)
103 {
104 if ( ((a.y < b.y) && (c.y < b.y)) ||
105 ((a.y > b.y) && (c.y > b.y)) )
106 {
107 // Behind.
108 return 0;
109 }
110 }
111 else
112 {
113 if ( ((a.x < b.x) && (c.x < b.x)) ||
114 ((a.x > b.x) && (c.x > b.x)) )
115 {
116 // Behind.
117 return 0;
118 }
119 }
121 // Ahead.
122 return 3;
123 }
126 // Returns a less than operation for a set exploration order for orthogonal
127 // searching. Forward, then left, then right. Or if there is no previous
128 // point, then the order is north, east, south, then west.
129 // Note: This method assumes the two Edges that share a common point.
130 bool EdgeInf::rotationLessThan(const VertInf *lastV, const EdgeInf *rhs) const
131 {
132 if ((_v1 == rhs->_v1) && (_v2 == rhs->_v2))
133 {
134 // Effectively the same visibility edge, so they are equal.
135 return false;
136 }
137 VertInf *lhsV = NULL, *rhsV = NULL, *commonV = NULL;
139 // Determine common Point and the comparison point on the left- and
140 // the right-hand-side.
141 if (_v1 == rhs->_v1)
142 {
143 commonV = _v1;
144 lhsV = _v2;
145 rhsV = rhs->_v2;
146 }
147 else if (_v1 == rhs->_v2)
148 {
149 commonV = _v1;
150 lhsV = _v2;
151 rhsV = rhs->_v1;
152 }
153 else if (_v2 == rhs->_v1)
154 {
155 commonV = _v2;
156 lhsV = _v1;
157 rhsV = rhs->_v2;
158 }
159 else if (_v2 == rhs->_v2)
160 {
161 commonV = _v2;
162 lhsV = _v1;
163 rhsV = rhs->_v1;
164 }
166 const Point& lhsPt = lhsV->point;
167 const Point& rhsPt = rhsV->point;
168 const Point& commonPt = commonV->point;
170 // If no lastPt, use one directly to the left;
171 Point lastPt = (lastV) ? lastV->point : Point(commonPt.x - 10, commonPt.y);
173 int lhsVal = orthogTurnOrder(lastPt, commonPt, lhsPt);
174 int rhsVal = orthogTurnOrder(lastPt, commonPt, rhsPt);
176 return lhsVal < rhsVal;
177 }
180 void EdgeInf::makeActive(void)
181 {
182 COLA_ASSERT(_added == false);
184 if (_orthogonal)
185 {
186 COLA_ASSERT(_visible);
187 _router->visOrthogGraph.addEdge(this);
188 _pos1 = _v1->orthogVisList.insert(_v1->orthogVisList.begin(), this);
189 _v1->orthogVisListSize++;
190 _pos2 = _v2->orthogVisList.insert(_v2->orthogVisList.begin(), this);
191 _v2->orthogVisListSize++;
192 }
193 else
194 {
195 if (_visible)
196 {
197 _router->visGraph.addEdge(this);
198 _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
199 _v1->visListSize++;
200 _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
201 _v2->visListSize++;
202 }
203 else // if (invisible)
204 {
205 _router->invisGraph.addEdge(this);
206 _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
207 _v1->invisListSize++;
208 _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
209 _v2->invisListSize++;
210 }
211 }
212 _added = true;
213 }
216 void EdgeInf::makeInactive(void)
217 {
218 COLA_ASSERT(_added == true);
220 if (_orthogonal)
221 {
222 COLA_ASSERT(_visible);
223 _router->visOrthogGraph.removeEdge(this);
224 _v1->orthogVisList.erase(_pos1);
225 _v1->orthogVisListSize--;
226 _v2->orthogVisList.erase(_pos2);
227 _v2->orthogVisListSize--;
228 }
229 else
230 {
231 if (_visible)
232 {
233 _router->visGraph.removeEdge(this);
234 _v1->visList.erase(_pos1);
235 _v1->visListSize--;
236 _v2->visList.erase(_pos2);
237 _v2->visListSize--;
238 }
239 else // if (invisible)
240 {
241 _router->invisGraph.removeEdge(this);
242 _v1->invisList.erase(_pos1);
243 _v1->invisListSize--;
244 _v2->invisList.erase(_pos2);
245 _v2->invisListSize--;
246 }
247 }
248 _blocker = 0;
249 _conns.clear();
250 _added = false;
251 }
254 void EdgeInf::setDist(double dist)
255 {
256 //COLA_ASSERT(dist != 0);
258 if (_added && !_visible)
259 {
260 makeInactive();
261 COLA_ASSERT(!_added);
262 }
263 if (!_added)
264 {
265 _visible = true;
266 makeActive();
267 }
268 _dist = dist;
269 _blocker = 0;
270 }
273 bool EdgeInf::added(void)
274 {
275 return _added;
276 }
279 void EdgeInf::alertConns(void)
280 {
281 FlagList::iterator finish = _conns.end();
282 for (FlagList::iterator i = _conns.begin(); i != finish; ++i)
283 {
284 *(*i) = true;
285 }
286 _conns.clear();
287 }
290 void EdgeInf::addConn(bool *flag)
291 {
292 _conns.push_back(flag);
293 }
296 void EdgeInf::addCycleBlocker(void)
297 {
298 // Needs to be in invisibility graph.
299 addBlocker(-1);
300 }
303 void EdgeInf::addBlocker(int b)
304 {
305 COLA_ASSERT(_router->InvisibilityGrph);
307 if (_added && _visible)
308 {
309 makeInactive();
310 COLA_ASSERT(!_added);
311 }
312 if (!_added)
313 {
314 _visible = false;
315 makeActive();
316 }
317 _dist = 0;
318 _blocker = b;
319 }
322 pair<VertID, VertID> EdgeInf::ids(void)
323 {
324 return std::make_pair(_v1->id, _v2->id);
325 }
328 pair<Point, Point> EdgeInf::points(void)
329 {
330 return std::make_pair(_v1->point, _v2->point);
331 }
334 void EdgeInf::db_print(void)
335 {
336 db_printf("Edge(");
337 _v1->id.db_print();
338 db_printf(",");
339 _v2->id.db_print();
340 db_printf(")\n");
341 }
344 void EdgeInf::checkVis(void)
345 {
346 if (_added && !_visible)
347 {
348 db_printf("\tChecking visibility for existing invisibility edge..."
349 "\n\t\t");
350 db_print();
351 }
352 else if (_added && _visible)
353 {
354 db_printf("\tChecking visibility for existing visibility edge..."
355 "\n\t\t");
356 db_print();
357 }
359 int blocker = 0;
360 bool cone1 = true;
361 bool cone2 = true;
363 VertInf *i = _v1;
364 VertInf *j = _v2;
365 const VertID& iID = i->id;
366 const VertID& jID = j->id;
367 const Point& iPoint = i->point;
368 const Point& jPoint = j->point;
370 _router->st_checked_edges++;
372 if (iID.isShape)
373 {
374 cone1 = inValidRegion(_router->IgnoreRegions, i->shPrev->point,
375 iPoint, i->shNext->point, jPoint);
376 }
377 else if (_router->IgnoreRegions == false)
378 {
379 // If Ignoring regions then this case is already caught by
380 // the invalid regions, so only check it when not ignoring
381 // regions.
382 ShapeSet& ss = _router->contains[iID];
384 if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
385 {
386 db_printf("1: Edge of bounding shape\n");
387 // Don't even check this edge, it should be zero,
388 // since a point in a shape can't see it's corners
389 cone1 = false;
390 }
391 }
393 if (cone1)
394 {
395 // If outside the first cone, don't even bother checking.
396 if (jID.isShape)
397 {
398 cone2 = inValidRegion(_router->IgnoreRegions, j->shPrev->point,
399 jPoint, j->shNext->point, iPoint);
400 }
401 else if (_router->IgnoreRegions == false)
402 {
403 // If Ignoring regions then this case is already caught by
404 // the invalid regions, so only check it when not ignoring
405 // regions.
406 ShapeSet& ss = _router->contains[jID];
408 if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
409 {
410 db_printf("2: Edge of bounding shape\n");
411 // Don't even check this edge, it should be zero,
412 // since a point in a shape can't see it's corners
413 cone2 = false;
414 }
415 }
416 }
418 if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
419 {
421 // if i and j see each other, add edge
422 db_printf("\tSetting visibility edge... \n\t\t");
423 db_print();
425 double d = euclideanDist(iPoint, jPoint);
427 setDist(d);
429 }
430 else if (_router->InvisibilityGrph)
431 {
432 #if 0
433 db_printf("%d, %d, %d\n", cone1, cone2, blocker);
434 db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x,
435 (int) iInfo.point.y, (int) jInfo.point.x,
436 (int) jInfo.point.y);
437 #endif
439 // if i and j can't see each other, add blank edge
440 db_printf("\tSetting invisibility edge... \n\t\t");
441 db_print();
442 addBlocker(blocker);
443 }
444 }
447 int EdgeInf::firstBlocker(void)
448 {
449 ShapeSet ss = ShapeSet();
451 Point& pti = _v1->point;
452 Point& ptj = _v2->point;
453 VertID& iID = _v1->id;
454 VertID& jID = _v2->id;
456 ContainsMap &contains = _router->contains;
457 if (!(iID.isShape))
458 {
459 ss.insert(contains[iID].begin(), contains[iID].end());
460 }
461 if (!(jID.isShape))
462 {
463 ss.insert(contains[jID].begin(), contains[jID].end());
464 }
466 VertInf *last = _router->vertices.end();
467 unsigned int lastId = 0;
468 bool seenIntersectionAtEndpoint = false;
469 for (VertInf *k = _router->vertices.shapesBegin(); k != last; )
470 {
471 VertID kID = k->id;
472 if (k->id == dummyOrthogID)
473 {
474 // Don't include orthogonal dummy vertices.
475 k = k->lstNext;
476 continue;
477 }
478 if (kID.objID != lastId)
479 {
480 if ((ss.find(kID.objID) != ss.end()))
481 {
482 unsigned int shapeID = kID.objID;
483 db_printf("Endpoint is inside shape %u so ignore shape "
484 "edges.\n", kID.objID);
485 // One of the endpoints is inside this shape so ignore it.
486 while ((k != last) && (k->id.objID == shapeID))
487 {
488 // And skip the other vertices from this shape.
489 k = k->lstNext;
490 }
491 continue;
492 }
493 seenIntersectionAtEndpoint = false;
494 lastId = kID.objID;
495 }
496 Point& kPoint = k->point;
497 Point& kPrevPoint = k->shPrev->point;
498 if (segmentShapeIntersect(pti, ptj, kPrevPoint, kPoint,
499 seenIntersectionAtEndpoint))
500 {
501 ss.clear();
502 return kID.objID;
503 }
504 k = k->lstNext;
505 }
506 ss.clear();
507 return 0;
508 }
511 bool EdgeInf::isBetween(VertInf *i, VertInf *j)
512 {
513 if ( ((i == _v1) && (j == _v2)) ||
514 ((i == _v2) && (j == _v1)) )
515 {
516 return true;
517 }
518 return false;
519 }
522 // Returns true if this edge is a vertical or horizontal line segment.
523 bool EdgeInf::isOrthogonal(void) const
524 {
525 return ((_v1->point.x == _v2->point.x) ||
526 (_v1->point.y == _v2->point.y));
527 }
530 VertInf *EdgeInf::otherVert(VertInf *vert)
531 {
532 COLA_ASSERT((vert == _v1) || (vert == _v2));
534 if (vert == _v1)
535 {
536 return _v2;
537 }
538 return _v1;
539 }
542 EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
543 {
544 // This is for polyline routing, so check we're not
545 // considering orthogonal vertices.
546 COLA_ASSERT(i->id != dummyOrthogID);
547 COLA_ASSERT(j->id != dummyOrthogID);
549 Router *router = i->_router;
550 EdgeInf *edge = NULL;
552 if (knownNew)
553 {
554 COLA_ASSERT(existingEdge(i, j) == NULL);
555 edge = new EdgeInf(i, j);
556 }
557 else
558 {
559 edge = existingEdge(i, j);
560 if (edge == NULL)
561 {
562 edge = new EdgeInf(i, j);
563 }
564 }
565 edge->checkVis();
566 if (!(edge->_added) && !(router->InvisibilityGrph))
567 {
568 delete edge;
569 edge = NULL;
570 }
572 return edge;
573 }
576 // XXX: This function is ineffecient, and shouldn't even really be
577 // required.
578 EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
579 {
580 VertInf *selected = NULL;
582 // Look through poly-line visibility edges.
583 selected = (i->visListSize <= j->visListSize) ? i : j;
584 EdgeInfList& visList = selected->visList;
585 EdgeInfList::const_iterator finish = visList.end();
586 for (EdgeInfList::const_iterator edge = visList.begin(); edge != finish;
587 ++edge)
588 {
589 if ((*edge)->isBetween(i, j))
590 {
591 return (*edge);
592 }
593 }
595 // Look through orthogonal visbility edges.
596 selected = (i->orthogVisListSize <= j->orthogVisListSize) ? i : j;
597 EdgeInfList& orthogVisList = selected->orthogVisList;
598 finish = orthogVisList.end();
599 for (EdgeInfList::const_iterator edge = orthogVisList.begin();
600 edge != finish; ++edge)
601 {
602 if ((*edge)->isBetween(i, j))
603 {
604 return (*edge);
605 }
606 }
608 // Look through poly-line invisbility edges.
609 selected = (i->invisListSize <= j->invisListSize) ? i : j;
610 EdgeInfList& invisList = selected->invisList;
611 finish = invisList.end();
612 for (EdgeInfList::const_iterator edge = invisList.begin(); edge != finish;
613 ++edge)
614 {
615 if ((*edge)->isBetween(i, j))
616 {
617 return (*edge);
618 }
619 }
621 return NULL;
622 }
625 //===========================================================================
628 EdgeList::EdgeList(bool orthogonal)
629 : _orthogonal(orthogonal),
630 _firstEdge(NULL),
631 _lastEdge(NULL),
632 _count(0)
633 {
634 }
637 EdgeList::~EdgeList()
638 {
639 clear();
640 }
643 void EdgeList::clear(void)
644 {
645 while (_firstEdge)
646 {
647 delete _firstEdge;
648 }
649 COLA_ASSERT(_count == 0);
650 _lastEdge = NULL;
651 }
654 int EdgeList::size(void) const
655 {
656 return _count;
657 }
660 void EdgeList::addEdge(EdgeInf *edge)
661 {
662 COLA_ASSERT(!_orthogonal || edge->isOrthogonal());
664 if (_firstEdge == NULL)
665 {
666 COLA_ASSERT(_lastEdge == NULL);
668 _lastEdge = edge;
669 _firstEdge = edge;
671 edge->lstPrev = NULL;
672 edge->lstNext = NULL;
673 }
674 else
675 {
676 COLA_ASSERT(_lastEdge != NULL);
678 _lastEdge->lstNext = edge;
679 edge->lstPrev = _lastEdge;
681 _lastEdge = edge;
683 edge->lstNext = NULL;
684 }
685 _count++;
686 }
689 void EdgeList::removeEdge(EdgeInf *edge)
690 {
691 if (edge->lstPrev)
692 {
693 edge->lstPrev->lstNext = edge->lstNext;
694 }
695 if (edge->lstNext)
696 {
697 edge->lstNext->lstPrev = edge->lstPrev;
698 }
699 if (edge == _lastEdge)
700 {
701 _lastEdge = edge->lstPrev;
702 if (edge == _firstEdge)
703 {
704 _firstEdge = NULL;
705 }
706 }
707 else if (edge == _firstEdge)
708 {
709 _firstEdge = edge->lstNext;
710 }
713 edge->lstPrev = NULL;
714 edge->lstNext = NULL;
716 _count--;
717 }
720 EdgeInf *EdgeList::begin(void)
721 {
722 return _firstEdge;
723 }
726 EdgeInf *EdgeList::end(void)
727 {
728 return NULL;
729 }
732 }