← Back to branch summary

~vaifrax/inkscape/bugfix170049

« back to all changes in this revision

Viewing changes to src/libavoid/vertices.cpp

  • Committer: mental
  • Date: 2006-01-16 02:36:01 UTC
  • Revision ID: mental@users.sourceforge.net-20060116023601-wkr0h7edl5veyudq
moving trunk for module inkscape

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libavoid/vertices.cpp
 
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
*/
 
22
 
 
23
#include "libavoid/geometry.h"
 
24
#include "libavoid/graph.h"  // For alertConns
 
25
#include "libavoid/debug.h"
 
26
 
 
27
 
 
28
 
 
29
namespace Avoid {
 
30
 
 
31
 
 
32
ContainsMap contains;
 
33
 
 
34
 
 
35
VertID::VertID()
 
36
{
 
37
}
 
38
 
 
39
 
 
40
VertID::VertID(unsigned int id, bool s, int n)
 
41
    : objID(id)
 
42
    , isShape(s)
 
43
    , vn(n)
 
44
{
 
45
}
 
46
 
 
47
 
 
48
VertID::VertID(const VertID& other)
 
49
    : objID(other.objID)
 
50
    , isShape(other.isShape)
 
51
    , vn(other.vn)
 
52
{
 
53
}
 
54
 
 
55
 
 
56
VertID& VertID::operator= (const VertID& rhs)
 
57
{
 
58
    // Gracefully handle self assignment
 
59
    //if (this == &rhs) return *this;
 
60
 
 
61
    objID = rhs.objID;
 
62
    isShape = rhs.isShape;
 
63
    vn = rhs.vn;
 
64
 
 
65
    return *this;
 
66
}
 
67
 
 
68
 
 
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
}
 
78
 
 
79
 
 
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
}
 
89
 
 
90
 
 
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
}
 
100
 
 
101
 
 
102
VertID VertID::operator+(const int& rhs) const
 
103
{
 
104
    return VertID(objID, isShape, vn + rhs);
 
105
}
 
106
 
 
107
 
 
108
VertID VertID::operator-(const int& rhs) const
 
109
{
 
110
    return VertID(objID, isShape, vn - rhs);
 
111
}
 
112
 
 
113
 
 
114
VertID& VertID::operator++(int)
 
115
{
 
116
    vn += 1;
 
117
    return *this;
 
118
}
 
119
 
 
120
 
 
121
void VertID::print(FILE *file) const
 
122
{
 
123
    fprintf(file, "[%u,%d]", objID, vn);
 
124
}
 
125
 
 
126
 
 
127
void VertID::db_print(void) const
 
128
{
 
129
    db_printf("[%u,%d]", objID, vn);
 
130
}
 
131
 
 
132
 
 
133
const int VertID::src = 1;
 
134
const int VertID::tar = 2;
 
135
 
 
136
 
 
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
}
 
150
 
 
151
 
 
152
void VertInf::Reset(const Point& vpoint)
 
153
{
 
154
    point = vpoint;
 
155
}
 
156
 
 
157
 
 
158
void VertInf::removeFromGraph(const bool isConnVert)
 
159
{
 
160
    if (isConnVert)
 
161
    {
 
162
        assert(!(id.isShape));
 
163
    }
 
164
 
 
165
    VertInf *tmp = this;
 
166
 
 
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
    }
 
177
 
 
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
}
 
186
 
 
187
 
 
188
bool directVis(VertInf *src, VertInf *dst)
 
189
{
 
190
    ShapeSet ss = ShapeSet();
 
191
 
 
192
    Point& p = src->point;
 
193
    Point& q = dst->point;
 
194
 
 
195
    VertID& pID = src->id;
 
196
    VertID& qID = dst->id;
 
197
 
 
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
    }
 
206
 
 
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
}
 
222
 
 
223
 
 
224
VertInfList::VertInfList()
 
225
    : _firstShapeVert(NULL)
 
226
    , _firstConnVert(NULL)
 
227
    , _lastShapeVert(NULL)
 
228
    , _lastConnVert(NULL)
 
229
    , _shapeVertices(0)
 
230
    , _connVertices(0)
 
231
{
 
232
}
 
233
 
 
234
 
 
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)
 
252
 
 
253
 
 
254
void VertInfList::addVertex(VertInf *vert)
 
255
{
 
256
    checkVertInfListConditions();
 
257
    assert(vert->lstPrev == NULL);
 
258
    assert(vert->lstNext == NULL);
 
259
 
 
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;
 
268
 
 
269
            // Make front
 
270
            _firstConnVert = vert;
 
271
        }
 
272
        else
 
273
        {
 
274
            // Make front and back
 
275
            _firstConnVert = vert;
 
276
            _lastConnVert = vert;
 
277
 
 
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;
 
291
 
 
292
            // Make back
 
293
            _lastShapeVert = vert;
 
294
        }
 
295
        else
 
296
        {
 
297
            // Make first and last
 
298
            _firstShapeVert = vert;
 
299
            _lastShapeVert = vert;
 
300
 
 
301
            // Join with conns list
 
302
            if (_lastConnVert)
 
303
            {
 
304
                assert (_lastConnVert->lstNext == NULL);
 
305
 
 
306
                _lastConnVert->lstNext = vert;
 
307
            }
 
308
        }
 
309
        _shapeVertices++;
 
310
    }
 
311
    checkVertInfListConditions();
 
312
}
 
313
 
 
314
 
 
315
void VertInfList::removeVertex(VertInf *vert)
 
316
{
 
317
    // Conditions for correct data structure
 
318
    checkVertInfListConditions();
 
319
 
 
320
    if (!(vert->id.isShape))
 
321
    {
 
322
        // A Connector vertex
 
323
        if (vert == _firstConnVert)
 
324
        {
 
325
 
 
326
            if (vert == _lastConnVert)
 
327
            {
 
328
                _firstConnVert = NULL;
 
329
                _lastConnVert = NULL;
 
330
            }
 
331
            else
 
332
            {
 
333
                // Set new first
 
334
                _firstConnVert = _firstConnVert->lstNext;
 
335
 
 
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;
 
347
 
 
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;
 
365
 
 
366
            if (vert == _firstShapeVert)
 
367
            {
 
368
                _firstShapeVert = NULL;
 
369
                if (_lastConnVert)
 
370
                {
 
371
                    _lastConnVert->lstNext = NULL;
 
372
                }
 
373
            }
 
374
 
 
375
            if (_lastShapeVert)
 
376
            {
 
377
                _lastShapeVert->lstNext = NULL;
 
378
            }
 
379
        }
 
380
        else if (vert == _firstShapeVert)
 
381
        {
 
382
            // Set new first
 
383
            _firstShapeVert = _firstShapeVert->lstNext;
 
384
 
 
385
            // Correct the last conn vertex
 
386
            if (_lastConnVert)
 
387
            {
 
388
                _lastConnVert->lstNext = _firstShapeVert;
 
389
            }
 
390
 
 
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;
 
405
 
 
406
    checkVertInfListConditions();
 
407
}
 
408
 
 
409
 
 
410
VertInf *VertInfList::shapesBegin(void)
 
411
{
 
412
    return _firstShapeVert;
 
413
}
 
414
 
 
415
 
 
416
VertInf *VertInfList::connsBegin(void)
 
417
{
 
418
    if (_firstConnVert)
 
419
    {
 
420
        return _firstConnVert;
 
421
    }
 
422
    // No connector vertices
 
423
    return _firstShapeVert;
 
424
}
 
425
 
 
426
 
 
427
VertInf *VertInfList::end(void)
 
428
{
 
429
    return NULL;
 
430
}
 
431
 
 
432
 
 
433
VertInfList vertices;
 
434
 
 
435
 
 
436
}
 
437
 
 
438