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-2005 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/geometry.h"
24 #include "libavoid/graph.h" // For alertConns
25 #include "libavoid/debug.h"
29 namespace Avoid {
32 ContainsMap contains;
35 VertID::VertID()
36 {
37 }
40 VertID::VertID(unsigned int id, bool s, int n)
41 : objID(id)
42 , isShape(s)
43 , vn(n)
44 {
45 }
48 VertID::VertID(const VertID& other)
49 : objID(other.objID)
50 , isShape(other.isShape)
51 , vn(other.vn)
52 {
53 }
56 VertID& VertID::operator= (const VertID& rhs)
57 {
58 // Gracefully handle self assignment
59 //if (this == &rhs) return *this;
61 objID = rhs.objID;
62 isShape = rhs.isShape;
63 vn = rhs.vn;
65 return *this;
66 }
69 bool VertID::operator==(const VertID& rhs) const
70 {
71 if ((objID != rhs.objID) || (vn != rhs.vn))
72 {
73 return false;
74 }
75 assert(isShape == rhs.isShape);
76 return true;
77 }
80 bool VertID::operator!=(const VertID& rhs) const
81 {
82 if ((objID != rhs.objID) || (vn != rhs.vn))
83 {
84 return true;
85 }
86 assert(isShape == rhs.isShape);
87 return false;
88 }
91 bool VertID::operator<(const VertID& rhs) const
92 {
93 if ((objID < rhs.objID) ||
94 ((objID == rhs.objID) && (vn < rhs.vn)))
95 {
96 return true;
97 }
98 return false;
99 }
102 VertID VertID::operator+(const int& rhs) const
103 {
104 return VertID(objID, isShape, vn + rhs);
105 }
108 VertID VertID::operator-(const int& rhs) const
109 {
110 return VertID(objID, isShape, vn - rhs);
111 }
114 VertID& VertID::operator++(int)
115 {
116 vn += 1;
117 return *this;
118 }
121 void VertID::print(FILE *file) const
122 {
123 fprintf(file, "[%u,%d]", objID, vn);
124 }
127 void VertID::db_print(void) const
128 {
129 db_printf("[%u,%d]", objID, vn);
130 }
133 const int VertID::src = 1;
134 const int VertID::tar = 2;
137 VertInf::VertInf(const VertID& vid, const Point& vpoint)
138 : id(vid)
139 , point(vpoint)
140 , lstPrev(NULL)
141 , lstNext(NULL)
142 , shPrev(NULL)
143 , shNext(NULL)
144 , visListSize(0)
145 , invisListSize(0)
146 , pathNext(NULL)
147 , pathDist(0)
148 {
149 }
152 void VertInf::Reset(const Point& vpoint)
153 {
154 point = vpoint;
155 }
158 void VertInf::removeFromGraph(const bool isConnVert)
159 {
160 if (isConnVert)
161 {
162 assert(!(id.isShape));
163 }
165 VertInf *tmp = this;
167 // For each vertex.
168 EdgeInfList& visList = tmp->visList;
169 EdgeInfList::iterator finish = visList.end();
170 EdgeInfList::iterator edge;
171 while ((edge = visList.begin()) != finish)
172 {
173 // Remove each visibility edge
174 (*edge)->alertConns();
175 delete (*edge);
176 }
178 EdgeInfList& invisList = tmp->invisList;
179 finish = invisList.end();
180 while ((edge = invisList.begin()) != finish)
181 {
182 // Remove each invisibility edge
183 delete (*edge);
184 }
185 }
188 bool directVis(VertInf *src, VertInf *dst)
189 {
190 ShapeSet ss = ShapeSet();
192 Point& p = src->point;
193 Point& q = dst->point;
195 VertID& pID = src->id;
196 VertID& qID = dst->id;
198 if (!(pID.isShape))
199 {
200 ss.insert(contains[pID].begin(), contains[pID].end());
201 }
202 if (!(qID.isShape))
203 {
204 ss.insert(contains[qID].begin(), contains[qID].end());
205 }
207 // The "beginning" should be the first shape vertex, rather
208 // than an endpoint, which are also stored in "vertices".
209 VertInf *endVert = vertices.end();
210 for (VertInf *k = vertices.shapesBegin(); k != endVert; k = k->lstNext)
211 {
212 if ((ss.find(k->id.objID) == ss.end()))
213 {
214 if (segmentIntersect(p, q, k->point, k->shNext->point))
215 {
216 return false;
217 }
218 }
219 }
220 return true;
221 }
224 VertInfList::VertInfList()
225 : _firstShapeVert(NULL)
226 , _firstConnVert(NULL)
227 , _lastShapeVert(NULL)
228 , _lastConnVert(NULL)
229 , _shapeVertices(0)
230 , _connVertices(0)
231 {
232 }
235 #define checkVertInfListConditions() \
236 do { \
237 assert((!_firstConnVert && (_connVertices == 0)) || \
238 ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \
239 assert((!_firstShapeVert && (_shapeVertices == 0)) || \
240 ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \
241 assert(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
242 assert(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
243 assert((!_firstConnVert && !_lastConnVert) || \
244 (_firstConnVert && _lastConnVert) ); \
245 assert((!_firstShapeVert && !_lastShapeVert) || \
246 (_firstShapeVert && _lastShapeVert) ); \
247 assert(!_firstShapeVert || _firstShapeVert->id.isShape); \
248 assert(!_lastShapeVert || _lastShapeVert->id.isShape); \
249 assert(!_firstConnVert || !(_firstConnVert->id.isShape)); \
250 assert(!_lastConnVert || !(_lastConnVert->id.isShape)); \
251 } while(0)
254 void VertInfList::addVertex(VertInf *vert)
255 {
256 checkVertInfListConditions();
257 assert(vert->lstPrev == NULL);
258 assert(vert->lstNext == NULL);
260 if (!(vert->id.isShape))
261 {
262 // A Connector vertex
263 if (_firstConnVert)
264 {
265 // Join with previous front
266 vert->lstNext = _firstConnVert;
267 _firstConnVert->lstPrev = vert;
269 // Make front
270 _firstConnVert = vert;
271 }
272 else
273 {
274 // Make front and back
275 _firstConnVert = vert;
276 _lastConnVert = vert;
278 // Link to front of shapes list
279 vert->lstNext = _firstShapeVert;
280 }
281 _connVertices++;
282 }
283 else // if (vert->id.shape > 0)
284 {
285 // A Shape vertex
286 if (_lastShapeVert)
287 {
288 // Join with previous back
289 vert->lstPrev = _lastShapeVert;
290 _lastShapeVert->lstNext = vert;
292 // Make back
293 _lastShapeVert = vert;
294 }
295 else
296 {
297 // Make first and last
298 _firstShapeVert = vert;
299 _lastShapeVert = vert;
301 // Join with conns list
302 if (_lastConnVert)
303 {
304 assert (_lastConnVert->lstNext == NULL);
306 _lastConnVert->lstNext = vert;
307 }
308 }
309 _shapeVertices++;
310 }
311 checkVertInfListConditions();
312 }
315 void VertInfList::removeVertex(VertInf *vert)
316 {
317 // Conditions for correct data structure
318 checkVertInfListConditions();
320 if (!(vert->id.isShape))
321 {
322 // A Connector vertex
323 if (vert == _firstConnVert)
324 {
326 if (vert == _lastConnVert)
327 {
328 _firstConnVert = NULL;
329 _lastConnVert = NULL;
330 }
331 else
332 {
333 // Set new first
334 _firstConnVert = _firstConnVert->lstNext;
336 if (_firstConnVert)
337 {
338 // Set previous
339 _firstConnVert->lstPrev = NULL;
340 }
341 }
342 }
343 else if (vert == _lastConnVert)
344 {
345 // Set new last
346 _lastConnVert = _lastConnVert->lstPrev;
348 // Make last point to shapes list
349 _lastConnVert->lstNext = _firstShapeVert;
350 }
351 else
352 {
353 vert->lstNext->lstPrev = vert->lstPrev;
354 vert->lstPrev->lstNext = vert->lstNext;
355 }
356 _connVertices--;
357 }
358 else // if (vert->id.shape > 0)
359 {
360 // A Shape vertex
361 if (vert == _lastShapeVert)
362 {
363 // Set new last
364 _lastShapeVert = _lastShapeVert->lstPrev;
366 if (vert == _firstShapeVert)
367 {
368 _firstShapeVert = NULL;
369 if (_lastConnVert)
370 {
371 _lastConnVert->lstNext = NULL;
372 }
373 }
375 if (_lastShapeVert)
376 {
377 _lastShapeVert->lstNext = NULL;
378 }
379 }
380 else if (vert == _firstShapeVert)
381 {
382 // Set new first
383 _firstShapeVert = _firstShapeVert->lstNext;
385 // Correct the last conn vertex
386 if (_lastConnVert)
387 {
388 _lastConnVert->lstNext = _firstShapeVert;
389 }
391 if (_firstShapeVert)
392 {
393 _firstShapeVert->lstPrev = NULL;
394 }
395 }
396 else
397 {
398 vert->lstNext->lstPrev = vert->lstPrev;
399 vert->lstPrev->lstNext = vert->lstNext;
400 }
401 _shapeVertices--;
402 }
403 vert->lstPrev = NULL;
404 vert->lstNext = NULL;
406 checkVertInfListConditions();
407 }
410 VertInf *VertInfList::shapesBegin(void)
411 {
412 return _firstShapeVert;
413 }
416 VertInf *VertInfList::connsBegin(void)
417 {
418 if (_firstConnVert)
419 {
420 return _firstConnVert;
421 }
422 // No connector vertices
423 return _firstShapeVert;
424 }
427 VertInf *VertInfList::end(void)
428 {
429 return NULL;
430 }
433 VertInfList vertices;
436 }