← Back to branch summary

~valavanisalex/ubuntu/precise/inkscape/fix-943984

« back to all changes in this revision

Viewing changes to inkscape-0.47pre1/src/libavoid/vertices.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Bryce Harrington
  • Date: 2009-07-02 17:09:45 UTC
  • mfrom: (1.1.9 upstream)
  • Revision ID: james.westby@ubuntu.com-20090702170945-nn6d6zswovbwju1t
Tags: 0.47~pre1-0ubuntu1
https://launchpad.net/bugs/348842
https://launchpad.net/bugs/391149
* New upstream release.
  - Don't constrain maximization on small resolution devices (pre0)
    (LP: #348842)
  - Fixes segfault on startup (pre0)
    (LP: #391149)

Show diffs side-by-side

added added

removed removed

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