← Back to branch summary

~vaifrax/inkscape/bugfix170049

« back to all changes in this revision

Viewing changes to src/libavoid/graph.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/graph.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/debug.h"
 
24
#include "libavoid/graph.h"
 
25
#include "libavoid/connector.h"
 
26
#include "libavoid/polyutil.h"
 
27
#include "libavoid/timer.h"
 
28
 
 
29
#include <math.h>
 
30
 
 
31
namespace Avoid {
 
32
 
 
33
 
 
34
static int st_checked_edges = 0;
 
35
 
 
36
EdgeList visGraph;
 
37
EdgeList invisGraph;
 
38
 
 
39
 
 
40
EdgeInf::EdgeInf(VertInf *v1, VertInf *v2)
 
41
    : lstPrev(NULL)
 
42
    , lstNext(NULL)
 
43
    , _added(false)
 
44
    , _visible(false)
 
45
    , _v1(v1)
 
46
    , _v2(v2)
 
47
    , _dist(-1)
 
48
{
 
49
    _blockers.clear();
 
50
    _conns.clear();
 
51
}
 
52
 
 
53
 
 
54
EdgeInf::~EdgeInf()
 
55
{
 
56
    if (_added)
 
57
    {
 
58
        makeInactive();
 
59
    }
 
60
}
 
61
 
 
62
 
 
63
void EdgeInf::makeActive(void)
 
64
{
 
65
    assert(_added == false);
 
66
 
 
67
    if (_visible)
 
68
    {
 
69
        visGraph.addEdge(this);
 
70
        _pos1 = _v1->visList.insert(_v1->visList.begin(), this);
 
71
        _v1->visListSize++;
 
72
        _pos2 = _v2->visList.insert(_v2->visList.begin(), this);
 
73
        _v2->visListSize++;
 
74
    }
 
75
    else // if (invisible)
 
76
    {
 
77
        invisGraph.addEdge(this);
 
78
        _pos1 = _v1->invisList.insert(_v1->invisList.begin(), this);
 
79
        _v1->invisListSize++;
 
80
        _pos2 = _v2->invisList.insert(_v2->invisList.begin(), this);
 
81
        _v2->invisListSize++;
 
82
    }
 
83
    _added = true;
 
84
}
 
85
 
 
86
 
 
87
void EdgeInf::makeInactive(void)
 
88
{
 
89
    assert(_added == true);
 
90
 
 
91
    if (_visible)
 
92
    {
 
93
        visGraph.removeEdge(this);
 
94
        _v1->visList.erase(_pos1);
 
95
        _v1->visListSize--;
 
96
        _v2->visList.erase(_pos2);
 
97
        _v2->visListSize--;
 
98
    }
 
99
    else // if (invisible)
 
100
    {
 
101
        invisGraph.removeEdge(this);
 
102
        _v1->invisList.erase(_pos1);
 
103
        _v1->invisListSize--;
 
104
        _v2->invisList.erase(_pos2);
 
105
        _v2->invisListSize--;
 
106
    }
 
107
    _blockers.clear();
 
108
    _conns.clear();
 
109
    _added = false;
 
110
}
 
111
 
 
112
 
 
113
double EdgeInf::getDist(void)
 
114
{
 
115
    return _dist;
 
116
}
 
117
 
 
118
 
 
119
void EdgeInf::setDist(double dist)
 
120
{
 
121
    //assert(dist != 0);
 
122
 
 
123
    if (_added && !_visible)
 
124
    {
 
125
        makeInactive();
 
126
    }
 
127
    if (!_added)
 
128
    {
 
129
        _visible = true;
 
130
        makeActive();
 
131
    }
 
132
    _dist = dist;
 
133
    _blockers.clear();
 
134
}
 
135
 
 
136
 
 
137
void EdgeInf::alertConns(void)
 
138
{
 
139
    for (FlagList::iterator i = _conns.begin(); i != _conns.end(); ++i)
 
140
    {
 
141
        *(*i) = true;
 
142
    }
 
143
    _conns.clear();
 
144
}
 
145
 
 
146
 
 
147
void EdgeInf::addConn(bool *flag)
 
148
{
 
149
    _conns.push_back(flag);
 
150
}
 
151
 
 
152
 
 
153
void EdgeInf::addCycleBlocker(void)
 
154
{
 
155
    // Needs to be in invisibility graph.
 
156
    addBlocker(-1);
 
157
}
 
158
 
 
159
 
 
160
void EdgeInf::addBlocker(int b)
 
161
{
 
162
    assert(InvisibilityGrph);
 
163
 
 
164
    if (_added && _visible)
 
165
    {
 
166
        makeInactive();
 
167
    }
 
168
    if (!_added)
 
169
    {
 
170
        _visible = false;
 
171
        makeActive();
 
172
    }
 
173
    _dist = 0;
 
174
    _blockers.clear();
 
175
    _blockers.push_back(b);
 
176
}
 
177
 
 
178
 
 
179
bool EdgeInf::hasBlocker(int b)
 
180
{
 
181
    assert(InvisibilityGrph);
 
182
 
 
183
    ShapeList::iterator finish = _blockers.end();
 
184
    for (ShapeList::iterator it = _blockers.begin(); it != finish; ++it)
 
185
    {
 
186
        if ((*it) == -1)
 
187
        {
 
188
            alertConns();
 
189
            return true;
 
190
        }
 
191
        else if ((*it) == b)
 
192
        {
 
193
            return true;
 
194
        }
 
195
    }
 
196
    return false;
 
197
}
 
198
 
 
199
 
 
200
pair<VertID, VertID> EdgeInf::ids(void)
 
201
{
 
202
    return std::make_pair(_v1->id, _v2->id);
 
203
}
 
204
 
 
205
 
 
206
pair<Point, Point> EdgeInf::points(void)
 
207
{
 
208
    return std::make_pair(_v1->point, _v2->point);
 
209
}
 
210
 
 
211
 
 
212
void EdgeInf::db_print(void)
 
213
{
 
214
    db_printf("Edge(");
 
215
    _v1->id.db_print();
 
216
    db_printf(",");
 
217
    _v2->id.db_print();
 
218
    db_printf(")\n");
 
219
}
 
220
 
 
221
 
 
222
void EdgeInf::checkVis(void)
 
223
{
 
224
    if (_added && !_visible)
 
225
    {
 
226
        db_printf("\tChecking visibility for existing invisibility edge..."
 
227
                "\n\t\t");
 
228
        db_print();
 
229
    }
 
230
    else if (_added && _visible)
 
231
    {
 
232
        db_printf("\tChecking visibility for existing visibility edge..."
 
233
                "\n\t\t");
 
234
        db_print();
 
235
    }
 
236
 
 
237
    int blocker = 0;
 
238
    bool cone1 = true;
 
239
    bool cone2 = true;
 
240
 
 
241
    VertInf *i = _v1;
 
242
    VertInf *j = _v2;
 
243
    const VertID& iID = i->id;
 
244
    const VertID& jID = j->id;
 
245
    const Point& iPoint = i->point;
 
246
    const Point& jPoint = j->point;
 
247
 
 
248
    st_checked_edges++;
 
249
 
 
250
    if (iID.isShape)
 
251
    {
 
252
        cone1 = inValidRegion(i->shPrev->point, iPoint, i->shNext->point,
 
253
                jPoint);
 
254
    }
 
255
    else
 
256
    {
 
257
        ShapeSet& ss = contains[iID];
 
258
 
 
259
        if ((jID.isShape) && (ss.find(jID.objID) != ss.end()))
 
260
        {
 
261
            db_printf("1: Edge of bounding shape\n");
 
262
            // Don't even check this edge, it should be zero,
 
263
            // since a point in a shape can't see it's corners
 
264
            cone1 = false;
 
265
        }
 
266
    }
 
267
 
 
268
    if (cone1)
 
269
    {
 
270
        // If outside the first cone, don't even bother checking.
 
271
        if (jID.isShape)
 
272
        {
 
273
            cone2 = inValidRegion(j->shPrev->point, jPoint, j->shNext->point,
 
274
                    iPoint);
 
275
        }
 
276
        else
 
277
        {
 
278
            ShapeSet& ss = contains[jID];
 
279
 
 
280
            if ((iID.isShape) && (ss.find(iID.objID) != ss.end()))
 
281
            {
 
282
                db_printf("2: Edge of bounding shape\n");
 
283
                // Don't even check this edge, it should be zero,
 
284
                // since a point in a shape can't see it's corners
 
285
                cone2 = false;
 
286
            }
 
287
        }
 
288
    }
 
289
 
 
290
    if (cone1 && cone2 && ((blocker = firstBlocker()) == 0))
 
291
    {
 
292
 
 
293
        // if i and j see each other, add edge
 
294
        db_printf("\tSetting visibility edge... \n\t\t");
 
295
        db_print();
 
296
 
 
297
        double d = dist(iPoint, jPoint);
 
298
 
 
299
        setDist(d);
 
300
 
 
301
    }
 
302
    else if (InvisibilityGrph)
 
303
    {
 
304
#if 0
 
305
        db_printf("%d, %d, %d\n", cone1, cone2, blocker);
 
306
        db_printf("\t(%d, %d)--(%d, %d)\n", (int) iInfo.point.x,
 
307
                (int) iInfo.point.y, (int) jInfo.point.x,
 
308
                (int) jInfo.point.y);
 
309
#endif
 
310
 
 
311
        // if i and j can't see each other, add blank edge
 
312
        db_printf("\tSetting invisibility edge... \n\t\t");
 
313
        db_print();
 
314
        addBlocker(blocker);
 
315
    }
 
316
}
 
317
 
 
318
 
 
319
int EdgeInf::firstBlocker(void)
 
320
{
 
321
    ShapeSet ss = ShapeSet();
 
322
 
 
323
    Point& pti = _v1->point;
 
324
    Point& ptj = _v2->point;
 
325
    VertID& iID = _v1->id;
 
326
    VertID& jID = _v2->id;
 
327
 
 
328
    if (!(iID.isShape))
 
329
    {
 
330
        ss.insert(contains[iID].begin(), contains[iID].end());
 
331
    }
 
332
    if (!(jID.isShape))
 
333
    {
 
334
        ss.insert(contains[jID].begin(), contains[jID].end());
 
335
    }
 
336
 
 
337
    VertInf *last = vertices.end();
 
338
    for (VertInf *k = vertices.shapesBegin(); k != last; )
 
339
    {
 
340
        VertID kID = k->id;
 
341
        if ((ss.find(kID.objID) != ss.end()))
 
342
        {
 
343
            uint shapeID = kID.objID;
 
344
            db_printf("Endpoint is inside shape %u so ignore shape edges.\n",
 
345
                    kID.objID);
 
346
            // One of the endpoints is inside this shape so ignore it.
 
347
            while ((k != last) && (k->id.objID == shapeID))
 
348
            {
 
349
                // And skip the other vertices from this shape.
 
350
                k = k->lstNext;
 
351
            }
 
352
            continue;
 
353
        }
 
354
        Point& kPoint = k->point;
 
355
        Point& kPrevPoint = k->shPrev->point;
 
356
 
 
357
        if (segmentIntersect(pti, ptj, kPrevPoint, kPoint))
 
358
        {
 
359
            ss.clear();
 
360
            return kID.objID;
 
361
        }
 
362
        k = k->lstNext;
 
363
    }
 
364
    ss.clear();
 
365
    return 0;
 
366
}
 
367
 
 
368
 
 
369
bool EdgeInf::isBetween(VertInf *i, VertInf *j)
 
370
{
 
371
    if ( ((i == _v1) && (j == _v2)) ||
 
372
         ((i == _v2) && (j == _v1)) )
 
373
    {
 
374
        return true;
 
375
    }
 
376
    return false;
 
377
}
 
378
 
 
379
 
 
380
VertInf *EdgeInf::otherVert(VertInf *vert)
 
381
{
 
382
    assert((vert == _v1) || (vert == _v2));
 
383
 
 
384
    if (vert == _v1)
 
385
    {
 
386
        return _v2;
 
387
    }
 
388
    return _v1;
 
389
}
 
390
 
 
391
 
 
392
EdgeInf *EdgeInf::checkEdgeVisibility(VertInf *i, VertInf *j, bool knownNew)
 
393
{
 
394
    EdgeInf *edge = NULL;
 
395
 
 
396
    if (knownNew)
 
397
    {
 
398
        assert(existingEdge(i, j) == NULL);
 
399
        edge = new EdgeInf(i, j);
 
400
    }
 
401
    else
 
402
    {
 
403
        edge = existingEdge(i, j);
 
404
        if (edge == NULL)
 
405
        {
 
406
            edge = new EdgeInf(i, j);
 
407
        }
 
408
    }
 
409
    edge->checkVis();
 
410
    if (!(edge->_added) && !InvisibilityGrph)
 
411
    {
 
412
        delete edge;
 
413
        edge = NULL;
 
414
    }
 
415
 
 
416
    return edge;
 
417
}
 
418
 
 
419
 
 
420
EdgeInf *EdgeInf::existingEdge(VertInf *i, VertInf *j)
 
421
{
 
422
    VertInf *selected = NULL;
 
423
 
 
424
    if (i->visListSize <= j->visListSize)
 
425
    {
 
426
        selected = i;
 
427
    }
 
428
    else
 
429
    {
 
430
        selected = j;
 
431
    }
 
432
 
 
433
    EdgeInfList& visList = selected->visList;
 
434
    EdgeInfList::iterator finish = visList.end();
 
435
    for (EdgeInfList::iterator edge = visList.begin(); edge != finish;
 
436
            ++edge)
 
437
    {
 
438
        if ((*edge)->isBetween(i, j))
 
439
        {
 
440
            return (*edge);
 
441
        }
 
442
    }
 
443
 
 
444
    if (i->invisListSize <= j->invisListSize)
 
445
    {
 
446
        selected = i;
 
447
    }
 
448
    else
 
449
    {
 
450
        selected = j;
 
451
    }
 
452
 
 
453
    EdgeInfList& invisList = selected->invisList;
 
454
    finish = invisList.end();
 
455
    for (EdgeInfList::iterator edge = invisList.begin(); edge != finish;
 
456
            ++edge)
 
457
    {
 
458
        if ((*edge)->isBetween(i, j))
 
459
        {
 
460
            return (*edge);
 
461
        }
 
462
    }
 
463
 
 
464
    return NULL;
 
465
}
 
466
 
 
467
 
 
468
//===========================================================================
 
469
 
 
470
 
 
471
EdgeList::EdgeList()
 
472
    : _firstEdge(NULL)
 
473
    , _lastEdge(NULL)
 
474
    , _count(0)
 
475
{
 
476
}
 
477
 
 
478
 
 
479
void EdgeList::addEdge(EdgeInf *edge)
 
480
{
 
481
    if (_firstEdge == NULL)
 
482
    {
 
483
        assert(_lastEdge == NULL);
 
484
 
 
485
        _lastEdge = edge;
 
486
        _firstEdge = edge;
 
487
 
 
488
        edge->lstPrev = NULL;
 
489
        edge->lstNext = NULL;
 
490
    }
 
491
    else
 
492
    {
 
493
        assert(_lastEdge != NULL);
 
494
 
 
495
        _lastEdge->lstNext = edge;
 
496
        edge->lstPrev = _lastEdge;
 
497
 
 
498
        _lastEdge = edge;
 
499
 
 
500
        edge->lstNext = NULL;
 
501
    }
 
502
    _count++;
 
503
}
 
504
 
 
505
 
 
506
void EdgeList::removeEdge(EdgeInf *edge)
 
507
{
 
508
    if (edge->lstPrev)
 
509
    {
 
510
        edge->lstPrev->lstNext = edge->lstNext;
 
511
    }
 
512
    if (edge->lstNext)
 
513
    {
 
514
        edge->lstNext->lstPrev = edge->lstPrev;
 
515
    }
 
516
    if (edge == _lastEdge)
 
517
    {
 
518
        _lastEdge = edge->lstPrev;
 
519
        if (edge == _firstEdge)
 
520
        {
 
521
            _firstEdge = NULL;
 
522
        }
 
523
    }
 
524
    else if (edge == _firstEdge)
 
525
    {
 
526
        _firstEdge = edge->lstNext;
 
527
    }
 
528
 
 
529
 
 
530
    edge->lstPrev = NULL;
 
531
    edge->lstNext = NULL;
 
532
 
 
533
    _count--;
 
534
}
 
535
 
 
536
 
 
537
EdgeInf *EdgeList::begin(void)
 
538
{
 
539
    return _firstEdge;
 
540
}
 
541
 
 
542
 
 
543
EdgeInf *EdgeList::end(void)
 
544
{
 
545
    return NULL;
 
546
}
 
547
 
 
548
 
 
549
// General visibility graph utility functions
 
550
 
 
551
 
 
552
void newBlockingShape(Polygn *poly, int pid)
 
553
{
 
554
    // o  Check all visibility edges to see if this one shape
 
555
    //    blocks them.
 
556
    EdgeInf *finish = visGraph.end();
 
557
    for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
 
558
    {
 
559
        EdgeInf *tmp = iter;
 
560
        iter = iter->lstNext;
 
561
 
 
562
        if (tmp->getDist() != 0)
 
563
        {
 
564
            pair<VertID, VertID> ids(tmp->ids());
 
565
            VertID eID1 = ids.first;
 
566
            VertID eID2 = ids.second;
 
567
            pair<Point, Point> points(tmp->points());
 
568
            Point e1 = points.first;
 
569
            Point e2 = points.second;
 
570
            bool blocked = false;
 
571
 
 
572
            bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
 
573
            bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
 
574
            if (ep_in_poly1 || ep_in_poly2)
 
575
            {
 
576
                // Don't check edges that have a connector endpoint
 
577
                // and are inside the shape being added.
 
578
                continue;
 
579
            }
 
580
 
 
581
            for (int pt_i = 0; pt_i < poly->pn; pt_i++)
 
582
            {
 
583
                int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
 
584
                if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
 
585
                {
 
586
                    blocked = true;
 
587
                    break;
 
588
                }
 
589
            }
 
590
            if (blocked)
 
591
            {
 
592
                db_printf("\tRemoving newly blocked edge (by shape %3d)"
 
593
                        "... \n\t\t", pid);
 
594
                tmp->alertConns();
 
595
                tmp->db_print();
 
596
                if (InvisibilityGrph)
 
597
                {
 
598
                    tmp->addBlocker(pid);
 
599
                }
 
600
                else
 
601
                {
 
602
                    delete tmp;
 
603
                }
 
604
            }
 
605
        }
 
606
    }
 
607
}
 
608
 
 
609
 
 
610
void checkAllBlockedEdges(int pid)
 
611
{
 
612
    assert(InvisibilityGrph);
 
613
 
 
614
    for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
 
615
    {
 
616
        EdgeInf *tmp = iter;
 
617
        iter = iter->lstNext;
 
618
 
 
619
        if (tmp->hasBlocker(pid))
 
620
        {
 
621
            tmp->checkVis();
 
622
        }
 
623
    }
 
624
}
 
625
 
 
626
 
 
627
void checkAllMissingEdges(void)
 
628
{
 
629
    assert(!InvisibilityGrph);
 
630
 
 
631
    VertInf *first = NULL;
 
632
 
 
633
    if (IncludeEndpoints)
 
634
    {
 
635
        first = vertices.connsBegin();
 
636
    }
 
637
    else
 
638
    {
 
639
        first = vertices.shapesBegin();
 
640
    }
 
641
 
 
642
    VertInf *pend = vertices.end();
 
643
    for (VertInf *i = first; i != pend; i = i->lstNext)
 
644
    {
 
645
        VertID iID = i->id;
 
646
 
 
647
        // Check remaining, earlier vertices
 
648
        for (VertInf *j = first ; j != i; j = j->lstNext)
 
649
        {
 
650
            VertID jID = j->id;
 
651
            if (!(iID.isShape) && (iID.objID != jID.objID))
 
652
            {
 
653
                // Don't keep visibility between edges of different conns
 
654
                continue;
 
655
            }
 
656
 
 
657
            // See if the edge is already there?
 
658
            bool found = (EdgeInf::existingEdge(i, j) != NULL);
 
659
 
 
660
            if (!found)
 
661
            {
 
662
                // Didn't already exist, check.
 
663
                bool knownNew = true;
 
664
                EdgeInf::checkEdgeVisibility(i, j, knownNew);
 
665
            }
 
666
        }
 
667
    }
 
668
}
 
669
 
 
670
 
 
671
void generateContains(VertInf *pt)
 
672
{
 
673
    contains[pt->id].clear();
 
674
 
 
675
    ShapeRefList::iterator finish = shapeRefs.end();
 
676
    for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
 
677
    {
 
678
        Polygn poly = copyPoly(*i);
 
679
        if (inPoly(poly, pt->point))
 
680
        {
 
681
            contains[pt->id].insert((*i)->id());
 
682
        }
 
683
        freePoly(poly);
 
684
    }
 
685
}
 
686
 
 
687
 
 
688
void adjustContainsWithAdd(const Polygn& poly, const int p_shape)
 
689
{
 
690
    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
 
691
            k = k->lstNext)
 
692
    {
 
693
        if (inPoly(poly, k->point))
 
694
        {
 
695
            contains[k->id].insert(p_shape);
 
696
        }
 
697
    }
 
698
}
 
699
 
 
700
 
 
701
void adjustContainsWithDel(const int p_shape)
 
702
{
 
703
    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
 
704
            k = k->lstNext)
 
705
    {
 
706
        contains[k->id].erase(p_shape);
 
707
    }
 
708
}
 
709
 
 
710
 
 
711
// Maybe this one should be in with the connector stuff, but it may later
 
712
// need to operate on a particular section of the visibility graph so it
 
713
// may have to stay here.
 
714
//
 
715
#define MIN(a, b) (((a) <= (b)) ? (a) : (b))
 
716
#define MAX(a, b) (((a) >= (b)) ? (a) : (b))
 
717
 
 
718
#ifdef SELECTIVE_DEBUG
 
719
static double AngleAFromThreeSides(const double a, const double b,
 
720
        const double c)
 
721
{
 
722
    // returns angle A, the angle opposite from side a, in radians
 
723
    return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
 
724
}
 
725
#endif
 
726
 
 
727
void markConnectors(ShapeRef *shape)
 
728
{
 
729
    assert(SelectiveReroute);
 
730
 
 
731
    ConnRefList::iterator end = connRefs.end();
 
732
    for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
 
733
    {
 
734
        ConnRef *conn = (*it);
 
735
 
 
736
        if (conn->_route.pn == 0)
 
737
        {
 
738
            // Ignore uninitialised connectors.
 
739
            continue;
 
740
        }
 
741
 
 
742
        Point start = conn->_route.ps[0];
 
743
        Point end = conn->_route.ps[conn->_route.pn - 1];
 
744
 
 
745
        double conndist = conn->_route_dist;
 
746
 
 
747
        double estdist;
 
748
        double e1, e2;
 
749
 
 
750
        VertInf *beginV = shape->firstVert();
 
751
        VertInf *endV = shape->lastVert()->lstNext;
 
752
        for (VertInf *i = beginV; i != endV; i = i->lstNext)
 
753
        {
 
754
            const Point& p1 = i->point;
 
755
            const Point& p2 = i->shNext->point;
 
756
 
 
757
            double offy;
 
758
            double a;
 
759
            double b;
 
760
            double c;
 
761
            double d;
 
762
 
 
763
            double min;
 
764
            double max;
 
765
 
 
766
            if (p1.y == p2.y)
 
767
            {
 
768
                // Standard case
 
769
                offy = p1.y;
 
770
                a = start.x;
 
771
                b = start.y - offy;
 
772
                c = end.x;
 
773
                d = end.y - offy;
 
774
 
 
775
                min = MIN(p1.x, p2.x);
 
776
                max = MAX(p1.x, p2.x);
 
777
            }
 
778
            else if (p1.x == p2.x)
 
779
            {
 
780
                // Other Standard case
 
781
                offy = p1.x;
 
782
                a = start.y;
 
783
                b = start.x - offy;
 
784
                c = end.y;
 
785
                d = end.x - offy;
 
786
 
 
787
                min = MIN(p1.y, p2.y);
 
788
                max = MAX(p1.y, p2.y);
 
789
            }
 
790
            else
 
791
            {
 
792
                // Need to do rotation
 
793
                Point n_p2 = { p2.x - p1.x, p2.y - p1.y };
 
794
                Point n_start = { start.x - p1.x, start.y - p1.y };
 
795
                Point n_end = { end.x - p1.x, end.y - p1.y };
 
796
                //printf("n_p2:    (%.1f, %.1f)\n", n_p2.x, n_p2.y);
 
797
                //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
 
798
                //printf("n_end:   (%.1f, %.1f)\n", n_end.x, n_end.y);
 
799
 
 
800
                double theta = 0 - atan2(n_p2.y, n_p2.x);
 
801
                //printf("theta = %.2f\n", theta * (180 / PI));
 
802
 
 
803
                Point r_p1 = {0, 0};
 
804
                Point r_p2 = n_p2;
 
805
                start = n_start;
 
806
                end = n_end;
 
807
 
 
808
                double cosv = cos(theta);
 
809
                double sinv = sin(theta);
 
810
 
 
811
                r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
 
812
                r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
 
813
                start.x = cosv * n_start.x - sinv * n_start.y;
 
814
                start.y = cosv * n_start.y + sinv * n_start.x;
 
815
                end.x = cosv * n_end.x - sinv * n_end.y;
 
816
                end.y = cosv * n_end.y + sinv * n_end.x;
 
817
                //printf("r_p2:    (%.1f, %.1f)\n", r_p2.x, r_p2.y);
 
818
                //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
 
819
                //printf("r_end:   (%.1f, %.1f)\n", end.x, end.y);
 
820
 
 
821
                if (((int) r_p2.y) != 0)
 
822
                {
 
823
                    printf("r_p2.y: %f != 0\n", r_p2.y);
 
824
                    abort();
 
825
                }
 
826
                // This might be slightly off.
 
827
                r_p2.y = 0;
 
828
 
 
829
                offy = r_p1.y;
 
830
                a = start.x;
 
831
                b = start.y - offy;
 
832
                c = end.x;
 
833
                d = end.y - offy;
 
834
 
 
835
                min = MIN(r_p1.x, r_p2.x);
 
836
                max = MAX(r_p1.x, r_p2.x);
 
837
 
 
838
            }
 
839
 
 
840
            double x;
 
841
            if ((b + d) == 0)
 
842
            {
 
843
                db_printf("WARNING: (b + d) == 0\n");
 
844
                d = d * -1;
 
845
            }
 
846
 
 
847
            if ((b == 0) && (d == 0))
 
848
            {
 
849
                db_printf("WARNING: b == d == 0\n");
 
850
                if (((a < min) && (c < min)) ||
 
851
                        ((a > max) && (c > max)))
 
852
                {
 
853
                    // It's going to get adjusted.
 
854
                    x = a;
 
855
                }
 
856
                else
 
857
                {
 
858
                    continue;
 
859
                }
 
860
            }
 
861
            else
 
862
            {
 
863
                x = ((b*c) + (a*d)) / (b + d);
 
864
            }
 
865
 
 
866
            //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
 
867
            //printf("x = %.1f\n", x);
 
868
 
 
869
            // XXX: Use MAX and MIN
 
870
            x = (x < min) ? min : x;
 
871
            x = (x > max) ? max : x;
 
872
 
 
873
            //printf("x = %.1f\n", x);
 
874
 
 
875
            Point xp;
 
876
            if (p1.x == p2.x)
 
877
            {
 
878
                xp.x = offy;
 
879
                xp.y = x;
 
880
            }
 
881
            else
 
882
            {
 
883
                xp.x = x;
 
884
                xp.y = offy;
 
885
            }
 
886
            //printf("(%.1f, %.1f)\n", xp.x, xp.y);
 
887
 
 
888
            e1 = dist(start, xp);
 
889
            e2 = dist(xp, end);
 
890
            estdist = e1 + e2;
 
891
 
 
892
 
 
893
            //printf("is %.1f < %.1f\n", estdist, conndist);
 
894
            if (estdist < conndist)
 
895
            {
 
896
#ifdef SELECTIVE_DEBUG
 
897
                //double angle = AngleAFromThreeSides(dist(start, end),
 
898
                //        e1, e2);
 
899
                printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
 
900
                        conn->_id, estdist, conndist);
 
901
#endif
 
902
                conn->_needs_reroute_flag = true;
 
903
                break;
 
904
            }
 
905
 
 
906
        }
 
907
    }
 
908
}
 
909
 
 
910
 
 
911
void printInfo(void)
 
912
{
 
913
    FILE *fp = stdout;
 
914
    fprintf(fp, "\nVisibility Graph info:\n");
 
915
    fprintf(fp, "----------------------\n");
 
916
 
 
917
    uint currshape = 0;
 
918
    int st_shapes = 0;
 
919
    int st_vertices = 0;
 
920
    int st_endpoints = 0;
 
921
    int st_valid_shape_visedges = 0;
 
922
    int st_valid_endpt_visedges = 0;
 
923
    int st_invalid_visedges = 0;
 
924
    VertInf *finish = vertices.end();
 
925
    for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
 
926
    {
 
927
        VertID pID = t->id;
 
928
 
 
929
        if ((pID.isShape) && (pID.objID != currshape))
 
930
        {
 
931
            currshape = pID.objID;
 
932
            st_shapes++;
 
933
        }
 
934
        if (pID.isShape)
 
935
        {
 
936
            st_vertices++;
 
937
        }
 
938
        else
 
939
        {
 
940
            // The shape 0 ones are temporary and not considered.
 
941
            st_endpoints++;
 
942
        }
 
943
    }
 
944
    for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
 
945
            t = t->lstNext)
 
946
    {
 
947
        std::pair<VertID, VertID> idpair = t->ids();
 
948
 
 
949
        if (!(idpair.first.isShape) || !(idpair.second.isShape))
 
950
        {
 
951
            st_valid_endpt_visedges++;
 
952
        }
 
953
        else
 
954
        {
 
955
            st_valid_shape_visedges++;
 
956
        }
 
957
    }
 
958
    for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
 
959
            t = t->lstNext)
 
960
    {
 
961
        st_invalid_visedges++;
 
962
    }
 
963
    fprintf(fp, "Number of shapes: %d\n", st_shapes);
 
964
    fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
 
965
            st_vertices + st_endpoints, st_vertices, st_endpoints);
 
966
    fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
 
967
            "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
 
968
            st_valid_endpt_visedges, st_valid_shape_visedges +
 
969
            st_valid_endpt_visedges, st_valid_shape_visedges,
 
970
            st_valid_endpt_visedges, st_invalid_visedges);
 
971
    fprintf(fp, "----------------------\n");
 
972
    fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
 
973
    fprintf(fp, "----------------------\n");
 
974
 
 
975
    fprintf(fp, "ADDS:  "); timers.Print(tmAdd);
 
976
    fprintf(fp, "DELS:  "); timers.Print(tmDel);
 
977
    fprintf(fp, "MOVS:  "); timers.Print(tmMov);
 
978
    fprintf(fp, "***S:  "); timers.Print(tmSev);
 
979
    fprintf(fp, "PTHS:  "); timers.Print(tmPth);
 
980
    fprintf(fp, "\n");
 
981
}
 
982
 
 
983
 
 
984
}
 
985
 
 
986