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