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