← Back to branch summary

~ubuntu-branches/ubuntu/precise/inkscape/precise-updates

« back to all changes in this revision

Viewing changes to src/libavoid/graph.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Alex Valavanis
  • Date: 2010-09-12 19:44:58 UTC
  • mfrom: (1.1.12 upstream) (45.1.3 maverick)
  • Revision ID: james.westby@ubuntu.com-20100912194458-4sjwmbl7dlsrk5dc
Tags: 0.48.0-1ubuntu1
https://launchpad.net/bugs/628048
https://launchpad.net/bugs/401567
https://launchpad.net/bugs/456248
https://launchpad.net/bugs/463602
https://launchpad.net/bugs/591986
https://launchpad.net/bugs/513319
* Merge with Debian unstable (LP: #628048, LP: #401567, LP: #456248, 
  LP: #463602, LP: #591986)
* debian/control: 
  - Ubuntu maintainers
  - Promote python-lxml, python-numpy, python-uniconvertor to Recommends.
  - Demote pstoedit to Suggests (universe package).
  - Suggests ttf-dejavu instead of ttf-bitstream-vera (LP: #513319)
* debian/rules:
  - Run intltool-update on build (Ubuntu-specific).
  - Add translation domain to .desktop files (Ubuntu-specific).
* debian/dirs:
  - Add usr/share/pixmaps.  Allow inkscape.xpm installation
* drop 50-poppler-API.dpatch (now upstream)
* drop 51-paste-in-unwritable-directory.dpatch (now upstream) 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libavoid/graph.cpp
2
2
 * vim: ts=4 sw=4 et tw=0 wm=0
3
3
 *
4
4
 * libavoid - Fast, Incremental, Object-avoiding Line Router
5
 
 * Copyright (C) 2004-2006  Michael Wybrow <mjwybrow@users.sourceforge.net>
 
5
 *
 
6
 * Copyright (C) 2004-2009  Monash University
6
7
 *
7
8
 * This library is free software; you can redistribute it and/or
8
9
 * modify it under the terms of the GNU Lesser General Public
9
10
 * License as published by the Free Software Foundation; either
10
11
 * version 2.1 of the License, or (at your option) any later version.
 
12
 * See the file LICENSE.LGPL distributed with the library.
 
13
 *
 
14
 * Licensees holding a valid commercial license may use this file in
 
15
 * accordance with the commercial license agreement provided with the 
 
16
 * library.
11
17
 *
12
18
 * This library is distributed in the hope that it will be useful,
13
19
 * 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
 
 *
 
20
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 
21
 *
 
22
 * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
21
23
*/
22
24
 
 
25
 
 
26
#include <cmath>
 
27
 
23
28
#include "libavoid/debug.h"
24
29
#include "libavoid/graph.h"
25
30
#include "libavoid/connector.h"
26
31
#include "libavoid/geometry.h"
27
 
#include "libavoid/polyutil.h"
28
32
#include "libavoid/timer.h"
29
33
#include "libavoid/vertices.h"
30
34
#include "libavoid/router.h"
 
35
#include "libavoid/assertions.h"
31
36
 
32
 
#include <math.h>
33
37
 
34
38
using std::pair;
35
39
 
36
40
namespace Avoid {
37
41
 
38
42
 
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)
 
43
EdgeInf::EdgeInf(VertInf *v1, VertInf *v2, const bool orthogonal)
 
44
    : lstPrev(NULL),
 
45
      lstNext(NULL),
 
46
      _blocker(0),
 
47
      _router(NULL),
 
48
      _added(false),
 
49
      _visible(false),
 
50
      _orthogonal(orthogonal),
 
51
      _v1(v1),
 
52
      _v2(v2),
 
53
      _dist(-1)
49
54
{
50
55
    // Not passed NULL values.
51
 
    assert(v1 && v2);
 
56
    COLA_ASSERT(v1 && v2);
52
57
 
53
58
    // We are in the same instance
54
 
    assert(_v1->_router == _v2->_router);
 
59
    COLA_ASSERT(_v1->_router == _v2->_router);
55
60
    _router = _v1->_router;
56
61
 
57
62
    _conns.clear();
67
72
}
68
73
 
69
74
 
 
75
// Gives an order value between 0 and 3 for the point c, given the last
 
76
// segment was from a to b.  Returns the following value:
 
77
//    0 : Point c is directly backwards from point b.
 
78
//    1 : Point c is a left-hand 90 degree turn.
 
79
//    2 : Point c is a right-hand 90 degree turn.
 
80
//    3 : Point c is straight ahead (collinear).
 
81
//
 
82
static inline int orthogTurnOrder(const Point& a, const Point& b, 
 
83
        const Point& c)
 
84
{
 
85
    // We should only be calling this with orthogonal points, 
 
86
    COLA_ASSERT((c.x == b.x) || (c.y == b.y));
 
87
    COLA_ASSERT((a.x == b.x) || (a.y == b.y));
 
88
 
 
89
    int direction = vecDir(a, b, c);
 
90
 
 
91
    if (direction > 0)
 
92
    {
 
93
        // Counterclockwise := left
 
94
        return 1;
 
95
    }
 
96
    else if (direction < 0)
 
97
    {
 
98
        // Clockwise := right
 
99
        return 2;
 
100
    }
 
101
 
 
102
    if (b.x == c.x)
 
103
    {
 
104
        if ( ((a.y < b.y) && (c.y < b.y)) || 
 
105
             ((a.y > b.y) && (c.y > b.y)) ) 
 
106
        {
 
107
            // Behind.
 
108
            return 0;
 
109
        }
 
110
    }
 
111
    else
 
112
    {
 
113
        if ( ((a.x < b.x) && (c.x < b.x)) || 
 
114
             ((a.x > b.x) && (c.x > b.x)) ) 
 
115
        {
 
116
            // Behind.
 
117
            return 0;
 
118
        }
 
119
    }
 
120
 
 
121
    // Ahead.
 
122
    return 3;
 
123
}
 
124
 
 
125
 
 
126
// Returns a less than operation for a set exploration order for orthogonal
 
127
// searching.  Forward, then left, then right.  Or if there is no previous 
 
128
// point, then the order is north, east, south, then west.
 
129
// Note: This method assumes the two Edges that share a common point.
 
130
bool EdgeInf::rotationLessThan(const VertInf *lastV, const EdgeInf *rhs) const
 
131
{
 
132
    if ((_v1 == rhs->_v1) && (_v2 == rhs->_v2))
 
133
    {
 
134
        // Effectively the same visibility edge, so they are equal.
 
135
        return false;
 
136
    }
 
137
    VertInf *lhsV = NULL, *rhsV = NULL, *commonV = NULL;
 
138
    
 
139
    // Determine common Point and the comparison point on the left- and
 
140
    // the right-hand-side.
 
141
    if (_v1 == rhs->_v1)
 
142
    {
 
143
        commonV = _v1;
 
144
        lhsV = _v2;
 
145
        rhsV = rhs->_v2;
 
146
    }
 
147
    else if (_v1 == rhs->_v2)
 
148
    {
 
149
        commonV = _v1;
 
150
        lhsV = _v2;
 
151
        rhsV = rhs->_v1;
 
152
    }
 
153
    else if (_v2 == rhs->_v1)
 
154
    {
 
155
        commonV = _v2;
 
156
        lhsV = _v1;
 
157
        rhsV = rhs->_v2;
 
158
    }
 
159
    else if (_v2 == rhs->_v2)
 
160
    {
 
161
        commonV = _v2;
 
162
        lhsV = _v1;
 
163
        rhsV = rhs->_v1;
 
164
    }
 
165
 
 
166
    const Point& lhsPt = lhsV->point;
 
167
    const Point& rhsPt = rhsV->point;
 
168
    const Point& commonPt = commonV->point;
 
169
    
 
170
    // If no lastPt, use one directly to the left;
 
171
    Point lastPt = (lastV) ? lastV->point : Point(commonPt.x - 10,  commonPt.y);
 
172
 
 
173
    int lhsVal = orthogTurnOrder(lastPt, commonPt, lhsPt);
 
174
    int rhsVal = orthogTurnOrder(lastPt, commonPt, rhsPt);
 
175
 
 
176
    return lhsVal < rhsVal;
 
177
}
 
178
 
 
179
 
70
180
void EdgeInf::makeActive(void)
71
181
{
72
 
    assert(_added == false);
 
182
    COLA_ASSERT(_added == false);
73
183
 
74
 
    if (_visible)
 
184
    if (_orthogonal)
75
185
    {
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++;
 
186
        COLA_ASSERT(_visible);
 
187
        _router->visOrthogGraph.addEdge(this);
 
188
        _pos1 = _v1->orthogVisList.insert(_v1->orthogVisList.begin(), this);
 
189
        _v1->orthogVisListSize++;
 
190
        _pos2 = _v2->orthogVisList.insert(_v2->orthogVisList.begin(), this);
 
191
        _v2->orthogVisListSize++;
81
192
    }
82
 
    else // if (invisible)
 
193
    else
83
194
    {
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++;
 
195
        if (_visible)
 
196
        {
 
197
            _router->visGraph.addEdge(this);
 
198
            _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
 
199
            _v1->visListSize++;
 
200
            _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
 
201
            _v2->visListSize++;
 
202
        }
 
203
        else // if (invisible)
 
204
        {
 
205
            _router->invisGraph.addEdge(this);
 
206
            _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
 
207
            _v1->invisListSize++;
 
208
            _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
 
209
            _v2->invisListSize++;
 
210
        }
89
211
    }
90
212
    _added = true;
91
213
}
93
215
 
94
216
void EdgeInf::makeInactive(void)
95
217
{
96
 
    assert(_added == true);
 
218
    COLA_ASSERT(_added == true);
97
219
 
98
 
    if (_visible)
 
220
    if (_orthogonal)
99
221
    {
100
 
        _router->visGraph.removeEdge(this);
101
 
        _v1->visList.erase(_pos1);
102
 
        _v1->visListSize--;
103
 
        _v2->visList.erase(_pos2);
104
 
        _v2->visListSize--;
 
222
        COLA_ASSERT(_visible);
 
223
        _router->visOrthogGraph.removeEdge(this);
 
224
        _v1->orthogVisList.erase(_pos1);
 
225
        _v1->orthogVisListSize--;
 
226
        _v2->orthogVisList.erase(_pos2);
 
227
        _v2->orthogVisListSize--;
105
228
    }
106
 
    else // if (invisible)
 
229
    else
107
230
    {
108
 
        _router->invisGraph.removeEdge(this);
109
 
        _v1->invisList.erase(_pos1);
110
 
        _v1->invisListSize--;
111
 
        _v2->invisList.erase(_pos2);
112
 
        _v2->invisListSize--;
 
231
        if (_visible)
 
232
        {
 
233
            _router->visGraph.removeEdge(this);
 
234
            _v1->visList.erase(_pos1);
 
235
            _v1->visListSize--;
 
236
            _v2->visList.erase(_pos2);
 
237
            _v2->visListSize--;
 
238
        }
 
239
        else // if (invisible)
 
240
        {
 
241
            _router->invisGraph.removeEdge(this);
 
242
            _v1->invisList.erase(_pos1);
 
243
            _v1->invisListSize--;
 
244
            _v2->invisList.erase(_pos2);
 
245
            _v2->invisListSize--;
 
246
        }
113
247
    }
114
248
    _blocker = 0;
115
249
    _conns.clear();
119
253
 
120
254
void EdgeInf::setDist(double dist)
121
255
{
122
 
    //assert(dist != 0);
 
256
    //COLA_ASSERT(dist != 0);
123
257
 
124
258
    if (_added && !_visible)
125
259
    {
126
260
        makeInactive();
 
261
        COLA_ASSERT(!_added);
127
262
    }
128
263
    if (!_added)
129
264
    {
135
270
}
136
271
 
137
272
 
 
273
bool EdgeInf::added(void)
 
274
{
 
275
    return _added;
 
276
}
 
277
 
 
278
 
138
279
void EdgeInf::alertConns(void)
139
280
{
140
281
    FlagList::iterator finish = _conns.end();
161
302
 
162
303
void EdgeInf::addBlocker(int b)
163
304
{
164
 
    assert(_router->InvisibilityGrph);
 
305
    COLA_ASSERT(_router->InvisibilityGrph);
165
306
 
166
307
    if (_added && _visible)
167
308
    {
168
309
        makeInactive();
 
310
        COLA_ASSERT(!_added);
169
311
    }
170
312
    if (!_added)
171
313
    {
232
374
        cone1 = inValidRegion(_router->IgnoreRegions, i->shPrev->point,
233
375
                iPoint, i->shNext->point, jPoint);
234
376
    }
235
 
    else
 
377
    else if (_router->IgnoreRegions == false)
236
378
    {
 
379
        // If Ignoring regions then this case is already caught by 
 
380
        // the invalid regions, so only check it when not ignoring
 
381
        // regions.
237
382
        ShapeSet& ss = _router->contains[iID];
238
383
 
239
384
        if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
253
398
            cone2 = inValidRegion(_router->IgnoreRegions, j->shPrev->point,
254
399
                    jPoint, j->shNext->point, iPoint);
255
400
        }
256
 
        else
 
401
        else if (_router->IgnoreRegions == false)
257
402
        {
 
403
            // If Ignoring regions then this case is already caught by 
 
404
            // the invalid regions, so only check it when not ignoring
 
405
            // regions.
258
406
            ShapeSet& ss = _router->contains[jID];
259
407
 
260
408
            if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
274
422
        db_printf("\tSetting visibility edge... \n\t\t");
275
423
        db_print();
276
424
 
277
 
        double d = dist(iPoint, jPoint);
 
425
        double d = euclideanDist(iPoint, jPoint);
278
426
 
279
427
        setDist(d);
280
428
 
316
464
    }
317
465
 
318
466
    VertInf *last = _router->vertices.end();
 
467
    unsigned int lastId = 0;
 
468
    bool seenIntersectionAtEndpoint = false;
319
469
    for (VertInf *k = _router->vertices.shapesBegin(); k != last; )
320
470
    {
321
471
        VertID kID = k->id;
322
 
        if ((ss.find(kID.objID) != ss.end()))
 
472
        if (k->id == dummyOrthogID)
323
473
        {
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
 
            }
 
474
            // Don't include orthogonal dummy vertices.
 
475
            k = k->lstNext;
333
476
            continue;
334
477
        }
 
478
        if (kID.objID != lastId)
 
479
        {
 
480
            if ((ss.find(kID.objID) != ss.end()))
 
481
            {
 
482
                unsigned int shapeID = kID.objID;
 
483
                db_printf("Endpoint is inside shape %u so ignore shape "
 
484
                        "edges.\n", kID.objID);
 
485
                // One of the endpoints is inside this shape so ignore it.
 
486
                while ((k != last) && (k->id.objID == shapeID))
 
487
                {
 
488
                    // And skip the other vertices from this shape.
 
489
                    k = k->lstNext;
 
490
                }
 
491
                continue;
 
492
            }
 
493
            seenIntersectionAtEndpoint = false;
 
494
            lastId = kID.objID;
 
495
        }
335
496
        Point& kPoint = k->point;
336
497
        Point& kPrevPoint = k->shPrev->point;
337
 
 
338
 
        if (segmentIntersect(pti, ptj, kPrevPoint, kPoint))
 
498
        if (segmentShapeIntersect(pti, ptj, kPrevPoint, kPoint, 
 
499
                    seenIntersectionAtEndpoint))
339
500
        {
340
501
            ss.clear();
341
502
            return kID.objID;
358
519
}
359
520
 
360
521
 
 
522
    // Returns true if this edge is a vertical or horizontal line segment.
 
523
bool EdgeInf::isOrthogonal(void) const
 
524
{
 
525
    return ((_v1->point.x == _v2->point.x) || 
 
526
            (_v1->point.y == _v2->point.y));
 
527
}
 
528
 
 
529
 
361
530
VertInf *EdgeInf::otherVert(VertInf *vert)
362
531
{
363
 
    assert((vert == _v1) || (vert == _v2));
 
532
    COLA_ASSERT((vert == _v1) || (vert == _v2));
364
533
 
365
534
    if (vert == _v1)
366
535
    {
372
541
 
373
542
EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
374
543
{
 
544
    // This is for polyline routing, so check we're not 
 
545
    // considering orthogonal vertices.
 
546
    COLA_ASSERT(i->id != dummyOrthogID);
 
547
    COLA_ASSERT(j->id != dummyOrthogID);
 
548
    
375
549
    Router *router = i->_router;
376
550
    EdgeInf *edge = NULL;
377
551
 
378
552
    if (knownNew)
379
553
    {
380
 
        assert(existingEdge(i, j) == NULL);
 
554
        COLA_ASSERT(existingEdge(i, j) == NULL);
381
555
        edge = new EdgeInf(i, j);
382
556
    }
383
557
    else
399
573
}
400
574
 
401
575
 
 
576
    // XXX: This function is ineffecient, and shouldn't even really be
 
577
    //      required.
402
578
EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
403
579
{
404
580
    VertInf *selected = NULL;
405
581
 
406
 
    if (i->visListSize <= j->visListSize)
407
 
    {
408
 
        selected = i;
409
 
    }
410
 
    else
411
 
    {
412
 
        selected = j;
413
 
    }
414
 
 
 
582
    // Look through poly-line visibility edges.
 
583
    selected = (i->visListSize <= j->visListSize) ? i : j;
415
584
    EdgeInfList& visList = selected->visList;
416
 
    EdgeInfList::iterator finish = visList.end();
417
 
    for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
 
585
    EdgeInfList::const_iterator finish = visList.end();
 
586
    for (EdgeInfList::const_iterator edge = visList.begin(); edge != finish;
418
587
            ++edge)
419
588
    {
420
589
        if ((*edge)->isBetween(i, j))
423
592
        }
424
593
    }
425
594
 
426
 
    if (i->invisListSize <= j->invisListSize)
427
 
    {
428
 
        selected = i;
429
 
    }
430
 
    else
431
 
    {
432
 
        selected = j;
 
595
    // Look through orthogonal visbility edges.
 
596
    selected = (i->orthogVisListSize <= j->orthogVisListSize) ? i : j;
 
597
    EdgeInfList& orthogVisList = selected->orthogVisList;
 
598
    finish = orthogVisList.end();
 
599
    for (EdgeInfList::const_iterator edge = orthogVisList.begin(); 
 
600
            edge != finish; ++edge)
 
601
    {
 
602
        if ((*edge)->isBetween(i, j))
 
603
        {
 
604
            return (*edge);
 
605
        }
433
606
    }
434
607
 
 
608
    // Look through poly-line invisbility edges.
 
609
    selected = (i->invisListSize <= j->invisListSize) ? i : j;
435
610
    EdgeInfList& invisList = selected->invisList;
436
611
    finish = invisList.end();
437
 
    for (EdgeInfList::iterator edge = invisList.begin(); edge != finish;
 
612
    for (EdgeInfList::const_iterator edge = invisList.begin(); edge != finish;
438
613
            ++edge)
439
614
    {
440
615
        if ((*edge)->isBetween(i, j))
450
625
//===========================================================================
451
626
 
452
627
 
453
 
EdgeList::EdgeList()
454
 
    : _firstEdge(NULL)
455
 
    , _lastEdge(NULL)
456
 
    , _count(0)
457
 
{
 
628
EdgeList::EdgeList(bool orthogonal)
 
629
    : _orthogonal(orthogonal),
 
630
      _firstEdge(NULL),
 
631
      _lastEdge(NULL),
 
632
      _count(0)
 
633
{
 
634
}
 
635
 
 
636
 
 
637
EdgeList::~EdgeList()
 
638
{
 
639
    clear();
 
640
}
 
641
 
 
642
 
 
643
void EdgeList::clear(void)
 
644
{
 
645
    while (_firstEdge)
 
646
    {
 
647
        delete _firstEdge;
 
648
    }
 
649
    COLA_ASSERT(_count == 0);
 
650
    _lastEdge = NULL;
 
651
}
 
652
 
 
653
 
 
654
int EdgeList::size(void) const
 
655
{
 
656
    return _count;
458
657
}
459
658
 
460
659
 
461
660
void EdgeList::addEdge(EdgeInf *edge)
462
661
{
 
662
    COLA_ASSERT(!_orthogonal || edge->isOrthogonal());
 
663
    
463
664
    if (_firstEdge == NULL)
464
665
    {
465
 
        assert(_lastEdge == NULL);
 
666
        COLA_ASSERT(_lastEdge == NULL);
466
667
 
467
668
        _lastEdge = edge;
468
669
        _firstEdge = edge;
472
673
    }
473
674
    else
474
675
    {
475
 
        assert(_lastEdge != NULL);
 
676
        COLA_ASSERT(_lastEdge != NULL);
476
677
 
477
678
        _lastEdge->lstNext = edge;
478
679
        edge->lstPrev = _lastEdge;