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 using std::pair;
36 namespace Avoid {
39 EdgeInf::EdgeInf(VertInf *v1, VertInf *v2)
40 : lstPrev(NULL)
41 , lstNext(NULL)
42 , _blocker(0)
43 , _router(NULL)
44 , _added(false)
45 , _visible(false)
46 , _v1(v1)
47 , _v2(v2)
48 , _dist(-1)
49 {
50 // Not passed NULL values.
51 assert(v1 && v2);
53 // We are in the same instance
54 assert(_v1->_router == _v2->_router);
55 _router = _v1->_router;
57 _conns.clear();
58 }
61 EdgeInf::~EdgeInf()
62 {
63 if (_added)
64 {
65 makeInactive();
66 }
67 }
70 void EdgeInf::makeActive(void)
71 {
72 assert(_added == false);
74 if (_visible)
75 {
76 _router->visGraph.addEdge(this);
77 _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
78 _v1->visListSize++;
79 _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
80 _v2->visListSize++;
81 }
82 else // if (invisible)
83 {
84 _router->invisGraph.addEdge(this);
85 _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
86 _v1->invisListSize++;
87 _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
88 _v2->invisListSize++;
89 }
90 _added = true;
91 }
94 void EdgeInf::makeInactive(void)
95 {
96 assert(_added == true);
98 if (_visible)
99 {
100 _router->visGraph.removeEdge(this);
101 _v1->visList.erase(_pos1);
102 _v1->visListSize--;
103 _v2->visList.erase(_pos2);
104 _v2->visListSize--;
105 }
106 else // if (invisible)
107 {
108 _router->invisGraph.removeEdge(this);
109 _v1->invisList.erase(_pos1);
110 _v1->invisListSize--;
111 _v2->invisList.erase(_pos2);
112 _v2->invisListSize--;
113 }
114 _blocker = 0;
115 _conns.clear();
116 _added = false;
117 }
120 void EdgeInf::setDist(double dist)
121 {
122 //assert(dist != 0);
124 if (_added && !_visible)
125 {
126 makeInactive();
127 }
128 if (!_added)
129 {
130 _visible = true;
131 makeActive();
132 }
133 _dist = dist;
134 _blocker = 0;
135 }
138 void EdgeInf::alertConns(void)
139 {
140 FlagList::iterator finish = _conns.end();
141 for (FlagList::iterator i = _conns.begin(); i != finish; ++i)
142 {
143 *(*i) = true;
144 }
145 _conns.clear();
146 }
149 void EdgeInf::addConn(bool *flag)
150 {
151 _conns.push_back(flag);
152 }
155 void EdgeInf::addCycleBlocker(void)
156 {
157 // Needs to be in invisibility graph.
158 addBlocker(-1);
159 }
162 void EdgeInf::addBlocker(int b)
163 {
164 assert(_router->InvisibilityGrph);
166 if (_added && _visible)
167 {
168 makeInactive();
169 }
170 if (!_added)
171 {
172 _visible = false;
173 makeActive();
174 }
175 _dist = 0;
176 _blocker = b;
177 }
180 pair<VertID, VertID> EdgeInf::ids(void)
181 {
182 return std::make_pair(_v1->id, _v2->id);
183 }
186 pair<Point, Point> EdgeInf::points(void)
187 {
188 return std::make_pair(_v1->point, _v2->point);
189 }
192 void EdgeInf::db_print(void)
193 {
194 db_printf("Edge(");
195 _v1->id.db_print();
196 db_printf(",");
197 _v2->id.db_print();
198 db_printf(")\n");
199 }
202 void EdgeInf::checkVis(void)
203 {
204 if (_added && !_visible)
205 {
206 db_printf("\tChecking visibility for existing invisibility edge..."
207 "\n\t\t");
208 db_print();
209 }
210 else if (_added && _visible)
211 {
212 db_printf("\tChecking visibility for existing visibility edge..."
213 "\n\t\t");
214 db_print();
215 }
217 int blocker = 0;
218 bool cone1 = true;
219 bool cone2 = true;
221 VertInf *i = _v1;
222 VertInf *j = _v2;
223 const VertID& iID = i->id;
224 const VertID& jID = j->id;
225 const Point& iPoint = i->point;
226 const Point& jPoint = j->point;
228 _router->st_checked_edges++;
230 if (iID.isShape)
231 {
232 cone1 = inValidRegion(_router->IgnoreRegions, i->shPrev->point,
233 iPoint, i->shNext->point, jPoint);
234 }
235 else
236 {
237 ShapeSet& ss = _router->contains[iID];
239 if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
240 {
241 db_printf("1: Edge of bounding shape\n");
242 // Don't even check this edge, it should be zero,
243 // since a point in a shape can't see it's corners
244 cone1 = false;
245 }
246 }
248 if (cone1)
249 {
250 // If outside the first cone, don't even bother checking.
251 if (jID.isShape)
252 {
253 cone2 = inValidRegion(_router->IgnoreRegions, j->shPrev->point,
254 jPoint, j->shNext->point, iPoint);
255 }
256 else
257 {
258 ShapeSet& ss = _router->contains[jID];
260 if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
261 {
262 db_printf("2: Edge of bounding shape\n");
263 // Don't even check this edge, it should be zero,
264 // since a point in a shape can't see it's corners
265 cone2 = false;
266 }
267 }
268 }
270 if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
271 {
273 // if i and j see each other, add edge
274 db_printf("\tSetting visibility edge... \n\t\t");
275 db_print();
277 double d = dist(iPoint, jPoint);
279 setDist(d);
281 }
282 else if (_router->InvisibilityGrph)
283 {
284 #if 0
285 db_printf("%d, %d, %d\n", cone1, cone2, blocker);
286 db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x,
287 (int) iInfo.point.y, (int) jInfo.point.x,
288 (int) jInfo.point.y);
289 #endif
291 // if i and j can't see each other, add blank edge
292 db_printf("\tSetting invisibility edge... \n\t\t");
293 db_print();
294 addBlocker(blocker);
295 }
296 }
299 int EdgeInf::firstBlocker(void)
300 {
301 ShapeSet ss = ShapeSet();
303 Point& pti = _v1->point;
304 Point& ptj = _v2->point;
305 VertID& iID = _v1->id;
306 VertID& jID = _v2->id;
308 ContainsMap &contains = _router->contains;
309 if (!(iID.isShape))
310 {
311 ss.insert(contains[iID].begin(), contains[iID].end());
312 }
313 if (!(jID.isShape))
314 {
315 ss.insert(contains[jID].begin(), contains[jID].end());
316 }
318 VertInf *last = _router->vertices.end();
319 for (VertInf *k = _router->vertices.shapesBegin(); k != last; )
320 {
321 VertID kID = k->id;
322 if ((ss.find(kID.objID) != ss.end()))
323 {
324 unsigned int shapeID = kID.objID;
325 db_printf("Endpoint is inside shape %u so ignore shape edges.\n",
326 kID.objID);
327 // One of the endpoints is inside this shape so ignore it.
328 while ((k != last) && (k->id.objID == shapeID))
329 {
330 // And skip the other vertices from this shape.
331 k = k->lstNext;
332 }
333 continue;
334 }
335 Point& kPoint = k->point;
336 Point& kPrevPoint = k->shPrev->point;
338 if (segmentIntersect(pti, ptj, kPrevPoint, kPoint))
339 {
340 ss.clear();
341 return kID.objID;
342 }
343 k = k->lstNext;
344 }
345 ss.clear();
346 return 0;
347 }
350 bool EdgeInf::isBetween(VertInf *i, VertInf *j)
351 {
352 if ( ((i == _v1) && (j == _v2)) ||
353 ((i == _v2) && (j == _v1)) )
354 {
355 return true;
356 }
357 return false;
358 }
361 VertInf *EdgeInf::otherVert(VertInf *vert)
362 {
363 assert((vert == _v1) || (vert == _v2));
365 if (vert == _v1)
366 {
367 return _v2;
368 }
369 return _v1;
370 }
373 EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
374 {
375 Router *router = i->_router;
376 EdgeInf *edge = NULL;
378 if (knownNew)
379 {
380 assert(existingEdge(i, j) == NULL);
381 edge = new EdgeInf(i, j);
382 }
383 else
384 {
385 edge = existingEdge(i, j);
386 if (edge == NULL)
387 {
388 edge = new EdgeInf(i, j);
389 }
390 }
391 edge->checkVis();
392 if (!(edge->_added) && !(router->InvisibilityGrph))
393 {
394 delete edge;
395 edge = NULL;
396 }
398 return edge;
399 }
402 EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
403 {
404 VertInf *selected = NULL;
406 if (i->visListSize <= j->visListSize)
407 {
408 selected = i;
409 }
410 else
411 {
412 selected = j;
413 }
415 EdgeInfList& visList = selected->visList;
416 EdgeInfList::iterator finish = visList.end();
417 for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
418 ++edge)
419 {
420 if ((*edge)->isBetween(i, j))
421 {
422 return (*edge);
423 }
424 }
426 if (i->invisListSize <= j->invisListSize)
427 {
428 selected = i;
429 }
430 else
431 {
432 selected = j;
433 }
435 EdgeInfList& invisList = selected->invisList;
436 finish = invisList.end();
437 for (EdgeInfList::iterator edge = invisList.begin(); edge != finish;
438 ++edge)
439 {
440 if ((*edge)->isBetween(i, j))
441 {
442 return (*edge);
443 }
444 }
446 return NULL;
447 }
450 //===========================================================================
453 EdgeList::EdgeList()
454 : _firstEdge(NULL)
455 , _lastEdge(NULL)
456 , _count(0)
457 {
458 }
461 void EdgeList::addEdge(EdgeInf *edge)
462 {
463 if (_firstEdge == NULL)
464 {
465 assert(_lastEdge == NULL);
467 _lastEdge = edge;
468 _firstEdge = edge;
470 edge->lstPrev = NULL;
471 edge->lstNext = NULL;
472 }
473 else
474 {
475 assert(_lastEdge != NULL);
477 _lastEdge->lstNext = edge;
478 edge->lstPrev = _lastEdge;
480 _lastEdge = edge;
482 edge->lstNext = NULL;
483 }
484 _count++;
485 }
488 void EdgeList::removeEdge(EdgeInf *edge)
489 {
490 if (edge->lstPrev)
491 {
492 edge->lstPrev->lstNext = edge->lstNext;
493 }
494 if (edge->lstNext)
495 {
496 edge->lstNext->lstPrev = edge->lstPrev;
497 }
498 if (edge == _lastEdge)
499 {
500 _lastEdge = edge->lstPrev;
501 if (edge == _firstEdge)
502 {
503 _firstEdge = NULL;
504 }
505 }
506 else if (edge == _firstEdge)
507 {
508 _firstEdge = edge->lstNext;
509 }
512 edge->lstPrev = NULL;
513 edge->lstNext = NULL;
515 _count--;
516 }
519 EdgeInf *EdgeList::begin(void)
520 {
521 return _firstEdge;
522 }
525 EdgeInf *EdgeList::end(void)
526 {
527 return NULL;
528 }
531 }