Graphviz  2.41.20171026.1811
splines.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 /* Functions related to creating a spline and attaching it to
16  * an edge, starting from a list of control points.
17  */
18 
19 #include "render.h"
20 
21 #ifdef DEBUG
22 static int debugleveln(edge_t* e, int i)
23 {
24  return (GD_showboxes(agraphof(aghead(e))) == i ||
25  GD_showboxes(agraphof(agtail(e))) == i ||
26  ED_showboxes(e) == i ||
27  ND_showboxes(aghead(e)) == i ||
28  ND_showboxes(agtail(e)) == i);
29 }
30 
31 static void showPoints(pointf ps[], int pn)
32 {
33  char buf[BUFSIZ];
34  int newcnt = Show_cnt + pn + 3;
35  int bi, li;
36 
37  Show_boxes = ALLOC(newcnt+2,Show_boxes,char*);
38  li = Show_cnt+1;
39  Show_boxes[li++] = strdup ("%% self list");
40  Show_boxes[li++] = strdup ("dbgstart");
41  for (bi = 0; bi < pn; bi++) {
42  sprintf(buf, "%.5g %.5g point", ps[bi].x, ps[bi].y);
43  Show_boxes[li++] = strdup (buf);
44  }
45  Show_boxes[li++] = strdup ("grestore");
46 
47  Show_cnt = newcnt;
48  Show_boxes[Show_cnt+1] = NULL;
49 }
50 #endif
51 
52 /* arrow_clip:
53  * Clip arrow to node boundary.
54  * The real work is done elsewhere. Here we get the real edge,
55  * check that the edge has arrowheads, and that an endpoint
56  * isn't a merge point where several parts of an edge meet.
57  * (e.g., with edge concentrators).
58  */
59 static void
60 arrow_clip(edge_t * fe, node_t * hn,
61  pointf * ps, int *startp, int *endp,
62  bezier * spl, splineInfo * info)
63 {
64  edge_t *e;
65  int i, j, sflag, eflag;
66 
67  for (e = fe; ED_to_orig(e); e = ED_to_orig(e));
68 
69  if (info->ignoreSwap)
70  j = 0;
71  else
72  j = info->swapEnds(e);
73  arrow_flags(e, &sflag, &eflag);
74  if (info->splineMerge(hn))
75  eflag = ARR_NONE;
76  if (info->splineMerge(agtail(fe)))
77  sflag = ARR_NONE;
78  /* swap the two ends */
79  if (j) {
80  i = sflag;
81  sflag = eflag;
82  eflag = i;
83  }
84  if (info->isOrtho) {
85  if (eflag || sflag)
86  arrowOrthoClip(e, ps, *startp, *endp, spl, sflag, eflag);
87  }
88  else {
89  if (sflag)
90  *startp =
91  arrowStartClip(e, ps, *startp, *endp, spl, sflag);
92  if (eflag)
93  *endp =
94  arrowEndClip(e, ps, *startp, *endp, spl, eflag);
95  }
96 }
97 
98 /* bezier_clip
99  * Clip bezier to shape using binary search.
100  * The details of the shape are passed in the inside_context;
101  * The function providing the inside test is passed as a parameter.
102  * left_inside specifies that sp[0] is inside the node,
103  * else sp[3] is taken as inside.
104  * The points p are in node coordinates.
105  */
106 void bezier_clip(inside_t * inside_context,
107  boolean(*inside) (inside_t * inside_context, pointf p),
108  pointf * sp, boolean left_inside)
109 {
110  pointf seg[4], best[4], pt, opt, *left, *right;
111  double low, high, t, *idir, *odir;
112  boolean found;
113  int i;
114 
115  if (left_inside) {
116  left = NULL;
117  right = seg;
118  pt = sp[0];
119  idir = &low;
120  odir = &high;
121  } else {
122  left = seg;
123  right = NULL;
124  pt = sp[3];
125  idir = &high;
126  odir = &low;
127  }
128  found = FALSE;
129  low = 0.0;
130  high = 1.0;
131  do {
132  opt = pt;
133  t = (high + low) / 2.0;
134  pt = Bezier(sp, 3, t, left, right);
135  if (inside(inside_context, pt)) {
136  *idir = t;
137  } else {
138  for (i = 0; i < 4; i++)
139  best[i] = seg[i];
140  found = TRUE;
141  *odir = t;
142  }
143  } while (ABS(opt.x - pt.x) > .5 || ABS(opt.y - pt.y) > .5);
144  if (found)
145  for (i = 0; i < 4; i++)
146  sp[i] = best[i];
147  else
148  for (i = 0; i < 4; i++)
149  sp[i] = seg[i];
150 }
151 
152 /* shape_clip0:
153  * Clip Bezier to node shape using binary search.
154  * left_inside specifies that curve[0] is inside the node, else
155  * curve[3] is taken as inside.
156  * Assumes ND_shape(n) and ND_shape(n)->fns->insidefn are non-NULL.
157  * See note on shape_clip.
158  */
159 static void
160 shape_clip0(inside_t * inside_context, node_t * n, pointf curve[4],
161  boolean left_inside)
162 {
163  int i;
164  double save_real_size;
165  pointf c[4];
166 
167  save_real_size = ND_rw(n);
168  for (i = 0; i < 4; i++) {
169  c[i].x = curve[i].x - ND_coord(n).x;
170  c[i].y = curve[i].y - ND_coord(n).y;
171  }
172 
173  bezier_clip(inside_context, ND_shape(n)->fns->insidefn, c,
174  left_inside);
175 
176  for (i = 0; i < 4; i++) {
177  curve[i].x = c[i].x + ND_coord(n).x;
178  curve[i].y = c[i].y + ND_coord(n).y;
179  }
180  ND_rw(n) = save_real_size;
181 }
182 
183 /* shape_clip:
184  * Clip Bezier to node shape
185  * Uses curve[0] to determine which which side is inside the node.
186  * NOTE: This test is bad. It is possible for previous call to
187  * shape_clip to produce a Bezier with curve[0] moved to the boundary
188  * for which insidefn(curve[0]) is true. Thus, if the new Bezier is
189  * fed back to shape_clip, it will again assume left_inside is true.
190  * To be safe, shape_clip0 should guarantee that the computed boundary
191  * point fails insidefn.
192  * The edge e is used to provide a port box. If NULL, the spline is
193  * clipped to the node shape.
194  */
195 void shape_clip(node_t * n, pointf curve[4])
196 {
197  double save_real_size;
198  boolean left_inside;
199  pointf c;
200  inside_t inside_context;
201 
202  if (ND_shape(n) == NULL || ND_shape(n)->fns->insidefn == NULL)
203  return;
204 
205  inside_context.s.n = n;
206  inside_context.s.bp = NULL;
207  save_real_size = ND_rw(n);
208  c.x = curve[0].x - ND_coord(n).x;
209  c.y = curve[0].y - ND_coord(n).y;
210  left_inside = ND_shape(n)->fns->insidefn(&inside_context, c);
211  ND_rw(n) = save_real_size;
212  shape_clip0(&inside_context, n, curve, left_inside);
213 }
214 
215 /* new_spline:
216  * Create and attach a new bezier of size sz to the edge d
217  */
218 bezier *new_spline(edge_t * e, int sz)
219 {
220  bezier *rv;
221  while (ED_edge_type(e) != NORMAL)
222  e = ED_to_orig(e);
223  if (ED_spl(e) == NULL)
224  ED_spl(e) = NEW(splines);
225  ED_spl(e)->list = ALLOC(ED_spl(e)->size + 1, ED_spl(e)->list, bezier);
226  rv = &(ED_spl(e)->list[ED_spl(e)->size++]);
227  rv->list = N_NEW(sz, pointf);
228  rv->size = sz;
229  rv->sflag = rv->eflag = FALSE;
230  rv->sp.x = rv->sp.y = rv->ep.x = rv->ep.y = 0;
231  return rv;
232 }
233 
234 /* clip_and_install:
235  * Given a raw spline (pn control points in ps), representing
236  * a path from edge agtail(fe) ending in node hn, clip the ends to
237  * the node boundaries and attach the resulting spline to the
238  * edge.
239  */
240 void
241 clip_and_install(edge_t * fe, node_t * hn, pointf * ps, int pn,
242  splineInfo * info)
243 {
244  pointf p2;
245  bezier *newspl;
246  node_t *tn;
247  int start, end, i, clipTail, clipHead;
248  graph_t *g;
249  edge_t *orig;
250  boxf *tbox, *hbox;
251  inside_t inside_context;
252 
253  tn = agtail(fe);
254  g = agraphof(tn);
255  newspl = new_spline(fe, pn);
256 
257  for (orig = fe; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
258 
259  /* may be a reversed flat edge */
260  if (!info->ignoreSwap && (ND_rank(tn) == ND_rank(hn)) && (ND_order(tn) > ND_order(hn))) {
261  node_t *tmp;
262  tmp = hn;
263  hn = tn;
264  tn = tmp;
265  }
266  if (tn == agtail(orig)) {
267  clipTail = ED_tail_port(orig).clip;
268  clipHead = ED_head_port(orig).clip;
269  tbox = ED_tail_port(orig).bp;
270  hbox = ED_head_port(orig).bp;
271  }
272  else { /* fe and orig are reversed */
273  clipTail = ED_head_port(orig).clip;
274  clipHead = ED_tail_port(orig).clip;
275  hbox = ED_tail_port(orig).bp;
276  tbox = ED_head_port(orig).bp;
277  }
278 
279  /* spline may be interior to node */
280  if(clipTail && ND_shape(tn) && ND_shape(tn)->fns->insidefn) {
281  inside_context.s.n = tn;
282  inside_context.s.bp = tbox;
283  for (start = 0; start < pn - 4; start += 3) {
284  p2.x = ps[start + 3].x - ND_coord(tn).x;
285  p2.y = ps[start + 3].y - ND_coord(tn).y;
286  if (ND_shape(tn)->fns->insidefn(&inside_context, p2) == FALSE)
287  break;
288  }
289  shape_clip0(&inside_context, tn, &ps[start], TRUE);
290  } else
291  start = 0;
292  if(clipHead && ND_shape(hn) && ND_shape(hn)->fns->insidefn) {
293  inside_context.s.n = hn;
294  inside_context.s.bp = hbox;
295  for (end = pn - 4; end > 0; end -= 3) {
296  p2.x = ps[end].x - ND_coord(hn).x;
297  p2.y = ps[end].y - ND_coord(hn).y;
298  if (ND_shape(hn)->fns->insidefn(&inside_context, p2) == FALSE)
299  break;
300  }
301  shape_clip0(&inside_context, hn, &ps[end], FALSE);
302  } else
303  end = pn - 4;
304  for (; start < pn - 4; start += 3)
305  if (! APPROXEQPT(ps[start], ps[start + 3], MILLIPOINT))
306  break;
307  for (; end > 0; end -= 3)
308  if (! APPROXEQPT(ps[end], ps[end + 3], MILLIPOINT))
309  break;
310  arrow_clip(fe, hn, ps, &start, &end, newspl, info);
311  for (i = start; i < end + 4; ) {
312  pointf cp[4];
313  newspl->list[i - start] = ps[i];
314  cp[0] = ps[i];
315  i++;
316  if ( i >= end + 4)
317  break;
318  newspl->list[i - start] = ps[i];
319  cp[1] = ps[i];
320  i++;
321  newspl->list[i - start] = ps[i];
322  cp[2] = ps[i];
323  i++;
324  cp[3] = ps[i];
325  update_bb_bz(&GD_bb(g), cp);
326  }
327  newspl->size = end - start + 4;
328 }
329 
330 static double
331 conc_slope(node_t* n)
332 {
333  double s_in, s_out, m_in, m_out;
334  int cnt_in, cnt_out;
335  pointf p;
336  edge_t *e;
337 
338  s_in = s_out = 0.0;
339  for (cnt_in = 0; (e = ND_in(n).list[cnt_in]); cnt_in++)
340  s_in += ND_coord(agtail(e)).x;
341  for (cnt_out = 0; (e = ND_out(n).list[cnt_out]); cnt_out++)
342  s_out += ND_coord(aghead(e)).x;
343  p.x = ND_coord(n).x - (s_in / cnt_in);
344  p.y = ND_coord(n).y - ND_coord(agtail(ND_in(n).list[0])).y;
345  m_in = atan2(p.y, p.x);
346  p.x = (s_out / cnt_out) - ND_coord(n).x;
347  p.y = ND_coord(aghead(ND_out(n).list[0])).y - ND_coord(n).y;
348  m_out = atan2(p.y, p.x);
349  return ((m_in + m_out) / 2.0);
350 }
351 
352 void add_box(path * P, boxf b)
353 {
354  if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
355  P->boxes[P->nbox++] = b;
356 }
357 
358 /* beginpath:
359  * Set up boxes near the tail node.
360  * For regular nodes, the result should be a list of contiguous rectangles
361  * such that the last one has the smallest LL.y and its LL.y is above
362  * the bottom of the rank (rank.ht1).
363  *
364  * For flat edges, we assume endp->sidemask has been set. For regular
365  * edges, we set this, but it doesn't appear to be needed any more.
366  *
367  * In many cases, we tweak the x or y coordinate of P->start.p by 1.
368  * This is because of a problem in the path routing code. If the starting
369  * point actually lies on the polygon, in some cases, the router gets
370  * confused and routes the path outside the polygon. So, the offset ensures
371  * the starting point is in the polygon.
372  *
373  * FIX: Creating the initial boxes only really works for rankdir=TB and
374  * rankdir=LR. For the others, we rely on compassPort flipping the side
375  * and then assume that the node shape has top-bottom symmetry. Since we
376  * at present only put compass points on the bounding box, this works.
377  * If we attempt to implement compass points on actual node perimeters,
378  * something major will probably be necessary. Doing the coordinate
379  * flip (postprocess) before spline routing will be too disruptive. The
380  * correct solution is probably to have beginpath/endpath create the
381  * boxes assuming an inverted node. Note that compassPort already does
382  * some flipping. Even better would be to allow the *_path function
383  * to provide a polygon.
384  *
385  * The extra space provided by FUDGE-2 prevents the edge from getting
386  * too close the side of the node.
387  *
388  */
389 #define FUDGE 2
390 #define HT2(n) (ND_ht(n)/2)
391 
392 void
393 beginpath(path * P, edge_t * e, int et, pathend_t * endp, boolean merge)
394 {
395  int side, mask;
396  node_t *n;
397  int (*pboxfn) (node_t*, port*, int, boxf*, int*);
398 
399  n = agtail(e);
400 
401  if (ED_tail_port(e).dyna)
402  ED_tail_port(e) = resolvePort(agtail(e), aghead(e), &ED_tail_port(e));
403  if (ND_shape(n))
404  pboxfn = ND_shape(n)->fns->pboxfn;
405  else
406  pboxfn = NULL;
407  P->start.p = add_pointf(ND_coord(n), ED_tail_port(e).p);
408  if (merge) {
409  /*P->start.theta = - M_PI / 2; */
410  P->start.theta = conc_slope(agtail(e));
411  P->start.constrained = TRUE;
412  } else {
413  if (ED_tail_port(e).constrained) {
414  P->start.theta = ED_tail_port(e).theta;
415  P->start.constrained = TRUE;
416  } else
417  P->start.constrained = FALSE;
418  }
419  P->nbox = 0;
420  P->data = (void *) e;
421  endp->np = P->start.p;
422  if ((et == REGULAREDGE) && (ND_node_type(n) == NORMAL) && ((side = ED_tail_port(e).side))) {
423  edge_t* orig;
424  boxf b0, b = endp->nb;
425  if (side & TOP) {
426  endp->sidemask = TOP;
427  if (P->start.p.x < ND_coord(n).x) { /* go left */
428  b0.LL.x = b.LL.x - 1;
429  /* b0.LL.y = ND_coord(n).y + HT2(n); */
430  b0.LL.y = P->start.p.y;
431  b0.UR.x = b.UR.x;
432  b0.UR.y = ND_coord(n).y + HT2(n) + GD_ranksep(agraphof(n))/2;
433  b.UR.x = ND_coord(n).x - ND_lw(n) - (FUDGE-2);
434  b.UR.y = b0.LL.y;
435  b.LL.y = ND_coord(n).y - HT2(n);
436  b.LL.x -= 1;
437  endp->boxes[0] = b0;
438  endp->boxes[1] = b;
439  }
440  else {
441  b0.LL.x = b.LL.x;
442  b0.LL.y = P->start.p.y;
443  /* b0.LL.y = ND_coord(n).y + HT2(n); */
444  b0.UR.x = b.UR.x+1;
445  b0.UR.y = ND_coord(n).y + HT2(n) + GD_ranksep(agraphof(n))/2;
446  b.LL.x = ND_coord(n).x + ND_rw(n) + (FUDGE-2);
447  b.UR.y = b0.LL.y;
448  b.LL.y = ND_coord(n).y - HT2(n);
449  b.UR.x += 1;
450  endp->boxes[0] = b0;
451  endp->boxes[1] = b;
452  }
453  P->start.p.y += 1;
454  endp->boxn = 2;
455  }
456  else if (side & BOTTOM) {
457  endp->sidemask = BOTTOM;
458  b.UR.y = MAX(b.UR.y,P->start.p.y);
459  endp->boxes[0] = b;
460  endp->boxn = 1;
461  P->start.p.y -= 1;
462  }
463  else if (side & LEFT) {
464  endp->sidemask = LEFT;
465  b.UR.x = P->start.p.x;
466  b.LL.y = ND_coord(n).y - HT2(n);
467  b.UR.y = P->start.p.y;
468  endp->boxes[0] = b;
469  endp->boxn = 1;
470  P->start.p.x -= 1;
471  }
472  else {
473  endp->sidemask = RIGHT;
474  b.LL.x = P->start.p.x;
475  b.LL.y = ND_coord(n).y - HT2(n);
476  b.UR.y = P->start.p.y;
477  endp->boxes[0] = b;
478  endp->boxn = 1;
479  P->start.p.x += 1;
480  }
481  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
482  if (n == agtail(orig))
483  ED_tail_port(orig).clip = FALSE;
484  else
485  ED_head_port(orig).clip = FALSE;
486  return;
487  }
488  if ((et == FLATEDGE) && ((side = ED_tail_port(e).side))) {
489  boxf b0, b = endp->nb;
490  edge_t* orig;
491  if (side & TOP) {
492  b.LL.y = MIN(b.LL.y,P->start.p.y);
493  endp->boxes[0] = b;
494  endp->boxn = 1;
495  P->start.p.y += 1;
496  }
497  else if (side & BOTTOM) {
498  if (endp->sidemask == TOP) {
499  b0.UR.y = ND_coord(n).y - HT2(n);
500  b0.UR.x = b.UR.x+1;
501  b0.LL.x = P->start.p.x;
502  b0.LL.y = b0.UR.y - GD_ranksep(agraphof(n))/2;
503  b.LL.x = ND_coord(n).x + ND_rw(n) + (FUDGE-2);
504  b.LL.y = b0.UR.y;
505  b.UR.y = ND_coord(n).y + HT2(n);
506  b.UR.x += 1;
507  endp->boxes[0] = b0;
508  endp->boxes[1] = b;
509  endp->boxn = 2;
510  }
511  else {
512  b.UR.y = MAX(b.UR.y,P->start.p.y);
513  endp->boxes[0] = b;
514  endp->boxn = 1;
515  }
516  P->start.p.y -= 1;
517  }
518  else if (side & LEFT) {
519  b.UR.x = P->start.p.x+1;
520  if (endp->sidemask == TOP) {
521  b.UR.y = ND_coord(n).y + HT2(n);
522  b.LL.y = P->start.p.y-1;
523  }
524  else {
525  b.LL.y = ND_coord(n).y - HT2(n);
526  b.UR.y = P->start.p.y+1;
527  }
528  endp->boxes[0] = b;
529  endp->boxn = 1;
530  P->start.p.x -= 1;
531  }
532  else {
533  b.LL.x = P->start.p.x;
534  if (endp->sidemask == TOP) {
535  b.UR.y = ND_coord(n).y + HT2(n);
536  b.LL.y = P->start.p.y;
537  }
538  else {
539  b.LL.y = ND_coord(n).y - HT2(n);
540  b.UR.y = P->start.p.y+1;
541  }
542  endp->boxes[0] = b;
543  endp->boxn = 1;
544  P->start.p.x += 1;
545  }
546  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
547  if (n == agtail(orig))
548  ED_tail_port(orig).clip = FALSE;
549  else
550  ED_head_port(orig).clip = FALSE;
551  endp->sidemask = side;
552  return;
553  }
554 
555  if (et == REGULAREDGE) side = BOTTOM;
556  else side = endp->sidemask; /* for flat edges */
557  if (pboxfn
558  && (mask = (*pboxfn) (n, &ED_tail_port(e), side, &endp->boxes[0], &endp->boxn)))
559  endp->sidemask = mask;
560  else {
561  endp->boxes[0] = endp->nb;
562  endp->boxn = 1;
563 
564  switch (et) {
565  case SELFEDGE:
566  /* moving the box UR.y by + 1 avoids colinearity between
567  port point and box that confuses Proutespline(). it's
568  a bug in Proutespline() but this is the easiest fix. */
569  assert(0); /* at present, we don't use beginpath for selfedges */
570  endp->boxes[0].UR.y = P->start.p.y - 1;
571  endp->sidemask = BOTTOM;
572  break;
573  case FLATEDGE:
574  if (endp->sidemask == TOP)
575  endp->boxes[0].LL.y = P->start.p.y;
576  else
577  endp->boxes[0].UR.y = P->start.p.y;
578  break;
579  case REGULAREDGE:
580  endp->boxes[0].UR.y = P->start.p.y;
581  endp->sidemask = BOTTOM;
582  P->start.p.y -= 1;
583  break;
584  }
585  }
586 }
587 
588 void endpath(path * P, edge_t * e, int et, pathend_t * endp, boolean merge)
589 {
590  int side, mask;
591  node_t *n;
592  int (*pboxfn) (node_t* n, port*, int, boxf*, int*);
593 
594  n = aghead(e);
595 
596  if (ED_head_port(e).dyna)
597  ED_head_port(e) = resolvePort(aghead(e), agtail(e), &ED_head_port(e));
598  if (ND_shape(n))
599  pboxfn = ND_shape(n)->fns->pboxfn;
600  else
601  pboxfn = NULL;
602  P->end.p = add_pointf(ND_coord(n), ED_head_port(e).p);
603  if (merge) {
604  /*P->end.theta = M_PI / 2; */
605  P->end.theta = conc_slope(aghead(e)) + M_PI;
606  assert(P->end.theta < 2 * M_PI);
607  P->end.constrained = TRUE;
608  } else {
609  if (ED_head_port(e).constrained) {
610  P->end.theta = ED_head_port(e).theta;
611  P->end.constrained = TRUE;
612  } else
613  P->end.constrained = FALSE;
614  }
615  endp->np = P->end.p;
616  if ((et == REGULAREDGE) && (ND_node_type(n) == NORMAL) && ((side = ED_head_port(e).side))) {
617  edge_t* orig;
618  boxf b0, b = endp->nb;
619  if (side & TOP) {
620  endp->sidemask = TOP;
621  b.LL.y = MIN(b.LL.y,P->end.p.y);
622  endp->boxes[0] = b;
623  endp->boxn = 1;
624  P->end.p.y += 1;
625  }
626  else if (side & BOTTOM) {
627  endp->sidemask = BOTTOM;
628  if (P->end.p.x < ND_coord(n).x) { /* go left */
629  b0.LL.x = b.LL.x-1;
630  /* b0.UR.y = ND_coord(n).y - HT2(n); */
631  b0.UR.y = P->end.p.y;
632  b0.UR.x = b.UR.x;
633  b0.LL.y = ND_coord(n).y - HT2(n) - GD_ranksep(agraphof(n))/2;
634  b.UR.x = ND_coord(n).x - ND_lw(n) - (FUDGE-2);
635  b.LL.y = b0.UR.y;
636  b.UR.y = ND_coord(n).y + HT2(n);
637  b.LL.x -= 1;
638  endp->boxes[0] = b0;
639  endp->boxes[1] = b;
640  }
641  else {
642  b0.LL.x = b.LL.x;
643  b0.UR.y = P->end.p.y;
644  /* b0.UR.y = ND_coord(n).y - HT2(n); */
645  b0.UR.x = b.UR.x+1;
646  b0.LL.y = ND_coord(n).y - HT2(n) - GD_ranksep(agraphof(n))/2;
647  b.LL.x = ND_coord(n).x + ND_rw(n) + (FUDGE-2);
648  b.LL.y = b0.UR.y;
649  b.UR.y = ND_coord(n).y + HT2(n);
650  b.UR.x += 1;
651  endp->boxes[0] = b0;
652  endp->boxes[1] = b;
653  }
654  endp->boxn = 2;
655  P->end.p.y -= 1;
656  }
657  else if (side & LEFT) {
658  endp->sidemask = LEFT;
659  b.UR.x = P->end.p.x;
660  b.UR.y = ND_coord(n).y + HT2(n);
661  b.LL.y = P->end.p.y;
662  endp->boxes[0] = b;
663  endp->boxn = 1;
664  P->end.p.x -= 1;
665  }
666  else {
667  endp->sidemask = RIGHT;
668  b.LL.x = P->end.p.x;
669  b.UR.y = ND_coord(n).y + HT2(n);
670  b.LL.y = P->end.p.y;
671  endp->boxes[0] = b;
672  endp->boxn = 1;
673  P->end.p.x += 1;
674  }
675  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
676  if (n == aghead(orig))
677  ED_head_port(orig).clip = FALSE;
678  else
679  ED_tail_port(orig).clip = FALSE;
680  endp->sidemask = side;
681  return;
682  }
683 
684  if ((et == FLATEDGE) && ((side = ED_head_port(e).side))) {
685  boxf b0, b = endp->nb;
686  edge_t* orig;
687  if (side & TOP) {
688  b.LL.y = MIN(b.LL.y,P->end.p.y);
689  endp->boxes[0] = b;
690  endp->boxn = 1;
691  P->end.p.y += 1;
692  }
693  else if (side & BOTTOM) {
694  if (endp->sidemask == TOP) {
695  b0.LL.x = b.LL.x-1;
696  b0.UR.y = ND_coord(n).y - HT2(n);
697  b0.UR.x = P->end.p.x;
698  b0.LL.y = b0.UR.y - GD_ranksep(agraphof(n))/2;
699  b.UR.x = ND_coord(n).x - ND_lw(n) - 2;
700  b.LL.y = b0.UR.y;
701  b.UR.y = ND_coord(n).y + HT2(n);
702  b.LL.x -= 1;
703  endp->boxes[0] = b0;
704  endp->boxes[1] = b;
705  endp->boxn = 2;
706  }
707  else {
708  b.UR.y = MAX(b.UR.y,P->start.p.y);
709  endp->boxes[0] = b;
710  endp->boxn = 1;
711  }
712  P->end.p.y -= 1;
713  }
714  else if (side & LEFT) {
715  b.UR.x = P->end.p.x+1;
716  if (endp->sidemask == TOP) {
717  b.UR.y = ND_coord(n).y + HT2(n);
718  b.LL.y = P->end.p.y-1;
719  }
720  else {
721  b.LL.y = ND_coord(n).y - HT2(n);
722  b.UR.y = P->end.p.y+1;
723  }
724  endp->boxes[0] = b;
725  endp->boxn = 1;
726  P->end.p.x -= 1;
727  }
728  else {
729  b.LL.x = P->end.p.x-1;
730  if (endp->sidemask == TOP) {
731  b.UR.y = ND_coord(n).y + HT2(n);
732  b.LL.y = P->end.p.y-1;
733  }
734  else {
735  b.LL.y = ND_coord(n).y - HT2(n);
736  b.UR.y = P->end.p.y;
737  }
738  endp->boxes[0] = b;
739  endp->boxn = 1;
740  P->end.p.x += 1;
741  }
742  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
743  if (n == aghead(orig))
744  ED_head_port(orig).clip = FALSE;
745  else
746  ED_tail_port(orig).clip = FALSE;
747  endp->sidemask = side;
748  return;
749  }
750 
751  if (et == REGULAREDGE) side = TOP;
752  else side = endp->sidemask; /* for flat edges */
753  if (pboxfn
754  && (mask = (*pboxfn) (n, &ED_head_port(e), side, &endp->boxes[0], &endp->boxn)))
755  endp->sidemask = mask;
756  else {
757  endp->boxes[0] = endp->nb;
758  endp->boxn = 1;
759 
760  switch (et) {
761  case SELFEDGE:
762  /* offset of -1 is symmetric w.r.t. beginpath()
763  * FIXME: is any of this right? what if self-edge
764  * doesn't connect from BOTTOM to TOP??? */
765  assert(0); /* at present, we don't use endpath for selfedges */
766  endp->boxes[0].LL.y = P->end.p.y + 1;
767  endp->sidemask = TOP;
768  break;
769  case FLATEDGE:
770  if (endp->sidemask == TOP)
771  endp->boxes[0].LL.y = P->end.p.y;
772  else
773  endp->boxes[0].UR.y = P->end.p.y;
774  break;
775  case REGULAREDGE:
776  endp->boxes[0].LL.y = P->end.p.y;
777  endp->sidemask = TOP;
778  P->end.p.y += 1;
779  break;
780  }
781  }
782 }
783 
784 
785 static int convert_sides_to_points(int tail_side, int head_side)
786 {
787 int vertices[] = {12,4,6,2,3,1,9,8}; //the cumulative side value of each node point
788 int i, tail_i, head_i;
789 int pair_a[8][8] = { //array of possible node point pairs
790 {11,12,13,14,15,16,17,18},
791 {21,22,23,24,25,26,27,28},
792 {31,32,33,34,35,36,37,38},
793 {41,42,43,44,45,46,47,48},
794 {51,52,53,54,55,56,57,58},
795 {61,62,63,64,65,66,67,68},
796 {71,72,73,74,75,76,77,78},
797 {81,82,83,84,85,86,87,88}
798 };
799 
800  tail_i = head_i = -1;
801  for(i=0;i< 8; i++){
802  if(head_side == vertices[i]){
803  head_i = i;
804  break;
805  }
806  }
807  for(i=0;i< 8; i++){
808  if(tail_side == vertices[i]){
809  tail_i = i;
810  break;
811  }
812  }
813 
814 if( tail_i < 0 || head_i < 0)
815  return 0;
816 else
817  return pair_a[tail_i][head_i];
818 }
819 
820 
821 static void selfBottom (edge_t* edges[], int ind, int cnt,
822  double sizex, double stepy, splineInfo* sinfo)
823 {
824  pointf tp, hp, np;
825  node_t *n;
826  edge_t *e;
827  int i, sgn, point_pair;
828  double hy, ty, stepx, dx, dy, width, height;
829  pointf points[1000];
830  int pointn;
831 
832  e = edges[ind];
833  n = agtail(e);
834 
835  stepx = (sizex / 2.) / cnt;
836  stepx = MAX(stepx,2.);
837  pointn = 0;
838  np = ND_coord(n);
839  tp = ED_tail_port(e).p;
840  tp.x += np.x;
841  tp.y += np.y;
842  hp = ED_head_port(e).p;
843  hp.x += np.x;
844  hp.y += np.y;
845  if (tp.x >= hp.x) sgn = 1;
846  else sgn = -1;
847  dy = ND_ht(n)/2., dx = 0.;
848  // certain adjustments are required for some point_pairs in order to improve the
849  // display of the edge path between them
850  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
851  switch(point_pair){
852  case 67: sgn = -sgn;
853  break;
854  default:
855  break;
856  }
857  ty = MIN(dy, 3*(tp.y + dy - np.y));
858  hy = MIN(dy, 3*(hp.y + dy - np.y));
859  for (i = 0; i < cnt; i++) {
860  e = edges[ind++];
861  dy += stepy, ty += stepy, hy += stepy, dx += sgn*stepx;
862  pointn = 0;
863  points[pointn++] = tp;
864  points[pointn++] = pointfof(tp.x + dx, tp.y - ty / 3);
865  points[pointn++] = pointfof(tp.x + dx, np.y - dy);
866  points[pointn++] = pointfof((tp.x+hp.x)/2, np.y - dy);
867  points[pointn++] = pointfof(hp.x - dx, np.y - dy);
868  points[pointn++] = pointfof(hp.x - dx, hp.y - hy / 3);
869  points[pointn++] = hp;
870  if (ED_label(e)) {
871  if (GD_flip(agraphof(agtail(e)))) {
872  width = ED_label(e)->dimen.y;
873  height = ED_label(e)->dimen.x;
874  } else {
875  width = ED_label(e)->dimen.x;
876  height = ED_label(e)->dimen.y;
877  }
878  ED_label(e)->pos.y = ND_coord(n).y - dy - height / 2.0;
879  ED_label(e)->pos.x = ND_coord(n).x;
880  ED_label(e)->set = TRUE;
881  if (height > stepy)
882  dy += height - stepy;
883  }
884  clip_and_install(e, aghead(e), points, pointn, sinfo);
885 #ifdef DEBUG
886  if (debugleveln(e,1))
887  showPoints (points, pointn);
888 #endif
889  }
890 }
891 
892 
893 static void
894 selfTop (edge_t* edges[], int ind, int cnt, double sizex, double stepy,
895  splineInfo* sinfo)
896 {
897  int i, sgn, point_pair;
898  double hy, ty, stepx, dx, dy, width, height;
899  pointf tp, hp, np;
900  node_t *n;
901  edge_t *e;
902  pointf points[1000];
903  int pointn;
904 
905  e = edges[ind];
906  n = agtail(e);
907 
908  stepx = (sizex / 2.) / cnt;
909  stepx = MAX(stepx, 2.);
910  pointn = 0;
911  np = ND_coord(n);
912  tp = ED_tail_port(e).p;
913  tp.x += np.x;
914  tp.y += np.y;
915  hp = ED_head_port(e).p;
916  hp.x += np.x;
917  hp.y += np.y;
918  if (tp.x >= hp.x) sgn = 1;
919  else sgn = -1;
920  dy = ND_ht(n)/2., dx = 0.;
921  // certain adjustments are required for some point_pairs in order to improve the
922  // display of the edge path between them
923  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
924  switch(point_pair){
925  case 15:
926  dx = sgn*(ND_rw(n) - (hp.x-np.x) + stepx);
927  break;
928 
929  case 38:
930  dx = sgn*(ND_lw(n)-(np.x-hp.x) + stepx);
931  break;
932  case 41:
933  dx = sgn*(ND_rw(n)-(tp.x-np.x) + stepx);
934  break;
935  case 48:
936  dx = sgn*(ND_rw(n)-(tp.x-np.x) + stepx);
937  break;
938 
939  case 14:
940  case 37:
941  case 47:
942  case 51:
943  case 57:
944  case 58:
945  dx = sgn*((((ND_lw(n)-(np.x-tp.x)) + (ND_rw(n)-(hp.x-np.x)))/3.));
946  break;
947  case 73:
948  dx = sgn*(ND_lw(n)-(np.x-tp.x) + stepx);
949  break;
950  case 83:
951  dx = sgn*(ND_lw(n)-(np.x-tp.x));
952  break;
953  case 84:
954  dx = sgn*((((ND_lw(n)-(np.x-tp.x)) + (ND_rw(n)-(hp.x-np.x)))/2.) + stepx);
955  break;
956  case 74:
957  case 75:
958  case 85:
959  dx = sgn*((((ND_lw(n)-(np.x-tp.x)) + (ND_rw(n)-(hp.x-np.x)))/2.) + 2*stepx);
960  break;
961  default:
962  break;
963  }
964  ty = MIN(dy, 3*(np.y + dy - tp.y));
965  hy = MIN(dy, 3*(np.y + dy - hp.y));
966  for (i = 0; i < cnt; i++) {
967  e = edges[ind++];
968  dy += stepy, ty += stepy, hy += stepy, dx += sgn*stepx;
969  pointn = 0;
970  points[pointn++] = tp;
971  points[pointn++] = pointfof(tp.x + dx, tp.y + ty / 3);
972  points[pointn++] = pointfof(tp.x + dx, np.y + dy);
973  points[pointn++] = pointfof((tp.x+hp.x)/2, np.y + dy);
974  points[pointn++] = pointfof(hp.x - dx, np.y + dy);
975  points[pointn++] = pointfof(hp.x - dx, hp.y + hy / 3);
976  points[pointn++] = hp;
977  if (ED_label(e)) {
978  if (GD_flip(agraphof(agtail(e)))) {
979  width = ED_label(e)->dimen.y;
980  height = ED_label(e)->dimen.x;
981  } else {
982  width = ED_label(e)->dimen.x;
983  height = ED_label(e)->dimen.y;
984  }
985  ED_label(e)->pos.y = ND_coord(n).y + dy + height / 2.0;
986  ED_label(e)->pos.x = ND_coord(n).x;
987  ED_label(e)->set = TRUE;
988  if (height > stepy)
989  dy += height - stepy;
990  }
991  clip_and_install(e, aghead(e), points, pointn, sinfo);
992 #ifdef DEBUG
993  if (debugleveln(e,1))
994  showPoints (points, pointn);
995 #endif
996  }
997  return;
998 }
999 
1000 static void
1001 selfRight (edge_t* edges[], int ind, int cnt, double stepx, double sizey,
1002  splineInfo* sinfo)
1003 {
1004  int i, sgn, point_pair;
1005  double hx, tx, stepy, dx, dy, width, height;
1006  pointf tp, hp, np;
1007  node_t *n;
1008  edge_t *e;
1009  pointf points[1000];
1010  int pointn;
1011 
1012  e = edges[ind];
1013  n = agtail(e);
1014 
1015  stepy = (sizey / 2.) / cnt;
1016  stepy = MAX(stepy, 2.);
1017  pointn = 0;
1018  np = ND_coord(n);
1019  tp = ED_tail_port(e).p;
1020  tp.x += np.x;
1021  tp.y += np.y;
1022  hp = ED_head_port(e).p;
1023  hp.x += np.x;
1024  hp.y += np.y;
1025  if (tp.y >= hp.y) sgn = 1;
1026  else sgn = -1;
1027  dx = ND_rw(n), dy = 0;
1028  // certain adjustments are required for some point_pairs in order to improve the
1029  // display of the edge path between them
1030  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
1031  switch(point_pair){
1032  case 32:
1033  case 65: if(tp.y == hp.y)
1034  sgn = -sgn;
1035  break;
1036  default:
1037  break;
1038  }
1039  tx = MIN(dx, 3*(np.x + dx - tp.x));
1040  hx = MIN(dx, 3*(np.x + dx - hp.x));
1041  for (i = 0; i < cnt; i++) {
1042  e = edges[ind++];
1043  dx += stepx, tx += stepx, hx += stepx, dy += sgn*stepy;
1044  pointn = 0;
1045  points[pointn++] = tp;
1046  points[pointn++] = pointfof(tp.x + tx / 3, tp.y + dy);
1047  points[pointn++] = pointfof(np.x + dx, tp.y + dy);
1048  points[pointn++] = pointfof(np.x + dx, (tp.y+hp.y)/2);
1049  points[pointn++] = pointfof(np.x + dx, hp.y - dy);
1050  points[pointn++] = pointfof(hp.x + hx / 3, hp.y - dy);
1051  points[pointn++] = hp;
1052  if (ED_label(e)) {
1053  if (GD_flip(agraphof(agtail(e)))) {
1054  width = ED_label(e)->dimen.y;
1055  height = ED_label(e)->dimen.x;
1056  } else {
1057  width = ED_label(e)->dimen.x;
1058  height = ED_label(e)->dimen.y;
1059  }
1060  ED_label(e)->pos.x = ND_coord(n).x + dx + width / 2.0;
1061  ED_label(e)->pos.y = ND_coord(n).y;
1062  ED_label(e)->set = TRUE;
1063  if (width > stepx)
1064  dx += width - stepx;
1065  }
1066  clip_and_install(e, aghead(e), points, pointn, sinfo);
1067 #ifdef DEBUG
1068  if (debugleveln(e,1))
1069  showPoints (points, pointn);
1070 #endif
1071  }
1072  return;
1073 }
1074 
1075 static void
1076 selfLeft (edge_t* edges[], int ind, int cnt, double stepx, double sizey,
1077  splineInfo* sinfo)
1078 {
1079  int i, sgn,point_pair;
1080  double hx, tx, stepy, dx, dy, width, height;
1081  pointf tp, hp, np;
1082  node_t *n;
1083  edge_t *e;
1084  pointf points[1000];
1085  int pointn;
1086 
1087  e = edges[ind];
1088  n = agtail(e);
1089 
1090  stepy = (sizey / 2.) / cnt;
1091  stepy = MAX(stepy,2.);
1092  pointn = 0;
1093  np = ND_coord(n);
1094  tp = ED_tail_port(e).p;
1095  tp.x += np.x;
1096  tp.y += np.y;
1097  hp = ED_head_port(e).p;
1098  hp.x += np.x;
1099  hp.y += np.y;
1100 
1101 
1102  if (tp.y >= hp.y) sgn = 1;
1103  else sgn = -1;
1104  dx = ND_lw(n), dy = 0.;
1105  // certain adjustments are required for some point_pairs in order to improve the
1106  // display of the edge path between them
1107  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
1108  switch(point_pair){
1109  case 12:
1110  case 67:
1111  if(tp.y == hp.y)
1112  sgn = -sgn;
1113  break;
1114  default:
1115  break;
1116  }
1117  tx = MIN(dx, 3*(tp.x + dx - np.x));
1118  hx = MIN(dx, 3*(hp.x + dx - np.x));
1119  for (i = 0; i < cnt; i++) {
1120  e = edges[ind++];
1121  dx += stepx, tx += stepx, hx += stepx, dy += sgn*stepy;
1122  pointn = 0;
1123  points[pointn++] = tp;
1124  points[pointn++] = pointfof(tp.x - tx / 3, tp.y + dy);
1125  points[pointn++] = pointfof(np.x - dx, tp.y + dy);
1126  points[pointn++] = pointfof(np.x - dx, (tp.y+hp.y)/2);
1127  points[pointn++] = pointfof(np.x - dx, hp.y - dy);
1128  points[pointn++] = pointfof(hp.x - hx / 3, hp.y - dy);
1129 
1130  points[pointn++] = hp;
1131  if (ED_label(e)) {
1132  if (GD_flip(agraphof(agtail(e)))) {
1133  width = ED_label(e)->dimen.y;
1134  height = ED_label(e)->dimen.x;
1135  } else {
1136  width = ED_label(e)->dimen.x;
1137  height = ED_label(e)->dimen.y;
1138  }
1139  ED_label(e)->pos.x = ND_coord(n).x - dx - width / 2.0;
1140  ED_label(e)->pos.y = ND_coord(n).y;
1141  ED_label(e)->set = TRUE;
1142  if (width > stepx)
1143  dx += width - stepx;
1144  }
1145 
1146  clip_and_install(e, aghead(e), points, pointn, sinfo);
1147 #ifdef DEBUG
1148  if (debugleveln(e,1))
1149  showPoints (points, pointn);
1150 #endif
1151  }
1152 }
1153 
1154 /* selfRightSpace:
1155  * Assume e is self-edge.
1156  * Return extra space necessary on the right for this edge.
1157  * If the edge does not go on the right, return 0.
1158  * NOTE: the actual space is determined dynamically by GD_nodesep,
1159  * so using the constant SELF_EDGE_SIZE is going to be wrong.
1160  * Fortunately, the default nodesep is the same as SELF_EDGE_SIZE.
1161  */
1162 int
1163 selfRightSpace (edge_t* e)
1164 {
1165  int sw;
1166  double label_width;
1167  textlabel_t* l = ED_label(e);
1168 
1169  if (((!ED_tail_port(e).defined) && (!ED_head_port(e).defined)) ||
1170  (!(ED_tail_port(e).side & LEFT) &&
1171  !(ED_head_port(e).side & LEFT) &&
1172  ((ED_tail_port(e).side != ED_head_port(e).side) ||
1173  (!(ED_tail_port(e).side & (TOP|BOTTOM)))))) {
1174  sw = SELF_EDGE_SIZE;
1175  if (l) {
1176  label_width = GD_flip(agraphof(aghead(e))) ? l->dimen.y : l->dimen.x;
1177  sw += label_width;
1178  }
1179  }
1180  else sw = 0;
1181  return sw;
1182 }
1183 
1184 /* makeSelfEdge:
1185  * The routing is biased towards the right side because this is what
1186  * dot supports, and leaves room for.
1187  * FIX: With this bias, labels tend to be placed on top of each other.
1188  * Perhaps for self-edges, the label should be centered.
1189  */
1190 void
1191 makeSelfEdge(path * P, edge_t * edges[], int ind, int cnt, double sizex,
1192  double sizey, splineInfo * sinfo)
1193 {
1194  edge_t *e;
1195 
1196  e = edges[ind];
1197 
1198  /* self edge without ports or
1199  * self edge with all ports inside, on the right, or at most 1 on top
1200  * and at most 1 on bottom
1201  */
1202 
1203  if (((!ED_tail_port(e).defined) && (!ED_head_port(e).defined)) ||
1204  (!(ED_tail_port(e).side & LEFT) &&
1205  !(ED_head_port(e).side & LEFT) &&
1206  ((ED_tail_port(e).side != ED_head_port(e).side) ||
1207  (!(ED_tail_port(e).side & (TOP|BOTTOM)))))) {
1208  selfRight(edges, ind, cnt, sizex, sizey, sinfo);
1209  }
1210 
1211  /* self edge with port on left side */
1212  else if ((ED_tail_port(e).side & LEFT) || (ED_head_port(e).side & LEFT)) {
1213 
1214  /* handle L-R specially */
1215  if ((ED_tail_port(e).side & RIGHT) || (ED_head_port(e).side & RIGHT)) {
1216  selfTop(edges, ind, cnt, sizex, sizey, sinfo);
1217  }
1218  else {
1219  selfLeft(edges, ind, cnt, sizex, sizey, sinfo);
1220  }
1221  }
1222 
1223  /* self edge with both ports on top side */
1224  else if (ED_tail_port(e).side & TOP) {
1225  selfTop(edges, ind, cnt, sizex, sizey, sinfo);
1226  }
1227  else if (ED_tail_port(e).side & BOTTOM) {
1228  selfBottom(edges, ind, cnt, sizex, sizey, sinfo);
1229  }
1230 
1231  else assert(0);
1232 }
1233 
1234 /* makePortLabels:
1235  * Add head and tail labels if necessary and update bounding box.
1236  */
1237 void makePortLabels(edge_t * e)
1238 {
1239  /* Only use this if labelangle or labeldistance is set for the edge;
1240  * otherwise, handle with external labels.
1241  */
1242  if (!E_labelangle && !E_labeldistance) return;
1243 
1244  if (ED_head_label(e) && !ED_head_label(e)->set) {
1245  if (place_portlabel(e, TRUE))
1246  updateBB(agraphof(agtail(e)), ED_head_label(e));
1247  }
1248  if (ED_tail_label(e) && !ED_tail_label(e)->set) {
1249  if (place_portlabel(e, FALSE))
1250  updateBB(agraphof(agtail(e)), ED_tail_label(e));
1251  }
1252 }
1253 
1254 /* endPoints:
1255  * Extract the actual end points of the spline, where
1256  * they touch the node.
1257  */
1258 static void endPoints(splines * spl, pointf * p, pointf * q)
1259 {
1260  bezier bz;
1261 
1262  bz = spl->list[0];
1263  if (bz.sflag) {
1264  *p = bz.sp;
1265  }
1266  else {
1267  *p = bz.list[0];
1268  }
1269  bz = spl->list[spl->size - 1];
1270  if (bz.eflag) {
1271  *q = bz.ep;
1272  }
1273  else {
1274  *q = bz.list[bz.size - 1];
1275  }
1276 }
1277 
1278 /* polylineMidpoint;
1279  * Find midpoint of polyline.
1280  * pp and pq are set to the endpoints of the line segment containing it.
1281  */
1282 static pointf
1283 polylineMidpoint (splines* spl, pointf* pp, pointf* pq)
1284 {
1285  bezier bz;
1286  int i, j, k;
1287  double d, dist = 0;
1288  pointf pf, qf, mf;
1289 
1290  for (i = 0; i < spl->size; i++) {
1291  bz = spl->list[i];
1292  for (j = 0, k=3; k < bz.size; j+=3,k+=3) {
1293  pf = bz.list[j];
1294  qf = bz.list[k];
1295  dist += DIST(pf, qf);
1296  }
1297  }
1298  dist /= 2;
1299  for (i = 0; i < spl->size; i++) {
1300  bz = spl->list[i];
1301  for (j = 0, k=3; k < bz.size; j+=3,k+=3) {
1302  pf = bz.list[j];
1303  qf = bz.list[k];
1304  d = DIST(pf,qf);
1305  if (d >= dist) {
1306  *pp = pf;
1307  *pq = qf;
1308  mf.x = ((qf.x*dist) + (pf.x*(d-dist)))/d;
1309  mf.y = ((qf.y*dist) + (pf.y*(d-dist)))/d;
1310  return mf;
1311  }
1312  else
1313  dist -= d;
1314  }
1315  }
1316  assert (FALSE); /* should never get here */
1317  return mf;
1318 }
1319 
1320 pointf
1321 edgeMidpoint (graph_t* g, edge_t * e)
1322 {
1323  int et = EDGE_TYPE (g);
1324  pointf d, spf, p, q;
1325 
1326  endPoints(ED_spl(e), &p, &q);
1327  if (APPROXEQPT(p, q, MILLIPOINT)) { /* degenerate spline */
1328  spf = p;
1329  }
1330  else if ((et == ET_SPLINE) || (et == ET_CURVED)) {
1331  d.x = (q.x + p.x) / 2.;
1332  d.y = (p.y + q.y) / 2.;
1333  spf = dotneato_closest(ED_spl(e), d);
1334  }
1335  else { /* ET_PLINE, ET_ORTHO or ET_LINE */
1336  spf = polylineMidpoint (ED_spl(e), &p, &q);
1337  }
1338 
1339  return spf;
1340 }
1341 
1342 #define LEFTOF(a,b,c) (((a.y - b.y)*(c.x - b.x) - (c.y - b.y)*(a.x - b.x)) > 0)
1343 #define MAXLABELWD (POINTS_PER_INCH/2.0)
1344 
1345 /* addEdgeLabels:
1346  * rp and rq are the port points of the tail and head node.
1347  * Adds label, headlabel and taillabel.
1348  * The use of 2 and 4 in computing ld.x and ld.y are fudge factors, to
1349  * introduce a bit of spacing.
1350  * Updates bounding box.
1351  * We try to use the actual endpoints of the spline, as they may differ
1352  * significantly from rp and rq, but if the spline is degenerate (e.g.,
1353  * the nodes overlap), we use rp and rq.
1354  */
1355 void addEdgeLabels(graph_t* g, edge_t * e, pointf rp, pointf rq)
1356 {
1357 #if 0
1358  int et = EDGE_TYPE (g);
1359  pointf p, q;
1360  pointf d; /* midpoint of segment p-q */
1361  point ld;
1362  point del;
1363  pointf spf;
1364  double f, ht, wd, dist2;
1365  int leftOf;
1366 
1367  if (ED_label(e) && !ED_label(e)->set) {
1368  endPoints(ED_spl(e), &p, &q);
1369  if (APPROXEQPT(p, q, MILLIPOINT)) { /* degenerate spline */
1370  p = rp;
1371  q = rq;
1372  spf = p;
1373  }
1374  else if (et == ET_SPLINE) {
1375  d.x = (q.x + p.x) / 2.;
1376  d.y = (p.y + q.y) / 2.;
1377  spf = dotneato_closest(ED_spl(e), d);
1378  }
1379  else { /* ET_PLINE, ET_ORTHO or ET_LINE */
1380  spf = polylineMidpoint (ED_spl(e), &p, &q);
1381  }
1382  del.x = q.x - p.x;
1383  del.y = q.y - p.y;
1384  dist2 = del.x*del.x + del.y*del.y;
1385  ht = (ED_label(e)->dimen.y + 2)/2.0;
1386  if (dist2) {
1387  wd = (MIN(ED_label(e)->dimen.x + 2, MAXLABELWD))/2.0;
1388  leftOf = LEFTOF(p, q, spf);
1389  if ((leftOf && (del.y >= 0)) || (!leftOf && (del.y < 0))) {
1390  if (del.x*del.y >= 0)
1391  ht *= -1;
1392  }
1393  else {
1394  wd *= -1;
1395  if (del.x*del.y < 0)
1396  ht *= -1;
1397  }
1398  f = (del.y*wd - del.x*ht)/dist2;
1399  ld.x = -f*del.y;
1400  ld.y = f*del.x;
1401  }
1402  else { /* end points the same */
1403  ld.x = 0;
1404  ld.y = -ht;
1405  }
1406 
1407  ED_label(e)->pos.x = spf.x + ld.x;
1408  ED_label(e)->pos.y = spf.y + ld.y;
1409  ED_label(e)->set = TRUE;
1410  updateBB(agraphof(agtail(e)), ED_label(e));
1411  }
1412 #endif
1413  makePortLabels(e);
1414 }
1415 
1416 #define AGXGET(o,a) agxget(o,a)
1417 
1418 /* vladimir */
1419 /* place_portlabel:
1420  * place the {head,tail}label (depending on HEAD_P) of edge E
1421  * N.B. Assume edges are normalized, so tail is at spl->list[0].list[0]
1422  * and head is at spl->list[spl->size-l].list[bez->size-1]
1423  * Return 1 on success
1424  */
1425 int place_portlabel(edge_t * e, boolean head_p)
1426 {
1427  textlabel_t *l;
1428  splines *spl;
1429  bezier *bez;
1430  double dist, angle;
1431  pointf c[4], pe, pf;
1432  int i;
1433  char* la;
1434  char* ld;
1435 
1436  if (ED_edge_type(e) == IGNORED)
1437  return 0;
1438  /* add label here only if labelangle or labeldistance is defined; else, use external label */
1439  if ((!E_labelangle || (*(la = AGXGET(e,E_labelangle)) == '\0')) &&
1440  (!E_labeldistance || (*(ld = AGXGET(e,E_labeldistance)) == '\0'))) {
1441  return 0;
1442  }
1443 
1444  l = head_p ? ED_head_label(e) : ED_tail_label(e);
1445  if ((spl = getsplinepoints(e)) == NULL) return 0;
1446  if (!head_p) {
1447  bez = &spl->list[0];
1448  if (bez->sflag) {
1449  pe = bez->sp;
1450  pf = bez->list[0];
1451  } else {
1452  pe = bez->list[0];
1453  for (i = 0; i < 4; i++)
1454  c[i] = bez->list[i];
1455  pf = Bezier(c, 3, 0.1, NULL, NULL);
1456  }
1457  } else {
1458  bez = &spl->list[spl->size - 1];
1459  if (bez->eflag) {
1460  pe = bez->ep;
1461  pf = bez->list[bez->size - 1];
1462  } else {
1463  pe = bez->list[bez->size - 1];
1464  for (i = 0; i < 4; i++)
1465  c[i] = bez->list[bez->size - 4 + i];
1466  pf = Bezier(c, 3, 0.9, NULL, NULL);
1467  }
1468  }
1469  angle = atan2(pf.y - pe.y, pf.x - pe.x) +
1470  RADIANS(late_double(e, E_labelangle, PORT_LABEL_ANGLE, -180.0));
1471  dist = PORT_LABEL_DISTANCE * late_double(e, E_labeldistance, 1.0, 0.0);
1472  l->pos.x = pe.x + dist * cos(angle);
1473  l->pos.y = pe.y + dist * sin(angle);
1474  l->set = TRUE;
1475  return 1;
1476 }
1477 
1478 splines *getsplinepoints(edge_t * e)
1479 {
1480  edge_t *le;
1481  splines *sp;
1482 
1483  for (le = e; !(sp = ED_spl(le)) && ED_edge_type(le) != NORMAL;
1484  le = ED_to_orig(le));
1485  if (sp == NULL)
1486  agerr (AGERR, "getsplinepoints: no spline points available for edge (%s,%s)\n",
1487  agnameof(agtail(e)), agnameof(aghead(e)));
1488  return sp;
1489 }
1490 
path::data
void * data
Definition: types.h:105
MAX
#define MAX(a, b)
Definition: agerror.c:17
path::start
port start
Definition: types.h:101
new_spline
bezier * new_spline(edge_t *e, int sz)
Definition: splines.c:218
ND_rank
#define ND_rank(n)
Definition: types.h:529
AGERR
Definition: cgraph.h:388
pathend_t::sidemask
int sidemask
Definition: types.h:95
ABS
#define ABS(a)
Definition: arith.h:45
port
Definition: types.h:67
bezier::eflag
int eflag
Definition: types.h:112
ET_SPLINE
#define ET_SPLINE
Definition: const.h:275
N_NEW
#define N_NEW(n, t)
Definition: memory.h:36
textlabel_t
Definition: types.h:123
pathend_t::nb
boxf nb
Definition: types.h:93
bezier::size
int size
Definition: types.h:110
pathend_t::np
pointf np
Definition: types.h:94
edgeMidpoint
pointf edgeMidpoint(graph_t *g, edge_t *e)
Definition: splines.c:1321
textlabel_t::set
boolean set
Definition: types.h:142
MIN
#define MIN(a, b)
Definition: arith.h:35
ND_node_type
#define ND_node_type(n)
Definition: types.h:518
getsplinepoints
splines * getsplinepoints(edge_t *e)
Definition: splines.c:1478
ALLOC
#define ALLOC(size, ptr, type)
Definition: memory.h:41
splineInfo::swapEnds
boolean(* swapEnds)(edge_t *e)
Definition: types.h:86
splines
Definition: types.h:117
FUDGE
#define FUDGE
Definition: splines.c:389
ED_head_port
#define ED_head_port(e)
Definition: types.h:591
splines::size
int size
Definition: types.h:119
assert
#define assert(x)
Definition: cghdr.h:47
beginpath
void beginpath(path *, Agedge_t *, int, pathend_t *, boolean)
Definition: splines.c:393
pointf_s
Definition: geom.h:28
RIGHT
#define RIGHT
Definition: const.h:119
E_labeldistance
EXTERN Agsym_t * E_labeldistance
Definition: globals.h:107
E_labelangle
EXTERN Agsym_t * E_labelangle
Definition: globals.h:107
ED_to_orig
#define ED_to_orig(e)
Definition: types.h:601
ED_label
#define ED_label(e)
Definition: types.h:592
TOP
#define TOP
Definition: const.h:120
endpath
void endpath(path *, Agedge_t *, int, pathend_t *, boolean)
Definition: splines.c:588
clip_and_install
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, int pn, splineInfo *info)
Definition: splines.c:241
EDGE_TYPE
#define EDGE_TYPE(g)
Definition: macros.h:33
GD_showboxes
#define GD_showboxes(g)
Definition: types.h:410
APPROXEQPT
#define APPROXEQPT(p, q, tol)
Definition: geom.h:78
Agraph_s
Definition: cgraph.h:239
agerr
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
port::constrained
boolean constrained
Definition: types.h:74
arrow_flags
void arrow_flags(Agedge_t *e, int *sflag, int *eflag)
Definition: arrows.c:198
arrowEndClip
int arrowEndClip(edge_t *e, pointf *ps, int startp, int endp, bezier *spl, int eflag)
Definition: arrows.c:256
add_box
void add_box(path *, boxf)
Definition: splines.c:352
splines::list
bezier * list
Definition: types.h:118
ED_tail_label
#define ED_tail_label(e)
Definition: types.h:599
point::x
int x
Definition: geom.h:26
path::boxes
boxf * boxes
Definition: types.h:104
MAXLABELWD
#define MAXLABELWD
Definition: splines.c:1343
GD_ranksep
#define GD_ranksep(g)
Definition: types.h:406
agraphof
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
agtail
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
addEdgeLabels
void addEdgeLabels(graph_t *g, edge_t *e, pointf rp, pointf rq)
Definition: splines.c:1355
splineInfo::ignoreSwap
boolean ignoreSwap
Definition: types.h:88
DIST
#define DIST(p, q)
Definition: geom.h:60
AGXGET
#define AGXGET(o, a)
Definition: splines.c:1416
ED_showboxes
#define ED_showboxes(e)
Definition: types.h:597
ED_tail_port
#define ED_tail_port(e)
Definition: types.h:600
le
#define le
Definition: edges.h:32
textlabel_t::pos
pointf pos
Definition: types.h:133
int
int
Definition: grammar.c:1264
Agedge_s
Definition: cgraph.h:139
ED_spl
#define ED_spl(e)
Definition: types.h:598
leftOf
int leftOf(Point a, Point b, Point c)
Definition: geometry.c:62
ND_ht
#define ND_ht(n)
Definition: types.h:506
aghead
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
ND_shape
#define ND_shape(n)
Definition: types.h:534
pointf_s::y
double y
Definition: geom.h:28
ND_order
#define ND_order(n)
Definition: types.h:520
selfRightSpace
int selfRightSpace(edge_t *e)
Definition: splines.c:1163
bezier::sflag
int sflag
Definition: types.h:111
agnameof
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
splineInfo::isOrtho
boolean isOrtho
Definition: types.h:89
SELF_EDGE_SIZE
#define SELF_EDGE_SIZE
Definition: const.h:99
update_bb_bz
void update_bb_bz(boxf *bb, pointf *cp)
Definition: emit.c:794
bezier::sp
pointf sp
Definition: types.h:113
pathend_t::boxn
int boxn
Definition: types.h:96
LEFT
#define LEFT
Definition: const.h:121
Agnode_s
Definition: cgraph.h:133
ND_rw
#define ND_rw(n)
Definition: types.h:531
ND_showboxes
#define ND_showboxes(n)
Definition: types.h:536
makePortLabels
void makePortLabels(edge_t *e)
Definition: splines.c:1237
bezier::list
pointf * list
Definition: types.h:109
BOTTOM
#define BOTTOM
Definition: const.h:118
textlabel_t::dimen
pointf dimen
Definition: types.h:129
pathend_t::boxes
boxf boxes[20]
Definition: types.h:97
port::theta
double theta
Definition: types.h:69
GD_flip
#define GD_flip(g)
Definition: types.h:385
dist2
COORD dist2(Ppoint_t, Ppoint_t)
Definition: visibility.c:213
bezier::ep
pointf ep
Definition: types.h:114
ET_CURVED
#define ET_CURVED
Definition: const.h:272
ND_lw
#define ND_lw(n)
Definition: types.h:513
Bezier
pointf Bezier(pointf *V, int degree, double t, pointf *Left, pointf *Right)
Definition: utils.c:221
arrowOrthoClip
void arrowOrthoClip(edge_t *e, pointf *ps, int startp, int endp, bezier *spl, int sflag, int eflag)
Definition: arrows.c:323
RADIANS
#define RADIANS(deg)
Definition: arith.h:85
NULL
#define NULL
Definition: logic.h:39
Show_cnt
EXTERN int Show_cnt
Definition: globals.h:73
ED_head_label
#define ED_head_label(e)
Definition: types.h:590
HT2
#define HT2(n)
Definition: splines.c:390
point
Definition: geom.h:26
ND_in
#define ND_in(n)
Definition: types.h:507
pointf_s::x
double x
Definition: geom.h:28
ND_coord
#define ND_coord(n)
Definition: types.h:496
right
#define right(i)
Definition: closest.c:87
late_double
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:87
shape_clip
void shape_clip(node_t *n, pointf curve[4])
Definition: splines.c:195
inside_t::bp
boxf * bp
Definition: types.h:63
makeSelfEdge
void makeSelfEdge(path *P, edge_t *edges[], int ind, int cnt, double sizex, double sizey, splineInfo *sinfo)
Definition: splines.c:1191
port::p
pointf p
Definition: types.h:68
bezier
Definition: types.h:108
PORT_LABEL_DISTANCE
#define PORT_LABEL_DISTANCE
Definition: const.h:102
inside_t::n
node_t * n
Definition: types.h:62
splineInfo::splineMerge
boolean(* splineMerge)(node_t *n)
Definition: types.h:87
IGNORED
#define IGNORED
Definition: const.h:33
inside_t::s
struct inside_t::@19 s
FLATEDGE
#define FLATEDGE
Definition: const.h:164
ND_out
#define ND_out(n)
Definition: types.h:522
boxf::LL
pointf LL
Definition: geom.h:35
path
Definition: types.h:100
updateBB
void updateBB(graph_t *g, textlabel_t *lp)
Definition: utils.c:842
Show_boxes
EXTERN char ** Show_boxes
Definition: globals.h:74
LEFTOF
#define LEFTOF(a, b, c)
Definition: splines.c:1342
resolvePort
port resolvePort(node_t *n, node_t *other, port *oldport)
Definition: shapes.c:4196
inside_t
Definition: types.h:56
pf
void(* pf)(char *, void *)
Definition: xdot.c:501
left
#define left
Definition: dthdr.h:16
MILLIPOINT
#define MILLIPOINT
Definition: geom.h:81
GD_bb
#define GD_bb(g)
Definition: types.h:357
SELFEDGE
#define SELFEDGE
Definition: const.h:167
ARR_NONE
#define ARR_NONE
Definition: const.h:109
M_PI
#define M_PI
Definition: arith.h:77
place_portlabel
int place_portlabel(edge_t *e, boolean head_p)
Definition: splines.c:1425
dist
double dist(Site *s, Site *t)
Definition: site.c:41
NORMAL
#define NORMAL
Definition: const.h:27
REGULAREDGE
#define REGULAREDGE
Definition: const.h:163
point::y
int y
Definition: geom.h:26
path::nbox
int nbox
Definition: types.h:103
ED_edge_type
#define ED_edge_type(e)
Definition: types.h:585
path::end
port end
Definition: types.h:102
dotneato_closest
pointf dotneato_closest(splines *spl, pointf pt)
Definition: utils.c:477
boxf::UR
pointf UR
Definition: geom.h:35
boxf
Definition: geom.h:35
FALSE
#define FALSE
Definition: cgraph.h:35
bezier_clip
void bezier_clip(inside_t *inside_context, boolean(*insidefn)(inside_t *inside_context, pointf p), pointf *sp, boolean left_inside)
Definition: splines.c:106
arrowStartClip
int arrowStartClip(edge_t *e, pointf *ps, int startp, int endp, bezier *spl, int sflag)
Definition: arrows.c:285
PORT_LABEL_ANGLE
#define PORT_LABEL_ANGLE
Definition: const.h:103
NEW
#define NEW(t)
Definition: memory.h:35
pathend_t
Definition: types.h:92
TRUE
#define TRUE
Definition: cgraph.h:38
Generated by   doxygen 1.8.5