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#include "render.h"
16
17#define EPSILON .0001
18
19/* standard arrow length in points */
20#define ARROW_LENGTH 10.
21
22#define NUMB_OF_ARROW_HEADS 4
23/* each arrow in 8 bits. Room for NUMB_OF_ARROW_HEADS arrows in 32 bit int. */
24
25#define BITS_PER_ARROW 8
26
27#define BITS_PER_ARROW_TYPE 4
28/* arrow types (in BITS_PER_ARROW_TYPE bits) */
29#define ARR_TYPE_NONE (ARR_NONE)
30#define ARR_TYPE_NORM 1
31#define ARR_TYPE_CROW 2
32#define ARR_TYPE_TEE 3
33#define ARR_TYPE_BOX 4
34#define ARR_TYPE_DIAMOND 5
35#define ARR_TYPE_DOT 6
36#define ARR_TYPE_CURVE 7
37#define ARR_TYPE_GAP 8
38/* Spare: 9-15 */
39
40/* arrow mods (in (BITS_PER_ARROW - BITS_PER_ARROW_TYPE) bits) */
41#define ARR_MOD_OPEN (1<<(BITS_PER_ARROW_TYPE+0))
42#define ARR_MOD_INV (1<<(BITS_PER_ARROW_TYPE+1))
43#define ARR_MOD_LEFT (1<<(BITS_PER_ARROW_TYPE+2))
44#define ARR_MOD_RIGHT (1<<(BITS_PER_ARROW_TYPE+3))
45/* No spares */
46
47typedef struct arrowdir_t {
48 char *dir;
49 int sflag;
50 int eflag;
51} arrowdir_t;
52
53static arrowdir_t Arrowdirs[] = {
54 {"forward", ARR_TYPE_NONE, ARR_TYPE_NORM},
55 {"back", ARR_TYPE_NORM, ARR_TYPE_NONE},
56 {"both", ARR_TYPE_NORM, ARR_TYPE_NORM},
57 {"none", ARR_TYPE_NONE, ARR_TYPE_NONE},
58 {(char *) 0, ARR_TYPE_NONE, ARR_TYPE_NONE}
59};
60
61typedef struct arrowname_t {
62 char *name;
63 int type;
64} arrowname_t;
65
66static arrowname_t Arrowsynonyms[] = {
67 /* synonyms for deprecated arrow names - included for backward compatibility */
68 /* evaluated before primary names else "invempty" would give different results */
69 {"invempty", (ARR_TYPE_NORM | ARR_MOD_INV | ARR_MOD_OPEN)}, /* oinv */
70 {(char *) 0, (ARR_TYPE_NONE)}
71};
72
73static arrowname_t Arrowmods[] = {
74 {"o", ARR_MOD_OPEN},
75 {"r", ARR_MOD_RIGHT},
76 {"l", ARR_MOD_LEFT},
77 /* deprecated alternates for backward compat */
78 {"e", ARR_MOD_OPEN}, /* o - needed for "ediamond" */
79 {"half", ARR_MOD_LEFT}, /* l - needed for "halfopen" */
80 {(char *) 0, ARR_TYPE_NONE}
81};
82
83static arrowname_t Arrownames[] = {
84 {"normal", ARR_TYPE_NORM},
85 {"crow", ARR_TYPE_CROW},
86 {"tee", ARR_TYPE_TEE},
87 {"box", ARR_TYPE_BOX},
88 {"diamond", ARR_TYPE_DIAMOND},
89 {"dot", ARR_TYPE_DOT},
90// {"none", ARR_TYPE_NONE},
91 {"none", ARR_TYPE_GAP},
92// {"gap", ARR_TYPE_GAP},
93 /* ARR_MOD_INV is used only here to define two additional shapes
94 since not all types can use it */
95 {"inv", (ARR_TYPE_NORM | ARR_MOD_INV)},
96 {"vee", (ARR_TYPE_CROW | ARR_MOD_INV)},
97 /* WARNING ugly kludge to deal with "o" v "open" conflict */
98 /* Define "open" as just "pen" since "o" already taken as ARR_MOD_OPEN */
99 /* Note that ARR_MOD_OPEN has no meaning for ARR_TYPE_CROW shape */
100 {"pen", (ARR_TYPE_CROW | ARR_MOD_INV)},
101 /* WARNING ugly kludge to deal with "e" v "empty" conflict */
102 /* Define "empty" as just "mpty" since "e" already taken as ARR_MOD_OPEN */
103 /* Note that ARR_MOD_OPEN has expected meaning for ARR_TYPE_NORM shape */
104 {"mpty", ARR_TYPE_NORM},
105 {"curve", ARR_TYPE_CURVE},
106 {"icurve", (ARR_TYPE_CURVE | ARR_MOD_INV)},
107 {(char *) 0, ARR_TYPE_NONE}
108};
109
110typedef struct arrowtype_t {
111 int type;
112 double lenfact; /* ratio of length of this arrow type to standard arrow */
113 void (*gen) (GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag); /* generator function for type */
114} arrowtype_t;
115
116/* forward declaration of functions used in Arrowtypes[] */
117static void arrow_type_normal(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
118static void arrow_type_crow(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
119static void arrow_type_tee(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
120static void arrow_type_box(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
121static void arrow_type_diamond(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
122static void arrow_type_dot(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
123static void arrow_type_curve(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
124static void arrow_type_gap(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag);
125
126static arrowtype_t Arrowtypes[] = {
127 {ARR_TYPE_NORM, 1.0, arrow_type_normal},
128 {ARR_TYPE_CROW, 1.0, arrow_type_crow},
129 {ARR_TYPE_TEE, 0.5, arrow_type_tee},
130 {ARR_TYPE_BOX, 1.0, arrow_type_box},
131 {ARR_TYPE_DIAMOND, 1.2, arrow_type_diamond},
132 {ARR_TYPE_DOT, 0.8, arrow_type_dot},
133 {ARR_TYPE_CURVE, 1.0, arrow_type_curve},
134 {ARR_TYPE_GAP, 0.5, arrow_type_gap},
135 {ARR_TYPE_NONE, 0.0, NULL}
136};
137
138static char *arrow_match_name_frag(char *name, arrowname_t * arrownames, int *flag)
139{
140 arrowname_t *arrowname;
141 size_t namelen = 0;
142 char *rest = name;
143
144 for (arrowname = arrownames; arrowname->name; arrowname++) {
145 namelen = strlen(arrowname->name);
146 if (strncmp(name, arrowname->name, namelen) == 0) {
147 *flag |= arrowname->type;
148 rest += namelen;
149 break;
150 }
151 }
152 return rest;
153}
154
155static char *arrow_match_shape(char *name, int *flag)
156{
157 char *next, *rest;
158 int f = ARR_TYPE_NONE;
159
160 rest = arrow_match_name_frag(name, Arrowsynonyms, &f);
161 if (rest == name) {
162 do {
163 next = rest;
164 rest = arrow_match_name_frag(next, Arrowmods, &f);
165 } while (next != rest);
166 rest = arrow_match_name_frag(rest, Arrownames, &f);
167 }
168 if (f && !(f & ((1 << BITS_PER_ARROW_TYPE) - 1)))
169 f |= ARR_TYPE_NORM;
170 *flag |= f;
171 return rest;
172}
173
174static void arrow_match_name(char *name, int *flag)
175{
176 char *rest = name;
177 char *next;
178 int i, f;
179
180 *flag = 0;
181 for (i = 0; *rest != '\0' && i < NUMB_OF_ARROW_HEADS; ) {
182 f = ARR_TYPE_NONE;
183 next = rest;
184 rest = arrow_match_shape(next, &f);
185 if (f == ARR_TYPE_NONE) {
186 agerr(AGWARN, "Arrow type \"%s\" unknown - ignoring\n", next);
187 return;
188 }
189 if (f == ARR_TYPE_GAP && i == (NUMB_OF_ARROW_HEADS -1))
190 f = ARR_TYPE_NONE;
191 if ((f == ARR_TYPE_GAP) && (i == 0) && (*rest == '\0'))
192 f = ARR_TYPE_NONE;
193 if (f != ARR_TYPE_NONE)
194 *flag |= (f << (i++ * BITS_PER_ARROW));
195 }
196}
197
198void arrow_flags(Agedge_t * e, int *sflag, int *eflag)
199{
200 char *attr;
201 arrowdir_t *arrowdir;
202
203 *sflag = ARR_TYPE_NONE;
204 *eflag = agisdirected(agraphof(e)) ? ARR_TYPE_NORM : ARR_TYPE_NONE;
205 if (E_dir && ((attr = agxget(e, E_dir)))[0]) {
206 for (arrowdir = Arrowdirs; arrowdir->dir; arrowdir++) {
207 if (streq(attr, arrowdir->dir)) {
208 *sflag = arrowdir->sflag;
209 *eflag = arrowdir->eflag;
210 break;
211 }
212 }
213 }
214 if (E_arrowhead && (*eflag == ARR_TYPE_NORM) && ((attr = agxget(e, E_arrowhead)))[0])
215 arrow_match_name(attr, eflag);
216 if (E_arrowtail && (*sflag == ARR_TYPE_NORM) && ((attr = agxget(e, E_arrowtail)))[0])
217 arrow_match_name(attr, sflag);
218 if (ED_conc_opp_flag(e)) {
219 edge_t *f;
220 int s0, e0;
221 /* pick up arrowhead of opposing edge */
222 f = agfindedge(agraphof(aghead(e)), aghead(e), agtail(e));
223 arrow_flags(f, &s0, &e0);
224 *eflag = *eflag | s0;
225 *sflag = *sflag | e0;
226 }
227}
228
229double arrow_length(edge_t * e, int flag)
230{
231 arrowtype_t *arrowtype;
232 double lenfact = 0.0;
233 int f, i;
234
235 for (i = 0; i < NUMB_OF_ARROW_HEADS; i++) {
236 /* we don't simply index with flag because arrowtypes are not necessarily sorted */
237 f = (flag >> (i * BITS_PER_ARROW)) & ((1 << BITS_PER_ARROW_TYPE) - 1);
238 for (arrowtype = Arrowtypes; arrowtype->gen; arrowtype++) {
239 if (f == arrowtype->type) {
240 lenfact += arrowtype->lenfact;
241 break;
242 }
243 }
244 }
245 /* The original was missing the factor E_arrowsz, but I believe it
246 should be here for correct arrow clipping */
247 return ARROW_LENGTH * lenfact * late_double(e, E_arrowsz, 1.0, 0.0);
248}
249
250/* inside function for calls to bezier_clip */
251static boolean inside(inside_t * inside_context, pointf p)
252{
253 return DIST2(p, inside_context->a.p[0]) <= inside_context->a.r[0];
254}
255
256int arrowEndClip(edge_t* e, pointf * ps, int startp,
257 int endp, bezier * spl, int eflag)
258{
259 inside_t inside_context;
260 pointf sp[4];
261 double elen, elen2;
262
263 elen = arrow_length(e, eflag);
264 elen2 = elen * elen;
265 spl->eflag = eflag, spl->ep = ps[endp + 3];
266 if (endp > startp && DIST2(ps[endp], ps[endp + 3]) < elen2) {
267 endp -= 3;
268 }
269 sp[3] = ps[endp];
270 sp[2] = ps[endp + 1];
271 sp[1] = ps[endp + 2];
272 sp[0] = spl->ep; /* ensure endpoint starts inside */
273
274 inside_context.a.p = &sp[0];
275 inside_context.a.r = &elen2;
276 bezier_clip(&inside_context, inside, sp, TRUE);
277
278 ps[endp] = sp[3];
279 ps[endp + 1] = sp[2];
280 ps[endp + 2] = sp[1];
281 ps[endp + 3] = sp[0];
282 return endp;
283}
284
285int arrowStartClip(edge_t* e, pointf * ps, int startp,
286 int endp, bezier * spl, int sflag)
287{
288 inside_t inside_context;
289 pointf sp[4];
290 double slen, slen2;
291
292 slen = arrow_length(e, sflag);
293 slen2 = slen * slen;
294 spl->sflag = sflag, spl->sp = ps[startp];
295 if (endp > startp && DIST2(ps[startp], ps[startp + 3]) < slen2) {
296 startp += 3;
297 }
298 sp[0] = ps[startp + 3];
299 sp[1] = ps[startp + 2];
300 sp[2] = ps[startp + 1];
301 sp[3] = spl->sp; /* ensure endpoint starts inside */
302
303 inside_context.a.p = &sp[3];
304 inside_context.a.r = &slen2;
305 bezier_clip(&inside_context, inside, sp, FALSE);
306
307 ps[startp] = sp[3];
308 ps[startp + 1] = sp[2];
309 ps[startp + 2] = sp[1];
310 ps[startp + 3] = sp[0];
311 return startp;
312}
313
314/* arrowOrthoClip:
315 * For orthogonal routing, we know each Bezier of spl is a horizontal or vertical
316 * line segment. We need to guarantee the B-spline stays this way. At present, we shrink
317 * the arrows if necessary to fit the last segment at either end. Alternatively, we could
318 * maintain the arrow size by dropping the 3 points of spl, and adding a new spl encoding
319 * the arrow, something "ex_0,y_0 x_1,y_1 x_1,y_1 x_1,y_1 x_1,y_1", when the last line
320 * segment is x_1,y_1 x_2,y_2 x_3,y_3 x_0,y_0. With a good deal more work, we could guarantee
321 * that the truncated spl clips to the arrow shape.
322 */
323void arrowOrthoClip(edge_t* e, pointf* ps, int startp, int endp, bezier* spl, int sflag, int eflag)
324{
325 pointf p, q, r, s, t;
326 double d, tlen, hlen, maxd;
327
328 if (sflag && eflag && (endp == startp)) { /* handle special case of two arrows on a single segment */
329 p = ps[endp];
330 q = ps[endp+3];
331 tlen = arrow_length (e, sflag);
332 hlen = arrow_length (e, eflag);
333 d = DIST(p, q);
334 if (hlen + tlen >= d) {
335 hlen = tlen = d/3.0;
336 }
337 if (p.y == q.y) { /* horz segment */
338 s.y = t.y = p.y;
339 if (p.x < q.x) {
340 t.x = q.x - hlen;
341 s.x = p.x + tlen;
342 }
343 else {
344 t.x = q.x + hlen;
345 s.x = p.x - tlen;
346 }
347 }
348 else { /* vert segment */
349 s.x = t.x = p.x;
350 if (p.y < q.y) {
351 t.y = q.y - hlen;
352 s.y = p.y + tlen;
353 }
354 else {
355 t.y = q.y + hlen;
356 s.y = p.y - tlen;
357 }
358 }
359 ps[endp] = ps[endp + 1] = s;
360 ps[endp + 2] = ps[endp + 3] = t;
361 spl->eflag = eflag, spl->ep = p;
362 spl->sflag = sflag, spl->sp = q;
363 return;
364 }
365 if (eflag) {
366 hlen = arrow_length(e, eflag);
367 p = ps[endp];
368 q = ps[endp+3];
369 d = DIST(p, q);
370 maxd = 0.9*d;
371 if (hlen >= maxd) { /* arrow too long */
372 hlen = maxd;
373 }
374 if (p.y == q.y) { /* horz segment */
375 r.y = p.y;
376 if (p.x < q.x) r.x = q.x - hlen;
377 else r.x = q.x + hlen;
378 }
379 else { /* vert segment */
380 r.x = p.x;
381 if (p.y < q.y) r.y = q.y - hlen;
382 else r.y = q.y + hlen;
383 }
384 ps[endp + 1] = p;
385 ps[endp + 2] = ps[endp + 3] = r;
386 spl->eflag = eflag;
387 spl->ep = q;
388 }
389 if (sflag) {
390 tlen = arrow_length(e, sflag);
391 p = ps[startp];
392 q = ps[startp+3];
393 d = DIST(p, q);
394 maxd = 0.9*d;
395 if (tlen >= maxd) { /* arrow too long */
396 tlen = maxd;
397 }
398 if (p.y == q.y) { /* horz segment */
399 r.y = p.y;
400 if (p.x < q.x) r.x = p.x + tlen;
401 else r.x = p.x - tlen;
402 }
403 else { /* vert segment */
404 r.x = p.x;
405 if (p.y < q.y) r.y = p.y + tlen;
406 else r.y = p.y - tlen;
407 }
408 ps[startp] = ps[startp + 1] = r;
409 ps[startp + 2] = q;
410 spl->sflag = sflag;
411 spl->sp = p;
412 }
413}
414
415static void arrow_type_normal(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
416{
417 pointf q, v, a[5];
418 double arrowwidth;
419
420 arrowwidth = 0.35;
421 if (penwidth > 4)
422 arrowwidth *= penwidth / 4;
423
424 v.x = -u.y * arrowwidth;
425 v.y = u.x * arrowwidth;
426 q.x = p.x + u.x;
427 q.y = p.y + u.y;
428 if (flag & ARR_MOD_INV) {
429 a[0] = a[4] = p;
430 a[1].x = p.x - v.x;
431 a[1].y = p.y - v.y;
432 a[2] = q;
433 a[3].x = p.x + v.x;
434 a[3].y = p.y + v.y;
435 } else {
436 a[0] = a[4] = q;
437 a[1].x = q.x - v.x;
438 a[1].y = q.y - v.y;
439 a[2] = p;
440 a[3].x = q.x + v.x;
441 a[3].y = q.y + v.y;
442 }
443 if (flag & ARR_MOD_LEFT)
444 gvrender_polygon(job, a, 3, !(flag & ARR_MOD_OPEN));
445 else if (flag & ARR_MOD_RIGHT)
446 gvrender_polygon(job, &a[2], 3, !(flag & ARR_MOD_OPEN));
447 else
448 gvrender_polygon(job, &a[1], 3, !(flag & ARR_MOD_OPEN));
449}
450
451static void arrow_type_crow(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
452{
453 pointf m, q, v, w, a[9];
454 double arrowwidth, shaftwidth;
455
456 arrowwidth = 0.45;
457 if (penwidth > (4 * arrowsize) && (flag & ARR_MOD_INV))
458 arrowwidth *= penwidth / (4 * arrowsize);
459
460 shaftwidth = 0;
461 if (penwidth > 1 && (flag & ARR_MOD_INV))
462 shaftwidth = 0.05 * (penwidth - 1) / arrowsize; /* arrowsize to cancel the arrowsize term already in u */
463
464 v.x = -u.y * arrowwidth;
465 v.y = u.x * arrowwidth;
466 w.x = -u.y * shaftwidth;
467 w.y = u.x * shaftwidth;
468 q.x = p.x + u.x;
469 q.y = p.y + u.y;
470 m.x = p.x + u.x * 0.5;
471 m.y = p.y + u.y * 0.5;
472 if (flag & ARR_MOD_INV) { /* vee */
473 a[0] = a[8] = p;
474 a[1].x = q.x - v.x;
475 a[1].y = q.y - v.y;
476 a[2].x = m.x - w.x;
477 a[2].y = m.y - w.y;
478 a[3].x = q.x - w.x;
479 a[3].y = q.y - w.y;
480 a[4] = q;
481 a[5].x = q.x + w.x;
482 a[5].y = q.y + w.y;
483 a[6].x = m.x + w.x;
484 a[6].y = m.y + w.y;
485 a[7].x = q.x + v.x;
486 a[7].y = q.y + v.y;
487 } else { /* crow */
488 a[0] = a[8] = q;
489 a[1].x = p.x - v.x;
490 a[1].y = p.y - v.y;
491 a[2].x = m.x - w.x;
492 a[2].y = m.y - w.y;
493 a[3].x = p.x;
494 a[3].y = p.y;
495 a[4] = p;
496 a[5].x = p.x;
497 a[5].y = p.y;
498 a[6].x = m.x + w.x;
499 a[6].y = m.y + w.y;
500 a[7].x = p.x + v.x;
501 a[7].y = p.y + v.y;
502 }
503 if (flag & ARR_MOD_LEFT)
504 gvrender_polygon(job, a, 6, 1);
505 else if (flag & ARR_MOD_RIGHT)
506 gvrender_polygon(job, &a[3], 6, 1);
507 else
508 gvrender_polygon(job, a, 9, 1);
509}
510
511static void arrow_type_gap(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
512{
513 pointf q, a[2];
514
515 q.x = p.x + u.x;
516 q.y = p.y + u.y;
517 a[0] = p;
518 a[1] = q;
519 gvrender_polyline(job, a, 2);
520}
521
522static void arrow_type_tee(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
523{
524 pointf m, n, q, v, a[4];
525
526 v.x = -u.y;
527 v.y = u.x;
528 q.x = p.x + u.x;
529 q.y = p.y + u.y;
530 m.x = p.x + u.x * 0.2;
531 m.y = p.y + u.y * 0.2;
532 n.x = p.x + u.x * 0.6;
533 n.y = p.y + u.y * 0.6;
534 a[0].x = m.x + v.x;
535 a[0].y = m.y + v.y;
536 a[1].x = m.x - v.x;
537 a[1].y = m.y - v.y;
538 a[2].x = n.x - v.x;
539 a[2].y = n.y - v.y;
540 a[3].x = n.x + v.x;
541 a[3].y = n.y + v.y;
542 if (flag & ARR_MOD_LEFT) {
543 a[0] = m;
544 a[3] = n;
545 } else if (flag & ARR_MOD_RIGHT) {
546 a[1] = m;
547 a[2] = n;
548 }
549 gvrender_polygon(job, a, 4, 1);
550 a[0] = p;
551 a[1] = q;
552 gvrender_polyline(job, a, 2);
553}
554
555static void arrow_type_box(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
556{
557 pointf m, q, v, a[4];
558
559 v.x = -u.y * 0.4;
560 v.y = u.x * 0.4;
561 m.x = p.x + u.x * 0.8;
562 m.y = p.y + u.y * 0.8;
563 q.x = p.x + u.x;
564 q.y = p.y + u.y;
565 a[0].x = p.x + v.x;
566 a[0].y = p.y + v.y;
567 a[1].x = p.x - v.x;
568 a[1].y = p.y - v.y;
569 a[2].x = m.x - v.x;
570 a[2].y = m.y - v.y;
571 a[3].x = m.x + v.x;
572 a[3].y = m.y + v.y;
573 if (flag & ARR_MOD_LEFT) {
574 a[0] = p;
575 a[3] = m;
576 } else if (flag & ARR_MOD_RIGHT) {
577 a[1] = p;
578 a[2] = m;
579 }
580 gvrender_polygon(job, a, 4, !(flag & ARR_MOD_OPEN));
581 a[0] = m;
582 a[1] = q;
583 gvrender_polyline(job, a, 2);
584}
585
586static void arrow_type_diamond(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
587{
588 pointf q, r, v, a[5];
589
590 v.x = -u.y / 3.;
591 v.y = u.x / 3.;
592 r.x = p.x + u.x / 2.;
593 r.y = p.y + u.y / 2.;
594 q.x = p.x + u.x;
595 q.y = p.y + u.y;
596 a[0] = a[4] = q;
597 a[1].x = r.x + v.x;
598 a[1].y = r.y + v.y;
599 a[2] = p;
600 a[3].x = r.x - v.x;
601 a[3].y = r.y - v.y;
602 if (flag & ARR_MOD_LEFT)
603 gvrender_polygon(job, &a[2], 3, !(flag & ARR_MOD_OPEN));
604 else if (flag & ARR_MOD_RIGHT)
605 gvrender_polygon(job, a, 3, !(flag & ARR_MOD_OPEN));
606 else
607 gvrender_polygon(job, a, 4, !(flag & ARR_MOD_OPEN));
608}
609
610static void arrow_type_dot(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
611{
612 double r;
613 pointf AF[2];
614
615 r = sqrt(u.x * u.x + u.y * u.y) / 2.;
616 AF[0].x = p.x + u.x / 2. - r;
617 AF[0].y = p.y + u.y / 2. - r;
618 AF[1].x = p.x + u.x / 2. + r;
619 AF[1].y = p.y + u.y / 2. + r;
620 gvrender_ellipse(job, AF, 2, !(flag & ARR_MOD_OPEN));
621}
622
623
624/* Draw a concave semicircle using a single cubic bezier curve that touches p at its midpoint.
625 * See http://digerati-illuminatus.blogspot.com.au/2008/05/approximating-semicircle-with-cubic.html for details.
626 */
627static void arrow_type_curve(GVJ_t* job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
628{
629 double arrowwidth = penwidth > 4 ? 0.5 * penwidth / 4 : 0.5;
630 pointf q, v, w;
631 pointf AF[4], a[2];
632
633 q.x = p.x + u.x;
634 q.y = p.y + u.y;
635 v.x = -u.y * arrowwidth;
636 v.y = u.x * arrowwidth;
637 w.x = v.y; // same direction as u, same magnitude as v.
638 w.y = -v.x;
639 a[0] = p;
640 a[1] = q;
641
642 AF[0].x = p.x + v.x + w.x;
643 AF[0].y = p.y + v.y + w.y;
644
645 AF[3].x = p.x - v.x + w.x;
646 AF[3].y = p.y - v.y + w.y;
647
648 if (flag & ARR_MOD_INV) { /* ----(-| */
649 AF[1].x = p.x + 0.95 * v.x + w.x + w.x * 4.0 / 3.0;
650 AF[1].y = AF[0].y + w.y * 4.0 / 3.0;
651
652 AF[2].x = p.x - 0.95 * v.x + w.x + w.x * 4.0 / 3.0;
653 AF[2].y = AF[3].y + w.y * 4.0 / 3.0;
654 }
655 else { /* ----)-| */
656 AF[1].x = p.x + 0.95 * v.x + w.x - w.x * 4.0 / 3.0;
657 AF[1].y = AF[0].y - w.y * 4.0 / 3.0;
658
659 AF[2].x = p.x - 0.95 * v.x + w.x - w.x * 4.0 / 3.0;
660 AF[2].y = AF[3].y - w.y * 4.0 / 3.0;
661 }
662
663 gvrender_polyline(job, a, 2);
664 if (flag & ARR_MOD_LEFT)
665 Bezier(AF, 3, 0.5, NULL, AF);
666 else if (flag & ARR_MOD_RIGHT)
667 Bezier(AF, 3, 0.5, AF, NULL);
668 gvrender_beziercurve(job, AF, sizeof(AF) / sizeof(pointf), FALSE, FALSE, FALSE);
669}
670
671
672static pointf arrow_gen_type(GVJ_t * job, pointf p, pointf u, double arrowsize, double penwidth, int flag)
673{
674 int f;
675 arrowtype_t *arrowtype;
676
677 f = flag & ((1 << BITS_PER_ARROW_TYPE) - 1);
678 for (arrowtype = Arrowtypes; arrowtype->type; arrowtype++) {
679 if (f == arrowtype->type) {
680 u.x *= arrowtype->lenfact * arrowsize;
681 u.y *= arrowtype->lenfact * arrowsize;
682 (arrowtype->gen) (job, p, u, arrowsize, penwidth, flag);
683 p.x = p.x + u.x;
684 p.y = p.y + u.y;
685 break;
686 }
687 }
688 return p;
689}
690
691boxf arrow_bb(pointf p, pointf u, double arrowsize, int flag)
692{
693 double s;
694 boxf bb;
695 double ax,ay,bx,by,cx,cy,dx,dy;
696 double ux2, uy2;
697
698 /* generate arrowhead vector */
699 u.x -= p.x;
700 u.y -= p.y;
701 /* the EPSILONs are to keep this stable as length of u approaches 0.0 */
702 s = ARROW_LENGTH * arrowsize / (sqrt(u.x * u.x + u.y * u.y) + EPSILON);
703 u.x += (u.x >= 0.0) ? EPSILON : -EPSILON;
704 u.y += (u.y >= 0.0) ? EPSILON : -EPSILON;
705 u.x *= s;
706 u.y *= s;
707
708 /* compute all 4 corners of rotated arrowhead bounding box */
709 ux2 = u.x / 2.;
710 uy2 = u.y / 2.;
711 ax = p.x - uy2;
712 ay = p.y - ux2;
713 bx = p.x + uy2;
714 by = p.y + ux2;
715 cx = ax + u.x;
716 cy = ay + u.y;
717 dx = bx + u.x;
718 dy = by + u.y;
719
720 /* compute a right bb */
721 bb.UR.x = MAX(ax, MAX(bx, MAX(cx, dx)));
722 bb.UR.y = MAX(ay, MAX(by, MAX(cy, dy)));
723 bb.LL.x = MIN(ax, MIN(bx, MIN(cx, dx)));
724 bb.LL.y = MIN(ay, MIN(by, MIN(cy, dy)));
725
726 return bb;
727}
728
729void arrow_gen(GVJ_t * job, emit_state_t emit_state, pointf p, pointf u, double arrowsize, double penwidth, int flag)
730{
731 obj_state_t *obj = job->obj;
732 double s;
733 int i, f;
734 emit_state_t old_emit_state;
735
736 old_emit_state = obj->emit_state;
737 obj->emit_state = emit_state;
738
739 /* Dotted and dashed styles on the arrowhead are ugly (dds) */
740 /* linewidth needs to be reset */
741 gvrender_set_style(job, job->gvc->defaultlinestyle);
742
743 gvrender_set_penwidth(job, penwidth);
744
745 /* generate arrowhead vector */
746 u.x -= p.x;
747 u.y -= p.y;
748 /* the EPSILONs are to keep this stable as length of u approaches 0.0 */
749 s = ARROW_LENGTH / (sqrt(u.x * u.x + u.y * u.y) + EPSILON);
750 u.x += (u.x >= 0.0) ? EPSILON : -EPSILON;
751 u.y += (u.y >= 0.0) ? EPSILON : -EPSILON;
752 u.x *= s;
753 u.y *= s;
754
755 /* the first arrow head - closest to node */
756 for (i = 0; i < NUMB_OF_ARROW_HEADS; i++) {
757 f = (flag >> (i * BITS_PER_ARROW)) & ((1 << BITS_PER_ARROW) - 1);
758 if (f == ARR_TYPE_NONE)
759 break;
760 p = arrow_gen_type(job, p, u, arrowsize, penwidth, f);
761 }
762
763 obj->emit_state = old_emit_state;
764}
765