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 */
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"
32 #include <math.h>
34 namespace Avoid {
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);
51 // We are in the same instance
52 assert(_v1->_router == _v2->_router);
53 _router = _v1->_router;
55 _conns.clear();
56 }
59 EdgeInf::~EdgeInf()
60 {
61 if (_added)
62 {
63 makeInactive();
64 }
65 }
68 void EdgeInf::makeActive(void)
69 {
70 assert(_added == false);
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 }
92 void EdgeInf::makeInactive(void)
93 {
94 assert(_added == true);
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 }
118 void EdgeInf::setDist(double dist)
119 {
120 //assert(dist != 0);
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 }
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 }
147 void EdgeInf::addConn(bool *flag)
148 {
149 _conns.push_back(flag);
150 }
153 void EdgeInf::addCycleBlocker(void)
154 {
155 // Needs to be in invisibility graph.
156 addBlocker(-1);
157 }
160 void EdgeInf::addBlocker(int b)
161 {
162 assert(_router->InvisibilityGrph);
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 }
178 pair<VertID, VertID> EdgeInf::ids(void)
179 {
180 return std::make_pair(_v1->id, _v2->id);
181 }
184 pair<Point, Point> EdgeInf::points(void)
185 {
186 return std::make_pair(_v1->point, _v2->point);
187 }
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 }
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 }
215 int blocker = 0;
216 bool cone1 = true;
217 bool cone2 = true;
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;
226 _router->st_checked_edges++;
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];
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 }
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];
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 }
268 if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
269 {
271 // if i and j see each other, add edge
272 db_printf("\tSetting visibility edge... \n\t\t");
273 db_print();
275 double d = dist(iPoint, jPoint);
277 setDist(d);
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
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 }
297 int EdgeInf::firstBlocker(void)
298 {
299 ShapeSet ss = ShapeSet();
301 Point& pti = _v1->point;
302 Point& ptj = _v2->point;
303 VertID& iID = _v1->id;
304 VertID& jID = _v2->id;
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 }
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;
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 }
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 }
359 VertInf *EdgeInf::otherVert(VertInf *vert)
360 {
361 assert((vert == _v1) || (vert == _v2));
363 if (vert == _v1)
364 {
365 return _v2;
366 }
367 return _v1;
368 }
371 EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
372 {
373 Router *router = i->_router;
374 EdgeInf *edge = NULL;
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 }
396 return edge;
397 }
400 EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
401 {
402 VertInf *selected = NULL;
404 if (i->visListSize <= j->visListSize)
405 {
406 selected = i;
407 }
408 else
409 {
410 selected = j;
411 }
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 }
424 if (i->invisListSize <= j->invisListSize)
425 {
426 selected = i;
427 }
428 else
429 {
430 selected = j;
431 }
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 }
444 return NULL;
445 }
448 //===========================================================================
451 EdgeList::EdgeList()
452 : _firstEdge(NULL)
453 , _lastEdge(NULL)
454 , _count(0)
455 {
456 }
459 void EdgeList::addEdge(EdgeInf *edge)
460 {
461 if (_firstEdge == NULL)
462 {
463 assert(_lastEdge == NULL);
465 _lastEdge = edge;
466 _firstEdge = edge;
468 edge->lstPrev = NULL;
469 edge->lstNext = NULL;
470 }
471 else
472 {
473 assert(_lastEdge != NULL);
475 _lastEdge->lstNext = edge;
476 edge->lstPrev = _lastEdge;
478 _lastEdge = edge;
480 edge->lstNext = NULL;
481 }
482 _count++;
483 }
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 }
510 edge->lstPrev = NULL;
511 edge->lstNext = NULL;
513 _count--;
514 }
517 EdgeInf *EdgeList::begin(void)
518 {
519 return _firstEdge;
520 }
523 EdgeInf *EdgeList::end(void)
524 {
525 return NULL;
526 }
529 }