← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to dotneato/neatogen/splines.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
dotneato/neatogen/splines.c
 
1
/*
 
2
    This software may only be used by you under license from AT&T Corp.
 
3
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
 
4
    AT&T's Internet website having the URL:
 
5
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
 
6
    If you received this software without first entering into a license
 
7
    with AT&T, you have an infringing copy of this software and cannot use
 
8
    it without violating AT&T's intellectual property rights.
 
9
*/
 
10
 
 
11
#include "neato.h"
 
12
#include "pathplan.h"
 
13
#include "vispath.h"
 
14
 
 
15
#ifdef DMALLOC
 
16
#include "dmalloc.h"
 
17
#endif
 
18
 
 
19
extern void printvis (vconfig_t *cp);
 
20
static boolean swap_ends_p (edge_t *);
 
21
static void place_portlabel (edge_t *e, boolean head_p);
 
22
static int neato_set_aspect(graph_t *g, pointf* pf);
 
23
static splines *getsplinepoints (edge_t* e);
 
24
extern int      in_poly(Ppoly_t argpoly, Ppoint_t q);
 
25
 
 
26
void neato_compute_bb(graph_t *g)
 
27
{
 
28
        node_t          *n;
 
29
        edge_t          *e;
 
30
        box                     b,bb;
 
31
        point           pt,s2;
 
32
        int             i,j;
 
33
 
 
34
        bb.LL = pointof(MAXINT,MAXINT);
 
35
        bb.UR = pointof(-MAXINT,-MAXINT);
 
36
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
37
                pt = coord(n);
 
38
                s2.x = n->u.xsize/2+1; s2.y = n->u.ysize/2+1;
 
39
                b.LL = sub_points(pt,s2);
 
40
                b.UR = add_points(pt,s2);
 
41
 
 
42
                bb.LL.x = MIN(bb.LL.x,b.LL.x);
 
43
                bb.LL.y = MIN(bb.LL.y,b.LL.y);
 
44
                bb.UR.x = MAX(bb.UR.x,b.UR.x);
 
45
                bb.UR.y = MAX(bb.UR.y,b.UR.y);
 
46
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
47
                        if (e->u.spl == 0) continue;
 
48
                        for (i = 0; i < e->u.spl->size; i++) {
 
49
                                for (j = 0; j < e->u.spl->list[i].size; j++) {
 
50
                                        pt = e->u.spl->list[i].list[j];
 
51
                                        if (bb.LL.x > pt.x) bb.LL.x = pt.x;
 
52
                                        if (bb.LL.y > pt.y) bb.LL.y = pt.y;
 
53
                                        if (bb.UR.x < pt.x) bb.UR.x = pt.x;
 
54
                                        if (bb.UR.y < pt.y) bb.UR.y = pt.y;
 
55
                                }
 
56
                        }
 
57
                }
 
58
        }
 
59
        g->u.bb = bb;
 
60
}
 
61
 
 
62
 
 
63
static bezier *new_spline (edge_t *e, int sz)
 
64
{
 
65
        bezier *rv;
 
66
 
 
67
        if (e->u.spl == NULL) e->u.spl = NEW (splines);
 
68
        e->u.spl->list = ALLOC (e->u.spl->size + 1, e->u.spl->list, bezier);
 
69
        rv = &(e->u.spl->list[e->u.spl->size++]);
 
70
        rv->list = N_NEW (sz, point);
 
71
        rv->size = sz;
 
72
        rv->sflag = rv->eflag = FALSE;
 
73
        return rv;
 
74
}
 
75
 
 
76
static Ppoint_t mkPoint(point p) {Ppoint_t rv; rv.x = p.x; rv.y = p.y; return rv;}
 
77
 
 
78
 
 
79
static void
 
80
make_barriers(Ppoly_t **poly, int npoly, int pp, int qp, Pedge_t **barriers, int *n_barriers){
 
81
    int     i, j, k, n, b;
 
82
    Pedge_t *bar;
 
83
 
 
84
    n = 0;
 
85
    for (i = 0; i < npoly; i++) {
 
86
        if (i == pp) continue;
 
87
        if (i == qp) continue;
 
88
        n = n + poly[i]->pn;
 
89
    }
 
90
    bar = malloc(n * sizeof(Pedge_t));
 
91
    b = 0;
 
92
    for (i = 0; i < npoly; i++) {
 
93
        if (i == pp) continue;
 
94
        if (i == qp) continue;
 
95
        for (j = 0; j < poly[i]->pn; j++) {
 
96
            k = j + 1;
 
97
            if (k >= poly[i]->pn) k = 0;
 
98
            bar[b].a = poly[i]->ps[j];
 
99
            bar[b].b = poly[i]->ps[k];
 
100
            b++;
 
101
        }
 
102
    }
 
103
    assert(b == n);
 
104
    *barriers = bar;
 
105
    *n_barriers = n;
 
106
}
 
107
 
 
108
extern int Plegal_arrangement( Ppoly_t  **polys, int    n_polys);
 
109
 
 
110
static int
 
111
numFields (char* pos)
 
112
{
 
113
    int    cnt = 0;
 
114
    char   c;
 
115
 
 
116
    while (isspace(*pos)) pos++;
 
117
    while (*pos) {
 
118
      cnt++;
 
119
      while ((c = *pos) && !isspace(c)) pos++;  /* skip token */
 
120
      while (isspace(*pos)) pos++;
 
121
    }
 
122
    return cnt;
 
123
}
 
124
 
 
125
static point*
 
126
user_spline (attrsym_t* symptr, edge_t* e, int* np, pointf* offset,
 
127
             int doScale, pointf* scalef)
 
128
{
 
129
    char*  pos;
 
130
    int    i, n, nc;
 
131
    point* ps = 0;
 
132
    point* pp;
 
133
    double x,y;
 
134
 
 
135
    if (symptr == NULL) return 0;
 
136
    pos = agxget(e,symptr->index);
 
137
    if (*pos == '\0') return 0;
 
138
    n = numFields (pos);
 
139
    *np = n;
 
140
    if (n > 1) {
 
141
      ps = ALLOC(n,0,point);
 
142
      pp = ps;
 
143
      while (n) {
 
144
        i = sscanf(pos,"%lf,%lf%n",&x,&y,&nc);
 
145
        if (i < 2) {
 
146
          free (ps);
 
147
          ps = 0;
 
148
          break;
 
149
        }
 
150
        pos = pos+nc;
 
151
        if (doScale) {
 
152
          pp->x = (int)((scalef->x)*(x - offset->x));
 
153
          pp->y = (int)((scalef->y)*(y - offset->y));
 
154
        }
 
155
        else {
 
156
          pp->x = (int)(x - offset->x);
 
157
          pp->y = (int)(y - offset->y);
 
158
        }
 
159
        pp++;
 
160
        n--;
 
161
      }
 
162
    }
 
163
    return ps;
 
164
}
 
165
 
 
166
void spline_edges(graph_t *g)
 
167
{
 
168
        node_t          *n;
 
169
        edge_t          *e;
 
170
        point           dumb[4],d,ld;
 
171
        pointf          offset, polyp;
 
172
        Ppoly_t         **obs;
 
173
        polygon_t       *poly;
 
174
        int             i=0, j, npoly, sides;
 
175
        extern void     poly_init(node_t *);
 
176
        Ppoint_t        p,q;
 
177
        vconfig_t       *vconfig;
 
178
        Pedge_t     *barriers;
 
179
        double          adj=0.0, SEP;
 
180
        char            *str;
 
181
    point       *sp;
 
182
    pointf      scalef;
 
183
    int         doScale;
 
184
    int         pn;
 
185
        attrsym_t       *symptr=NULL;
 
186
 
 
187
        if ((str = agget(g,"sep"))) {SEP = 1.0 + atof(str);}
 
188
        else SEP = 1.01;
 
189
        neato_compute_bb(g);
 
190
        offset = cvt2ptf(g->u.bb.LL);
 
191
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
192
                n->u.pos[0] -= offset.x;
 
193
                n->u.pos[1] -= offset.y;
 
194
        }
 
195
        g->u.bb.UR.x -= g->u.bb.LL.x;
 
196
        g->u.bb.UR.y -= g->u.bb.LL.y;
 
197
        g->u.bb.LL.x = 0;
 
198
        g->u.bb.LL.y = 0;
 
199
        doScale = neato_set_aspect(g,&scalef);
 
200
        
 
201
        /* build configuration */
 
202
        if (mapbool(agget(g,"splines"))) {
 
203
                obs = N_NEW (agnnodes(g), Ppoly_t*);
 
204
                for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
205
                        n->u.coord.x = POINTS(n->u.pos[0]);
 
206
                        n->u.coord.y = POINTS(n->u.pos[1]);
 
207
        
 
208
                        if (n->u.shape->initfn == poly_init) {
 
209
                                obs[i] = NEW(Ppoly_t);
 
210
                                poly = (polygon_t*) n->u.shape_info;
 
211
                                if (poly->sides >= 3) {
 
212
                                        sides = poly->sides;
 
213
                                }
 
214
                                else {  /* ellipse */
 
215
                                        sides = 8;
 
216
                                        adj = drand48() * .01;
 
217
                                }
 
218
                                obs[i]->pn = sides;
 
219
                                obs[i]->ps = N_NEW(sides, Ppoint_t);
 
220
                                /* assuming polys are in CCW order, and pathplan needs CW */
 
221
                                for (j = 0; j < sides; j++) {
 
222
                                        if (poly->sides >= 3) {
 
223
                                                polyp.x = POINTS(poly->vertices[j].x) * SEP;
 
224
                                                polyp.y = POINTS(poly->vertices[j].y) * SEP;
 
225
                                        }
 
226
                                        else {
 
227
                                                double  c, s;
 
228
                                                c = cos(2.0 * PI * j / sides + adj);
 
229
                                                s = sin(2.0 * PI * j / sides + adj);
 
230
                                                polyp.x = SEP * c * (n->u.lw + n->u.rw) / 2.0;
 
231
                                                polyp.y = SEP * s * n->u.ht / 2.0;
 
232
                                        }
 
233
                                        obs[i]->ps[sides - j - 1].x = polyp.x + n->u.coord.x;
 
234
                                        obs[i]->ps[sides - j - 1].y = polyp.y + n->u.coord.y;
 
235
                                }
 
236
                                i++;
 
237
                        }
 
238
                }
 
239
        }
 
240
        else {
 
241
        obs = 0;
 
242
                for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
243
                        n->u.coord.x = POINTS(n->u.pos[0]);
 
244
                        n->u.coord.y = POINTS(n->u.pos[1]);
 
245
        }
 
246
    }
 
247
        npoly = i;
 
248
        if (obs && NOT(Plegal_arrangement(obs,npoly))) {
 
249
                if (Verbose) fprintf(stderr,"nodes touch - falling back to straight line edges\n");
 
250
                vconfig = 0;
 
251
        }
 
252
        else {
 
253
                if (obs) vconfig = Pobsopen(obs,npoly);
 
254
                else vconfig = 0;
 
255
        }
 
256
 
 
257
        /* route edges  */
 
258
        if (Verbose) fprintf(stderr,"neato: compute paths\n");
 
259
        if (vconfig) {
 
260
                /* path-finding pass */
 
261
                for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
262
                        for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
263
                                Ppolyline_t line;
 
264
                                int                     pp, qp;
 
265
 
 
266
                                p = mkPoint(coord(e->tail));
 
267
                                q = mkPoint(coord(e->head));
 
268
 
 
269
                           /* determine the polygons (if any) that contain the endpoints */
 
270
                                pp = qp = POLYID_NONE;
 
271
                                for (i = 0; i < npoly; i++) {
 
272
                                        if ((pp == POLYID_NONE) && in_poly(*obs[i], p)) pp = i;
 
273
                                        if ((qp == POLYID_NONE) && in_poly(*obs[i], q)) qp = i;
 
274
                                }
 
275
                                /*Pobspath(vconfig, p, POLYID_UNKNOWN, q, POLYID_UNKNOWN, &line);*/
 
276
                                Pobspath(vconfig, p, pp, q, qp, &line);
 
277
                                e->u.path = line;
 
278
                        }
 
279
                }
 
280
        }
 
281
        if (Verbose && vconfig) fprintf(stderr,"neato: fit splines...\n");
 
282
 
 
283
    if (Nop > 1) {
 
284
      symptr = agfindattr(g->proto->e,"pos");
 
285
      if (PSinputscale) {
 
286
        offset.x *= PSinputscale;
 
287
        offset.y *= PSinputscale;
 
288
      }
 
289
    }
 
290
 
 
291
        /* spline-drawing pass */
 
292
        for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
293
                for (e = agfstout(g,n); e; e = agnxtout(g,e)) {
 
294
 
 
295
                        p = mkPoint(coord(e->tail));
 
296
                        q = mkPoint(coord(e->head));
 
297
            if ((Nop > 1) && 
 
298
              ((sp = user_spline(symptr,e,&pn,&offset,doScale,&scalef)) != 0)) {
 
299
                                clip_and_install(e,sp,pn);
 
300
                                free(sp);
 
301
            }
 
302
                        else if (vconfig && (e->tail != e->head)) {
 
303
                                Ppolyline_t line, spline;
 
304
                                Pvector_t       slopes[2];
 
305
                                int                     n_barriers;
 
306
                                int                     pp, qp;
 
307
                                point           *ispline;
 
308
 
 
309
                           /* determine the polygons (if any) that contain the endpoints */
 
310
                                pp = qp = POLYID_NONE;
 
311
                                for (i = 0; i < npoly; i++) {
 
312
                                        if ((pp == POLYID_NONE) && in_poly(*obs[i], p)) pp = i;
 
313
                                        if ((qp == POLYID_NONE) && in_poly(*obs[i], q)) qp = i;
 
314
                                }
 
315
                                line = e->u.path;
 
316
 
 
317
                                make_barriers(obs, npoly, pp, qp, &barriers, &n_barriers);
 
318
                                slopes[0].x = slopes[0].y = 0.0;
 
319
                                slopes[1].x = slopes[1].y = 0.0;
 
320
                                Proutespline (barriers, n_barriers, line, slopes, &spline);
 
321
 
 
322
                                /* north why did you ever use int coords */
 
323
                                ispline = malloc(sizeof(point)*spline.pn);
 
324
                                for (i = 0; i < spline.pn; i++) {
 
325
                                        ispline[i].x = ROUND(spline.ps[i].x);
 
326
                                        ispline[i].y = ROUND(spline.ps[i].y);
 
327
                                }
 
328
                                if (Verbose) fprintf(stderr,"spline %s %s\n",e->tail->name,e->head->name);
 
329
                                clip_and_install(e,ispline,spline.pn);
 
330
                                free(ispline);
 
331
                                free(barriers);
 
332
                        }
 
333
                        else {
 
334
                                dumb[0] = coord(e->tail);
 
335
                                dumb[3] = coord(e->head);
 
336
                                if (e->tail != e->head) {
 
337
                                        d = sub_points(dumb[3],dumb[0]);
 
338
                                        d.x = d.x / 3;
 
339
                                        d.y = d.y / 3;
 
340
                                        dumb[1] = add_points(dumb[0],d);
 
341
                                        dumb[2] = sub_points(dumb[3],d);
 
342
                                }
 
343
                                else {  /* self arc */
 
344
                                        d.x = e->head->u.rw + POINTS(.66 * SEP);
 
345
                                        d.y = 0;
 
346
                                        dumb[1] = dumb[2] = add_points(dumb[0],d);
 
347
                                        dumb[1].y += d.x;
 
348
                                        dumb[2].y -= d.x;
 
349
                                }
 
350
                                clip_and_install(e,dumb,4);
 
351
                        }
 
352
 
 
353
                        if (e->u.label) {
 
354
                                d.x = (q.x + p.x)/ 2;
 
355
                                d.y = (p.y + q.y)/ 2;
 
356
                                if (abs(p.x - q.x) > abs(p.y - q.y)) {
 
357
                                        ld.x = 0; ld.y = POINTS(e->u.label->dimen.y)/2 + 2;
 
358
                                }
 
359
                                else {
 
360
                                        ld.x = POINTS(e->u.label->dimen.y)/2+e->u.label->fontsize;
 
361
                                        ld.y = 0;
 
362
                                }
 
363
                                d = add_points(d,ld);
 
364
                                e->u.label->p = d;
 
365
                        }
 
366
                }
 
367
        }
 
368
        /* g->u.bb.UR = sub_points(g->u.bb.UR,g->u.bb.LL); */
 
369
        /* g->u.bb.LL = pointof(0,0); */
 
370
        neato_compute_bb(g);
 
371
 
 
372
    /* vladimir: place port labels */
 
373
    if (E_headlabel || E_taillabel)
 
374
      for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
 
375
        if (E_headlabel) for (e = agfstin(g,n); e; e = agnxtin(g,e))
 
376
          if (e->u.head_label) place_portlabel (e, TRUE);
 
377
        if (E_taillabel) for (e = agfstout(g,n); e; e = agnxtout(g,e))
 
378
          if (e->u.tail_label) place_portlabel (e, FALSE);
 
379
      }
 
380
    /* end vladimir */
 
381
}
 
382
 
 
383
void clip_and_install (edge_t *e, point *ps, int  pn)
 
384
{
 
385
        pointf          p2;
 
386
        bezier          *newspl;
 
387
        node_t          *tn, *hn;
 
388
        int             start, end, i;
 
389
        point           pt;
 
390
 
 
391
        tn = e->tail; hn = e->head;
 
392
        newspl = new_spline (e, pn);
 
393
                /* spline may be interior to node */
 
394
        for (start = 0; start < pn - 4; start+=3) {
 
395
                pt = coord(tn);
 
396
                p2.x = ps[start+3].x - pt.x;
 
397
                p2.y = ps[start+3].y - pt.y;
 
398
                if (tn->u.shape == NULL) break;
 
399
                if (tn->u.shape->insidefn == NULL) break;
 
400
                if (tn->u.shape->insidefn (tn, p2, e) == FALSE) break;
 
401
        }
 
402
        neato_shape_clip (tn, &ps[start], e);
 
403
        for (end = pn - 4; end > 0; end -= 3) {
 
404
                pt = coord(hn);
 
405
                p2.x = ps[end].x - pt.x;
 
406
                p2.y = ps[end].y - pt.y;
 
407
                if (hn->u.shape == NULL) break;
 
408
                if (hn->u.shape->insidefn == NULL) break;
 
409
                if (hn->u.shape->insidefn (hn, p2, e) == FALSE) break;
 
410
        }
 
411
        neato_shape_clip (hn, &ps[end], e);
 
412
        for (; start < pn - 4; start+=3)
 
413
                if (ps[start].x != ps[start + 3].x || ps[start].y != ps[start + 3].y)
 
414
                        break;
 
415
        for (; end > 0; end -= 3)
 
416
                if (ps[end].x != ps[end + 3].x || ps[end].y != ps[end + 3].y)
 
417
                        break;
 
418
        neato_arrow_clip (e, e, ps, &start, &end, newspl);
 
419
        for (i = start; i < end + 4; i++)
 
420
                newspl->list[i - start] = ps[i];
 
421
        newspl->size = end - start + 4;
 
422
}
 
423
 
 
424
void neato_shape_clip (node_t *n, point curve[4], edge_t *e)
 
425
{
 
426
        int                     i;
 
427
        boolean         found, inside, left_inside;
 
428
        pointf          pt, opt, c[4], seg[4], best[4], *left, *right;
 
429
        point           p;
 
430
        double          low, high, t;
 
431
 
 
432
        if (n->u.shape == NULL) return;
 
433
        if (n->u.shape->insidefn == NULL) return;
 
434
        for (i = 0; i < 4; i++) {
 
435
                p = coord(n);
 
436
                c[i].x = curve[i].x - p.x;
 
437
                c[i].y = curve[i].y - p.y;
 
438
        }
 
439
 
 
440
        left_inside = n->u.shape->insidefn (n, c[0], e);
 
441
        if (left_inside)
 
442
                left = NULL, right = seg;
 
443
        else
 
444
                left = seg, right = NULL;
 
445
 
 
446
        found = FALSE;
 
447
        low = 0.0; high = 1.0;
 
448
        if (left_inside)
 
449
                pt = c[0];
 
450
        else
 
451
                pt = c[3];
 
452
        do {
 
453
                opt = pt;
 
454
                t = (high + low) / 2.0;
 
455
                pt = Bezier (c, 3, t, left, right);
 
456
                inside = n->u.shape->insidefn (n, pt, e);
 
457
                if (inside == FALSE) {
 
458
                        for (i = 0; i < 4; i++)
 
459
                                best[i] = seg[i];
 
460
                        found = TRUE;
 
461
                }
 
462
                if (inside == left_inside)
 
463
                        low = t;
 
464
                else
 
465
                        high = t;
 
466
        } while (ABS (opt.x - pt.x) > .5 || ABS (opt.y - pt.y) > .5);
 
467
        if (found == FALSE)
 
468
                for (i = 0; i < 4; i++)
 
469
                        best[i] = seg[i];
 
470
 
 
471
        for (i = 0; i < 4; i++) {
 
472
                p = coord(n);
 
473
                curve[i].x = ROUND(best[i].x + p.x);
 
474
                curve[i].y = ROUND(best[i].y + p.y);
 
475
        }
 
476
}
 
477
 
 
478
/* #define ARROWLENGTH 9  shouldn't this be ARROW_LENGTH from const.h? */
 
479
/* #define ARROWLENGTHSQ 81  bah */
 
480
#define sqr(a) ((long) (a) * (a))
 
481
#define dstsq(a, b) (sqr (a.x - b.x) + sqr (a.y - b.y))
 
482
#define ldstsq(a, b) (sqr ((long) a.x - b.x) + sqr ((long) a.y - b.y))
 
483
#define dst(a, b) sqrt ((double) dstsq (a, b))
 
484
#define P2PF(p, pf) (pf.x = p.x, pf.y = p.y)
 
485
#define PF2P(pf, p) (p.x = ROUND (pf.x), p.y = ROUND (pf.y))         
 
486
 
 
487
/* vladimir */
 
488
static char *arrowdirname[] = {"forward","back","both","none",(char*)0};
 
489
static char *arrowheadname[] = {"none","normal","inv","dot","odot", 
 
490
                          "invdot","invodot",(char*)0};
 
491
static int dir_sflag[] = {ARR_NONE,ARR_NORM,ARR_NORM,ARR_NONE};
 
492
static int dir_eflag[] = {ARR_NORM,ARR_NONE,ARR_NORM,ARR_NONE};
 
493
static int arr_type[] = {ARR_NONE,ARR_NORM,ARR_INV,ARR_DOT,ARR_ODOT,
 
494
                         ARR_INVDOT,ARR_INVODOT};
 
495
#define ARR_TYPES (sizeof(arr_type)/sizeof(arr_type[0]))
 
496
static int arr_len[] = {0,ARROW_LENGTH,ARROW_INV_LENGTH,
 
497
                        ARROW_DOT_RADIUS,ARROW_DOT_RADIUS, 
 
498
                        /* or ARROW_DOT_RADIUS*2 if we want the dot to touch
 
499
                           the node instead of being embedded in it */
 
500
                        ARROW_INV_LENGTH+ARROW_DOT_RADIUS,
 
501
                        ARROW_INV_LENGTH+ARROW_DOT_RADIUS};
 
502
 
 
503
void neato_arrow_flags (edge_t *e, int *sflag, int *eflag)
 
504
{
 
505
  char *attr,*p;
 
506
  int i;
 
507
 
 
508
  *sflag = ARR_NONE;
 
509
  *eflag = AG_IS_DIRECTED(e->tail->graph) ? ARR_NORM : ARR_NONE;
 
510
  if (E_dir && ((attr = agxget (e, E_dir->index)))[0]) {
 
511
    for (i = 0; (p = arrowdirname[i]); i++) {
 
512
      if (streq(attr,p)) {
 
513
        *sflag = dir_sflag[i];
 
514
        *eflag = dir_eflag[i];
 
515
        break;
 
516
      }
 
517
    }
 
518
  }
 
519
  if (E_arrowhead && ((attr = agxget (e, E_arrowhead->index)))[0]) {
 
520
    for (i = 0; (p = arrowheadname[i]); i++) {
 
521
      if (strcmp(attr,p) == 0) {
 
522
        *eflag = arr_type[i];
 
523
        break;
 
524
      }
 
525
    }
 
526
  }
 
527
  if (E_arrowtail && ((attr = agxget (e, E_arrowtail->index)))[0]) {
 
528
    for (i = 0; (p = arrowheadname[i]); i++) {
 
529
      if (strcmp(attr,p) == 0) {
 
530
        *sflag = arr_type[i];
 
531
        break;
 
532
      }
 
533
    }
 
534
  }
 
535
}
 
536
 
 
537
double neato_arrow_length (edge_t* e, int flag)
 
538
{
 
539
  int i;
 
540
 
 
541
  /* we don't simply index with flag because arr_type's are not consecutive */
 
542
  for (i=0; i<ARR_TYPES; i++) 
 
543
    if (flag==arr_type[i]) {
 
544
      return arr_len[i] * late_float(e,E_arrowsz,1.0,0.0);
 
545
      /* The original was missing the factor E_arrowsz, but I believe it
 
546
         should be here for correct arrow clipping */
 
547
    }
 
548
  return 0;
 
549
}
 
550
/* end vladimir */
 
551
 
 
552
static int neato_spline_merge(node_t *n)
 
553
{
 
554
    return FALSE;
 
555
}
 
556
 
 
557
void neato_arrow_clip (fe, le, ps, startp, endp, spl)
 
558
        edge_t *fe, *le;
 
559
        point *ps;
 
560
        int *startp, *endp;
 
561
        bezier *spl;
 
562
{
 
563
        edge_t *e;
 
564
        pointf sp[4], sp2[4], pf;
 
565
        int i, j, sflag, eflag;
 
566
        double d, t, slen, elen;
 
567
 
 
568
        for (e = fe; e->u.to_orig; e = e->u.to_orig)
 
569
      ;
 
570
    j = swap_ends_p(e);
 
571
    neato_arrow_flags (e, &sflag, &eflag);
 
572
        if (neato_spline_merge (le->head)) eflag = ARR_NONE;
 
573
        if (neato_spline_merge (fe->tail)) sflag = ARR_NONE;
 
574
        if (j) {i=sflag; sflag=eflag; eflag=i;} /* swap the two ends */
 
575
    slen = neato_arrow_length(e,sflag);
 
576
    elen = neato_arrow_length(e,eflag);
 
577
        if (sflag) {
 
578
                spl->sflag = sflag, spl->sp = ps[*startp];
 
579
                if (*endp > *startp && ldstsq (ps[*startp], ps[*startp + 3]) < sqr(slen)) {
 
580
                        *startp += 3;
 
581
                }
 
582
                P2PF (ps[*startp], sp[0]);
 
583
                P2PF (ps[*startp + 1], sp[1]);
 
584
                P2PF (ps[*startp + 2], sp[2]);
 
585
                P2PF (ps[*startp + 3], sp[3]);
 
586
                d = dst (sp[0], sp[1]) + dst (sp[1], sp[2]) + dst (sp[2], sp[3]);
 
587
                if ((t = slen / d) > 1.0)
 
588
                        t = 1.0;
 
589
                else if (t < 0.1)
 
590
                        t = 0.1;
 
591
                for (;;) {
 
592
                        pf = Bezier (sp, 3, t, NULL, sp2);
 
593
                        if (ldstsq (pf, spl->sp) <= sqr(slen))
 
594
                                break;
 
595
                        t *= (2.0/3.0);
 
596
                }
 
597
                PF2P (sp2[0], ps[*startp]);
 
598
                PF2P (sp2[1], ps[*startp + 1]);
 
599
                PF2P (sp2[2], ps[*startp + 2]);
 
600
                PF2P (sp2[3], ps[*startp + 3]);
 
601
        }
 
602
        if (eflag) {
 
603
                spl->eflag = eflag, spl->ep = ps[*endp + 3];
 
604
                if (*endp > *startp && ldstsq (ps[*endp], ps[*endp + 3]) < sqr(elen)) {
 
605
                        *endp -= 3;
 
606
                }
 
607
                P2PF (ps[*endp], sp[3]);
 
608
                P2PF (ps[*endp + 1], sp[2]);
 
609
                P2PF (ps[*endp + 2], sp[1]);
 
610
                P2PF (ps[*endp + 3], sp[0]);
 
611
                d = dst (sp[0], sp[1]) + dst (sp[1], sp[2]) + dst (sp[2], sp[3]);
 
612
                if ((t = elen / d) > 1.0)
 
613
                        t = 1.0;
 
614
                else if (t < 0.1)
 
615
                        t = 0.1;
 
616
                for (;;) {
 
617
                        pf = Bezier (sp, 3, t, NULL, sp2);
 
618
                        if (ldstsq (pf, spl->ep) <= sqr(elen))
 
619
                                break;
 
620
                        t *= (2.0/3.0);
 
621
                }
 
622
                PF2P (sp2[3], ps[*endp]);
 
623
                PF2P (sp2[2], ps[*endp + 1]);
 
624
                PF2P (sp2[1], ps[*endp + 2]);
 
625
                PF2P (sp2[0], ps[*endp + 3]);
 
626
        }
 
627
}
 
628
 
 
629
static boolean swap_ends_p (edge_t *e)
 
630
{
 
631
        return FALSE;
 
632
}
 
633
 
 
634
/* neato_set_aspect;
 
635
 * Assume bounding box has LL at origin.
 
636
 */
 
637
static int 
 
638
neato_set_aspect(graph_t *g, pointf* pf)
 
639
{
 
640
        int             i;
 
641
        double  xf,yf,actual,desired;
 
642
        char    *str;
 
643
        node_t  *n;
 
644
 
 
645
        /* neato_compute_bb(g); */
 
646
        if (/* (g->u.maxrank > 0) && */(str = agget(g,"ratio"))) {
 
647
                        /* normalize */
 
648
        assert (g->u.bb.LL.x == 0);
 
649
        assert (g->u.bb.LL.y == 0);
 
650
                /* g->u.bb.UR.x -= g->u.bb.LL.x; */
 
651
                /* g->u.bb.UR.y -= g->u.bb.LL.y; */
 
652
                if (g->u.left_to_right)
 
653
                        {int t = g->u.bb.UR.x; g->u.bb.UR.x = g->u.bb.UR.y; g->u.bb.UR.y = t;}
 
654
                if (strcmp(str,"fill") == 0) {
 
655
                        /* fill is weird because both X and Y can stretch */
 
656
                        if (g->u.drawing->size.x <= 0) return 0;
 
657
                        xf = (double)g->u.drawing->size.x / (double)g->u.bb.UR.x;
 
658
                        yf = (double)g->u.drawing->size.y / (double)g->u.bb.UR.y;
 
659
                        if ((xf < 1.0) || (yf < 1.0)) {
 
660
                                if (xf < yf) {yf = yf / xf; xf = 1.0;}
 
661
                                else {xf = xf / yf; yf = 1.0;}
 
662
                        }
 
663
                }
 
664
                else {
 
665
                        desired = atof(str);
 
666
                        if (desired == 0.0) return 0;
 
667
                        actual = ((float)g->u.bb.UR.y)/((float)g->u.bb.UR.x);
 
668
                        if (actual < desired) {yf = desired/actual; xf = 1.0;}
 
669
                        else {xf = actual/desired; yf = 1.0;}
 
670
                }
 
671
                if (g->u.left_to_right) {float t = xf; xf = yf; yf = t;}
 
672
                for (i = 0; (n = g->u.neato_nlist[i]); i++) {
 
673
                        n->u.pos[0] = n->u.pos[0] * xf;
 
674
                        n->u.pos[1] = n->u.pos[1] * yf;
 
675
                }
 
676
                g->u.bb.UR.x *= xf;
 
677
                g->u.bb.UR.y *= yf;
 
678
                pf->x = xf;
 
679
                pf->y = yf;
 
680
        return 1;
 
681
        }
 
682
    else return 0;
 
683
}
 
684
 
 
685
/* vladimir */
 
686
static void place_portlabel (edge_t *e, boolean head_p)
 
687
/* place the {head,tail}label (depending on HEAD_P) of edge E */
 
688
{
 
689
  textlabel_t *l;
 
690
  splines *spl;
 
691
  bezier *bez;
 
692
  float dist, angle;
 
693
  point p;
 
694
  pointf c[4], pf;
 
695
  int i;
 
696
 
 
697
  l = head_p ? e->u.head_label : e->u.tail_label;
 
698
  if (swap_ends_p(e)) head_p = !head_p;
 
699
  spl = getsplinepoints(e);
 
700
  if (!head_p) {
 
701
    bez = &spl->list[0];
 
702
    if (bez->sflag) {
 
703
      p = bez->sp; 
 
704
      P2PF(bez->list[0],pf);
 
705
    }
 
706
    else {
 
707
      p = bez->list[0];
 
708
      for (i=0; i<4; i++) P2PF(bez->list[i], c[i]);
 
709
      pf = Bezier (c, 3, 0.1, NULL, NULL);
 
710
    }
 
711
  } else {
 
712
    bez = &spl->list[spl->size-1];
 
713
    if (bez->eflag) {
 
714
      p = bez->ep; 
 
715
      P2PF(bez->list[bez->size-1],pf);
 
716
    }
 
717
    else {
 
718
      p = bez->list[bez->size-1];  
 
719
      for (i=0; i<4; i++) P2PF(bez->list[bez->size-4+i], c[i]);
 
720
      pf = Bezier (c, 3, 0.9, NULL, NULL);
 
721
    }
 
722
  }
 
723
  angle = atan2 (pf.y-p.y, pf.x-p.x) + 
 
724
    RADIANS(late_float(e,E_labelangle,PORT_LABEL_ANGLE,-180.0));
 
725
  dist = PORT_LABEL_DISTANCE * late_float(e,E_labeldistance,1.0,0.0);
 
726
  l->p.x = p.x + ROUND(dist * cos(angle));
 
727
  l->p.y = p.y + ROUND(dist * sin(angle));
 
728
}
 
729
 
 
730
static splines *getsplinepoints (edge_t* e)
 
731
{
 
732
        splines *sp;
 
733
 
 
734
        sp = e->u.spl;
 
735
        if (sp == NULL) abort ();
 
736
        return sp;
 
737
}