← Back to branch summary

~ubuntu-branches/ubuntu/natty/inkscape/natty

« back to all changes in this revision

Viewing changes to src/libavoid/router.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/router.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
 
23
 
#include <cstdlib>
 
25
 
 
26
#include <algorithm>
 
27
#include <cmath>
 
28
 
24
29
#include "libavoid/shape.h"
25
30
#include "libavoid/router.h"
26
31
#include "libavoid/visibility.h"
27
32
#include "libavoid/connector.h"
28
 
#include "libavoid/polyutil.h"
29
33
#include "libavoid/debug.h"
30
 
#include "libavoid/region.h"
31
 
#include "math.h"
32
 
 
33
 
//#define ORTHOGONAL_ROUTING
 
34
#include "libavoid/orthogonal.h"
 
35
#include "libavoid/assertions.h"
34
36
 
35
37
namespace Avoid {
36
38
 
37
39
 
38
 
static const unsigned int infoAdd = 1;
39
 
static const unsigned int infoDel = 2;
40
 
static const unsigned int infoMov = 3;
41
 
 
42
 
 
43
 
class MoveInfo {
 
40
enum ActionType {
 
41
    ShapeMove,
 
42
    ShapeAdd,
 
43
    ShapeRemove,
 
44
    ConnChange
 
45
};
 
46
 
 
47
typedef std::list<std::pair<unsigned int, ConnEnd> > ConnUpdateList;
 
48
 
 
49
class ActionInfo {
44
50
    public:
45
 
        MoveInfo(ShapeRef *s, Polygn *p, bool fM)
46
 
            : shape(s)
47
 
            , newPoly(copyPoly(*p))
48
 
            , firstMove(fM)
49
 
        { }
50
 
        ~MoveInfo()
51
 
        {
52
 
            freePoly(newPoly);
53
 
        }
54
 
        ShapeRef *shape;
55
 
        Polygn newPoly;
 
51
        ActionInfo(ActionType t, ShapeRef *s, const Polygon& p, bool fM)
 
52
            : type(t),
 
53
              objPtr(s),
 
54
              newPoly(p),
 
55
              firstMove(fM)
 
56
        {
 
57
            COLA_ASSERT(type == ShapeMove);
 
58
        }
 
59
        ActionInfo(ActionType t, ShapeRef *s)
 
60
            : type(t),
 
61
              objPtr(s)
 
62
        {
 
63
            COLA_ASSERT(type != ConnChange);
 
64
        }
 
65
        ActionInfo(ActionType t, ConnRef *c)
 
66
            : type(t),
 
67
              objPtr(c)
 
68
        {
 
69
            COLA_ASSERT(type == ConnChange);
 
70
        }
 
71
        ~ActionInfo()
 
72
        {
 
73
        }
 
74
        ShapeRef *shape(void) const
 
75
        {
 
76
            COLA_ASSERT((type == ShapeMove) || (type == ShapeAdd) ||
 
77
                    (type == ShapeRemove));
 
78
            return (static_cast<ShapeRef *> (objPtr));
 
79
        }
 
80
        ConnRef *conn(void) const
 
81
        {
 
82
            COLA_ASSERT(type == ConnChange);
 
83
            return (static_cast<ConnRef *> (objPtr));
 
84
        }
 
85
        bool operator==(const ActionInfo& rhs) const
 
86
        {
 
87
            return (type == rhs.type) && (objPtr == rhs.objPtr);
 
88
        }
 
89
        bool operator<(const ActionInfo& rhs) const
 
90
        {
 
91
            if (type != rhs.type)
 
92
            {
 
93
                return type < rhs.type;
 
94
            }
 
95
            return objPtr < rhs.objPtr;
 
96
        }
 
97
        ActionType type;
 
98
        void *objPtr;
 
99
        Polygon newPoly;
56
100
        bool firstMove;
 
101
        ConnUpdateList conns;
57
102
};
58
103
 
59
104
 
60
 
 
61
 
Router::Router()
62
 
    : PartialTime(false)
63
 
    , SimpleRouting(false)
64
 
    , segmt_penalty(0)
65
 
    , angle_penalty(0)
66
 
    , crossing_penalty(200)
67
 
    // Algorithm options:
68
 
    , UseAStarSearch(true)
69
 
    , IgnoreRegions(true)
70
 
    , SelectiveReroute(true)
71
 
    , IncludeEndpoints(true)
72
 
    , UseLeesAlgorithm(false)
73
 
    , InvisibilityGrph(true)
74
 
    , ConsolidateMoves(true)
75
 
    , PartialFeedback(false)
76
 
    // Instrumentation:
77
 
    , st_checked_edges(0)
78
 
#ifdef LINEDEBUG
79
 
    , avoid_screen(NULL)
 
105
Router::Router(const unsigned int flags)
 
106
    : visOrthogGraph(true),
 
107
      PartialTime(false),
 
108
      SimpleRouting(false),
 
109
      ClusteredRouting(true),
 
110
      // Poly-line algorithm options:
 
111
      IgnoreRegions(true),
 
112
      UseLeesAlgorithm(true),
 
113
      InvisibilityGrph(true),
 
114
      // General algorithm options:
 
115
      SelectiveReroute(true),
 
116
      PartialFeedback(false),
 
117
      RubberBandRouting(false),
 
118
      // Instrumentation:
 
119
      st_checked_edges(0),
 
120
#ifdef LIBAVOID_SDL
 
121
      avoid_screen(NULL),
80
122
#endif
81
 
{ }
82
 
 
83
 
 
 
123
      _largestAssignedId(0),
 
124
      _consolidateActions(true),
 
125
      _orthogonalNudgeDistance(4.0),
 
126
      // Mode options:
 
127
      _polyLineRouting(false),
 
128
      _orthogonalRouting(false),
 
129
      _staticGraphInvalidated(true),
 
130
      _inCrossingPenaltyReroutingStage(false)
 
131
{
 
132
    // At least one of the Routing modes must be set.
 
133
    COLA_ASSERT(flags & (PolyLineRouting | OrthogonalRouting));
 
134
 
 
135
    if (flags & PolyLineRouting)
 
136
    {
 
137
        _polyLineRouting = true;
 
138
    }
 
139
    if (flags & OrthogonalRouting)
 
140
    {
 
141
        _orthogonalRouting = true;
 
142
    }
 
143
 
 
144
    for (size_t p = 0; p < lastPenaltyMarker; ++p)
 
145
    {
 
146
        _routingPenalties[p] = 0.0;
 
147
    }
 
148
    _routingPenalties[clusterCrossingPenalty] = 4000;
 
149
}
 
150
 
 
151
 
 
152
Router::~Router()
 
153
{
 
154
    // Delete remaining connectors.
 
155
    ConnRefList::iterator conn = connRefs.begin();
 
156
    while (conn != connRefs.end())
 
157
    {
 
158
        db_printf("Deleting connector %u in ~Router()\n", (*conn)->id());
 
159
        delete *conn;
 
160
        conn = connRefs.begin();
 
161
    }
 
162
 
 
163
    // Remove remaining shapes.
 
164
    ShapeRefList::iterator shape = shapeRefs.begin();
 
165
    while (shape != shapeRefs.end())
 
166
    {
 
167
        ShapeRef *shapePtr = *shape;
 
168
        db_printf("Deleting shape %u in ~Router()\n", shapePtr->id());
 
169
        if (shapePtr->isActive())
 
170
        {
 
171
            shapePtr->removeFromGraph();
 
172
            shapePtr->makeInactive();
 
173
        }
 
174
        delete shapePtr;
 
175
        shape = shapeRefs.begin();
 
176
    }
 
177
 
 
178
    // Cleanup orphaned orthogonal graph vertices.
 
179
    destroyOrthogonalVisGraph();
 
180
 
 
181
    COLA_ASSERT(connRefs.size() == 0);
 
182
    COLA_ASSERT(shapeRefs.size() == 0);
 
183
    COLA_ASSERT(visGraph.size() == 0);
 
184
    COLA_ASSERT(invisGraph.size() == 0);
 
185
}
 
186
 
 
187
 
 
188
void Router::modifyConnector(ConnRef *conn, const unsigned int type,
 
189
        const ConnEnd& connEnd)
 
190
{
 
191
    ActionInfo modInfo(ConnChange, conn);
 
192
 
 
193
    ActionInfoList::iterator found =
 
194
            find(actionList.begin(), actionList.end(), modInfo);
 
195
    if (found == actionList.end())
 
196
    {
 
197
        modInfo.conns.push_back(std::make_pair(type, connEnd));
 
198
        actionList.push_back(modInfo);
 
199
    }
 
200
    else
 
201
    {
 
202
        found->conns.push_back(std::make_pair(type, connEnd));
 
203
    }
 
204
 
 
205
    if (!_consolidateActions)
 
206
    {
 
207
        processTransaction();
 
208
    }
 
209
}
 
210
 
 
211
 
 
212
void Router::modifyConnector(ConnRef *conn)
 
213
{
 
214
    ActionInfo modInfo(ConnChange, conn);
 
215
 
 
216
    ActionInfoList::iterator found =
 
217
            find(actionList.begin(), actionList.end(), modInfo);
 
218
    if (found == actionList.end())
 
219
    {
 
220
        actionList.push_back(modInfo);
 
221
    }
 
222
 
 
223
    if (!_consolidateActions)
 
224
    {
 
225
        processTransaction();
 
226
    }
 
227
}
 
228
 
 
229
 
 
230
void Router::removeQueuedConnectorActions(ConnRef *conn)
 
231
{
 
232
    ActionInfo modInfo(ConnChange, conn);
 
233
 
 
234
    ActionInfoList::iterator found =
 
235
            find(actionList.begin(), actionList.end(), modInfo);
 
236
    if (found != actionList.end())
 
237
    {
 
238
        actionList.erase(found);
 
239
    }
 
240
}
84
241
 
85
242
 
86
243
void Router::addShape(ShapeRef *shape)
87
244
{
88
 
    unsigned int pid = shape->id();
89
 
    Polygn poly = shape->poly();
90
 
 
91
 
    adjustContainsWithAdd(poly, pid);
92
 
    
93
 
    // o  Check all visibility edges to see if this one shape
94
 
    //    blocks them.
95
 
    newBlockingShape(&poly, pid);
96
 
 
97
 
#ifdef ORTHOGONAL_ROUTING
98
 
    Region::addShape(shape);
99
 
#endif
100
 
 
101
 
    // o  Calculate visibility for the new vertices.
102
 
    if (UseLeesAlgorithm)
103
 
    {
104
 
        shapeVisSweep(shape);
105
 
    }
106
 
    else
107
 
    {
108
 
        shapeVis(shape);
109
 
    }
110
 
    callbackAllInvalidConnectors();
111
 
}
112
 
 
113
 
 
114
 
void Router::delShape(ShapeRef *shape)
115
 
{
116
 
    unsigned int pid = shape->id();
117
 
 
118
 
    // Delete items that are queued in the movList.
119
 
    for (MoveInfoList::iterator it = moveList.begin(); it != moveList.end(); )
120
 
    {
121
 
        if ((*it)->shape->id() == pid)
122
 
        {
123
 
            MoveInfoList::iterator doomed = it;
124
 
            ++it;
125
 
            moveList.erase(doomed);
126
 
        }
127
 
        else
128
 
        {
129
 
            ++it;
130
 
        }
131
 
    }
132
 
 
133
 
    // o  Remove entries related to this shape's vertices
134
 
    shape->removeFromGraph();
135
 
    
136
 
    if (SelectiveReroute)
137
 
    {
138
 
        markConnectors(shape);
139
 
    }
140
 
 
141
 
    adjustContainsWithDel(pid);
142
 
    
143
 
#ifdef ORTHOGONAL_ROUTING
144
 
    Region::removeShape(shape);
145
 
#endif
146
 
 
147
 
    delete shape;
148
 
    
149
 
    // o  Check all edges that were blocked by this shape.
150
 
    if (InvisibilityGrph)
151
 
    {
152
 
        checkAllBlockedEdges(pid);
153
 
    }
154
 
    else
155
 
    {
156
 
        // check all edges not in graph
157
 
        checkAllMissingEdges();
158
 
    }
159
 
    callbackAllInvalidConnectors();
160
 
}
161
 
 
162
 
 
163
 
void Router::moveShape(ShapeRef *shape, Polygn *newPoly, const bool first_move)
164
 
{
 
245
    // There shouldn't be remove events or move events for the same shape
 
246
    // already in the action list.
 
247
    // XXX: Possibly we could handle this by ordering them intelligently.
 
248
    COLA_ASSERT(find(actionList.begin(), actionList.end(),
 
249
                ActionInfo(ShapeRemove, shape)) == actionList.end());
 
250
    COLA_ASSERT(find(actionList.begin(), actionList.end(),
 
251
                ActionInfo(ShapeMove, shape)) == actionList.end());
 
252
 
 
253
    ActionInfo addInfo(ShapeAdd, shape);
 
254
 
 
255
    ActionInfoList::iterator found =
 
256
            find(actionList.begin(), actionList.end(), addInfo);
 
257
    if (found == actionList.end())
 
258
    {
 
259
        actionList.push_back(addInfo);
 
260
    }
 
261
 
 
262
    if (!_consolidateActions)
 
263
    {
 
264
        processTransaction();
 
265
    }
 
266
}
 
267
 
 
268
 
 
269
void Router::removeShape(ShapeRef *shape)
 
270
{
 
271
    // There shouldn't be add events events for the same shape already
 
272
    // in the action list.
 
273
    // XXX: Possibly we could handle this by ordering them intelligently.
 
274
    COLA_ASSERT(find(actionList.begin(), actionList.end(),
 
275
                ActionInfo(ShapeAdd, shape)) == actionList.end());
 
276
 
 
277
    // Delete any ShapeMove entries for this shape in the action list.
 
278
    ActionInfoList::iterator found = find(actionList.begin(),
 
279
            actionList.end(), ActionInfo(ShapeMove, shape));
 
280
    if (found != actionList.end())
 
281
    {
 
282
        actionList.erase(found);
 
283
    }
 
284
 
 
285
    // Add the ShapeRemove entry.
 
286
    ActionInfo remInfo(ShapeRemove, shape);
 
287
    found = find(actionList.begin(), actionList.end(), remInfo);
 
288
    if (found == actionList.end())
 
289
    {
 
290
        actionList.push_back(remInfo);
 
291
    }
 
292
 
 
293
    if (!_consolidateActions)
 
294
    {
 
295
        processTransaction();
 
296
    }
 
297
}
 
298
 
 
299
 
 
300
void Router::moveShape(ShapeRef *shape, const double xDiff, const double yDiff)
 
301
{
 
302
    Polygon newPoly = shape->polygon();
 
303
    newPoly.translate(xDiff, yDiff);
 
304
 
 
305
    moveShape(shape, newPoly);
 
306
}
 
307
 
 
308
 
 
309
void Router::moveShape(ShapeRef *shape, const Polygon& newPoly,
 
310
        const bool first_move)
 
311
{
 
312
    // There shouldn't be remove events or add events for the same shape
 
313
    // already in the action list.
 
314
    // XXX: Possibly we could handle this by ordering them intelligently.
 
315
    COLA_ASSERT(find(actionList.begin(), actionList.end(),
 
316
                ActionInfo(ShapeRemove, shape)) == actionList.end());
 
317
 
 
318
    if (find(actionList.begin(), actionList.end(),
 
319
                ActionInfo(ShapeAdd, shape)) != actionList.end())
 
320
    {
 
321
        // The Add is enough, no need for the Move action too.
 
322
        return;
 
323
    }
 
324
 
 
325
    ActionInfo moveInfo(ShapeMove, shape, newPoly, first_move);
165
326
    // Sanely cope with the case where the user requests moving the same
166
327
    // shape multiple times before rerouting connectors.
167
 
    bool alreadyThere = false;
168
 
    unsigned int id = shape->id();
169
 
    MoveInfoList::iterator finish = moveList.end();
170
 
    for (MoveInfoList::iterator it = moveList.begin(); it != finish; ++it)
171
 
    {
172
 
        if ((*it)->shape->id() == id)
173
 
        {
174
 
            if (!SimpleRouting)
175
 
            {
176
 
                fprintf(stderr,
177
 
                        "warning: multiple moves requested for shape %d.\n",
178
 
                        (int) id);
179
 
            }
180
 
            // Just update the MoveInfo with the second polygon, but
181
 
            // leave the firstMove setting alone.
182
 
            (*it)->newPoly = copyPoly(*newPoly);
183
 
            alreadyThere = true;
184
 
        }
185
 
    }
186
 
 
187
 
    if (!alreadyThere)
188
 
    {
189
 
        MoveInfo *moveInfo = new MoveInfo(shape, newPoly, first_move);
190
 
        moveList.push_back(moveInfo);
191
 
    }
192
 
 
193
 
    if (!ConsolidateMoves)
194
 
    {
195
 
        processMoves();
196
 
    }
197
 
}
198
 
 
199
 
 
200
 
void Router::processMoves(void)
201
 
{
202
 
    // If SimpleRouting, then don't update yet.
203
 
    if (moveList.empty() || SimpleRouting)
204
 
    {
205
 
        return;
206
 
    }
207
 
 
208
 
    MoveInfoList::iterator curr;
209
 
    MoveInfoList::iterator finish = moveList.end();
210
 
    for (curr = moveList.begin(); curr != finish; ++curr)
211
 
    {
212
 
        MoveInfo *moveInf = *curr;
213
 
        ShapeRef *shape = moveInf->shape;
214
 
        Polygn *newPoly = &(moveInf->newPoly);
215
 
        bool first_move = moveInf->firstMove;
 
328
    ActionInfoList::iterator found =
 
329
            find(actionList.begin(), actionList.end(), moveInfo);
 
330
 
 
331
    if (found != actionList.end())
 
332
    {
 
333
        if (!SimpleRouting)
 
334
        {
 
335
            db_printf("warning: multiple moves requested for shape %d "
 
336
                    "within a single transaction.\n", (int) shape->id());
 
337
        }
 
338
        // Just update the ActionInfo with the second polygon, but
 
339
        // leave the firstMove setting alone.
 
340
        found->newPoly = newPoly;
 
341
    }
 
342
    else
 
343
    {
 
344
        actionList.push_back(moveInfo);
 
345
    }
 
346
 
 
347
    if (!_consolidateActions)
 
348
    {
 
349
        processTransaction();
 
350
    }
 
351
}
 
352
 
 
353
 
 
354
void Router::setStaticGraphInvalidated(const bool invalidated)
 
355
{
 
356
    _staticGraphInvalidated = invalidated;
 
357
}
 
358
 
 
359
 
 
360
void Router::destroyOrthogonalVisGraph(void)
 
361
{
 
362
    // Remove orthogonal visibility graph edges.
 
363
    visOrthogGraph.clear();
 
364
 
 
365
    // Remove the now orphaned vertices.
 
366
    VertInf *curr = vertices.shapesBegin();
 
367
    while (curr)
 
368
    {
 
369
        if (curr->orphaned() && (curr->id == dummyOrthogID))
 
370
        {
 
371
            VertInf *following = vertices.removeVertex(curr);
 
372
            delete curr;
 
373
            curr = following;
 
374
            continue;
 
375
        }
 
376
        curr = curr->lstNext;
 
377
    }
 
378
}
 
379
 
 
380
 
 
381
void Router::regenerateStaticBuiltGraph(void)
 
382
{
 
383
    // Here we do talks involved in updating the static-built visibility
 
384
    // graph (if necessary) before we do any routing.
 
385
    if (_staticGraphInvalidated)
 
386
    {
 
387
        if (_orthogonalRouting)
 
388
        {
 
389
            destroyOrthogonalVisGraph();
 
390
 
 
391
            timers.Register(tmOrthogGraph, timerStart);
 
392
            // Regenerate a new visibility graph.
 
393
            generateStaticOrthogonalVisGraph(this);
 
394
 
 
395
            timers.Stop();
 
396
        }
 
397
        _staticGraphInvalidated = false;
 
398
    }
 
399
}
 
400
 
 
401
 
 
402
bool Router::shapeInQueuedActionList(ShapeRef *shape) const
 
403
{
 
404
    bool foundAdd = find(actionList.begin(), actionList.end(),
 
405
                ActionInfo(ShapeAdd, shape)) != actionList.end();
 
406
    bool foundRem = find(actionList.begin(), actionList.end(),
 
407
                ActionInfo(ShapeRemove, shape)) != actionList.end();
 
408
    bool foundMove = find(actionList.begin(), actionList.end(),
 
409
                ActionInfo(ShapeMove, shape)) != actionList.end();
 
410
 
 
411
    return (foundAdd || foundRem || foundMove);
 
412
}
 
413
 
 
414
 
 
415
bool Router::transactionUse(void) const
 
416
{
 
417
    return _consolidateActions;
 
418
}
 
419
 
 
420
 
 
421
void Router::setTransactionUse(const bool transactions)
 
422
{
 
423
    _consolidateActions = transactions;
 
424
}
 
425
 
 
426
 
 
427
bool Router::processTransaction(void)
 
428
{
 
429
    bool notPartialTime = !(PartialFeedback && PartialTime);
 
430
    bool seenShapeMovesOrDeletes = false;
 
431
 
 
432
    // If SimpleRouting, then don't update here.
 
433
    if (actionList.empty() || SimpleRouting)
 
434
    {
 
435
        return false;
 
436
    }
 
437
 
 
438
    actionList.sort();
 
439
    ActionInfoList::iterator curr;
 
440
    ActionInfoList::iterator finish = actionList.end();
 
441
    for (curr = actionList.begin(); curr != finish; ++curr)
 
442
    {
 
443
        ActionInfo& actInf = *curr;
 
444
        if (!((actInf.type == ShapeRemove) || (actInf.type == ShapeMove)))
 
445
        {
 
446
            // Not a move or remove action, so don't do anything.
 
447
            continue;
 
448
        }
 
449
        seenShapeMovesOrDeletes = true;
 
450
 
 
451
        ShapeRef *shape = actInf.shape();
 
452
        bool isMove = (actInf.type == ShapeMove);
 
453
        bool first_move = actInf.firstMove;
216
454
 
217
455
        unsigned int pid = shape->id();
218
 
        bool notPartialTime = !(PartialFeedback && PartialTime);
219
456
 
220
457
        // o  Remove entries related to this shape's vertices
221
458
        shape->removeFromGraph();
222
 
        
223
 
        if (SelectiveReroute && (notPartialTime || first_move))
 
459
 
 
460
        if (SelectiveReroute && (!isMove || notPartialTime || first_move))
224
461
        {
225
462
            markConnectors(shape);
226
463
        }
227
464
 
228
465
        adjustContainsWithDel(pid);
229
 
        
230
 
#ifdef ORTHOGONAL_ROUTING
231
 
        Region::removeShape(shape);
232
 
#endif
233
 
 
234
 
        shape->setNewPoly(*newPoly);
235
 
 
236
 
        adjustContainsWithAdd(*newPoly, pid);
237
466
 
238
467
        // Ignore this shape for visibility.
239
468
        // XXX: We don't really need to do this if we're not using Partial
240
469
        //      Feedback.  Without this the blocked edges still route
241
470
        //      around the shape until it leaves the connector.
242
471
        shape->makeInactive();
243
 
        
244
 
    }
245
 
    
246
 
    if (InvisibilityGrph)
247
 
    {
248
 
        for (curr = moveList.begin(); curr != finish; ++curr)
249
 
        {
250
 
            MoveInfo *moveInf = *curr;
251
 
            ShapeRef *shape = moveInf->shape;
252
 
            unsigned int pid = shape->id();
253
 
            
254
 
            // o  Check all edges that were blocked by this shape.
255
 
            checkAllBlockedEdges(pid);
256
 
        }
257
 
    }
258
 
    else
259
 
    {
260
 
        // check all edges not in graph
261
 
        checkAllMissingEdges();
262
 
    }
263
 
 
264
 
    while ( ! moveList.empty() )
265
 
    {
266
 
        MoveInfo *moveInf = moveList.front();
267
 
        ShapeRef *shape = moveInf->shape;
268
 
        Polygn *newPoly = &(moveInf->newPoly);
 
472
    }
 
473
 
 
474
    if (seenShapeMovesOrDeletes && _polyLineRouting)
 
475
    {
 
476
        if (InvisibilityGrph)
 
477
        {
 
478
            for (curr = actionList.begin(); curr != finish; ++curr)
 
479
            {
 
480
                ActionInfo& actInf = *curr;
 
481
                if (!((actInf.type == ShapeRemove) ||
 
482
                            (actInf.type == ShapeMove)))
 
483
                {
 
484
                    // Not a move or remove action, so don't do anything.
 
485
                    continue;
 
486
                }
 
487
 
 
488
                // o  Check all edges that were blocked by this shape.
 
489
                checkAllBlockedEdges(actInf.shape()->id());
 
490
            }
 
491
        }
 
492
        else
 
493
        {
 
494
            // check all edges not in graph
 
495
            checkAllMissingEdges();
 
496
        }
 
497
    }
 
498
 
 
499
    for (curr = actionList.begin(); curr != finish; ++curr)
 
500
    {
 
501
        ActionInfo& actInf = *curr;
 
502
        if (!((actInf.type == ShapeAdd) || (actInf.type == ShapeMove)))
 
503
        {
 
504
            // Not a move or add action, so don't do anything.
 
505
            continue;
 
506
        }
 
507
 
 
508
        ShapeRef *shape = actInf.shape();
 
509
        Polygon& newPoly = actInf.newPoly;
 
510
        bool isMove = (actInf.type == ShapeMove);
269
511
 
270
512
        unsigned int pid = shape->id();
271
 
        bool notPartialTime = !(PartialFeedback && PartialTime);
272
513
 
273
514
        // Restore this shape for visibility.
274
515
        shape->makeActive();
275
516
 
276
 
#ifdef ORTHOGONAL_ROUTING
277
 
        Region::addShape(shape);
278
 
#endif
279
 
 
280
 
        // o  Check all visibility edges to see if this one shape
281
 
        //    blocks them.
282
 
        if (notPartialTime)
283
 
        {
284
 
            newBlockingShape(newPoly, pid);
285
 
        }
286
 
 
287
 
        // o  Calculate visibility for the new vertices.
288
 
        if (UseLeesAlgorithm)
289
 
        {
290
 
            shapeVisSweep(shape);
291
 
        }
292
 
        else
293
 
        {
294
 
            shapeVis(shape);
295
 
        }
296
 
        
297
 
        moveList.pop_front();
298
 
        delete moveInf;
299
 
    }
300
 
    callbackAllInvalidConnectors();
 
517
        if (isMove)
 
518
        {
 
519
            shape->setNewPoly(newPoly);
 
520
        }
 
521
        const Polygon& shapePoly = shape->polygon();
 
522
 
 
523
        adjustContainsWithAdd(shapePoly, pid);
 
524
 
 
525
        if (_polyLineRouting)
 
526
        {
 
527
            // o  Check all visibility edges to see if this one shape
 
528
            //    blocks them.
 
529
            if (!isMove || notPartialTime)
 
530
            {
 
531
                newBlockingShape(shapePoly, pid);
 
532
            }
 
533
 
 
534
            // o  Calculate visibility for the new vertices.
 
535
            if (UseLeesAlgorithm)
 
536
            {
 
537
                shapeVisSweep(shape);
 
538
            }
 
539
            else
 
540
            {
 
541
                shapeVis(shape);
 
542
            }
 
543
        }
 
544
    }
 
545
 
 
546
    // Update connector endpoints.
 
547
    for (curr = actionList.begin(); curr != finish; ++curr)
 
548
    {
 
549
        ActionInfo& actInf = *curr;
 
550
        if (actInf.type != ConnChange)
 
551
        {
 
552
            continue;
 
553
        }
 
554
        for (ConnUpdateList::iterator conn = actInf.conns.begin();
 
555
                conn != actInf.conns.end(); ++conn)
 
556
        {
 
557
            actInf.conn()->updateEndPoint(conn->first, conn->second);
 
558
        }
 
559
    }
 
560
    // Clear the actionList.
 
561
    actionList.clear();
 
562
 
 
563
    _staticGraphInvalidated = true;
 
564
    rerouteAndCallbackConnectors();
 
565
 
 
566
    return true;
 
567
}
 
568
 
 
569
 
 
570
void Router::addCluster(ClusterRef *cluster)
 
571
{
 
572
    cluster->makeActive();
 
573
 
 
574
    unsigned int pid = cluster->id();
 
575
    ReferencingPolygon& poly = cluster->polygon();
 
576
 
 
577
    adjustClustersWithAdd(poly, pid);
 
578
}
 
579
 
 
580
 
 
581
void Router::delCluster(ClusterRef *cluster)
 
582
{
 
583
    cluster->makeInactive();
 
584
 
 
585
    unsigned int pid = cluster->id();
 
586
 
 
587
    adjustClustersWithDel(pid);
 
588
}
 
589
 
 
590
 
 
591
void Router::setOrthogonalNudgeDistance(const double dist)
 
592
{
 
593
    COLA_ASSERT(dist >= 0);
 
594
    _orthogonalNudgeDistance = dist;
 
595
}
 
596
 
 
597
 
 
598
double Router::orthogonalNudgeDistance(void) const
 
599
{
 
600
    return _orthogonalNudgeDistance;
 
601
}
 
602
 
 
603
 
 
604
unsigned int Router::assignId(const unsigned int suggestedId)
 
605
{
 
606
    // If the suggestedId is zero, then we assign the object the next
 
607
    // smallest unassigned ID, otherwise we trust the ID given is unique.
 
608
    unsigned int assignedId = (suggestedId == 0) ?
 
609
            (_largestAssignedId + 1) : suggestedId;
 
610
 
 
611
    // Have the router record if this ID is larger than the _largestAssignedId.
 
612
    _largestAssignedId = std::max(_largestAssignedId, assignedId);
 
613
 
 
614
    // If assertions are enabled, then we check that this ID really is unique.
 
615
    COLA_ASSERT(idIsUnique(assignedId));
 
616
 
 
617
    return assignedId;
 
618
}
 
619
 
 
620
 
 
621
    // Returns whether the given ID is unique among all objects known by the
 
622
    // router.  Outputs a warning if the ID is found ore than once.
 
623
    // It is expected this is only going to be called from assertions while
 
624
    // debugging, so efficiency is not an issue and we just iterate over all
 
625
    // objects.
 
626
bool Router::idIsUnique(const unsigned int id) const
 
627
{
 
628
    unsigned int count = 0;
 
629
 
 
630
    // Examine shapes.
 
631
    for (ShapeRefList::const_iterator i = shapeRefs.begin();
 
632
            i != shapeRefs.end(); ++i)
 
633
    {
 
634
        if ((*i)->id() == id)
 
635
        {
 
636
            count++;
 
637
        }
 
638
    }
 
639
 
 
640
    // Examine connectors.
 
641
    for (ConnRefList::const_iterator i = connRefs.begin();
 
642
            i != connRefs.end(); ++i)
 
643
    {
 
644
        if ((*i)->id() == id)
 
645
        {
 
646
            count++;
 
647
        }
 
648
    }
 
649
 
 
650
    // Examine clusters.
 
651
    for (ClusterRefList::const_iterator i = clusterRefs.begin();
 
652
            i != clusterRefs.end(); ++i)
 
653
    {
 
654
        if ((*i)->id() == id)
 
655
        {
 
656
            count++;
 
657
        }
 
658
    }
 
659
 
 
660
    if (count > 1)
 
661
    {
 
662
        db_printf("Warning:\tlibavoid object ID %d not unique.\n", id);
 
663
        return false;
 
664
    }
 
665
    return true;
301
666
}
302
667
 
303
668
 
313
678
void Router::attachedConns(IntList &conns, const unsigned int shapeId,
314
679
        const unsigned int type)
315
680
{
316
 
    ConnRefList::iterator fin = connRefs.end();
317
 
    for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
318
 
 
319
 
        if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
 
681
    ConnRefList::const_iterator fin = connRefs.end();
 
682
    for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 
683
    {
 
684
        if ((type & runningTo) && ((*i)->_dstId == shapeId))
 
685
        {
320
686
            conns.push_back((*i)->_id);
321
687
        }
322
 
        else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
 
688
        else if ((type & runningFrom) && ((*i)->_srcId == shapeId))
 
689
        {
323
690
            conns.push_back((*i)->_id);
324
691
        }
325
692
    }
331
698
void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
332
699
        const unsigned int type)
333
700
{
334
 
    ConnRefList::iterator fin = connRefs.end();
335
 
    for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
336
 
        if ((type & runningTo) && ((*i)->_dstId == shapeId)) {
 
701
    ConnRefList::const_iterator fin = connRefs.end();
 
702
    for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 
703
    {
 
704
        if ((type & runningTo) && ((*i)->_dstId == shapeId))
 
705
        {
337
706
            if ((*i)->_srcId != 0)
338
707
            {
339
708
                // Only if there is a shape attached to the other end.
340
709
                shapes.push_back((*i)->_srcId);
341
710
            }
342
711
        }
343
 
        else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) {
 
712
        else if ((type & runningFrom) && ((*i)->_srcId == shapeId))
 
713
        {
344
714
            if ((*i)->_dstId != 0)
345
715
            {
346
716
                // Only if there is a shape attached to the other end.
351
721
}
352
722
 
353
723
 
354
 
    // It's intended this function is called after shape movement has 
355
 
    // happened to alert connectors that they need to be rerouted.
356
 
void Router::callbackAllInvalidConnectors(void)
357
 
{
 
724
    // It's intended this function is called after visibility changes
 
725
    // resulting from shape movement have happened.  It will alert
 
726
    // rerouted connectors (via a callback) that they need to be redrawn.
 
727
void Router::rerouteAndCallbackConnectors(void)
 
728
{
 
729
    std::set<ConnRef *> reroutedConns;
 
730
    ConnRefList::const_iterator fin = connRefs.end();
 
731
 
 
732
    // Updating the orthogonal visibility graph if necessary.
 
733
    regenerateStaticBuiltGraph();
 
734
 
 
735
    timers.Register(tmOrthogRoute, timerStart);
 
736
    for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 
737
    {
 
738
        (*i)->_needs_repaint = false;
 
739
        bool rerouted = (*i)->generatePath();
 
740
        if (rerouted)
 
741
        {
 
742
            reroutedConns.insert(*i);
 
743
        }
 
744
    }
 
745
    timers.Stop();
 
746
 
 
747
    // Find and reroute crossing connectors if crossing penalties are set.
 
748
    improveCrossings();
 
749
 
 
750
    // Perform centring and nudging for othogonal routes.
 
751
    improveOrthogonalRoutes(this);
 
752
 
 
753
    // Alert connectors that they need redrawing.
 
754
    for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 
755
    {
 
756
        (*i)->_needs_repaint = true;
 
757
        (*i)->performCallback();
 
758
    }
 
759
}
 
760
 
 
761
 
 
762
typedef std::set<ConnRef *> ConnRefSet;
 
763
 
 
764
void Router::improveCrossings(void)
 
765
{
 
766
    const double crossing_penalty = routingPenalty(crossingPenalty);
 
767
    const double shared_path_penalty = routingPenalty(fixedSharedPathPenalty);
 
768
    if ((crossing_penalty == 0) && (shared_path_penalty == 0))
 
769
    {
 
770
        // No penalties, return.
 
771
        return;
 
772
    }
 
773
 
 
774
    // Find crossings and reroute connectors.
 
775
    _inCrossingPenaltyReroutingStage = true;
 
776
    ConnRefSet crossingConns;
358
777
    ConnRefList::iterator fin = connRefs.end();
359
 
    for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
360
 
        (*i)->handleInvalid();
361
 
    }
 
778
    for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
 
779
    {
 
780
        Avoid::Polygon& iRoute = (*i)->routeRef();
 
781
        ConnRefList::iterator j = i;
 
782
        for (++j; j != fin; ++j)
 
783
        {
 
784
            if ((crossingConns.find(*i) != crossingConns.end()) &&
 
785
                    (crossingConns.find(*j) != crossingConns.end()))
 
786
            {
 
787
                // We already know both these have crossings.
 
788
                continue;
 
789
            }
 
790
            // Determine if this pair cross.
 
791
            Avoid::Polygon& jRoute = (*j)->routeRef();
 
792
            CrossingsInfoPair crossingInfo = std::make_pair(0, 0);
 
793
            bool meetsPenaltyCriteria = false;
 
794
            for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
 
795
            {
 
796
                const bool finalSegment = ((jInd + 1) == jRoute.size());
 
797
                CrossingsInfoPair crossingInfo = countRealCrossings(
 
798
                        iRoute, true, jRoute, jInd, false,
 
799
                        finalSegment, NULL, NULL, *i, *j);
 
800
 
 
801
                if ((shared_path_penalty > 0) &&
 
802
                    (crossingInfo.second & CROSSING_SHARES_PATH) &&
 
803
                    (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) &&
 
804
                    !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END))
 
805
                {
 
806
                    // We are penalising fixedSharedPaths and there is a
 
807
                    // fixedSharedPath.
 
808
                    meetsPenaltyCriteria = true;
 
809
                    break;
 
810
                }
 
811
                else if ((crossing_penalty > 0) && (crossingInfo.first > 0))
 
812
                {
 
813
                    // We are penalising crossings and this is a crossing.
 
814
                    meetsPenaltyCriteria = true;
 
815
                    break;
 
816
                }
 
817
            }
 
818
            if (meetsPenaltyCriteria)
 
819
            {
 
820
                crossingConns.insert(*i);
 
821
                crossingConns.insert(*j);
 
822
            }
 
823
        }
 
824
    }
 
825
 
 
826
    for (ConnRefSet::iterator i = crossingConns.begin();
 
827
            i != crossingConns.end(); ++i)
 
828
    {
 
829
        ConnRef *conn = *i;
 
830
        conn->makePathInvalid();
 
831
        // XXX: Could we free these routes here for extra savings?
 
832
        // conn->freeRoutes();
 
833
    }
 
834
    for (ConnRefSet::iterator i = crossingConns.begin();
 
835
            i != crossingConns.end(); ++i)
 
836
    {
 
837
        ConnRef *conn = *i;
 
838
        conn->generatePath();
 
839
    }
 
840
    _inCrossingPenaltyReroutingStage = false;
362
841
}
363
842
 
364
843
 
365
 
void Router::newBlockingShape(Polygn *poly, int pid)
 
844
void Router::newBlockingShape(const Polygon& poly, int pid)
366
845
{
367
846
    // o  Check all visibility edges to see if this one shape
368
847
    //    blocks them.
382
861
            Point e2 = points.second;
383
862
            bool blocked = false;
384
863
 
385
 
            bool ep_in_poly1 = !(eID1.isShape) ? inPoly(*poly, e1) : false;
386
 
            bool ep_in_poly2 = !(eID2.isShape) ? inPoly(*poly, e2) : false;
 
864
            bool countBorder = false;
 
865
            bool ep_in_poly1 = !(eID1.isShape) ?
 
866
                    inPoly(poly, e1, countBorder) : false;
 
867
            bool ep_in_poly2 = !(eID2.isShape) ?
 
868
                    inPoly(poly, e2, countBorder) : false;
387
869
            if (ep_in_poly1 || ep_in_poly2)
388
870
            {
389
871
                // Don't check edges that have a connector endpoint
391
873
                continue;
392
874
            }
393
875
 
394
 
            for (int pt_i = 0; pt_i < poly->pn; pt_i++)
 
876
            bool seenIntersectionAtEndpoint = false;
 
877
            for (size_t pt_i = 0; pt_i < poly.size(); ++pt_i)
395
878
            {
396
 
                int pt_n = (pt_i == (poly->pn - 1)) ? 0 : pt_i + 1;
397
 
                if (segmentIntersect(e1, e2, poly->ps[pt_i], poly->ps[pt_n]))
 
879
                size_t pt_n = (pt_i == (poly.size() - 1)) ? 0 : pt_i + 1;
 
880
                const Point& pi = poly.ps[pt_i];
 
881
                const Point& pn = poly.ps[pt_n];
 
882
                if (segmentShapeIntersect(e1, e2, pi, pn,
 
883
                        seenIntersectionAtEndpoint))
398
884
                {
399
885
                    blocked = true;
400
886
                    break;
422
908
 
423
909
void Router::checkAllBlockedEdges(int pid)
424
910
{
425
 
    assert(InvisibilityGrph);
 
911
    COLA_ASSERT(InvisibilityGrph);
426
912
 
427
913
    for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
428
914
    {
444
930
 
445
931
void Router::checkAllMissingEdges(void)
446
932
{
447
 
    assert(!InvisibilityGrph);
448
 
 
449
 
    VertInf *first = NULL;
450
 
 
451
 
    if (IncludeEndpoints)
452
 
    {
453
 
        first = vertices.connsBegin();
454
 
    }
455
 
    else
456
 
    {
457
 
        first = vertices.shapesBegin();
458
 
    }
 
933
    COLA_ASSERT(!InvisibilityGrph);
 
934
 
 
935
    VertInf *first = vertices.connsBegin();
459
936
 
460
937
    VertInf *pend = vertices.end();
461
938
    for (VertInf *i = first; i != pend; i = i->lstNext)
489
966
void Router::generateContains(VertInf *pt)
490
967
{
491
968
    contains[pt->id].clear();
492
 
 
493
 
    ShapeRefList::iterator finish = shapeRefs.end();
494
 
    for (ShapeRefList::iterator i = shapeRefs.begin(); i != finish; ++i)
 
969
    enclosingClusters[pt->id].clear();
 
970
 
 
971
    // Don't count points on the border as being inside.
 
972
    bool countBorder = false;
 
973
 
 
974
    // Compute enclosing shapes.
 
975
    ShapeRefList::const_iterator finish = shapeRefs.end();
 
976
    for (ShapeRefList::const_iterator i = shapeRefs.begin(); i != finish; ++i)
495
977
    {
496
 
        Polygn poly = copyPoly(*i);
497
 
        if (inPoly(poly, pt->point))
 
978
        if (inPoly((*i)->polygon(), pt->point, countBorder))
498
979
        {
499
980
            contains[pt->id].insert((*i)->id());
500
981
        }
501
 
        freePoly(poly);
502
 
    }
503
 
}
504
 
 
505
 
 
506
 
void Router::adjustContainsWithAdd(const Polygn& poly, const int p_shape)
507
 
{
508
 
    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
509
 
            k = k->lstNext)
510
 
    {
511
 
        if (inPoly(poly, k->point))
 
982
    }
 
983
 
 
984
    // Computer enclosing Clusters
 
985
    ClusterRefList::const_iterator clFinish = clusterRefs.end();
 
986
    for (ClusterRefList::const_iterator i = clusterRefs.begin();
 
987
            i != clFinish; ++i)
 
988
    {
 
989
        if (inPolyGen((*i)->polygon(), pt->point))
 
990
        {
 
991
            enclosingClusters[pt->id].insert((*i)->id());
 
992
        }
 
993
    }
 
994
}
 
995
 
 
996
 
 
997
void Router::adjustClustersWithAdd(const PolygonInterface& poly,
 
998
        const int p_cluster)
 
999
{
 
1000
    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
 
1001
            k = k->lstNext)
 
1002
    {
 
1003
        if (inPolyGen(poly, k->point))
 
1004
        {
 
1005
            enclosingClusters[k->id].insert(p_cluster);
 
1006
        }
 
1007
    }
 
1008
}
 
1009
 
 
1010
 
 
1011
void Router::adjustClustersWithDel(const int p_cluster)
 
1012
{
 
1013
    for (ContainsMap::iterator k = enclosingClusters.begin();
 
1014
            k != enclosingClusters.end(); ++k)
 
1015
    {
 
1016
        (*k).second.erase(p_cluster);
 
1017
    }
 
1018
}
 
1019
 
 
1020
 
 
1021
void Router::adjustContainsWithAdd(const Polygon& poly, const int p_shape)
 
1022
{
 
1023
    // Don't count points on the border as being inside.
 
1024
    bool countBorder = false;
 
1025
 
 
1026
    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
 
1027
            k = k->lstNext)
 
1028
    {
 
1029
        if (inPoly(poly, k->point, countBorder))
512
1030
        {
513
1031
            contains[k->id].insert(p_shape);
514
1032
        }
518
1036
 
519
1037
void Router::adjustContainsWithDel(const int p_shape)
520
1038
{
521
 
    for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
522
 
            k = k->lstNext)
 
1039
    for (ContainsMap::iterator k = contains.begin(); k != contains.end(); ++k)
523
1040
    {
524
 
        contains[k->id].erase(p_shape);
 
1041
        (*k).second.erase(p_shape);
525
1042
    }
526
1043
}
527
1044
 
537
1054
 
538
1055
void Router::markConnectors(ShapeRef *shape)
539
1056
{
540
 
    assert(SelectiveReroute);
541
 
 
542
 
    ConnRefList::iterator end = connRefs.end();
543
 
    for (ConnRefList::iterator it = connRefs.begin(); it != end; ++it)
 
1057
    if (RubberBandRouting)
 
1058
    {
 
1059
        // When rubber-band routing, we do no reroute connectors that
 
1060
        // may have a better route, only invalid connectors.
 
1061
        return;
 
1062
    }
 
1063
 
 
1064
    COLA_ASSERT(SelectiveReroute);
 
1065
 
 
1066
    ConnRefList::const_iterator end = connRefs.end();
 
1067
    for (ConnRefList::const_iterator it = connRefs.begin(); it != end; ++it)
544
1068
    {
545
1069
        ConnRef *conn = (*it);
546
1070
 
547
 
        if (conn->_route.pn == 0)
 
1071
        if (conn->_route.empty())
548
1072
        {
549
1073
            // Ignore uninitialised connectors.
550
1074
            continue;
556
1080
        }
557
1081
 
558
1082
        Point start = conn->_route.ps[0];
559
 
        Point end = conn->_route.ps[conn->_route.pn - 1];
 
1083
        Point end = conn->_route.ps[conn->_route.size() - 1];
560
1084
 
561
1085
        double conndist = conn->_route_dist;
562
1086
 
609
1133
                Point n_p2(p2.x - p1.x, p2.y - p1.y);
610
1134
                Point n_start(start.x - p1.x, start.y - p1.y);
611
1135
                Point n_end(end.x - p1.x, end.y - p1.y);
612
 
                //printf("n_p2:    (%.1f, %.1f)\n", n_p2.x, n_p2.y);
613
 
                //printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
614
 
                //printf("n_end:   (%.1f, %.1f)\n", n_end.x, n_end.y);
 
1136
                //db_printf("n_p2:    (%.1f, %.1f)\n", n_p2.x, n_p2.y);
 
1137
                //db_printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
 
1138
                //db_printf("n_end:   (%.1f, %.1f)\n", n_end.x, n_end.y);
615
1139
 
616
1140
                double theta = 0 - atan2(n_p2.y, n_p2.x);
617
 
                //printf("theta = %.2f\n", theta * (180 / PI));
 
1141
                //db_printf("theta = %.2f\n", theta * (180 / PI));
618
1142
 
619
1143
                Point r_p1(0, 0);
620
1144
                Point r_p2 = n_p2;
630
1154
                start.y = cosv * n_start.y + sinv * n_start.x;
631
1155
                end.x = cosv * n_end.x - sinv * n_end.y;
632
1156
                end.y = cosv * n_end.y + sinv * n_end.x;
633
 
                //printf("r_p2:    (%.1f, %.1f)\n", r_p2.x, r_p2.y);
634
 
                //printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
635
 
                //printf("r_end:   (%.1f, %.1f)\n", end.x, end.y);
 
1157
                //db_printf("r_p2:    (%.1f, %.1f)\n", r_p2.x, r_p2.y);
 
1158
                //db_printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
 
1159
                //db_printf("r_end:   (%.1f, %.1f)\n", end.x, end.y);
636
1160
 
637
 
                if (((int) r_p2.y) != 0)
638
 
                {
639
 
                    printf("r_p2.y: %f != 0\n", r_p2.y);
640
 
                    std::abort();
641
 
                }
642
1161
                // This might be slightly off.
 
1162
                if (fabs(r_p2.y) > 0.0001)
 
1163
                {
 
1164
                    db_printf("r_p2.y: %f != 0\n", r_p2.y);
 
1165
                }
643
1166
                r_p2.y = 0;
644
1167
 
645
1168
                offy = r_p1.y;
679
1202
                x = ((b*c) + (a*d)) / (b + d);
680
1203
            }
681
1204
 
682
 
            //printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
683
 
            //printf("x = %.1f\n", x);
 
1205
            //db_printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
 
1206
            //db_printf("x = %.1f\n", x);
684
1207
 
685
1208
            x = std::max(min, x);
686
1209
            x = std::min(max, x);
687
1210
 
688
 
            //printf("x = %.1f\n", x);
 
1211
            //db_printf("x = %.1f\n", x);
689
1212
 
690
1213
            Point xp;
691
1214
            if (p1.x == p2.x)
698
1221
                xp.x = x;
699
1222
                xp.y = offy;
700
1223
            }
701
 
            //printf("(%.1f, %.1f)\n", xp.x, xp.y);
 
1224
            //db_printf("(%.1f, %.1f)\n", xp.x, xp.y);
702
1225
 
703
 
            e1 = dist(start, xp);
704
 
            e2 = dist(xp, end);
 
1226
            e1 = euclideanDist(start, xp);
 
1227
            e2 = euclideanDist(xp, end);
705
1228
            estdist = e1 + e2;
706
1229
 
707
1230
 
708
 
            //printf("is %.1f < %.1f\n", estdist, conndist);
 
1231
            //db_printf("is %.1f < %.1f\n", estdist, conndist);
709
1232
            if (estdist < conndist)
710
1233
            {
711
1234
#ifdef SELECTIVE_DEBUG
712
1235
                //double angle = AngleAFromThreeSides(dist(start, end),
713
1236
                //        e1, e2);
714
 
                printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
 
1237
                db_printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
715
1238
                        conn->_id, estdist, conndist);
716
1239
#endif
717
1240
                conn->_needs_reroute_flag = true;
723
1246
}
724
1247
 
725
1248
 
 
1249
ConnType Router::validConnType(const ConnType select) const
 
1250
{
 
1251
    if (select != ConnType_None)
 
1252
    {
 
1253
        if ((select == ConnType_Orthogonal) && _orthogonalRouting)
 
1254
        {
 
1255
            return ConnType_Orthogonal;
 
1256
        }
 
1257
        else if ((select == ConnType_PolyLine) && _polyLineRouting)
 
1258
        {
 
1259
            return ConnType_PolyLine;
 
1260
        }
 
1261
    }
 
1262
 
 
1263
    if (_polyLineRouting)
 
1264
    {
 
1265
        return ConnType_PolyLine;
 
1266
    }
 
1267
    else if (_orthogonalRouting)
 
1268
    {
 
1269
        return ConnType_Orthogonal;
 
1270
    }
 
1271
    return ConnType_None;
 
1272
}
 
1273
 
 
1274
 
 
1275
void Router::setRoutingPenalty(const PenaltyType penType, const double penVal)
 
1276
{
 
1277
    COLA_ASSERT(penType < lastPenaltyMarker);
 
1278
    if (penVal < 0)
 
1279
    {
 
1280
        // Set some sensible penalty.
 
1281
        switch (penType)
 
1282
        {
 
1283
            case segmentPenalty:
 
1284
                _routingPenalties[penType] = 50;
 
1285
                break;
 
1286
            case fixedSharedPathPenalty:
 
1287
                _routingPenalties[penType] = 110;
 
1288
                break;
 
1289
            case anglePenalty:
 
1290
                _routingPenalties[penType] = 50;
 
1291
                break;
 
1292
            case crossingPenalty:
 
1293
                _routingPenalties[penType] = 200;
 
1294
                break;
 
1295
            case clusterCrossingPenalty:
 
1296
                _routingPenalties[penType] = 4000;
 
1297
                break;
 
1298
            default:
 
1299
                _routingPenalties[penType] = 50;
 
1300
                break;
 
1301
        }
 
1302
    }
 
1303
    else
 
1304
    {
 
1305
        _routingPenalties[penType] = penVal;
 
1306
    }
 
1307
}
 
1308
 
 
1309
 
 
1310
double Router::routingPenalty(const PenaltyType penType) const
 
1311
{
 
1312
    COLA_ASSERT(penType < lastPenaltyMarker);
 
1313
    return _routingPenalties[penType];
 
1314
}
 
1315
 
 
1316
 
 
1317
double& Router::penaltyRef(const PenaltyType penType)
 
1318
{
 
1319
    COLA_ASSERT(penType < lastPenaltyMarker);
 
1320
    return _routingPenalties[penType];
 
1321
}
 
1322
 
 
1323
 
726
1324
void Router::printInfo(void)
727
1325
{
728
1326
    FILE *fp = stdout;
735
1333
    int st_endpoints = 0;
736
1334
    int st_valid_shape_visedges = 0;
737
1335
    int st_valid_endpt_visedges = 0;
 
1336
    int st_orthogonal_visedges = 0;
738
1337
    int st_invalid_visedges = 0;
739
1338
    VertInf *finish = vertices.end();
740
1339
    for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
775
1374
    {
776
1375
        st_invalid_visedges++;
777
1376
    }
 
1377
    for (EdgeInf *t = visOrthogGraph.begin(); t != visOrthogGraph.end();
 
1378
            t = t->lstNext)
 
1379
    {
 
1380
        st_orthogonal_visedges++;
 
1381
    }
778
1382
    fprintf(fp, "Number of shapes: %d\n", st_shapes);
779
1383
    fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
780
1384
            st_vertices + st_endpoints, st_vertices, st_endpoints);
 
1385
    fprintf(fp, "Number of orhtog_vis_edges: %d\n", st_orthogonal_visedges);
781
1386
    fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
782
1387
            "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
783
1388
            st_valid_endpt_visedges, st_valid_shape_visedges +
787
1392
    fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
788
1393
    fprintf(fp, "----------------------\n");
789
1394
 
790
 
    fprintf(fp, "ADDS:  "); timers.Print(tmAdd);
791
 
    fprintf(fp, "DELS:  "); timers.Print(tmDel);
792
 
    fprintf(fp, "MOVS:  "); timers.Print(tmMov);
793
 
    fprintf(fp, "***S:  "); timers.Print(tmSev);
794
 
    fprintf(fp, "PTHS:  "); timers.Print(tmPth);
 
1395
    fprintf(fp, "ADDS:  "); timers.Print(tmAdd, fp);
 
1396
    fprintf(fp, "DELS:  "); timers.Print(tmDel, fp);
 
1397
    fprintf(fp, "MOVS:  "); timers.Print(tmMov, fp);
 
1398
    fprintf(fp, "***S:  "); timers.Print(tmSev, fp);
 
1399
    fprintf(fp, "PTHS:  "); timers.Print(tmPth, fp);
 
1400
    fprintf(fp, "OrthogGraph:  "); timers.Print(tmOrthogGraph, fp);
 
1401
    fprintf(fp, "OrthogRoute:  "); timers.Print(tmOrthogRoute, fp);
 
1402
    fprintf(fp, "OrthogCentre:  "); timers.Print(tmOrthogCentre, fp);
 
1403
    fprintf(fp, "OrthogNudge:  "); timers.Print(tmOrthogNudge, fp);
795
1404
    fprintf(fp, "\n");
 
1405
    timers.Reset();
 
1406
}
 
1407
 
 
1408
 
 
1409
static const double LIMIT = 100000000;
 
1410
 
 
1411
static void reduceRange(double& val)
 
1412
{
 
1413
    val = std::min(val, LIMIT);
 
1414
    val = std::max(val, -LIMIT);
 
1415
}
 
1416
 
 
1417
 
 
1418
//=============================================================================
 
1419
// The following methods are for testing and debugging.
 
1420
 
 
1421
 
 
1422
bool Router::existsOrthogonalPathOverlap(void)
 
1423
{
 
1424
    ConnRefList::iterator fin = connRefs.end();
 
1425
    for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
 
1426
    {
 
1427
        Avoid::Polygon iRoute = (*i)->displayRoute();
 
1428
        ConnRefList::iterator j = i;
 
1429
        for (++j; j != fin; ++j)
 
1430
        {
 
1431
            // Determine if this pair overlap
 
1432
            Avoid::Polygon jRoute = (*j)->displayRoute();
 
1433
            CrossingsInfoPair crossingInfo = std::make_pair(0, 0);
 
1434
            for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
 
1435
            {
 
1436
                const bool finalSegment = ((jInd + 1) == jRoute.size());
 
1437
                CrossingsInfoPair crossingInfo = countRealCrossings(
 
1438
                        iRoute, true, jRoute, jInd, true,
 
1439
                        finalSegment, NULL, NULL, *i, *j);
 
1440
 
 
1441
                if ((crossingInfo.second & CROSSING_SHARES_PATH) &&
 
1442
                    (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) &&
 
1443
                    !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END))
 
1444
                {
 
1445
                    // We looking for fixedSharedPaths and there is a
 
1446
                    // fixedSharedPath.
 
1447
                    return true;
 
1448
                }
 
1449
            }
 
1450
        }
 
1451
    }
 
1452
    return false;
 
1453
}
 
1454
 
 
1455
 
 
1456
bool Router::existsOrthogonalTouchingCorners(void)
 
1457
{
 
1458
    ConnRefList::iterator fin = connRefs.end();
 
1459
    for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
 
1460
    {
 
1461
        Avoid::Polygon iRoute = (*i)->displayRoute();
 
1462
        ConnRefList::iterator j = i;
 
1463
        for (++j; j != fin; ++j)
 
1464
        {
 
1465
            // Determine if this pair overlap
 
1466
            Avoid::Polygon jRoute = (*j)->displayRoute();
 
1467
            CrossingsInfoPair crossingInfo = std::make_pair(0, 0);
 
1468
            for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
 
1469
            {
 
1470
                const bool finalSegment = ((jInd + 1) == jRoute.size());
 
1471
                CrossingsInfoPair crossingInfo = countRealCrossings(
 
1472
                        iRoute, true, jRoute, jInd, true,
 
1473
                        finalSegment, NULL, NULL, *i, *j);
 
1474
 
 
1475
                if (crossingInfo.second & CROSSING_TOUCHES)
 
1476
                {
 
1477
                    return true;
 
1478
                }
 
1479
            }
 
1480
        }
 
1481
    }
 
1482
    return false;
 
1483
}
 
1484
 
 
1485
 
 
1486
void Router::outputInstanceToSVG(std::string instanceName)
 
1487
{
 
1488
    std::string filename;
 
1489
    if (!instanceName.empty())
 
1490
    {
 
1491
        filename = instanceName;
 
1492
    }
 
1493
    else
 
1494
    {
 
1495
        filename = "libavoid-debug";
 
1496
    }
 
1497
    filename += ".svg";
 
1498
    FILE *fp = fopen(filename.c_str(), "w");
 
1499
 
 
1500
    if (fp == NULL)
 
1501
    {
 
1502
        return;
 
1503
    }
 
1504
 
 
1505
    double minX = LIMIT;
 
1506
    double minY = LIMIT;
 
1507
    double maxX = -LIMIT;
 
1508
    double maxY = -LIMIT;
 
1509
 
 
1510
    VertInf *curr = vertices.connsBegin();
 
1511
    while (curr)
 
1512
    {
 
1513
        Point p = curr->point;
 
1514
 
 
1515
        reduceRange(p.x);
 
1516
        reduceRange(p.y);
 
1517
 
 
1518
        if (p.x > -LIMIT)
 
1519
        {
 
1520
            minX = std::min(minX, p.x);
 
1521
        }
 
1522
        if (p.x < LIMIT)
 
1523
        {
 
1524
            maxX = std::max(maxX, p.x);
 
1525
        }
 
1526
        if (p.y > -LIMIT)
 
1527
        {
 
1528
            minY = std::min(minY, p.y);
 
1529
        }
 
1530
        if (p.y < LIMIT)
 
1531
        {
 
1532
            maxY = std::max(maxY, p.y);
 
1533
        }
 
1534
        curr = curr->lstNext;
 
1535
    }
 
1536
    minX -= 50;
 
1537
    minY -= 50;
 
1538
    maxX += 50;
 
1539
    maxY += 50;
 
1540
 
 
1541
    fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
 
1542
    fprintf(fp, "<svg xmlns:inkscape=\"http://www.inkscape.org/namespaces/inkscape\" xmlns=\"http://www.w3.org/2000/svg\" width=\"100%%\" height=\"100%%\" viewBox=\"%g %g %g %g\">\n", minX, minY, maxX - minX, maxY - minY);
 
1543
 
 
1544
    // Output source code to generate this instance of the router.
 
1545
    fprintf(fp, "<!-- Source code to generate this instance:\n");
 
1546
    fprintf(fp, "#include \"libavoid/libavoid.h\"\n");
 
1547
    fprintf(fp, "using namespace Avoid;\n");
 
1548
    fprintf(fp, "int main(void) {\n");
 
1549
    fprintf(fp, "    Router *router = new Router(\n");
 
1550
    fprintf(fp, "            PolyLineRouting | OrthogonalRouting);\n");
 
1551
    for (size_t p = 0; p < lastPenaltyMarker; ++p)
 
1552
    {
 
1553
        fprintf(fp, "    router->setRoutingPenalty((PenaltyType)%lu, %g);\n",
 
1554
                static_cast<long unsigned int>(p), _routingPenalties[p]);
 
1555
    }
 
1556
    fprintf(fp, "    router->setOrthogonalNudgeDistance(%g);\n\n",
 
1557
            orthogonalNudgeDistance());
 
1558
    ShapeRefList::iterator shRefIt = shapeRefs.begin();
 
1559
    while (shRefIt != shapeRefs.end())
 
1560
    {
 
1561
        ShapeRef *shRef = *shRefIt;
 
1562
        fprintf(fp, "    Polygon poly%u(%lu);\n",
 
1563
                shRef->id(), static_cast<long unsigned int>(shRef->polygon().size()));
 
1564
        for (size_t i = 0; i < shRef->polygon().size(); ++i)
 
1565
        {
 
1566
            fprintf(fp, "    poly%u.ps[%lu] = Point(%g, %g);\n",
 
1567
                    shRef->id(), static_cast<long unsigned int>(i), shRef->polygon().at(i).x,
 
1568
                    shRef->polygon().at(i).y);
 
1569
        }
 
1570
        fprintf(fp, "    ShapeRef *shapeRef%u = new ShapeRef(router, poly%u, "
 
1571
                "%u);\n", shRef->id(), shRef->id(), shRef->id());
 
1572
        fprintf(fp, "    router->addShape(shapeRef%u);\n\n", shRef->id());
 
1573
        ++shRefIt;
 
1574
    }
 
1575
    ConnRefList::reverse_iterator revConnRefIt = connRefs.rbegin();
 
1576
    while (revConnRefIt != connRefs.rend())
 
1577
    {
 
1578
        ConnRef *connRef = *revConnRefIt;
 
1579
        fprintf(fp, "    ConnRef *connRef%u = new ConnRef(router, %u);\n",
 
1580
                connRef->id(), connRef->id());
 
1581
        if (connRef->src())
 
1582
        {
 
1583
            fprintf(fp, "    ConnEnd srcPt%u(Point(%g, %g), %u);\n",
 
1584
                    connRef->id(), connRef->src()->point.x,
 
1585
                    connRef->src()->point.y, connRef->src()->visDirections);
 
1586
            fprintf(fp, "    connRef%u->setSourceEndpoint(srcPt%u);\n",
 
1587
                    connRef->id(), connRef->id());
 
1588
        }
 
1589
        if (connRef->dst())
 
1590
        {
 
1591
            fprintf(fp, "    ConnEnd dstPt%u(Point(%g, %g), %u);\n",
 
1592
                    connRef->id(), connRef->dst()->point.x,
 
1593
                    connRef->dst()->point.y, connRef->dst()->visDirections);
 
1594
            fprintf(fp, "    connRef%u->setDestEndpoint(dstPt%u);\n",
 
1595
                    connRef->id(), connRef->id());
 
1596
        }
 
1597
        fprintf(fp, "    connRef%u->setRoutingType((ConnType)%u);\n\n",
 
1598
                connRef->id(), connRef->routingType());
 
1599
        ++revConnRefIt;
 
1600
    }
 
1601
    fprintf(fp, "    router->processTransaction();\n");
 
1602
    fprintf(fp, "    router->outputInstanceToSVG();\n");
 
1603
    fprintf(fp, "    delete router;\n");
 
1604
    fprintf(fp, "    return 0;\n");
 
1605
    fprintf(fp, "};\n");
 
1606
    fprintf(fp, "-->\n");
 
1607
 
 
1608
 
 
1609
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1610
            "inkscape:label=\"ShapesPoly\">\n");
 
1611
    shRefIt = shapeRefs.begin();
 
1612
    while (shRefIt != shapeRefs.end())
 
1613
    {
 
1614
        ShapeRef *shRef = *shRefIt;
 
1615
 
 
1616
        fprintf(fp, "<path id=\"poly-%u\" style=\"stroke-width: 1px; "
 
1617
                "stroke: black; fill: blue; fill-opacity: 0.3;\" d=\"",
 
1618
                shRef->id());
 
1619
        for (size_t i = 0; i < shRef->polygon().size(); ++i)
 
1620
        {
 
1621
            fprintf(fp, "%c %g,%g ", ((i == 0) ? 'M' : 'L'),
 
1622
                    shRef->polygon().at(i).x, shRef->polygon().at(i).y);
 
1623
        }
 
1624
        fprintf(fp, "Z\" />\n");
 
1625
        ++shRefIt;
 
1626
    }
 
1627
    fprintf(fp, "</g>\n");
 
1628
 
 
1629
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1630
            "style=\"display: none;\" "
 
1631
            "inkscape:label=\"ShapesRect\">\n");
 
1632
    shRefIt = shapeRefs.begin();
 
1633
    while (shRefIt != shapeRefs.end())
 
1634
    {
 
1635
        ShapeRef *shRef = *shRefIt;
 
1636
        double minX, minY, maxX, maxY;
 
1637
        shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
 
1638
 
 
1639
        fprintf(fp, "<rect id=\"rect-%u\" x=\"%g\" y=\"%g\" width=\"%g\" height=\"%g\" "
 
1640
                "style=\"stroke-width: 1px; stroke: black; fill: blue; fill-opacity: 0.3;\" />\n",
 
1641
                shRef->id(), minX, minY, maxX - minX, maxY - minY);
 
1642
        ++shRefIt;
 
1643
    }
 
1644
    fprintf(fp, "</g>\n");
 
1645
 
 
1646
 
 
1647
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1648
            "inkscape:label=\"VisGraph\""
 
1649
            ">\n");
 
1650
    EdgeInf *finish = NULL;
 
1651
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1652
            "style=\"display: none;\" "
 
1653
            "inkscape:label=\"VisGraph-shape\""
 
1654
            ">\n");
 
1655
    finish = visGraph.end();
 
1656
    for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext)
 
1657
    {
 
1658
        std::pair<VertID, VertID> ids = t->ids();
 
1659
        bool isShape = (ids.first.isShape) && (ids.second.isShape);
 
1660
        if (!isShape)
 
1661
        {
 
1662
            continue;
 
1663
        }
 
1664
        std::pair<Point, Point> ptpair = t->points();
 
1665
        Point p1 = ptpair.first;
 
1666
        Point p2 = ptpair.second;
 
1667
 
 
1668
        reduceRange(p1.x);
 
1669
        reduceRange(p1.y);
 
1670
        reduceRange(p2.x);
 
1671
        reduceRange(p2.y);
 
1672
 
 
1673
        fprintf(fp, "<path d=\"M %g,%g L %g,%g\" "
 
1674
                "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
 
1675
                p1.x, p1.y, p2.x, p2.y,
 
1676
                (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" :
 
1677
                "red");
 
1678
    }
 
1679
    fprintf(fp, "</g>\n");
 
1680
 
 
1681
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1682
            "style=\"display: none;\" "
 
1683
            "inkscape:label=\"VisGraph-conn\""
 
1684
            ">\n");
 
1685
    finish = visGraph.end();
 
1686
    for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext)
 
1687
    {
 
1688
        std::pair<VertID, VertID> ids = t->ids();
 
1689
        bool isShape = (ids.first.isShape) && (ids.second.isShape);
 
1690
        if (isShape)
 
1691
        {
 
1692
            continue;
 
1693
        }
 
1694
        std::pair<Point, Point> ptpair = t->points();
 
1695
        Point p1 = ptpair.first;
 
1696
        Point p2 = ptpair.second;
 
1697
 
 
1698
        reduceRange(p1.x);
 
1699
        reduceRange(p1.y);
 
1700
        reduceRange(p2.x);
 
1701
        reduceRange(p2.y);
 
1702
 
 
1703
        fprintf(fp, "<path d=\"M %g,%g L %g,%g\" "
 
1704
                "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
 
1705
                p1.x, p1.y, p2.x, p2.y,
 
1706
                (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" :
 
1707
                "red");
 
1708
    }
 
1709
    fprintf(fp, "</g>\n");
 
1710
    fprintf(fp, "</g>\n");
 
1711
 
 
1712
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1713
            "style=\"display: none;\" "
 
1714
            "inkscape:label=\"OrthogVisGraph\">\n");
 
1715
    finish = visOrthogGraph.end();
 
1716
    for (EdgeInf *t = visOrthogGraph.begin(); t != finish; t = t->lstNext)
 
1717
    {
 
1718
        std::pair<Point, Point> ptpair = t->points();
 
1719
        Point p1 = ptpair.first;
 
1720
        Point p2 = ptpair.second;
 
1721
 
 
1722
        reduceRange(p1.x);
 
1723
        reduceRange(p1.y);
 
1724
        reduceRange(p2.x);
 
1725
        reduceRange(p2.y);
 
1726
 
 
1727
        std::pair<VertID, VertID> ids = t->ids();
 
1728
 
 
1729
        fprintf(fp, "<path d=\"M %g,%g L %g,%g\" "
 
1730
                "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
 
1731
                p1.x, p1.y, p2.x, p2.y,
 
1732
                (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" :
 
1733
                "red");
 
1734
    }
 
1735
    fprintf(fp, "</g>\n");
 
1736
 
 
1737
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1738
            "style=\"display: none;\" "
 
1739
            "inkscape:label=\"RawConnectors\""
 
1740
            ">\n");
 
1741
    ConnRefList::iterator connRefIt = connRefs.begin();
 
1742
    while (connRefIt != connRefs.end())
 
1743
    {
 
1744
        ConnRef *connRef = *connRefIt;
 
1745
 
 
1746
        PolyLine route = connRef->route();
 
1747
        if (!route.empty())
 
1748
        {
 
1749
            fprintf(fp, "<path id=\"raw-%u\" d=\"M %g,%g ", connRef->id(),
 
1750
                    route.ps[0].x, route.ps[0].y);
 
1751
            for (size_t i = 1; i < route.size(); ++i)
 
1752
            {
 
1753
                fprintf(fp, "L %g,%g ", route.ps[i].x, route.ps[i].y);
 
1754
            }
 
1755
            fprintf(fp, "\" ");
 
1756
            if (connRef->src() && connRef->dst())
 
1757
            {
 
1758
                fprintf(fp, "debug=\"src: %d dst: %d\" ",
 
1759
                        connRef->src()->visDirections,
 
1760
                        connRef->dst()->visDirections);
 
1761
            }
 
1762
            fprintf(fp, "style=\"fill: none; stroke: black; "
 
1763
                    "stroke-width: 1px;\" />\n");
 
1764
        }
 
1765
 
 
1766
        ++connRefIt;
 
1767
    }
 
1768
    fprintf(fp, "</g>\n");
 
1769
 
 
1770
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1771
            "style=\"display: none;\" "
 
1772
            "inkscape:label=\"CurvedDisplayConnectors\""
 
1773
            ">\n");
 
1774
    connRefIt = connRefs.begin();
 
1775
    while (connRefIt != connRefs.end())
 
1776
    {
 
1777
        ConnRef *connRef = *connRefIt;
 
1778
 
 
1779
        PolyLine route = connRef->displayRoute().curvedPolyline(8);
 
1780
        if (!route.empty())
 
1781
        {
 
1782
            fprintf(fp, "<path id=\"curved-%u\" d=\"M %g,%g ", connRef->id(),
 
1783
                    route.ps[0].x, route.ps[0].y);
 
1784
            for (size_t i = 1; i < route.size(); ++i)
 
1785
            {
 
1786
                if (route.ts[i] == 'C')
 
1787
                {
 
1788
                    fprintf(fp, "%c %g,%g %g,%g %g,%g", route.ts[i],
 
1789
                            route.ps[i].x, route.ps[i].y,
 
1790
                            route.ps[i+1].x, route.ps[i+1].y,
 
1791
                            route.ps[i+2].x, route.ps[i+2].y);
 
1792
                    i += 2;
 
1793
                }
 
1794
                else
 
1795
                {
 
1796
                    fprintf(fp, "%c %g,%g ", route.ts[i],
 
1797
                            route.ps[i].x, route.ps[i].y);
 
1798
                }
 
1799
            }
 
1800
            fprintf(fp, "\" ");
 
1801
            if (connRef->src() && connRef->dst())
 
1802
            {
 
1803
                fprintf(fp, "debug=\"src: %d dst: %d\" ",
 
1804
                        connRef->src()->visDirections,
 
1805
                        connRef->dst()->visDirections);
 
1806
            }
 
1807
            fprintf(fp, "style=\"fill: none; stroke: black; "
 
1808
                    "stroke-width: 1px;\" />\n");
 
1809
        }
 
1810
 
 
1811
        ++connRefIt;
 
1812
    }
 
1813
    fprintf(fp, "</g>\n");
 
1814
 
 
1815
 
 
1816
    fprintf(fp, "<g inkscape:groupmode=\"layer\" "
 
1817
            "inkscape:label=\"DisplayConnectors\""
 
1818
            ">\n");
 
1819
    connRefIt = connRefs.begin();
 
1820
    while (connRefIt != connRefs.end())
 
1821
    {
 
1822
        ConnRef *connRef = *connRefIt;
 
1823
 
 
1824
        PolyLine route = connRef->displayRoute();
 
1825
        if (!route.empty())
 
1826
        {
 
1827
            fprintf(fp, "<path id=\"disp-%u\" d=\"M %g,%g ", connRef->id(),
 
1828
                    route.ps[0].x, route.ps[0].y);
 
1829
            for (size_t i = 1; i < route.size(); ++i)
 
1830
            {
 
1831
                fprintf(fp, "L %g,%g ", route.ps[i].x, route.ps[i].y);
 
1832
            }
 
1833
            fprintf(fp, "\" ");
 
1834
            if (connRef->src() && connRef->dst())
 
1835
            {
 
1836
                fprintf(fp, "debug=\"src: %d dst: %d\" ",
 
1837
                        connRef->src()->visDirections,
 
1838
                        connRef->dst()->visDirections);
 
1839
            }
 
1840
            fprintf(fp, "style=\"fill: none; stroke: black; "
 
1841
                    "stroke-width: 1px;\" />\n");
 
1842
        }
 
1843
 
 
1844
        ++connRefIt;
 
1845
    }
 
1846
    fprintf(fp, "</g>\n");
 
1847
 
 
1848
 
 
1849
    fprintf(fp, "</svg>\n");
 
1850
    fclose(fp);
796
1851
}
797
1852
 
798
1853