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