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