Graphviz  2.41.20170921.2350
compound.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 /* Module for clipping splines to cluster boxes.
16  */
17 
18 #include "dot.h"
19 
20 /* pf2s:
21  * Convert a pointf to its string representation.
22  */
23 static char *pf2s(pointf p, char *buf)
24 {
25  sprintf(buf, "(%.5g,%.5g)", p.x, p.y);
26  return buf;
27 }
28 
29 /* Return point where line segment [pp,cp] intersects
30  * the box bp. Assume cp is outside the box, and pp is
31  * on or in the box.
32  */
33 static pointf boxIntersectf(pointf pp, pointf cp, boxf * bp)
34 {
35  pointf ipp;
36  double ppx = pp.x;
37  double ppy = pp.y;
38  double cpx = cp.x;
39  double cpy = cp.y;
40  pointf ll;
41  pointf ur;
42 
43  ll = bp->LL;
44  ur = bp->UR;
45  if (cp.x < ll.x) {
46  ipp.x = ll.x;
47  ipp.y = pp.y + (int) ((ipp.x - ppx) * (ppy - cpy) / (ppx - cpx));
48  if (ipp.y >= ll.y && ipp.y <= ur.y)
49  return ipp;
50  }
51  if (cp.x > ur.x) {
52  ipp.x = ur.x;
53  ipp.y = pp.y + (int) ((ipp.x - ppx) * (ppy - cpy) / (ppx - cpx));
54  if (ipp.y >= ll.y && ipp.y <= ur.y)
55  return ipp;
56  }
57  if (cp.y < ll.y) {
58  ipp.y = ll.y;
59  ipp.x = pp.x + (int) ((ipp.y - ppy) * (ppx - cpx) / (ppy - cpy));
60  if (ipp.x >= ll.x && ipp.x <= ur.x)
61  return ipp;
62  }
63  if (cp.y > ur.y) {
64  ipp.y = ur.y;
65  ipp.x = pp.x + (int) ((ipp.y - ppy) * (ppx - cpx) / (ppy - cpy));
66  if (ipp.x >= ll.x && ipp.x <= ur.x)
67  return ipp;
68  }
69 
70  /* failure */
71  {
72  char ppbuf[100], cpbuf[100], llbuf[100], urbuf[100];
73 
74  agerr(AGERR,
75  "segment [%s,%s] does not intersect box ll=%s,ur=%s\n",
76  pf2s(pp, ppbuf), pf2s(cp, cpbuf),
77  pf2s(ll, llbuf), pf2s(ur, urbuf));
78  assert(0);
79  }
80  return ipp;
81 }
82 
83 /* inBoxf:
84  * Returns true if p is on or in box bb
85  */
86 static int inBoxf(pointf p, boxf * bb)
87 {
88  return INSIDE(p, *bb);
89 }
90 
91 /* getCluster:
92  * Returns subgraph of g with given name.
93  * Returns NULL if no name is given, or subgraph of
94  * that name does not exist.
95  */
96 static graph_t *getCluster(graph_t * g, char *cluster_name, Dt_t* map)
97 {
98  Agraph_t* sg;
99 
100  if (!cluster_name || (*cluster_name == '\0'))
101  return NULL;
102  sg = findCluster (map, cluster_name);
103  if (sg == NULL) {
104  agerr(AGWARN, "cluster named %s not found\n", cluster_name);
105  }
106  return sg;
107 }
108 
109 /* The following functions are derived from pp. 411-415 (pp. 791-795)
110  * of Graphics Gems. In the code there, they use a SGN function to
111  * count crossings. This doesn't seem to handle certain special cases,
112  * as when the last point is on the line. It certainly didn't work
113  * for us when we used int values; see bug 145. We needed to use CMP instead.
114  *
115  * Possibly unnecessary with double values, but harmless.
116  */
117 
118 /* countVertCross:
119  * Return the number of times the Bezier control polygon crosses
120  * the vertical line x = xcoord.
121  */
122 static int countVertCross(pointf * pts, double xcoord)
123 {
124  int i;
125  int sign, old_sign;
126  int num_crossings = 0;
127 
128  sign = CMP(pts[0].x, xcoord);
129  if (sign == 0)
130  num_crossings++;
131  for (i = 1; i <= 3; i++) {
132  old_sign = sign;
133  sign = CMP(pts[i].x, xcoord);
134  if ((sign != old_sign) && (old_sign != 0))
135  num_crossings++;
136  }
137  return num_crossings;
138 }
139 
140 /* countHorzCross:
141  * Return the number of times the Bezier control polygon crosses
142  * the horizontal line y = ycoord.
143  */
144 static int countHorzCross(pointf * pts, double ycoord)
145 {
146  int i;
147  int sign, old_sign;
148  int num_crossings = 0;
149 
150  sign = CMP(pts[0].y, ycoord);
151  if (sign == 0)
152  num_crossings++;
153  for (i = 1; i <= 3; i++) {
154  old_sign = sign;
155  sign = CMP(pts[i].y, ycoord);
156  if ((sign != old_sign) && (old_sign != 0))
157  num_crossings++;
158  }
159  return num_crossings;
160 }
161 
162 /* findVertical:
163  * Given 4 Bezier control points pts, corresponding to the portion
164  * of an initial spline with path parameter in the range
165  * 0.0 <= tmin <= t <= tmax <= 1.0, return t where the spline
166  * first crosses a vertical line segment
167  * [(xcoord,ymin),(xcoord,ymax)]. Return -1 if not found.
168  * This is done by binary subdivision.
169  */
170 static double
171 findVertical(pointf * pts, double tmin, double tmax,
172  double xcoord, double ymin, double ymax)
173 {
174  pointf Left[4];
175  pointf Right[4];
176  double t;
177  int no_cross;
178 
179  if (tmin == tmax)
180  return tmin;
181 
182  no_cross = countVertCross(pts, xcoord);
183  if (no_cross == 0)
184  return -1.0;
185 
186  /* if 1 crossing and on the line x == xcoord (within 0.005 point) */
187  if ((no_cross == 1) && (fabs(pts[3].x - xcoord) <= 0.005)) {
188  if ((ymin <= pts[3].y) && (pts[3].y <= ymax)) {
189  return tmax;
190  } else
191  return -1.0;
192  }
193 
194  /* split the Bezier into halves, trying the first half first. */
195  Bezier(pts, 3, 0.5, Left, Right);
196  t = findVertical(Left, tmin, (tmin + tmax) / 2.0, xcoord, ymin, ymax);
197  if (t >= 0.0)
198  return t;
199  return findVertical(Right, (tmin + tmax) / 2.0, tmax, xcoord, ymin,
200  ymax);
201 
202 }
203 
204 /* findHorizontal:
205  * Given 4 Bezier control points pts, corresponding to the portion
206  * of an initial spline with path parameter in the range
207  * 0.0 <= tmin <= t <= tmax <= 1.0, return t where the spline
208  * first crosses a horizontal line segment
209  * [(xmin,ycoord),(xmax,ycoord)]. Return -1 if not found.
210  * This is done by binary subdivision.
211  */
212 static double
213 findHorizontal(pointf * pts, double tmin, double tmax,
214  double ycoord, double xmin, double xmax)
215 {
216  pointf Left[4];
217  pointf Right[4];
218  double t;
219  int no_cross;
220 
221  if (tmin == tmax)
222  return tmin;
223 
224  no_cross = countHorzCross(pts, ycoord);
225  if (no_cross == 0)
226  return -1.0;
227 
228  /* if 1 crossing and on the line y == ycoord (within 0.005 point) */
229  if ((no_cross == 1) && (fabs(pts[3].y - ycoord) <= 0.005)) {
230  if ((xmin <= pts[3].x) && (pts[3].x <= xmax)) {
231  return tmax;
232  } else
233  return -1.0;
234  }
235 
236  /* split the Bezier into halves, trying the first half first. */
237  Bezier(pts, 3, 0.5, Left, Right);
238  t = findHorizontal(Left, tmin, (tmin + tmax) / 2.0, ycoord, xmin,
239  xmax);
240  if (t >= 0.0)
241  return t;
242  return findHorizontal(Right, (tmin + tmax) / 2.0, tmax, ycoord, xmin,
243  xmax);
244 }
245 
246 /* splineIntersectf:
247  * Given four spline control points and a box,
248  * find the shortest portion of the spline from
249  * pts[0] to the intersection with the box, if any.
250  * If an intersection is found, the four points are stored in pts[0..3]
251  * with pts[3] being on the box, and 1 is returned. Otherwise, pts
252  * is left unchanged and 0 is returned.
253  */
254 static int splineIntersectf(pointf * pts, boxf * bb)
255 {
256  double tmin = 2.0;
257  double t;
258  pointf origpts[4];
259  int i;
260 
261  for (i = 0; i < 4; i++) {
262  origpts[i] = pts[i];
263  }
264 
265  t = findVertical(pts, 0.0, 1.0, bb->LL.x, bb->LL.y, bb->UR.y);
266  if ((t >= 0) && (t < tmin)) {
267  Bezier(origpts, 3, t, pts, NULL);
268  tmin = t;
269  }
270  t = findVertical(pts, 0.0, MIN(1.0, tmin), bb->UR.x, bb->LL.y,
271  bb->UR.y);
272  if ((t >= 0) && (t < tmin)) {
273  Bezier(origpts, 3, t, pts, NULL);
274  tmin = t;
275  }
276  t = findHorizontal(pts, 0.0, MIN(1.0, tmin), bb->LL.y, bb->LL.x,
277  bb->UR.x);
278  if ((t >= 0) && (t < tmin)) {
279  Bezier(origpts, 3, t, pts, NULL);
280  tmin = t;
281  }
282  t = findHorizontal(pts, 0.0, MIN(1.0, tmin), bb->UR.y, bb->LL.x,
283  bb->UR.x);
284  if ((t >= 0) && (t < tmin)) {
285  Bezier(origpts, 3, t, pts, NULL);
286  tmin = t;
287  }
288 
289  if (tmin < 2.0) {
290  return 1;
291  } else
292  return 0;
293 }
294 
295 /* makeCompoundEdge:
296  * If edge e has a cluster head and/or cluster tail,
297  * clip spline to outside of cluster.
298  * Requirement: spline is composed of only one part,
299  * with n control points where n >= 4 and n (mod 3) = 1.
300  * If edge has arrowheads, reposition them.
301  */
302 static void makeCompoundEdge(graph_t * g, edge_t * e, Dt_t* clustMap)
303 {
304  graph_t *lh; /* cluster containing head */
305  graph_t *lt; /* cluster containing tail */
306  bezier *bez; /* original Bezier for e */
307  bezier *nbez; /* new Bezier for e */
308  int starti = 0, endi = 0; /* index of first and last control point */
309  node_t *head;
310  node_t *tail;
311  boxf *bb;
312  int i, j;
313  int size;
314  pointf pts[4];
315  pointf p;
316  int fixed;
317 
318  /* find head and tail target clusters, if defined */
319  lh = getCluster(g, agget(e, "lhead"), clustMap);
320  lt = getCluster(g, agget(e, "ltail"), clustMap);
321  if (!lt && !lh)
322  return;
323  if (!ED_spl(e)) return;
324 
325  /* at present, we only handle single spline case */
326  if (ED_spl(e)->size > 1) {
327  agerr(AGWARN, "%s -> %s: spline size > 1 not supported\n",
328  agnameof(agtail(e)), agnameof(aghead(e)));
329  return;
330  }
331  bez = ED_spl(e)->list;
332  size = bez->size;
333 
334  head = aghead(e);
335  tail = agtail(e);
336 
337  /* allocate new Bezier */
338  nbez = GNEW(bezier);
339  nbez->eflag = bez->eflag;
340  nbez->sflag = bez->sflag;
341 
342  /* if Bezier has four points, almost collinear,
343  * make line - unimplemented optimization?
344  */
345 
346  /* If head cluster defined, find first Bezier
347  * crossing head cluster, and truncate spline to
348  * box edge.
349  * Otherwise, leave end alone.
350  */
351  fixed = 0;
352  if (lh) {
353  bb = &(GD_bb(lh));
354  if (!inBoxf(ND_coord(head), bb)) {
355  agerr(AGWARN, "%s -> %s: head not inside head cluster %s\n",
356  agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "lhead"));
357  } else {
358  /* If first control point is in bb, degenerate case. Spline
359  * reduces to four points between the arrow head and the point
360  * where the segment between the first control point and arrow head
361  * crosses box.
362  */
363  if (inBoxf(bez->list[0], bb)) {
364  if (inBoxf(ND_coord(tail), bb)) {
365  agerr(AGWARN,
366  "%s -> %s: tail is inside head cluster %s\n",
367  agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "lhead"));
368  } else {
369  assert(bez->sflag); /* must be arrowhead on tail */
370  p = boxIntersectf(bez->list[0], bez->sp, bb);
371  bez->list[3] = p;
372  bez->list[1] = mid_pointf(p, bez->sp);
373  bez->list[0] = mid_pointf(bez->list[1], bez->sp);
374  bez->list[2] = mid_pointf(bez->list[1], p);
375  if (bez->eflag)
376  endi = arrowEndClip(e, bez->list,
377  starti, 0, nbez, bez->eflag);
378  endi += 3;
379  fixed = 1;
380  }
381  } else {
382  for (endi = 0; endi < size - 1; endi += 3) {
383  if (splineIntersectf(&(bez->list[endi]), bb))
384  break;
385  }
386  if (endi == size - 1) { /* no intersection */
387  assert(bez->eflag);
388  nbez->ep = boxIntersectf(bez->ep, bez->list[endi], bb);
389  } else {
390  if (bez->eflag)
391  endi =
392  arrowEndClip(e, bez->list,
393  starti, endi, nbez, bez->eflag);
394  endi += 3;
395  }
396  fixed = 1;
397  }
398  }
399  }
400  if (fixed == 0) { /* if no lh, or something went wrong, use original head */
401  endi = size - 1;
402  if (bez->eflag)
403  nbez->ep = bez->ep;
404  }
405 
406  /* If tail cluster defined, find last Bezier
407  * crossing tail cluster, and truncate spline to
408  * box edge.
409  * Otherwise, leave end alone.
410  */
411  fixed = 0;
412  if (lt) {
413  bb = &(GD_bb(lt));
414  if (!inBoxf(ND_coord(tail), bb)) {
415  agerr(AGWARN, "%s -> %s: tail not inside tail cluster %s\n",
416  agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "ltail"));
417  } else {
418  /* If last control point is in bb, degenerate case. Spline
419  * reduces to four points between arrow head, and the point
420  * where the segment between the last control point and the
421  * arrow head crosses box.
422  */
423  if (inBoxf(bez->list[endi], bb)) {
424  if (inBoxf(ND_coord(head), bb)) {
425  agerr(AGWARN,
426  "%s -> %s: head is inside tail cluster %s\n",
427  agnameof(agtail(e)), agnameof(aghead(e)), agget(e, "ltail"));
428  } else {
429  assert(bez->eflag); /* must be arrowhead on head */
430  p = boxIntersectf(bez->list[endi], nbez->ep, bb);
431  starti = endi - 3;
432  bez->list[starti] = p;
433  bez->list[starti + 2] = mid_pointf(p, nbez->ep);
434  bez->list[starti + 3] = mid_pointf(bez->list[starti + 2], nbez->ep);
435  bez->list[starti + 1] = mid_pointf(bez->list[starti + 2], p);
436  if (bez->sflag)
437  starti = arrowStartClip(e, bez->list, starti,
438  endi - 3, nbez, bez->sflag);
439  fixed = 1;
440  }
441  } else {
442  for (starti = endi; starti > 0; starti -= 3) {
443  for (i = 0; i < 4; i++)
444  pts[i] = bez->list[starti - i];
445  if (splineIntersectf(pts, bb)) {
446  for (i = 0; i < 4; i++)
447  bez->list[starti - i] = pts[i];
448  break;
449  }
450  }
451  if (starti == 0) {
452  assert(bez->sflag);
453  nbez->sp =
454  boxIntersectf(bez->sp, bez->list[starti], bb);
455  } else {
456  starti -= 3;
457  if (bez->sflag)
458  starti = arrowStartClip(e, bez->list, starti,
459  endi - 3, nbez, bez->sflag);
460  }
461  fixed = 1;
462  }
463  }
464  }
465  if (fixed == 0) { /* if no lt, or something went wrong, use original tail */
466  /* Note: starti == 0 */
467  if (bez->sflag)
468  nbez->sp = bez->sp;
469  }
470 
471  /* complete Bezier, free garbage and attach new Bezier to edge
472  */
473  nbez->size = endi - starti + 1;
474  nbez->list = N_GNEW(nbez->size, pointf);
475  for (i = 0, j = starti; i < nbez->size; i++, j++)
476  nbez->list[i] = bez->list[j];
477  free(bez->list);
478  free(bez);
479  ED_spl(e)->list = nbez;
480 }
481 #if 0
482 static void dump(Dt_t* map)
483 {
484  clust_t* p;
485  fprintf (stderr, "# in map: %d\n", dtsize(map));
486  for (p=(clust_t*)dtfirst(map);p; p = (clust_t*)dtnext(map,p)) {
487  fprintf (stderr, " %s\n", p->name);
488  }
489 }
490 #endif
491 
492 /* dot_compoundEdges:
493  */
495 {
496  edge_t *e;
497  node_t *n;
498  Dt_t* clustMap = mkClustMap (g);
499  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
500  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
501  makeCompoundEdge(g, e, clustMap);
502  }
503  }
504  dtclose(clustMap);
505 }
Definition: cgraph.h:388
CDT_API int dtclose(Dt_t *)
int eflag
Definition: types.h:112
double xmax
Definition: geometry.c:20
Dt_t * mkClustMap(Agraph_t *g)
Definition: utils.c:2064
int size
Definition: types.h:110
#define head
Definition: dthdr.h:19
#define MIN(a, b)
Definition: arith.h:35
#define assert(x)
Definition: cghdr.h:47
Definition: geom.h:28
#define dtfirst(d)
Definition: cdt.h:254
char * name
Definition: utils.c:2015
double xmin
Definition: geometry.c:20
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
double ymax
Definition: geometry.c:20
int arrowEndClip(edge_t *e, pointf *ps, int startp, int endp, bezier *spl, int eflag)
Definition: arrows.c:256
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
double ymin
Definition: geometry.c:20
Definition: cgraph.h:388
char * agget(void *obj, char *name)
Definition: attr.c:428
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
int
Definition: grammar.c:1264
#define ED_spl(e)
Definition: types.h:598
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
double y
Definition: geom.h:28
int sflag
Definition: types.h:111
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define dtnext(d, o)
Definition: cdt.h:255
pointf sp
Definition: types.h:113
pointf * list
Definition: types.h:109
CDT_API int dtsize(Dt_t *)
Definition: dtsize.c:12
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
if(aagss+aagstacksize-1<=aagssp)
Definition: grammar.c:1332
pointf ep
Definition: types.h:114
pointf Bezier(pointf *V, int degree, double t, pointf *Left, pointf *Right)
Definition: utils.c:221
Agraph_t * findCluster(Dt_t *map, char *name)
Definition: utils.c:2074
#define NULL
Definition: logic.h:39
#define GNEW(t)
Definition: memory.h:37
double x
Definition: geom.h:28
#define CMP(a, b)
Definition: arith.h:49
#define ND_coord(n)
Definition: types.h:496
Definition: types.h:108
void dot_compoundEdges(graph_t *g)
Definition: compound.c:494
pointf LL
Definition: geom.h:35
#define INSIDE(p, b)
Definition: geom.h:39
Definition: cdt.h:99
#define GD_bb(g)
Definition: types.h:357
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
pointf UR
Definition: geom.h:35
Definition: geom.h:35
#define N_GNEW(n, t)
Definition: agxbuf.c:20
int arrowStartClip(edge_t *e, pointf *ps, int startp, int endp, bezier *spl, int sflag)
Definition: arrows.c:285