Graphviz  2.35.20130930.0449
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;
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  * The HT2 macro is needed because dot calculates ht2 and ht1 of ranks using
389  * integers.
390  */
391 #define FUDGE 2
392 #define HT2(n) ((ROUND(ND_ht(n))+1)/2)
393 
394 void
395 beginpath(path * P, edge_t * e, int et, pathend_t * endp, boolean merge)
396 {
397  int side, mask;
398  node_t *n;
399  int (*pboxfn) (node_t*, port*, int, boxf*, int*);
400 
401  n = agtail(e);
402 
403  if (ED_tail_port(e).dyna)
404  ED_tail_port(e) = resolvePort(agtail(e), aghead(e), &ED_tail_port(e));
405  if (ND_shape(n))
406  pboxfn = ND_shape(n)->fns->pboxfn;
407  else
408  pboxfn = NULL;
409  P->start.p = add_pointf(ND_coord(n), ED_tail_port(e).p);
410  if (merge) {
411  /*P->start.theta = - M_PI / 2; */
412  P->start.theta = conc_slope(agtail(e));
413  P->start.constrained = TRUE;
414  } else {
415  if (ED_tail_port(e).constrained) {
416  P->start.theta = ED_tail_port(e).theta;
417  P->start.constrained = TRUE;
418  } else
419  P->start.constrained = FALSE;
420  }
421  P->nbox = 0;
422  P->data = (void *) e;
423  endp->np = P->start.p;
424  if ((et == REGULAREDGE) && (ND_node_type(n) == NORMAL) && ((side = ED_tail_port(e).side))) {
425  edge_t* orig;
426  boxf b0, b = endp->nb;
427  if (side & TOP) {
428  endp->sidemask = TOP;
429  if (P->start.p.x < ND_coord(n).x) { /* go left */
430  b0.LL.x = b.LL.x - 1;
431  /* b0.LL.y = ND_coord(n).y + HT2(n); */
432  b0.LL.y = P->start.p.y;
433  b0.UR.x = b.UR.x;
434  b0.UR.y = ND_coord(n).y + HT2(n) + GD_ranksep(agraphof(n))/2;
435  b.UR.x = ND_coord(n).x - ND_lw(n) - (FUDGE-2);
436  b.UR.y = b0.LL.y;
437  b.LL.y = ND_coord(n).y - HT2(n);
438  b.LL.x -= 1;
439  endp->boxes[0] = b0;
440  endp->boxes[1] = b;
441  }
442  else {
443  b0.LL.x = b.LL.x;
444  b0.LL.y = P->start.p.y;
445  /* b0.LL.y = ND_coord(n).y + HT2(n); */
446  b0.UR.x = b.UR.x+1;
447  b0.UR.y = ND_coord(n).y + HT2(n) + GD_ranksep(agraphof(n))/2;
448  b.LL.x = ND_coord(n).x + ND_rw(n) + (FUDGE-2);
449  b.UR.y = b0.LL.y;
450  b.LL.y = ND_coord(n).y - HT2(n);
451  b.UR.x += 1;
452  endp->boxes[0] = b0;
453  endp->boxes[1] = b;
454  }
455  P->start.p.y += 1;
456  endp->boxn = 2;
457  }
458  else if (side & BOTTOM) {
459  endp->sidemask = BOTTOM;
460  b.UR.y = MAX(b.UR.y,P->start.p.y);
461  endp->boxes[0] = b;
462  endp->boxn = 1;
463  P->start.p.y -= 1;
464  }
465  else if (side & LEFT) {
466  endp->sidemask = LEFT;
467  b.UR.x = P->start.p.x;
468  b.LL.y = ND_coord(n).y - HT2(n);
469  b.UR.y = P->start.p.y;
470  endp->boxes[0] = b;
471  endp->boxn = 1;
472  P->start.p.x -= 1;
473  }
474  else {
475  endp->sidemask = RIGHT;
476  b.LL.x = P->start.p.x;
477  b.LL.y = ND_coord(n).y - HT2(n);
478  b.UR.y = P->start.p.y;
479  endp->boxes[0] = b;
480  endp->boxn = 1;
481  P->start.p.x += 1;
482  }
483  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
484  if (n == agtail(orig))
485  ED_tail_port(orig).clip = FALSE;
486  else
487  ED_head_port(orig).clip = FALSE;
488  return;
489  }
490  if ((et == FLATEDGE) && ((side = ED_tail_port(e).side))) {
491  boxf b0, b = endp->nb;
492  edge_t* orig;
493  if (side & TOP) {
494  b.LL.y = MIN(b.LL.y,P->start.p.y);
495  endp->boxes[0] = b;
496  endp->boxn = 1;
497  P->start.p.y += 1;
498  }
499  else if (side & BOTTOM) {
500  if (endp->sidemask == TOP) {
501  b0.UR.y = ND_coord(n).y - HT2(n);
502  b0.UR.x = b.UR.x+1;
503  b0.LL.x = P->start.p.x;
504  b0.LL.y = b0.UR.y - GD_ranksep(agraphof(n))/2;
505  b.LL.x = ND_coord(n).x + ND_rw(n) + (FUDGE-2);
506  b.LL.y = b0.UR.y;
507  b.UR.y = ND_coord(n).y + HT2(n);
508  b.UR.x += 1;
509  endp->boxes[0] = b0;
510  endp->boxes[1] = b;
511  endp->boxn = 2;
512  }
513  else {
514  b.UR.y = MAX(b.UR.y,P->start.p.y);
515  endp->boxes[0] = b;
516  endp->boxn = 1;
517  }
518  P->start.p.y -= 1;
519  }
520  else if (side & LEFT) {
521  b.UR.x = P->start.p.x+1;
522  if (endp->sidemask == TOP) {
523  b.UR.y = ND_coord(n).y + HT2(n);
524  b.LL.y = P->start.p.y-1;
525  }
526  else {
527  b.LL.y = ND_coord(n).y - HT2(n);
528  b.UR.y = P->start.p.y+1;
529  }
530  endp->boxes[0] = b;
531  endp->boxn = 1;
532  P->start.p.x -= 1;
533  }
534  else {
535  b.LL.x = P->start.p.x;
536  if (endp->sidemask == TOP) {
537  b.UR.y = ND_coord(n).y + HT2(n);
538  b.LL.y = P->start.p.y;
539  }
540  else {
541  b.LL.y = ND_coord(n).y - HT2(n);
542  b.UR.y = P->start.p.y+1;
543  }
544  endp->boxes[0] = b;
545  endp->boxn = 1;
546  P->start.p.x += 1;
547  }
548  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
549  if (n == agtail(orig))
550  ED_tail_port(orig).clip = FALSE;
551  else
552  ED_head_port(orig).clip = FALSE;
553  endp->sidemask = side;
554  return;
555  }
556 
557  if (et == REGULAREDGE) side = BOTTOM;
558  else side = endp->sidemask; /* for flat edges */
559  if (pboxfn
560  && (mask = (*pboxfn) (n, &ED_tail_port(e), side, &endp->boxes[0], &endp->boxn)))
561  endp->sidemask = mask;
562  else {
563  endp->boxes[0] = endp->nb;
564  endp->boxn = 1;
565 
566  switch (et) {
567  case SELFEDGE:
568  /* moving the box UR.y by + 1 avoids colinearity between
569  port point and box that confuses Proutespline(). it's
570  a bug in Proutespline() but this is the easiest fix. */
571  assert(0); /* at present, we don't use beginpath for selfedges */
572  endp->boxes[0].UR.y = P->start.p.y - 1;
573  endp->sidemask = BOTTOM;
574  break;
575  case FLATEDGE:
576  if (endp->sidemask == TOP)
577  endp->boxes[0].LL.y = P->start.p.y;
578  else
579  endp->boxes[0].UR.y = P->start.p.y;
580  break;
581  case REGULAREDGE:
582  endp->boxes[0].UR.y = P->start.p.y;
583  endp->sidemask = BOTTOM;
584  P->start.p.y -= 1;
585  break;
586  }
587  }
588 }
589 
590 void endpath(path * P, edge_t * e, int et, pathend_t * endp, boolean merge)
591 {
592  int side, mask;
593  node_t *n;
594  int (*pboxfn) (node_t* n, port*, int, boxf*, int*);
595 
596  n = aghead(e);
597 
598  if (ED_head_port(e).dyna)
599  ED_head_port(e) = resolvePort(aghead(e), agtail(e), &ED_head_port(e));
600  if (ND_shape(n))
601  pboxfn = ND_shape(n)->fns->pboxfn;
602  else
603  pboxfn = NULL;
604  P->end.p = add_pointf(ND_coord(n), ED_head_port(e).p);
605  if (merge) {
606  /*P->end.theta = M_PI / 2; */
607  P->end.theta = conc_slope(aghead(e)) + M_PI;
608  assert(P->end.theta < 2 * M_PI);
609  P->end.constrained = TRUE;
610  } else {
611  if (ED_head_port(e).constrained) {
612  P->end.theta = ED_head_port(e).theta;
613  P->end.constrained = TRUE;
614  } else
615  P->end.constrained = FALSE;
616  }
617  endp->np = P->end.p;
618  if ((et == REGULAREDGE) && (ND_node_type(n) == NORMAL) && ((side = ED_head_port(e).side))) {
619  edge_t* orig;
620  boxf b0, b = endp->nb;
621  if (side & TOP) {
622  endp->sidemask = TOP;
623  b.LL.y = MIN(b.LL.y,P->end.p.y);
624  endp->boxes[0] = b;
625  endp->boxn = 1;
626  P->end.p.y += 1;
627  }
628  else if (side & BOTTOM) {
629  endp->sidemask = BOTTOM;
630  if (P->end.p.x < ND_coord(n).x) { /* go left */
631  b0.LL.x = b.LL.x-1;
632  /* b0.UR.y = ND_coord(n).y - HT2(n); */
633  b0.UR.y = P->end.p.y;
634  b0.UR.x = b.UR.x;
635  b0.LL.y = ND_coord(n).y - HT2(n) - GD_ranksep(agraphof(n))/2;
636  b.UR.x = ND_coord(n).x - ND_lw(n) - (FUDGE-2);
637  b.LL.y = b0.UR.y;
638  b.UR.y = ND_coord(n).y + HT2(n);
639  b.LL.x -= 1;
640  endp->boxes[0] = b0;
641  endp->boxes[1] = b;
642  }
643  else {
644  b0.LL.x = b.LL.x;
645  b0.UR.y = P->end.p.y;
646  /* b0.UR.y = ND_coord(n).y - HT2(n); */
647  b0.UR.x = b.UR.x+1;
648  b0.LL.y = ND_coord(n).y - HT2(n) - GD_ranksep(agraphof(n))/2;
649  b.LL.x = ND_coord(n).x + ND_rw(n) + (FUDGE-2);
650  b.LL.y = b0.UR.y;
651  b.UR.y = ND_coord(n).y + HT2(n);
652  b.UR.x += 1;
653  endp->boxes[0] = b0;
654  endp->boxes[1] = b;
655  }
656  endp->boxn = 2;
657  P->end.p.y -= 1;
658  }
659  else if (side & LEFT) {
660  endp->sidemask = LEFT;
661  b.UR.x = P->end.p.x;
662  b.UR.y = ND_coord(n).y + HT2(n);
663  b.LL.y = P->end.p.y;
664  endp->boxes[0] = b;
665  endp->boxn = 1;
666  P->end.p.x -= 1;
667  }
668  else {
669  endp->sidemask = RIGHT;
670  b.LL.x = P->end.p.x;
671  b.UR.y = ND_coord(n).y + HT2(n);
672  b.LL.y = P->end.p.y;
673  endp->boxes[0] = b;
674  endp->boxn = 1;
675  P->end.p.x += 1;
676  }
677  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
678  if (n == aghead(orig))
679  ED_head_port(orig).clip = FALSE;
680  else
681  ED_tail_port(orig).clip = FALSE;
682  endp->sidemask = side;
683  return;
684  }
685 
686  if ((et == FLATEDGE) && ((side = ED_head_port(e).side))) {
687  boxf b0, b = endp->nb;
688  edge_t* orig;
689  if (side & TOP) {
690  b.LL.y = MIN(b.LL.y,P->end.p.y);
691  endp->boxes[0] = b;
692  endp->boxn = 1;
693  P->end.p.y += 1;
694  }
695  else if (side & BOTTOM) {
696  if (endp->sidemask == TOP) {
697  b0.LL.x = b.LL.x-1;
698  b0.UR.y = ND_coord(n).y - HT2(n);
699  b0.UR.x = P->end.p.x;
700  b0.LL.y = b0.UR.y - GD_ranksep(agraphof(n))/2;
701  b.UR.x = ND_coord(n).x - ND_lw(n) - 2;
702  b.LL.y = b0.UR.y;
703  b.UR.y = ND_coord(n).y + HT2(n);
704  b.LL.x -= 1;
705  endp->boxes[0] = b0;
706  endp->boxes[1] = b;
707  endp->boxn = 2;
708  }
709  else {
710  b.UR.y = MAX(b.UR.y,P->start.p.y);
711  endp->boxes[0] = b;
712  endp->boxn = 1;
713  }
714  P->end.p.y -= 1;
715  }
716  else if (side & LEFT) {
717  b.UR.x = P->end.p.x+1;
718  if (endp->sidemask == TOP) {
719  b.UR.y = ND_coord(n).y + HT2(n);
720  b.LL.y = P->end.p.y-1;
721  }
722  else {
723  b.LL.y = ND_coord(n).y - HT2(n);
724  b.UR.y = P->end.p.y+1;
725  }
726  endp->boxes[0] = b;
727  endp->boxn = 1;
728  P->end.p.x -= 1;
729  }
730  else {
731  b.LL.x = P->end.p.x-1;
732  if (endp->sidemask == TOP) {
733  b.UR.y = ND_coord(n).y + HT2(n);
734  b.LL.y = P->end.p.y-1;
735  }
736  else {
737  b.LL.y = ND_coord(n).y - HT2(n);
738  b.UR.y = P->end.p.y;
739  }
740  endp->boxes[0] = b;
741  endp->boxn = 1;
742  P->end.p.x += 1;
743  }
744  for (orig = e; ED_edge_type(orig) != NORMAL; orig = ED_to_orig(orig));
745  if (n == aghead(orig))
746  ED_head_port(orig).clip = FALSE;
747  else
748  ED_tail_port(orig).clip = FALSE;
749  endp->sidemask = side;
750  return;
751  }
752 
753  if (et == REGULAREDGE) side = TOP;
754  else side = endp->sidemask; /* for flat edges */
755  if (pboxfn
756  && (mask = (*pboxfn) (n, &ED_head_port(e), side, &endp->boxes[0], &endp->boxn)))
757  endp->sidemask = mask;
758  else {
759  endp->boxes[0] = endp->nb;
760  endp->boxn = 1;
761 
762  switch (et) {
763  case SELFEDGE:
764  /* offset of -1 is symmetric w.r.t. beginpath()
765  * FIXME: is any of this right? what if self-edge
766  * doesn't connect from BOTTOM to TOP??? */
767  assert(0); /* at present, we don't use endpath for selfedges */
768  endp->boxes[0].LL.y = P->end.p.y + 1;
769  endp->sidemask = TOP;
770  break;
771  case FLATEDGE:
772  if (endp->sidemask == TOP)
773  endp->boxes[0].LL.y = P->end.p.y;
774  else
775  endp->boxes[0].UR.y = P->end.p.y;
776  break;
777  case REGULAREDGE:
778  endp->boxes[0].LL.y = P->end.p.y;
779  endp->sidemask = TOP;
780  P->end.p.y += 1;
781  break;
782  }
783  }
784 }
785 
786 
787 static int convert_sides_to_points(int tail_side, int head_side)
788 {
789 int vertices[] = {12,4,6,2,3,1,9,8}; //the cumulative side value of each node point
790 int i, tail_i, head_i;
791 int pair_a[8][8] = { //array of possible node point pairs
792 {11,12,13,14,15,16,17,18},
793 {21,22,23,24,25,26,27,28},
794 {31,32,33,34,35,36,37,38},
795 {41,42,43,44,45,46,47,48},
796 {51,52,53,54,55,56,57,58},
797 {61,62,63,64,65,66,67,68},
798 {71,72,73,74,75,76,77,78},
799 {81,82,83,84,85,86,87,88}
800 };
801 
802  tail_i = head_i = -1;
803  for(i=0;i< 8; i++){
804  if(head_side == vertices[i]){
805  head_i = i;
806  break;
807  }
808  }
809  for(i=0;i< 8; i++){
810  if(tail_side == vertices[i]){
811  tail_i = i;
812  break;
813  }
814  }
815 
816 if( tail_i < 0 || head_i < 0)
817  return 0;
818 else
819  return pair_a[tail_i][head_i];
820 }
821 
822 
823 static void selfBottom (edge_t* edges[], int ind, int cnt,
824  double sizex, double stepy, splineInfo* sinfo)
825 {
826  pointf tp, hp, np;
827  node_t *n;
828  edge_t *e;
829  int i, sgn, point_pair;
830  double hy, ty, stepx, dx, dy, width, height;
831  pointf points[1000];
832  int pointn;
833 
834  e = edges[ind];
835  n = agtail(e);
836 
837  stepx = (sizex / 2.) / cnt;
838  stepx = MAX(stepx,2.);
839  pointn = 0;
840  np = ND_coord(n);
841  tp = ED_tail_port(e).p;
842  tp.x += np.x;
843  tp.y += np.y;
844  hp = ED_head_port(e).p;
845  hp.x += np.x;
846  hp.y += np.y;
847  if (tp.x >= hp.x) sgn = 1;
848  else sgn = -1;
849  dy = ND_ht(n)/2., dx = 0.;
850  // certain adjustments are required for some point_pairs in order to improve the
851  // display of the edge path between them
852  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
853  switch(point_pair){
854  case 67: sgn = -sgn;
855  break;
856  default:
857  break;
858  }
859  ty = MIN(dy, 3*(tp.y + dy - np.y));
860  hy = MIN(dy, 3*(hp.y + dy - np.y));
861  for (i = 0; i < cnt; i++) {
862  e = edges[ind++];
863  dy += stepy, ty += stepy, hy += stepy, dx += sgn*stepx;
864  pointn = 0;
865  points[pointn++] = tp;
866  points[pointn++] = pointfof(tp.x + dx, tp.y - ty / 3);
867  points[pointn++] = pointfof(tp.x + dx, np.y - dy);
868  points[pointn++] = pointfof((tp.x+hp.x)/2, np.y - dy);
869  points[pointn++] = pointfof(hp.x - dx, np.y - dy);
870  points[pointn++] = pointfof(hp.x - dx, hp.y - hy / 3);
871  points[pointn++] = hp;
872  if (ED_label(e)) {
873  if (GD_flip(agraphof(agtail(e)))) {
874  width = ED_label(e)->dimen.y;
875  height = ED_label(e)->dimen.x;
876  } else {
877  width = ED_label(e)->dimen.x;
878  height = ED_label(e)->dimen.y;
879  }
880  ED_label(e)->pos.y = ND_coord(n).y - dy - height / 2.0;
881  ED_label(e)->pos.x = ND_coord(n).x;
882  ED_label(e)->set = TRUE;
883  if (height > stepy)
884  dy += height - stepy;
885  }
886  clip_and_install(e, aghead(e), points, pointn, sinfo);
887 #ifdef DEBUG
888  if (debugleveln(e,1))
889  showPoints (points, pointn);
890 #endif
891  }
892 }
893 
894 
895 static void
896 selfTop (edge_t* edges[], int ind, int cnt, double sizex, double stepy,
897  splineInfo* sinfo)
898 {
899  int i, sgn, point_pair;
900  double hy, ty, stepx, dx, dy, width, height;
901  pointf tp, hp, np;
902  node_t *n;
903  edge_t *e;
904  pointf points[1000];
905  int pointn;
906 
907  e = edges[ind];
908  n = agtail(e);
909 
910  stepx = (sizex / 2.) / cnt;
911  stepx = MAX(stepx, 2.);
912  pointn = 0;
913  np = ND_coord(n);
914  tp = ED_tail_port(e).p;
915  tp.x += np.x;
916  tp.y += np.y;
917  hp = ED_head_port(e).p;
918  hp.x += np.x;
919  hp.y += np.y;
920  if (tp.x >= hp.x) sgn = 1;
921  else sgn = -1;
922  dy = ND_ht(n)/2., dx = 0.;
923  // certain adjustments are required for some point_pairs in order to improve the
924  // display of the edge path between them
925  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
926  switch(point_pair){
927  case 15:
928  dx = sgn*(ND_rw(n) - (hp.x-np.x) + stepx);
929  break;
930 
931  case 38:
932  dx = sgn*(ND_lw(n)-(np.x-hp.x) + stepx);
933  break;
934  case 41:
935  dx = sgn*(ND_rw(n)-(tp.x-np.x) + stepx);
936  break;
937  case 48:
938  dx = sgn*(ND_rw(n)-(tp.x-np.x) + stepx);
939  break;
940 
941  case 14:
942  case 37:
943  case 47:
944  case 51:
945  case 57:
946  case 58:
947  dx = sgn*((((ND_lw(n)-(np.x-tp.x)) + (ND_rw(n)-(hp.x-np.x)))/3.));
948  break;
949  case 73:
950  dx = sgn*(ND_lw(n)-(np.x-tp.x) + stepx);
951  break;
952  case 83:
953  dx = sgn*(ND_lw(n)-(np.x-tp.x));
954  break;
955  case 84:
956  dx = sgn*((((ND_lw(n)-(np.x-tp.x)) + (ND_rw(n)-(hp.x-np.x)))/2.) + stepx);
957  break;
958  case 74:
959  case 75:
960  case 85:
961  dx = sgn*((((ND_lw(n)-(np.x-tp.x)) + (ND_rw(n)-(hp.x-np.x)))/2.) + 2*stepx);
962  break;
963  default:
964  break;
965  }
966  ty = MIN(dy, 3*(np.y + dy - tp.y));
967  hy = MIN(dy, 3*(np.y + dy - hp.y));
968  for (i = 0; i < cnt; i++) {
969  e = edges[ind++];
970  dy += stepy, ty += stepy, hy += stepy, dx += sgn*stepx;
971  pointn = 0;
972  points[pointn++] = tp;
973  points[pointn++] = pointfof(tp.x + dx, tp.y + ty / 3);
974  points[pointn++] = pointfof(tp.x + dx, np.y + dy);
975  points[pointn++] = pointfof((tp.x+hp.x)/2, np.y + dy);
976  points[pointn++] = pointfof(hp.x - dx, np.y + dy);
977  points[pointn++] = pointfof(hp.x - dx, hp.y + hy / 3);
978  points[pointn++] = hp;
979  if (ED_label(e)) {
980  if (GD_flip(agraphof(agtail(e)))) {
981  width = ED_label(e)->dimen.y;
982  height = ED_label(e)->dimen.x;
983  } else {
984  width = ED_label(e)->dimen.x;
985  height = ED_label(e)->dimen.y;
986  }
987  ED_label(e)->pos.y = ND_coord(n).y + dy + height / 2.0;
988  ED_label(e)->pos.x = ND_coord(n).x;
989  ED_label(e)->set = TRUE;
990  if (height > stepy)
991  dy += height - stepy;
992  }
993  clip_and_install(e, aghead(e), points, pointn, sinfo);
994 #ifdef DEBUG
995  if (debugleveln(e,1))
996  showPoints (points, pointn);
997 #endif
998  }
999  return;
1000 }
1001 
1002 static void
1003 selfRight (edge_t* edges[], int ind, int cnt, double stepx, double sizey,
1004  splineInfo* sinfo)
1005 {
1006  int i, sgn, point_pair;
1007  double hx, tx, stepy, dx, dy, width, height;
1008  pointf tp, hp, np;
1009  node_t *n;
1010  edge_t *e;
1011  pointf points[1000];
1012  int pointn;
1013 
1014  e = edges[ind];
1015  n = agtail(e);
1016 
1017  stepy = (sizey / 2.) / cnt;
1018  stepy = MAX(stepy, 2.);
1019  pointn = 0;
1020  np = ND_coord(n);
1021  tp = ED_tail_port(e).p;
1022  tp.x += np.x;
1023  tp.y += np.y;
1024  hp = ED_head_port(e).p;
1025  hp.x += np.x;
1026  hp.y += np.y;
1027  if (tp.y >= hp.y) sgn = 1;
1028  else sgn = -1;
1029  dx = ND_rw(n), dy = 0;
1030  // certain adjustments are required for some point_pairs in order to improve the
1031  // display of the edge path between them
1032  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
1033  switch(point_pair){
1034  case 32:
1035  case 65: if(tp.y == hp.y)
1036  sgn = -sgn;
1037  break;
1038  default:
1039  break;
1040  }
1041  tx = MIN(dx, 3*(np.x + dx - tp.x));
1042  hx = MIN(dx, 3*(np.x + dx - hp.x));
1043  for (i = 0; i < cnt; i++) {
1044  e = edges[ind++];
1045  dx += stepx, tx += stepx, hx += stepx, dy += sgn*stepy;
1046  pointn = 0;
1047  points[pointn++] = tp;
1048  points[pointn++] = pointfof(tp.x + tx / 3, tp.y + dy);
1049  points[pointn++] = pointfof(np.x + dx, tp.y + dy);
1050  points[pointn++] = pointfof(np.x + dx, (tp.y+hp.y)/2);
1051  points[pointn++] = pointfof(np.x + dx, hp.y - dy);
1052  points[pointn++] = pointfof(hp.x + hx / 3, hp.y - dy);
1053  points[pointn++] = hp;
1054  if (ED_label(e)) {
1055  if (GD_flip(agraphof(agtail(e)))) {
1056  width = ED_label(e)->dimen.y;
1057  height = ED_label(e)->dimen.x;
1058  } else {
1059  width = ED_label(e)->dimen.x;
1060  height = ED_label(e)->dimen.y;
1061  }
1062  ED_label(e)->pos.x = ND_coord(n).x + dx + width / 2.0;
1063  ED_label(e)->pos.y = ND_coord(n).y;
1064  ED_label(e)->set = TRUE;
1065  if (width > stepx)
1066  dx += width - stepx;
1067  }
1068  clip_and_install(e, aghead(e), points, pointn, sinfo);
1069 #ifdef DEBUG
1070  if (debugleveln(e,1))
1071  showPoints (points, pointn);
1072 #endif
1073  }
1074  return;
1075 }
1076 
1077 static void
1078 selfLeft (edge_t* edges[], int ind, int cnt, double stepx, double sizey,
1079  splineInfo* sinfo)
1080 {
1081  int i, sgn,point_pair;
1082  double hx, tx, stepy, dx, dy, width, height;
1083  pointf tp, hp, np;
1084  node_t *n;
1085  edge_t *e;
1086  pointf points[1000];
1087  int pointn;
1088 
1089  e = edges[ind];
1090  n = agtail(e);
1091 
1092  stepy = (sizey / 2.) / cnt;
1093  stepy = MAX(stepy,2.);
1094  pointn = 0;
1095  np = ND_coord(n);
1096  tp = ED_tail_port(e).p;
1097  tp.x += np.x;
1098  tp.y += np.y;
1099  hp = ED_head_port(e).p;
1100  hp.x += np.x;
1101  hp.y += np.y;
1102 
1103 
1104  if (tp.y >= hp.y) sgn = 1;
1105  else sgn = -1;
1106  dx = ND_lw(n), dy = 0.;
1107  // certain adjustments are required for some point_pairs in order to improve the
1108  // display of the edge path between them
1109  point_pair = convert_sides_to_points(ED_tail_port(e).side,ED_head_port(e).side);
1110  switch(point_pair){
1111  case 12:
1112  case 67:
1113  if(tp.y == hp.y)
1114  sgn = -sgn;
1115  break;
1116  default:
1117  break;
1118  }
1119  tx = MIN(dx, 3*(tp.x + dx - np.x));
1120  hx = MIN(dx, 3*(hp.x + dx - np.x));
1121  for (i = 0; i < cnt; i++) {
1122  e = edges[ind++];
1123  dx += stepx, tx += stepx, hx += stepx, dy += sgn*stepy;
1124  pointn = 0;
1125  points[pointn++] = tp;
1126  points[pointn++] = pointfof(tp.x - tx / 3, tp.y + dy);
1127  points[pointn++] = pointfof(np.x - dx, tp.y + dy);
1128  points[pointn++] = pointfof(np.x - dx, (tp.y+hp.y)/2);
1129  points[pointn++] = pointfof(np.x - dx, hp.y - dy);
1130  points[pointn++] = pointfof(hp.x - hx / 3, hp.y - dy);
1131 
1132  points[pointn++] = hp;
1133  if (ED_label(e)) {
1134  if (GD_flip(agraphof(agtail(e)))) {
1135  width = ED_label(e)->dimen.y;
1136  height = ED_label(e)->dimen.x;
1137  } else {
1138  width = ED_label(e)->dimen.x;
1139  height = ED_label(e)->dimen.y;
1140  }
1141  ED_label(e)->pos.x = ND_coord(n).x - dx - width / 2.0;
1142  ED_label(e)->pos.y = ND_coord(n).y;
1143  ED_label(e)->set = TRUE;
1144  if (width > stepx)
1145  dx += width - stepx;
1146  }
1147 
1148  clip_and_install(e, aghead(e), points, pointn, sinfo);
1149 #ifdef DEBUG
1150  if (debugleveln(e,1))
1151  showPoints (points, pointn);
1152 #endif
1153  }
1154 }
1155 
1156 /* selfRightSpace:
1157  * Assume e is self-edge.
1158  * Return extra space necessary on the right for this edge.
1159  * If the edge does not go on the right, return 0.
1160  * NOTE: the actual space is determined dynamically by GD_nodesep,
1161  * so using the constant SELF_EDGE_SIZE is going to be wrong.
1162  * Fortunately, the default nodesep is the same as SELF_EDGE_SIZE.
1163  */
1164 int
1166 {
1167  int sw;
1168  double label_width;
1169  textlabel_t* l = ED_label(e);
1170 
1171  if (((!ED_tail_port(e).defined) && (!ED_head_port(e).defined)) ||
1172  (!(ED_tail_port(e).side & LEFT) &&
1173  !(ED_head_port(e).side & LEFT) &&
1174  ((ED_tail_port(e).side != ED_head_port(e).side) ||
1175  (!(ED_tail_port(e).side & (TOP|BOTTOM)))))) {
1176  sw = SELF_EDGE_SIZE;
1177  if (l) {
1178  label_width = GD_flip(agraphof(aghead(e))) ? l->dimen.y : l->dimen.x;
1179  sw += label_width;
1180  }
1181  }
1182  else sw = 0;
1183  return sw;
1184 }
1185 
1186 /* makeSelfEdge:
1187  * The routing is biased towards the right side because this is what
1188  * dot supports, and leaves room for.
1189  * FIX: With this bias, labels tend to be placed on top of each other.
1190  * Perhaps for self-edges, the label should be centered.
1191  */
1192 void
1193 makeSelfEdge(path * P, edge_t * edges[], int ind, int cnt, double sizex,
1194  double sizey, splineInfo * sinfo)
1195 {
1196  edge_t *e;
1197 
1198  e = edges[ind];
1199 
1200  /* self edge without ports or
1201  * self edge with all ports inside, on the right, or at most 1 on top
1202  * and at most 1 on bottom
1203  */
1204 
1205  if (((!ED_tail_port(e).defined) && (!ED_head_port(e).defined)) ||
1206  (!(ED_tail_port(e).side & LEFT) &&
1207  !(ED_head_port(e).side & LEFT) &&
1208  ((ED_tail_port(e).side != ED_head_port(e).side) ||
1209  (!(ED_tail_port(e).side & (TOP|BOTTOM)))))) {
1210  selfRight(edges, ind, cnt, sizex, sizey, sinfo);
1211  }
1212 
1213  /* self edge with port on left side */
1214  else if ((ED_tail_port(e).side & LEFT) || (ED_head_port(e).side & LEFT)) {
1215 
1216  /* handle L-R specially */
1217  if ((ED_tail_port(e).side & RIGHT) || (ED_head_port(e).side & RIGHT)) {
1218  selfTop(edges, ind, cnt, sizex, sizey, sinfo);
1219  }
1220  else {
1221  selfLeft(edges, ind, cnt, sizex, sizey, sinfo);
1222  }
1223  }
1224 
1225  /* self edge with both ports on top side */
1226  else if (ED_tail_port(e).side & TOP) {
1227  selfTop(edges, ind, cnt, sizex, sizey, sinfo);
1228  }
1229  else if (ED_tail_port(e).side & BOTTOM) {
1230  selfBottom(edges, ind, cnt, sizex, sizey, sinfo);
1231  }
1232 
1233  else assert(0);
1234 }
1235 
1236 /* makePortLabels:
1237  * Add head and tail labels if necessary and update bounding box.
1238  */
1240 {
1241  /* Only use this if labelangle or labeldistance is set for the edge;
1242  * otherwise, handle with external labels.
1243  */
1244  if (!E_labelangle && !E_labeldistance) return;
1245 
1246  if (ED_head_label(e) && !ED_head_label(e)->set) {
1247  if (place_portlabel(e, TRUE))
1248  updateBB(agraphof(agtail(e)), ED_head_label(e));
1249  }
1250  if (ED_tail_label(e) && !ED_tail_label(e)->set) {
1251  if (place_portlabel(e, FALSE))
1252  updateBB(agraphof(agtail(e)), ED_tail_label(e));
1253  }
1254 }
1255 
1256 /* endPoints:
1257  * Extract the actual end points of the spline, where
1258  * they touch the node.
1259  */
1260 static void endPoints(splines * spl, pointf * p, pointf * q)
1261 {
1262  bezier bz;
1263 
1264  bz = spl->list[0];
1265  if (bz.sflag) {
1266  *p = bz.sp;
1267  }
1268  else {
1269  *p = bz.list[0];
1270  }
1271  bz = spl->list[spl->size - 1];
1272  if (bz.eflag) {
1273  *q = bz.ep;
1274  }
1275  else {
1276  *q = bz.list[bz.size - 1];
1277  }
1278 }
1279 
1280 /* polylineMidpoint;
1281  * Find midpoint of polyline.
1282  * pp and pq are set to the endpoints of the line segment containing it.
1283  */
1284 static pointf
1285 polylineMidpoint (splines* spl, pointf* pp, pointf* pq)
1286 {
1287  bezier bz;
1288  int i, j, k;
1289  double d, dist = 0;
1290  pointf pf, qf, mf;
1291 
1292  for (i = 0; i < spl->size; i++) {
1293  bz = spl->list[i];
1294  for (j = 0, k=3; k < bz.size; j+=3,k+=3) {
1295  pf = bz.list[j];
1296  qf = bz.list[k];
1297  dist += DIST(pf, qf);
1298  }
1299  }
1300  dist /= 2;
1301  for (i = 0; i < spl->size; i++) {
1302  bz = spl->list[i];
1303  for (j = 0, k=3; k < bz.size; j+=3,k+=3) {
1304  pf = bz.list[j];
1305  qf = bz.list[k];
1306  d = DIST(pf,qf);
1307  if (d >= dist) {
1308  *pp = pf;
1309  *pq = qf;
1310  mf.x = ((qf.x*dist) + (pf.x*(d-dist)))/d;
1311  mf.y = ((qf.y*dist) + (pf.y*(d-dist)))/d;
1312  return mf;
1313  }
1314  else
1315  dist -= d;
1316  }
1317  }
1318  assert (FALSE); /* should never get here */
1319  return mf;
1320 }
1321 
1322 pointf
1324 {
1325  int et = EDGE_TYPE (g);
1326  pointf d, spf, p, q;
1327 
1328  endPoints(ED_spl(e), &p, &q);
1329  if (APPROXEQPT(p, q, MILLIPOINT)) { /* degenerate spline */
1330  spf = p;
1331  }
1332  else if ((et == ET_SPLINE) || (et == ET_CURVED)) {
1333  d.x = (q.x + p.x) / 2.;
1334  d.y = (p.y + q.y) / 2.;
1335  spf = dotneato_closest(ED_spl(e), d);
1336  }
1337  else { /* ET_PLINE, ET_ORTHO or ET_LINE */
1338  spf = polylineMidpoint (ED_spl(e), &p, &q);
1339  }
1340 
1341  return spf;
1342 }
1343 
1344 #define LEFTOF(a,b,c) (((a.y - b.y)*(c.x - b.x) - (c.y - b.y)*(a.x - b.x)) > 0)
1345 #define MAXLABELWD (POINTS_PER_INCH/2.0)
1346 
1347 /* addEdgeLabels:
1348  * rp and rq are the port points of the tail and head node.
1349  * Adds label, headlabel and taillabel.
1350  * The use of 2 and 4 in computing ld.x and ld.y are fudge factors, to
1351  * introduce a bit of spacing.
1352  * Updates bounding box.
1353  * We try to use the actual endpoints of the spline, as they may differ
1354  * significantly from rp and rq, but if the spline is degenerate (e.g.,
1355  * the nodes overlap), we use rp and rq.
1356  */
1358 {
1359 #if 0
1360  int et = EDGE_TYPE (g);
1361  pointf p, q;
1362  pointf d; /* midpoint of segment p-q */
1363  point ld;
1364  point del;
1365  pointf spf;
1366  double f, ht, wd, dist2;
1367  int leftOf;
1368 
1369  if (ED_label(e) && !ED_label(e)->set) {
1370  endPoints(ED_spl(e), &p, &q);
1371  if (APPROXEQPT(p, q, MILLIPOINT)) { /* degenerate spline */
1372  p = rp;
1373  q = rq;
1374  spf = p;
1375  }
1376  else if (et == ET_SPLINE) {
1377  d.x = (q.x + p.x) / 2.;
1378  d.y = (p.y + q.y) / 2.;
1379  spf = dotneato_closest(ED_spl(e), d);
1380  }
1381  else { /* ET_PLINE, ET_ORTHO or ET_LINE */
1382  spf = polylineMidpoint (ED_spl(e), &p, &q);
1383  }
1384  del.x = q.x - p.x;
1385  del.y = q.y - p.y;
1386  dist2 = del.x*del.x + del.y*del.y;
1387  ht = (ED_label(e)->dimen.y + 2)/2.0;
1388  if (dist2) {
1389  wd = (MIN(ED_label(e)->dimen.x + 2, MAXLABELWD))/2.0;
1390  leftOf = LEFTOF(p, q, spf);
1391  if ((leftOf && (del.y >= 0)) || (!leftOf && (del.y < 0))) {
1392  if (del.x*del.y >= 0)
1393  ht *= -1;
1394  }
1395  else {
1396  wd *= -1;
1397  if (del.x*del.y < 0)
1398  ht *= -1;
1399  }
1400  f = (del.y*wd - del.x*ht)/dist2;
1401  ld.x = -f*del.y;
1402  ld.y = f*del.x;
1403  }
1404  else { /* end points the same */
1405  ld.x = 0;
1406  ld.y = -ht;
1407  }
1408 
1409  ED_label(e)->pos.x = spf.x + ld.x;
1410  ED_label(e)->pos.y = spf.y + ld.y;
1411  ED_label(e)->set = TRUE;
1412  updateBB(agraphof(agtail(e)), ED_label(e));
1413  }
1414 #endif
1415  makePortLabels(e);
1416 }
1417 
1418 #ifndef WITH_CGRAPH
1419 #define AGXGET(o,a) agxget(o,a->index)
1420 #else /* WITH_CGRAPH */
1421 #define AGXGET(o,a) agxget(o,a)
1422 #endif /* WITH_CGRAPH */
1423 
1424 /* vladimir */
1425 /* place_portlabel:
1426  * place the {head,tail}label (depending on HEAD_P) of edge E
1427  * N.B. Assume edges are normalized, so tail is at spl->list[0].list[0]
1428  * and head is at spl->list[spl->size-l].list[bez->size-1]
1429  * Return 1 on success
1430  */
1431 int place_portlabel(edge_t * e, boolean head_p)
1432 {
1433  textlabel_t *l;
1434  splines *spl;
1435  bezier *bez;
1436  double dist, angle;
1437  pointf c[4], pe, pf;
1438  int i;
1439  char* la;
1440  char* ld;
1441 
1442  if (ED_edge_type(e) == IGNORED)
1443  return 0;
1444  /* add label here only if labelangle or labeldistance is defined; else, use external label */
1445  if ((!E_labelangle || (*(la = AGXGET(e,E_labelangle)) == '\0')) &&
1446  (!E_labeldistance || (*(ld = AGXGET(e,E_labeldistance)) == '\0'))) {
1447  return 0;
1448  }
1449 
1450  l = head_p ? ED_head_label(e) : ED_tail_label(e);
1451  if ((spl = getsplinepoints(e)) == NULL) return 0;
1452  if (!head_p) {
1453  bez = &spl->list[0];
1454  if (bez->sflag) {
1455  pe = bez->sp;
1456  pf = bez->list[0];
1457  } else {
1458  pe = bez->list[0];
1459  for (i = 0; i < 4; i++)
1460  c[i] = bez->list[i];
1461  pf = Bezier(c, 3, 0.1, NULL, NULL);
1462  }
1463  } else {
1464  bez = &spl->list[spl->size - 1];
1465  if (bez->eflag) {
1466  pe = bez->ep;
1467  pf = bez->list[bez->size - 1];
1468  } else {
1469  pe = bez->list[bez->size - 1];
1470  for (i = 0; i < 4; i++)
1471  c[i] = bez->list[bez->size - 4 + i];
1472  pf = Bezier(c, 3, 0.9, NULL, NULL);
1473  }
1474  }
1475  angle = atan2(pf.y - pe.y, pf.x - pe.x) +
1477  dist = PORT_LABEL_DISTANCE * late_double(e, E_labeldistance, 1.0, 0.0);
1478  l->pos.x = pe.x + dist * cos(angle);
1479  l->pos.y = pe.y + dist * sin(angle);
1480  l->set = TRUE;
1481  return 1;
1482 }
1483 
1485 {
1486  edge_t *le;
1487  splines *sp;
1488 
1489  for (le = e; !(sp = ED_spl(le)) && ED_edge_type(le) != NORMAL;
1490  le = ED_to_orig(le));
1491  if (sp == NULL)
1492  agerr (AGERR, "getsplinepoints: no spline points available for edge (%s,%s)\n",
1493  agnameof(agtail(e)), agnameof(aghead(e)));
1494  return sp;
1495 }
1496