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 * --------------------------------------------------------------------
9 * The Visibility Sweep technique is based upon the method described
10 * in Section 5.2 of:
11 * Lee, D.-T. (1978). Proximity and reachability in the plane.,
12 * PhD thesis, Department of Electrical Engineering,
13 * University of Illinois, Urbana, IL.
14 * --------------------------------------------------------------------
15 *
16 * This library is free software; you can redistribute it and/or
17 * modify it under the terms of the GNU Lesser General Public
18 * License as published by the Free Software Foundation; either
19 * version 2.1 of the License, or (at your option) any later version.
20 * See the file LICENSE.LGPL distributed with the library.
21 *
22 * Licensees holding a valid commercial license may use this file in
23 * accordance with the commercial license agreement provided with the
24 * library.
25 *
26 * This library is distributed in the hope that it will be useful,
27 * but WITHOUT ANY WARRANTY; without even the implied warranty of
28 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
29 *
30 * Author(s): Michael Wybrow
31 */
32
33
34 #include <algorithm>
35 #include <cfloat>
36
37 #include "libavoid/shape.h"
38 #include "libavoid/debug.h"
39 #include "libavoid/visibility.h"
40 #include "libavoid/vertices.h"
41 #include "libavoid/graph.h"
42 #include "libavoid/geometry.h"
43 #include "libavoid/router.h"
44 #include "libavoid/assertions.h"
45
46
47 namespace Avoid {
48
49
50 static void vertexSweep(VertInf *vert);
51
computeVisibilityNaive(void)52 void Obstacle::computeVisibilityNaive(void)
53 {
54 if ( !(router()->InvisibilityGrph) )
55 {
56 // Clear shape from graph.
57 removeFromGraph();
58 }
59
60 VertInf *shapeBegin = firstVert();
61 VertInf *shapeEnd = lastVert()->lstNext;
62
63 VertInf *pointsBegin = router()->vertices.connsBegin();
64 for (VertInf *curr = shapeBegin; curr != shapeEnd; curr = curr->lstNext)
65 {
66 bool knownNew = true;
67
68 db_printf("-- CONSIDERING --\n");
69 curr->id.db_print();
70
71 db_printf("\tFirst Half:\n");
72 for (VertInf *j = pointsBegin ; j != curr; j = j->lstNext)
73 {
74 if (j->id == dummyOrthogID)
75 {
76 // Don't include orthogonal dummy vertices.
77 continue;
78 }
79 EdgeInf::checkEdgeVisibility(curr, j, knownNew);
80 }
81
82 db_printf("\tSecond Half:\n");
83 VertInf *pointsEnd = router()->vertices.end();
84 for (VertInf *k = shapeEnd; k != pointsEnd; k = k->lstNext)
85 {
86 if (k->id == dummyOrthogID)
87 {
88 // Don't include orthogonal dummy vertices.
89 continue;
90 }
91 EdgeInf::checkEdgeVisibility(curr, k, knownNew);
92 }
93 }
94 }
95
96
computeVisibilitySweep(void)97 void Obstacle::computeVisibilitySweep(void)
98 {
99 if ( !(router()->InvisibilityGrph) )
100 {
101 // Clear shape from graph.
102 removeFromGraph();
103 }
104
105 VertInf *startIter = firstVert();
106 VertInf *endIter = lastVert()->lstNext;
107
108 for (VertInf *i = startIter; i != endIter; i = i->lstNext)
109 {
110 vertexSweep(i);
111 }
112 }
113
114
vertexVisibility(VertInf * point,VertInf * partner,bool knownNew,const bool gen_contains)115 void vertexVisibility(VertInf *point, VertInf *partner, bool knownNew,
116 const bool gen_contains)
117 {
118 Router *router = point->_router;
119 const VertID& pID = point->id;
120
121 // Make sure we're only doing ptVis for endpoints.
122 COLA_ASSERT(pID.isConnPt());
123
124 if ( !(router->InvisibilityGrph) )
125 {
126 point->removeFromGraph();
127 }
128
129 if (gen_contains && pID.isConnPt())
130 {
131 router->generateContains(point);
132 }
133
134 if (router->UseLeesAlgorithm)
135 {
136 vertexSweep(point);
137 }
138 else
139 {
140 VertInf *shapesEnd = router->vertices.end();
141 for (VertInf *k = router->vertices.connsBegin(); k != shapesEnd;
142 k = k->lstNext)
143 {
144 if (k->id == dummyOrthogID)
145 {
146 // Don't include orthogonal dummy vertices.
147 continue;
148 }
149 else if (k->id.isConnPt() && !k->id.isConnectionPin() &&
150 !(k->id.isConnCheckpoint() && k->id.objID == pID.objID))
151 {
152 // Include connection pins, but not connectors.
153 // Also include checkpoints with same ID as sweep point.
154 continue;
155 }
156 EdgeInf::checkEdgeVisibility(point, k, knownNew);
157 }
158 if (partner)
159 {
160 EdgeInf::checkEdgeVisibility(point, partner, knownNew);
161 }
162 }
163 }
164
165
166 //============================================================================
167 // SWEEP CODE
168 //
169
170
171 class PointPair
172 {
173 public:
PointPair(const Point & centerPoint,VertInf * inf)174 PointPair(const Point& centerPoint, VertInf *inf)
175 : vInf(inf),
176 centerPoint(centerPoint)
177 {
178 angle = rotationalAngle(vInf->point - centerPoint);
179 distance = euclideanDist(centerPoint, vInf->point);
180 }
operator <(const PointPair & rhs) const181 bool operator<(const PointPair& rhs) const
182 {
183 // Firstly order by angle.
184 if (angle == rhs.angle)
185 {
186 // If the points are collinear, then order them in increasing
187 // distance from the point we are sweeping around.
188 if (distance == rhs.distance)
189 {
190 // XXX: Add this assertion back if we require that
191 // connector endpoints have unique IDs. For the
192 // moment it is okay for them to have the same ID.
193 //COLA_ASSERT(vInf->id != rhs.vInf->id);
194
195 // If comparing two points at the same physical
196 // position, then order them by their VertIDs.
197 return vInf->id < rhs.vInf->id;
198 }
199 return distance < rhs.distance;
200 }
201 return angle < rhs.angle;
202 }
203
204 VertInf *vInf;
205 double angle;
206 double distance;
207 Point centerPoint;
208 };
209
210 typedef std::set<PointPair > VertSet;
211
212
213 class EdgePair
214 {
215 public:
EdgePair()216 EdgePair()
217 : vInf1(nullptr),
218 vInf2(nullptr),
219 dist1(0.0),
220 dist2(0.0),
221 angle(0.0),
222 angleDist(0.0)
223 {
224 // The default constuctor should never be called.
225 // This is defined to appease the MSVC compiler.
226 COLA_ASSERT(false);
227 }
EdgePair(const PointPair & p1,VertInf * v)228 EdgePair(const PointPair& p1, VertInf *v)
229 : vInf1(p1.vInf),
230 vInf2(v),
231 dist1(p1.distance),
232 dist2(euclideanDist(vInf2->point, p1.centerPoint)),
233 angle(p1.angle),
234 angleDist(p1.distance),
235 centerPoint(p1.centerPoint)
236 {
237 }
operator <(const EdgePair & rhs) const238 bool operator<(const EdgePair& rhs) const
239 {
240 COLA_ASSERT(angle == rhs.angle);
241 if (angleDist == rhs.angleDist)
242 {
243 return (dist2 < rhs.dist2);
244 }
245 return (angleDist < rhs.angleDist);
246 }
operator ==(const EdgePair & rhs) const247 bool operator==(const EdgePair& rhs) const
248 {
249 if (((vInf1->id == rhs.vInf1->id) &&
250 (vInf2->id == rhs.vInf2->id)) ||
251 ((vInf1->id == rhs.vInf2->id) &&
252 (vInf2->id == rhs.vInf1->id)))
253 {
254 return true;
255 }
256 return false;
257 }
operator !=(const EdgePair & rhs) const258 bool operator!=(const EdgePair& rhs) const
259 {
260 if (((vInf1->id == rhs.vInf1->id) &&
261 (vInf2->id == rhs.vInf2->id)) ||
262 ((vInf1->id == rhs.vInf2->id) &&
263 (vInf2->id == rhs.vInf1->id)))
264 {
265 return false;
266 }
267 return true;
268 }
setNegativeAngle(void)269 void setNegativeAngle(void)
270 {
271 angle = -1.0;
272 }
setCurrAngle(const PointPair & p)273 double setCurrAngle(const PointPair& p)
274 {
275 if (p.vInf->point == vInf1->point)
276 {
277 angleDist = dist1;
278 angle = p.angle;
279 }
280 else if (p.vInf->point == vInf2->point)
281 {
282 angleDist = dist2;
283 angle = p.angle;
284 }
285 else if (p.angle != angle)
286 {
287 COLA_ASSERT(p.angle > angle);
288 angle = p.angle;
289 Point pp;
290 int result = rayIntersectPoint(vInf1->point, vInf2->point,
291 centerPoint, p.vInf->point, &(pp.x), &(pp.y));
292 if (result != DO_INTERSECT)
293 {
294 // This can happen with points that appear to have the
295 // same angle but at are at slightly different positions
296 angleDist = std::min(dist1, dist2);
297 }
298 else
299 {
300 angleDist = euclideanDist(pp, centerPoint);
301 }
302 }
303
304 return angleDist;
305 }
306
307 VertInf *vInf1;
308 VertInf *vInf2;
309 double dist1;
310 double dist2;
311 double angle;
312 double angleDist;
313 Point centerPoint;
314 };
315
316 typedef std::list<EdgePair> SweepEdgeList;
317
318
319 #define AHEAD 1
320 #define BEHIND -1
321
322 class isBoundingShape
323 {
324 public:
325 // Class instance remembers the ShapeSet.
isBoundingShape(ShapeSet & set)326 isBoundingShape(ShapeSet& set) :
327 ss(set)
328 { }
329 // The following is an overloading of the function call operator.
operator ()(const PointPair & pp)330 bool operator () (const PointPair& pp)
331 {
332 if (!(pp.vInf->id.isConnPt()) &&
333 (ss.find(pp.vInf->id.objID) != ss.end()))
334 {
335 return true;
336 }
337 return false;
338 }
339 private:
340 // MSVC wants to generate the assignment operator and the default
341 // constructor, but fails. Therefore we declare them private and
342 // don't implement them.
343 isBoundingShape & operator=(isBoundingShape const &);
344 isBoundingShape();
345
346 ShapeSet& ss;
347 };
348
349
sweepVisible(SweepEdgeList & T,const PointPair & point,std::set<unsigned int> & onBorderIDs,int * blocker)350 static bool sweepVisible(SweepEdgeList& T, const PointPair& point,
351 std::set<unsigned int>& onBorderIDs, int *blocker)
352 {
353 if (T.empty())
354 {
355 // No blocking edges.
356 return true;
357 }
358
359 Router *router = point.vInf->_router;
360 bool visible = true;
361
362 SweepEdgeList::const_iterator closestIt = T.begin();
363 SweepEdgeList::const_iterator end = T.end();
364 while (closestIt != end)
365 {
366 if ((point.vInf->point == closestIt->vInf1->point) ||
367 (point.vInf->point == closestIt->vInf2->point))
368 {
369 // If the ray intersects just the endpoint of a
370 // blocking edge then ignore that edge.
371 ++closestIt;
372 continue;
373 }
374 break;
375 }
376 if (closestIt == end)
377 {
378 return true;
379 }
380
381 if (point.vInf->id.isConnPt())
382 {
383 // It's a connector endpoint, so we have to ignore
384 // edges of containing shapes for determining visibility.
385 ShapeSet& rss = router->contains[point.vInf->id];
386 while (closestIt != end)
387 {
388 if (rss.find(closestIt->vInf1->id.objID) == rss.end())
389 {
390 // This is not a containing edge so do the normal
391 // test and then stop.
392 if (point.distance > closestIt->angleDist)
393 {
394 visible = false;
395 }
396 else if ((point.distance == closestIt->angleDist) &&
397 onBorderIDs.find(closestIt->vInf1->id.objID) !=
398 onBorderIDs.end())
399 {
400 // Touching, but centerPoint is on another edge of
401 // shape shape, so count as blocking.
402 visible = false;
403 }
404 break;
405 }
406 // This was a containing edge, so consider the next along.
407 ++closestIt;
408 }
409 }
410 else
411 {
412 // Just test to see if this point is closer than the closest
413 // edge blocking this ray.
414 if (point.distance > closestIt->angleDist)
415 {
416 visible = false;
417 }
418 else if ((point.distance == closestIt->angleDist) &&
419 onBorderIDs.find(closestIt->vInf1->id.objID) !=
420 onBorderIDs.end())
421 {
422 // Touching, but centerPoint is on another edge of
423 // shape shape, so count as blocking.
424 visible = false;
425 }
426 }
427
428 if (!visible)
429 {
430 *blocker = (*closestIt).vInf1->id.objID;
431 }
432 return visible;
433 }
434
435
vertexSweep(VertInf * vert)436 static void vertexSweep(VertInf *vert)
437 {
438 Router *router = vert->_router;
439 VertID& pID = vert->id;
440 Point& pPoint = vert->point;
441
442 VertInf *centerInf = vert;
443 VertID centerID = pID;
444 Point centerPoint = pPoint;
445
446 // List of shape (and maybe endpt) vertices, except p
447 // Sort list, around
448 VertSet v;
449
450 // Initialise the vertex list
451 ShapeSet& ss = router->contains[centerID];
452 VertInf *beginVert = router->vertices.connsBegin();
453 VertInf *endVert = router->vertices.end();
454 for (VertInf *inf = beginVert; inf != endVert; inf = inf->lstNext)
455 {
456 if (inf == centerInf)
457 {
458 // Don't include the center point itself.
459 continue;
460 }
461 else if (inf->id == dummyOrthogID)
462 {
463 // Don't include orthogonal dummy vertices.
464 continue;
465 }
466
467 if (centerID.isConnPt() && (ss.find(inf->id.objID) != ss.end()) &&
468 !inf->id.isConnPt())
469 {
470 // Don't include edge points of containing shapes.
471 unsigned int shapeID = inf->id.objID;
472 db_printf("Center is inside shape %u so ignore shape edges.\n",
473 shapeID);
474 continue;
475 }
476
477 if (inf->id.isConnPt())
478 {
479 // Add connector endpoint.
480 if (centerID.isConnPt())
481 {
482 if (inf->id.isConnectionPin())
483 {
484 v.insert(PointPair(centerPoint, inf));
485 }
486 else if (centerID.isConnectionPin())
487 {
488 // Connection pins have visibility to everything.
489 v.insert(PointPair(centerPoint, inf));
490 }
491 else if (inf->id.objID == centerID.objID)
492 {
493 // Center is an endpoint, so only include the other
494 // endpoints or checkpoints from the matching connector.
495 v.insert(PointPair(centerPoint, inf));
496 }
497 }
498 else
499 {
500 // Center is a shape vertex, so add all endpoint vertices.
501 v.insert(PointPair(centerPoint, inf));
502 }
503 }
504 else
505 {
506 // Add shape vertex.
507 v.insert(PointPair(centerPoint, inf));
508 }
509 }
510 std::set<unsigned int> onBorderIDs;
511
512 // Add edges to T that intersect the initial ray.
513 SweepEdgeList e;
514 VertSet::const_iterator vbegin = v.begin();
515 VertSet::const_iterator vend = v.end();
516 const Point xaxis(DBL_MAX, centerInf->point.y);
517 for (VertSet::const_iterator t = vbegin; t != vend; ++t)
518 {
519 VertInf *k = t->vInf;
520
521 COLA_ASSERT(centerInf != k);
522
523 VertInf *kPrev = k->shPrev;
524 VertInf *kNext = k->shNext;
525 if (kPrev && (kPrev != centerInf) &&
526 (vecDir(centerInf->point, xaxis, kPrev->point) == AHEAD))
527 {
528 if (segmentIntersect(centerInf->point, xaxis, kPrev->point,
529 k->point))
530 {
531 EdgePair intPair = EdgePair(*t, kPrev);
532 e.push_back(intPair);
533 }
534 if (pointOnLine(kPrev->point, k->point, centerInf->point))
535 {
536 // Record that centerPoint is on an obstacle line.
537 onBorderIDs.insert(k->id.objID);
538 }
539 }
540 else if (kNext && (kNext != centerInf) &&
541 (vecDir(centerInf->point, xaxis, kNext->point) == AHEAD))
542 {
543 if (segmentIntersect(centerInf->point, xaxis, kNext->point,
544 k->point))
545 {
546 EdgePair intPair = EdgePair(*t, kNext);
547 e.push_back(intPair);
548 }
549 if (pointOnLine(kNext->point, k->point, centerInf->point))
550 {
551 // Record that centerPoint is on an obstacle line.
552 onBorderIDs.insert(k->id.objID);
553 }
554 }
555 }
556 for (SweepEdgeList::iterator c = e.begin(); c != e.end(); ++c)
557 {
558 (*c).setNegativeAngle();
559 }
560
561
562 // Start the actual sweep.
563 db_printf("SWEEP: "); centerID.db_print(); db_printf("\n");
564
565 isBoundingShape isBounding(ss);
566 for (VertSet::const_iterator t = vbegin; t != vend; ++t)
567 {
568 VertInf *currInf = (*t).vInf;
569 VertID& currID = currInf->id;
570 Point& currPt = currInf->point;
571
572 const double& currDist = (*t).distance;
573
574 EdgeInf *edge = EdgeInf::existingEdge(centerInf, currInf);
575 if (edge == nullptr)
576 {
577 edge = new EdgeInf(centerInf, currInf);
578 }
579
580 for (SweepEdgeList::iterator c = e.begin(); c != e.end(); ++c)
581 {
582 (*c).setCurrAngle(*t);
583 }
584 e.sort();
585
586 // Check visibility.
587 int blocker = 0;
588 bool currVisible = sweepVisible(e, *t, onBorderIDs, &blocker);
589
590 bool cone1 = true, cone2 = true;
591 if (!(centerID.isConnPt()))
592 {
593 cone1 = inValidRegion(router->IgnoreRegions,
594 centerInf->shPrev->point, centerPoint,
595 centerInf->shNext->point, currInf->point);
596 }
597 if (!(currInf->id.isConnPt()))
598 {
599 cone2 = inValidRegion(router->IgnoreRegions,
600 currInf->shPrev->point, currInf->point,
601 currInf->shNext->point, centerPoint);
602 }
603
604 if (!cone1 || !cone2)
605 {
606 if (router->InvisibilityGrph)
607 {
608 db_printf("\tSetting invisibility edge... \n\t\t");
609 edge->addBlocker(0);
610 edge->db_print();
611 }
612 }
613 else
614 {
615 if (currVisible)
616 {
617 db_printf("\tSetting visibility edge... \n\t\t");
618 edge->setDist(currDist);
619 edge->db_print();
620 }
621 else if (router->InvisibilityGrph)
622 {
623 db_printf("\tSetting invisibility edge... \n\t\t");
624 edge->addBlocker(blocker);
625 edge->db_print();
626 }
627 }
628
629 if (!(edge->added()) && !(router->InvisibilityGrph))
630 {
631 delete edge;
632 edge = nullptr;
633 }
634
635 if (!(currID.isConnPt()))
636 {
637 // This is a shape edge
638
639 if (currInf->shPrev != centerInf)
640 {
641 Point& prevPt = currInf->shPrev->point;
642 int prevDir = vecDir(centerPoint, currPt, prevPt);
643 EdgePair prevPair = EdgePair(*t, currInf->shPrev);
644
645 if (prevDir == BEHIND)
646 {
647 e.remove(prevPair);
648 }
649 else if (prevDir == AHEAD)
650 {
651 e.push_front(prevPair);
652 }
653 }
654
655 if (currInf->shNext != centerInf)
656 {
657 Point& nextPt = currInf->shNext->point;
658 int nextDir = vecDir(centerPoint, currPt, nextPt);
659 EdgePair nextPair = EdgePair(*t, currInf->shNext);
660
661 if (nextDir == BEHIND)
662 {
663 e.remove(nextPair);
664 }
665 else if (nextDir == AHEAD)
666 {
667 e.push_front(nextPair);
668 }
669 }
670 }
671 }
672 }
673
674
675 }
676
677