![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag_spline.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / dag|
Return to dag_spline.c CVS log | Up to [Research Unix] / researchv10no / cmd / dag |
1.1 root 1: #include "draw_dag.h"
2:
3: #include <sys/types.h>
4: #include <sys/times.h>
5: #define TIC 60
6:
7: // local storage for building splines
8: static const int max_cntrl_pts = 3;
9: static Point *Pt;
10: static int Pt_size;
11: static int N_points;
12:
13: static void addpoint(Point p)
14: {
15: if(!Pt || N_points >= Pt_size)
16: {
17: /*
18: extern Point *realloc(...), *malloc(...);
19: */
20: if(Pt)
21: {
22: Pt_size += 4;
23: /*
24: Pt = realloc(Pt,Pt_size*sizeof(Pt[0]));
25: */
26: Pt = (Point *)realloc((char *)Pt,Pt_size*sizeof(Pt[0]));
27: }
28: else
29: {
30: Pt_size = (Maxlevel+2)*max_cntrl_pts+1;
31: Pt = new Point[Pt_size];
32: }
33: if(!Pt)
34: panic("out of memory");
35: }
36:
37: Pt[N_points].x = p.x;
38: Pt[N_points].y = p.y;
39: N_points++;
40: }
41:
42:
43: // copy the contructed spline points
44: static Point *copypoints()
45: {
46: Point *pt = new Point[N_points];
47: for(int n = 0; n < N_points; ++n)
48: {
49: pt[n].x = Pt[n].x;
50: pt[n].y = Pt[n].y;
51: }
52: return pt;
53: }
54:
55:
56: // see if a straight edge can be drawn for a flat edge
57: static int straightedge(int v, edge_t *e)
58: {
59: int w = e->node;
60: int left = Invert[v], right = Invert[w], node = v;
61: if(left > right)
62: {
63: swap(left,right);
64: node = w;
65: }
66:
67: // if the left hand side node has a self edge, it can't be done
68: for(edge_t *f = Noedges[node]; f; f = f->next)
69: if(f->node == node)
70: return 0;
71:
72: // if there is an intervening real node, it can't be done
73: int *rank = Rank[Level[v]];
74: for(left += 1; left < right; ++left)
75: if(rank[left] < N_real_nodes)
76: return 0;
77:
78: // if there is not enough separation to draw an edge
79: if(iabs(Nodepos[v]-Nodepos[w])-(Width[v]+Width[w])/2 <
80: max(Levelsep/2,Levelsep-Nodesep))
81: return 0;
82:
83: // see if there is an opposite edge
84: int has_opposite = 0;
85: for(f = Noedges[w]; f; f = f->next)
86: if(f->node == v)
87: {
88: has_opposite = 1;
89: break;
90: }
91:
92: Point p0, p1;
93: p0.y = p1.y = Levelpos[Level[v]];
94: p0.x = Nodepos[v] + (Invert[v] < Invert[w] ? 1 : -1)*Width[v]/2;
95: p1.x = Nodepos[w] + (Invert[w] < Invert[v] ? 1 : -1)*Width[w]/2;
96: addpoint(p0);
97: if(has_opposite)
98: {
99: Point mid;
100: mid.x = (p0.x+p1.x)/2;
101: mid.y = p0.y + (e->weight > 0 ? -1 : 1)*(e->width+Nodesep)/2;
102: addpoint(mid);
103: }
104: addpoint(p1);
105:
106: p0.x = p0.y = -1;
107: addpoint(p0);
108:
109: e->splinept = copypoints();
110: return 1;
111: }
112:
113:
114:
115: // make splines for flat edges.
116: // Here we compute a circle arc that joins v and w and has an appropriate
117: // height, then use a few points on it to define the spline control points.
118: static void flatedge(int v, edge_t *e)
119: {
120: N_points = 0;
121:
122: // see if we can draw a straight line
123: if(straightedge(v,e))
124: return;
125:
126: // half the distance between v and w
127: int w = e->node;
128: double r = fabs((Nodepos[v]-Nodepos[w])/2.);
129:
130: // the height of the point half way between v and w
131: double h = Levelsep/3.;
132:
133: // the height of the point 1/4 of the way between v and w
134: // extern double sqrt(double);
135: double h4 = (h*h - r*r + sqrt((r*r + h*h)*(r*r + h*h) - r*r*h*h))/(2*h);
136:
137: int level = Level[v];
138: Point p0, p1, p2, p3, p4;
139: p0.x = Nodepos[v];
140: p1.x = (3*Nodepos[v] + Nodepos[w])/4;
141: p2.x = (Nodepos[v] + Nodepos[w])/2;
142: p3.x = (Nodepos[v] + 3*Nodepos[w])/4;
143: p4.x = Nodepos[w];
144: if(e->weight > 0)
145: {
146: p0.y = Levelpos[level] - Height[v]/2;
147: p1.y = (int)(Levelpos[level] - Levelheight[level]/2. - h4);
148: p2.y = (int)(Levelpos[level] - Levelheight[level]/2. - h);
149: p3.y = p1.y;
150: p4.y = Levelpos[level] - Height[w]/2;
151: }
152: else
153: {
154: p0.y = Levelpos[level] + Height[v]/2;
155: p1.y = (int)(Levelpos[level] + Levelheight[level]/2. + h4);
156: p2.y = (int)(Levelpos[level] + Levelheight[level]/2. + h);
157: p3.y = p1.y;
158: p4.y = Levelpos[level] + Height[w]/2;
159: }
160:
161: addpoint(p0);
162: addpoint(p1);
163: addpoint(p2);
164: addpoint(p3);
165: addpoint(p4);
166: p0.x = p0.y = -1;
167: addpoint(p0);
168:
169: e->splinept = copypoints();
170: }
171:
172:
173:
174: // spline for self edges
175: static void selfedge(int v, edge_t *e)
176: {
177: N_points = 0;
178:
179: Point p0, p1, p2, p3, p4;
180: p0.x = Nodepos[v]+Width[v]/2;
181: p0.y = Levelpos[Level[v]] - Height[v]/8;
182: p2.x = p0.x + Nodesep + e->width/2;
183: p2.y = Levelpos[Level[v]];
184: p1.x = (p2.x + p0.x)/2;
185: p1.y = p0.y - Nodesep/4 - e->width/4;
186: p4.x = Nodepos[v]+Width[v]/2;
187: p4.y = Levelpos[Level[v]] + Height[v]/8;
188: p3.x = p1.x;
189: p3.y = p4.y + Nodesep/4 + e->width/4;
190:
191: addpoint(p0);
192: addpoint(p1);
193: addpoint(p2);
194: addpoint(p3);
195: addpoint(p4);
196:
197: p0.x = p0.y = -1;
198: addpoint(p0);
199:
200: e->splinept = copypoints();
201: }
202:
203:
204: // compute a line aiming from v to w and confined to the box
205: // defined by 'tl' and 'br'.
206: // The line is guaranteed not to hit any adjacent boxes.
207: // Line equation is defined as x = my + b instead of y = mx + b to avoid
208: // the problem of infinite slopes with vertical lines.
209:
210: static int defineline(Point v, Point w, Point tl, Point br,
211: int thisnode, double &m, double &b)
212: {
213: // horizontal line
214: if(v.y == w.y)
215: {
216: m = HUGE;
217: return 0;
218: }
219:
220: // 1 if the defined ray meets w.
221: // -1 if ray doesnot meet w because of a parallel edge
222: // 0 if ray doesnot meet w because of intersection with nodes
223: int meet = 1;
224:
225: // the ray that aims at w
226: m = (v.x - w.x) / ((double)(v.y - w.y));
227: b = v.x - m*v.y;
228:
229: edge_t *e = v.y < w.y ? Inedges[thisnode] : Outedges[thisnode];
230: int ewidth = e->width/2;
231:
232: int dir = v.x < w.x ? -1 : 1;
233: int level = Level[thisnode];
234: int level_y = Levelpos[level];
235: int *rank = Rank[level];
236: for(int i = Invert[thisnode]+dir; i >= 0 && rank[i] >= 0; i += dir)
237: {
238: if(m == 0.)
239: break;
240:
241: int node = rank[i];
242: int x = Nodepos[node], y;
243:
244: // out of relevant bound
245: if((dir < 0 && x < v.x) || (dir > 0 && x > v.x))
246: break;
247:
248: if(node >= N_real_nodes)
249: {
250: // see if there is a parallel edge
251: if(v.y < w.y)
252: {
253: int ix = Nodepos[Inedges[node]->node];
254: if((ix-v.x)*(x-w.x) < 0)
255: continue;
256: }
257: else
258: {
259: int ox = Nodepos[Outedges[node]->node];
260: if((ox-v.x)*(x-w.x) < 0)
261: continue;
262: }
263: }
264:
265: int height = Height[node]/2 + max(1,min(Levelsep/4,Height[node]/4));
266:
267: x += dir < 0 ? Width[node]/2 : -Width[node]/2;
268: y = (int)(((x + (dir < 0 ? ewidth : -ewidth)) - b)/m);
269:
270: if((v.y < w.y && y < level_y-height) ||
271: (v.y > w.y && y > level_y+height))
272: continue;
273:
274: if(thisnode >= N_real_nodes && Outedges[thisnode]->count > 1)
275: {
276: w.y = v.y < w.y ? tl.y : br.y;
277: if(v.y == w.y)
278: break;
279: m = (v.x - w.x) / ((double)(v.y - w.y));
280: b = v.x - m*v.y;
281: break;
282: }
283:
284: if(node >= N_real_nodes)
285: {
286: y = v.y < w.y ? level_y-height : level_y+height;
287: if(meet == 1)
288: meet = -1;
289: }
290: else
291: {
292: // the line from v to w-corner
293: Point p;
294: p.x = v.x < w.x ? tl.x : br.x;
295: p.y = v.y > w.y ? br.y : tl.y;
296: if(v.y == p.y)
297: break;
298: m = (v.x - p.x) / ((double)(v.y - p.y));
299: b = v.x - m*v.y;
300: if(m == 0.)
301: break;
302:
303: y = (int)((x - b)/m);
304:
305: if(v.y > w.y)
306: {
307: int a_y = level_y+height;
308: y = p.y < a_y ? a_y : min(y,a_y);
309: }
310: else
311: {
312: int a_y = level_y-height;
313: y = p.y > a_y ? a_y : max(y,a_y);
314: }
315:
316: meet = 0;
317: }
318:
319: if(v.y == y)
320: break;
321: m = (v.x - x) / ((double)(v.y - y));
322: b = v.x - m*v.y;
323: }
324:
325: return meet;
326: }
327:
328:
329: // compute the point where a line enters a box.
330: static void lineXbox(Point v,int n,double m,double b,Point tl,Point br,Point &i)
331: {
332: // center line of the box
333: int mid_x = Nodepos[n];
334:
335: // try the top or bottom edge
336: i.y = v.y < tl.y ? tl.y : br.y;
337: i.x = m == HUGE ? mid_x : (int)(m*i.y + b + .5);
338: if(m == HUGE)
339: return;
340:
341: // miss the box, try the sides
342: if(i.x < tl.x-1 || i.x > br.x+1)
343: {
344: i.x = v.x < mid_x ? tl.x : br.x;
345: i.y = m == 0. ? (v.y < tl.y ? tl.y : br.y) : (int)((i.x - b)/m + .5);
346: }
347:
348: // still miss it
349: if(i.y > br.y+1 || i.y < tl.y-1 ||
350: (v.x < mid_x-1 && i.x > mid_x+1) ||
351: (v.x > mid_x+1 && i.x < mid_x-1))
352: {
353: if(v.x < mid_x)
354: {
355: if(Invert[n] > 0)
356: {
357: int a = Rank[Level[n]][Invert[n]-1];
358: int x = max(v.x,Nodepos[a]+Width[a]/2);
359: i.x = (x + tl.x + 1)/2;
360: }
361: else i.x = tl.x;
362: }
363: else
364: {
365: int a = Rank[Level[n]][Invert[n]+1];
366: if(a >= 0)
367: {
368: int x = min(v.x,Nodepos[a]-Width[a]/2);
369: i.x = (x + br.x + 1)/2;
370: }
371: else i.x = br.x;
372: }
373:
374: i.y = m == 0. ? (v.y < tl.y ? tl.y : br.y) : (int)((i.x - b)/m + .5);
375: }
376: }
377:
378:
379:
380: // see if a line cross a self edge
381: static int lineXselfedge(int v, Point nextpt, double &m, double &b, int &right_y)
382: {
383: if(N_self_edges <= 0 || m == 0. || m == HUGE)
384: return 0;
385: for(edge_t *e = Noedges[v]; e; e = e->next)
386: if(e->node == v)
387: break;
388: if(!e)
389: return 0;
390:
391: // location of the lowest point of self-edge
392: int self_x = Nodepos[v] + Width[v]/2 + Nodesep/2;
393: if(nextpt.x <= self_x)
394: return 0;
395: int self_y = Levelpos[Level[v]];
396: if(nextpt.y > self_y)
397: {
398: self_y += Height[v]/8 + Nodesep/4 + e->width/2 + Height[v]/16;
399: self_y = min(self_y,Levelpos[Level[v]]+Height[v]/2);
400: }
401: else
402: {
403: self_y -= Height[v]/8 + Nodesep/4 + e->width/2 + Height[v]/16;
404: self_y = max(self_y,Levelpos[Level[v]]-Height[v]/2);
405: }
406:
407: int y = (int)((self_x - b)/m);
408: if((nextpt.y > self_y && y >= self_y) ||
409: (nextpt.y < self_y && y <= self_y))
410: return 0;
411:
412: // compute the line that goes to self_x, self_y
413: m = ((double)(nextpt.x-self_x))/(nextpt.y-self_y);
414: b = self_x - m*self_y;
415:
416: // find where it intersects the middle of the box
417: y = (int)((Nodepos[v]-b)/m);
418:
419: if(nextpt.y > self_y)
420: right_y = max(right_y,y);
421: else right_y = min(right_y,y);
422:
423: return 1;
424: }
425:
426:
427: // compute the down part of a spline
428: static void downspline(int v, edge_t *edge, int &left_y, int &right_y)
429: {
430: N_points = 0;
431:
432: Point thispt, lastpt, nextpt, // the points to spline thru
433: tl, br, // box containing thispt
434: top_i, bot_i; // intersections with box
435: double m, b; // line equation coeffs
436:
437: int level = Level[v];
438: edge_t *e = edge;
439: thispt.x = Nodepos[v];
440: thispt.y = Levelpos[level];
441: nextpt.x = Nodepos[e->node];
442: nextpt.y = Levelpos[level+1] - Height[e->node]/2;
443:
444: // box containing v to be aimed at from below
445: tl.x = thispt.x - Width[v]/2;
446: tl.y = thispt.y - Height[v]/2;
447: br.x = thispt.x + Width[v]/2;
448: br.y = thispt.y + Height[v]/2;
449:
450: // the point to be aimed at
451: if(nextpt.x < thispt.x)
452: thispt.y = max(left_y,thispt.y);
453: else if(nextpt.x > thispt.x)
454: thispt.y = max(right_y,thispt.y);
455:
456: defineline(nextpt,thispt,tl,br,v,m,b);
457: if(lineXselfedge(v,nextpt,m,b,right_y))
458: thispt.y = max(right_y,thispt.y);
459: br.y = Levelpos[level] + Height[v]/2;
460: lineXbox(nextpt,v,m,b,tl,br,top_i);
461:
462: // if outside of the actual bounding box of v
463: if(top_i.y > br.y+1)
464: {
465: thispt.y = br.y;
466: defineline(top_i,thispt,tl,br,v,m,b);
467: lineXbox(top_i,v,m,b,tl,br,thispt);
468: addpoint(thispt);
469: if(nextpt.x < thispt.x)
470: left_y = br.y;
471: else if(nextpt.x > thispt.x)
472: right_y = br.y;
473: }
474: else
475: {
476: // compute the intersection with the vertical line thru v
477: int y = m == 0. ? br.y : (int)((thispt.x - b)/m);
478: if(nextpt.x < thispt.x)
479: left_y = max(y,left_y);
480: else if(nextpt.x > thispt.x)
481: right_y = max(y,right_y);
482: }
483:
484: addpoint(top_i);
485: lastpt.x = top_i.x;
486: lastpt.y = top_i.y;
487:
488: // loop thru all virtual nodes
489: int did_virtual = 0;
490: for(; e->chain; e = e->chain)
491: {
492: int thisnode = e->node;
493: if(Deleted[thisnode])
494: continue;
495:
496: level = Level[thisnode];
497: thispt.x = Nodepos[thisnode];
498: thispt.y = Levelpos[level];
499:
500: for(edge_t *f = e->chain; f; f = f->chain)
501: if(f->node < N_real_nodes || !Deleted[f->node])
502: break;
503: int nextnode = f->node;
504: nextpt.x = Nodepos[nextnode];
505: nextpt.y = Levelpos[Level[nextnode]] - Height[nextnode]/2;
506:
507: // top and bottom corners of the box containing this node.
508: int box_h = Height[thisnode];
509: int box_w = Width[thisnode] + Nodesep/2;
510: tl.y = thispt.y - box_h/2;
511: tl.x = thispt.x - box_w/2;
512: br.y = thispt.y + box_h/2;
513: br.x = thispt.x + box_w/2;
514:
515: // define the top/bot rays by aiming them at the box center.
516: double top_m, top_b, bot_m, bot_b;
517: int top_meet, bot_meet;
518: top_meet = defineline(lastpt,thispt,tl,br,thisnode,top_m,top_b);
519: bot_meet = defineline(nextpt,thispt,tl,br,thisnode,bot_m,bot_b);
520:
521: // these are identical lines!
522: if(top_m == bot_m && top_b == bot_b)
523: continue;
524:
525: // so we know that some spline points was outputed
526: did_virtual = 1;
527:
528: // increase box size if possible to smooth spline turns
529: int *rank = Rank[level];
530: int i = Invert[thisnode];
531: int l = i > 0 ? rank[i-1] : -1;
532: int r = rank[i+1];
533: int lx = l >= 0 ? Nodepos[l]+Width[l]/2+Nodesep : -1;
534: int rx = r >= 0 ? Nodepos[r]-Width[r]/2-Nodesep : -1;
535: if(lastpt.x < lx && nextpt.x > rx)
536: tl.x = min((lx+tl.x)/2,tl.x);
537: if(lastpt.x > rx && nextpt.x < lx)
538: br.x = max((rx+br.x)/2,br.x);
539:
540: if(lx >= 0)
541: lx -= Nodesep;
542: if(rx >= 0)
543: rx += Nodesep;
544:
545: // points where the lines enter the box
546: Point mid;
547: lineXbox(lastpt,thisnode,top_m,top_b,tl,br,top_i);
548: lineXbox(nextpt,thisnode,bot_m,bot_b,tl,br,bot_i);
549:
550: // horizontal line
551: if(top_m == HUGE || bot_m == HUGE)
552: {
553: addpoint(top_i);
554: addpoint(bot_i);
555: continue;
556: }
557:
558: if(top_m != bot_m || top_m == 0. || bot_m == 0.)
559: {
560: Point line_i;
561: line_i.y = (int)((bot_b - top_b)/(top_m - bot_m));
562: line_i.x = (int)(top_m*line_i.y + top_b);
563:
564: // see if the lines intersect inside the box
565: if(top_m == 0. || bot_m == 0. ||
566: (line_i.x >= tl.x-1 && line_i.x <= br.x+1))
567: {
568: // add spline point to avoid node intersection
569: mid.x = lastpt.x < thispt.x ? lx : rx;
570: if((!top_meet || top_i.y < tl.y-1) &&
571: top_m != 0. && mid.x >= 0)
572: {
573: mid.y = (int)((mid.x-top_b)/top_m+.5);
574: addpoint(mid);
575: }
576: addpoint(top_i);
577: mid.y = (top_i.y+bot_i.y+1)/2;
578: mid.x = (top_i.x+bot_i.x+1)/2;
579: addpoint(mid);
580: addpoint(bot_i);
581: mid.x = nextpt.x < thispt.x ? lx : rx;
582: if((!bot_meet || bot_i.y > br.y+1) &&
583: bot_m != 0. && mid.x >= 0)
584: {
585: mid.y = (int)((mid.x-bot_b)/bot_m+.5);
586: addpoint(mid);
587: bot_i.x = mid.x;
588: bot_i.y = mid.y;
589: }
590:
591: lastpt.x = bot_i.x;
592: lastpt.y = bot_i.y;
593: continue;
594: }
595:
596: // the intersection is outside the box.
597: // See if the two lines come from the same side
598: if((lastpt.x - thispt.x)*(nextpt.x - thispt.x) >= 0)
599: {
600: // boundaries of immediate neighbors;
601: // we don't want to overshoot them!
602: int adj, min_x, max_x;
603: adj = Invert[thisnode] <= 0 ? -1 :
604: Rank[level][Invert[thisnode]-1];
605: min_x = adj < 0 ? 0 :
606: Nodepos[adj]+(Width[adj]+Nodesep)/2;
607: adj = Rank[level][Invert[thisnode]+1];
608: max_x = adj < 0 ? Maxint :
609: Nodepos[adj]-(Width[adj]+Nodesep)/2;
610:
611: // find the points close to the intersection pt
612: // and use their midpoint to make the turn smooth
613: int x, top_y, bot_y;
614: if(line_i.x > min_x && line_i.x < max_x)
615: if(line_i.x < tl.x)
616: x = (line_i.x + tl.x)/2;
617: else x = (line_i.x + br.x)/2;
618: else if(line_i.x < tl.x)
619: x = (min_x + tl.x)/2;
620: else x = (max_x + br.x)/2;
621:
622: top_y = (int)((x - top_b)/top_m);
623: bot_y = (int)((x - bot_b)/bot_m);
624:
625: mid.x = x;
626: mid.y = (top_y + bot_y + 1)/2;
627:
628: addpoint(top_i);
629: addpoint(mid);
630: addpoint(bot_i);
631:
632: lastpt.x = bot_i.x;
633: lastpt.y = bot_i.y;
634: continue;
635: }
636: }
637:
638: // here we have lines that come from different sides
639: // of the box and intersect outside it.
640: // Move these lines as close to each other as possible.
641: int meet;
642: mid.x = thispt.x;
643: mid.y = (int)((mid.x - bot_b)/bot_m);
644: meet = defineline(lastpt,mid,tl,br,thisnode,top_m,top_b);
645: if(meet <= 0)
646: {
647: mid.y = (int)((mid.x - top_b)/top_m);
648: defineline(nextpt,mid,tl,br,thisnode,bot_m,bot_b);
649: }
650: lineXbox(lastpt,thisnode,top_m,top_b,tl,br,top_i);
651: lineXbox(nextpt,thisnode,bot_m,bot_b,tl,br,bot_i);
652:
653: addpoint(top_i);
654: mid.x = (top_i.x + bot_i.x + 1)/2;
655: mid.y = (top_i.y + bot_i.y + 1)/2;
656: addpoint(mid);
657: addpoint(bot_i);
658:
659: lastpt.x = bot_i.x;
660: lastpt.y = bot_i.y;
661: }
662:
663: // so in upspline we'll know whether a spline point was output */
664: thispt.y = did_virtual;
665:
666: thispt.x = -1;
667: addpoint(thispt);
668:
669: edge->splinept = copypoints();
670: }
671:
672:
673:
674: // now do the down end point of a spline
675: static void upspline(int w, edge_t *e, int &left_y, int &right_y)
676: {
677: N_points = 0;
678:
679: // find the corresponding Outedge
680: while(e->node >= N_real_nodes)
681: e = e->chain;
682: e = e->link;
683:
684: // current spline control points and their number
685: Point *spline = e->splinept;
686: for(int n_points = 0; spline[n_points].x >= 0; ++n_points)
687: ;
688:
689: Point lastpt, thispt, tl, br;
690:
691: // define the lastpt before routing to w
692: lastpt.y = spline[n_points-1].y;
693: lastpt.x = spline[n_points-1].x;
694:
695: // now define the point aiming to and the box around it
696: int level = Level[w];
697: thispt.x = Nodepos[w];
698: thispt.y = Levelpos[level];
699: tl.x = thispt.x - Width[w]/2;
700: tl.y = thispt.y - Height[w]/2;
701: br.x = thispt.x + Width[w]/2;
702: br.y = thispt.y + Height[w]/2;
703: if(lastpt.x < thispt.x)
704: thispt.y = min(left_y,thispt.y);
705: else if(lastpt.x > thispt.x)
706: thispt.y = min(right_y,thispt.y);
707:
708: Point i;
709: double m, b;
710: defineline(lastpt,thispt,tl,br,w,m,b);
711: if(lineXselfedge(w,lastpt,m,b,right_y))
712: thispt.y = min(right_y,thispt.y);
713: lineXbox(lastpt,w,m,b,tl,br,i);
714:
715: // see if a mid point is needed
716: // note that spline[n_points].y contains the info on
717: // whether a spline point had been output
718: if(e->count > 1 && spline[n_points].y == 0)
719: {
720: Point mid;
721: mid.x = (i.x+lastpt.x + 1)/2;
722: mid.y = (i.y+lastpt.y + 1)/2;
723: addpoint(mid);
724: }
725:
726: // the intersection is outside the bounding box
727: // add a few points to route it to the box
728: if(i.y < tl.y-1)
729: {
730: if(lastpt.x < thispt.x)
731: left_y = tl.y;
732: else if(lastpt.x > thispt.x)
733: right_y = tl.y;
734:
735: thispt.y = tl.y;
736: defineline(i,thispt,tl,br,w,m,b);
737: lineXbox(i,w,m,b,tl,br,thispt);
738: addpoint(i);
739: addpoint(thispt);
740: }
741: else
742: {
743: // compute the intersection with the vertical line thru w
744: int y = m == 0. ? thispt.y : (int)((thispt.x-b)/m);
745: if(lastpt.x < thispt.x)
746: left_y = min(y,left_y);
747: else if(lastpt.x > thispt.x)
748: right_y = min(y,right_y);
749:
750: addpoint(i);
751: }
752:
753: // extern Point *realloc(...);
754: spline = (Point *)realloc((char *)spline,(n_points+N_points+1)*sizeof(spline[0]));
755:
756: // copy new points back in
757: e->splinept = spline;
758: spline += n_points;
759: for(int n = 0; n < N_points; ++n, ++spline)
760: {
761: spline->x = Pt[n].x;
762: spline->y = Pt[n].y;
763: }
764: spline->x = spline->y = -1;
765: }
766:
767:
768:
769: // Given two nodes on the same rank, count how many edges
770: // go into the space between them.
771: static int between(int v, int w, edge_t **edges)
772: {
773: int *rank = Rank[Level[v]];
774: if((w = Invert[w]) < (v = Invert[v]))
775: swap(v,w);
776:
777: int count = 0;
778: for(v += 1; v < w; v++)
779: for(edge_t *e = edges[rank[v]]; e; e = e->next)
780: count += e->count;
781: return count;
782: }
783:
784:
785:
786: // partition flat edges below/above the rank to avoid edge crossings
787: static void assignside()
788: {
789: for(int i = 0; i <= Maxlevel; ++i)
790: {
791: int side = 1;
792: for(int *node = Rank[i]; *node != -1; ++node)
793: {
794: int v = *node;
795: if(v >= N_real_nodes)
796: continue;
797:
798: for(edge_t *e = Noedges[v]; e; e = e->next)
799: {
800: if(e->weight != 0)
801: continue;
802:
803: int w = e->node;
804: if (w >= N_real_nodes)
805: continue;
806:
807: // self edge
808: if(v == w)
809: continue;
810:
811: // see if there is an opposite edge and
812: // process it at the same time
813: for(edge_t *f = Noedges[w]; f; f = f->next)
814: if(f->node == v)
815: break;
816:
817: // calculate # of intersections from top or bot
818: int top_i = between(v,w,Inedges);
819: int bot_i = between(v,w,Outedges);
820: if(top_i-bot_i != 0)
821: {
822: if(!f || f->count < e->count)
823: e->weight = top_i < bot_i ? 1 : -1;
824: else e->weight = top_i > bot_i ? 1 : -1;
825: }
826: else e->weight = side;
827:
828: if(f)
829: f->weight = -e->weight;
830: else side = e->weight;
831: }
832: }
833: }
834: }
835:
836:
837: // dag_spline itself
838: static int adjcmp(edge_t **e1, edge_t **e2)
839: {
840: return Invert[(*e1)->node]-Invert[(*e2)->node];
841: }
842:
843: static void setmargins() {
844: // reset the margin
845: int xmax = 0, ymax = 0;
846: int leftmargin = 0;
847: int topmargin = Levelheight[0]/2;
848: int rightmargin, bottommargin;
849: int v;
850: for(int i = 0; i <= Maxlevel; i++)
851: leftmargin = max(leftmargin,Width[Rank[i][0]]);
852: leftmargin = (leftmargin+1)/2;
853: for(v = 0; v < N_nodes; ++v)
854: Nodepos[v] += leftmargin;
855:
856: /* here we adjust the node placement to fit user's desired aspect ratio */
857: if ((Xbound > 0) && (Ybound > 0)) {
858: for(v = 0; v < N_nodes; ++v) {
859: int w2 = (Width[v] + 1) / 2;
860: int h2 = (Height[v] + 1) / 2;
861: if (xmax < Nodepos[v] + w2) {
862: xmax = Nodepos[v] + w2;
863: rightmargin = w2;
864: }
865: if (ymax < Levelpos[Level[v]] + h2) {
866: ymax = Levelpos[Level[v]] + h2;
867: bottommargin = h2;
868: }
869: }
870: switch ((Xbound < xmax) + 2 * (!!(Ybound < ymax))) {
871: case 0:
872: break;
873: case 1:
874: Ybound = (int)(Ybound * (double)xmax/(double)Xbound);
875: Xbound = xmax;
876: break;
877: case 2:
878: Xbound = (int)(Xbound * (double)ymax/(double)Ybound);
879: Ybound = ymax;
880: break;
881: case 3:
882: double request_ratio = (double)Xbound/ (double)Ybound;
883: double actual_ratio = (double)xmax/ (double)ymax;
884: if (actual_ratio < request_ratio) {
885: Ybound = ymax;
886: Xbound = (int)(Ybound * request_ratio);
887: }
888: else {
889: Xbound = xmax;
890: Ybound = (int)(Xbound / request_ratio);
891: }
892: break;
893: }
894:
895: if ((xmax < Xbound) && (xmax > (rightmargin + leftmargin))) {
896: double t1 = Xbound - rightmargin - leftmargin;
897: double t2 = xmax - rightmargin - leftmargin;
898: double xstretch = t1 / t2;
899: for (int v = 0; v < N_nodes; ++v)
900: Nodepos[v] = (int)(leftmargin + (Nodepos[v] - leftmargin) * xstretch);
901: }
902: if ((ymax < Ybound) && (Maxlevel > 1)) {
903: double ystretch = ((double)Ybound - topmargin - bottommargin)/((double)ymax - topmargin - bottommargin);
904: for (int lev = 1; lev <= Maxlevel; lev++)
905: Levelpos[lev] = (int)(topmargin + ((Levelpos[lev] - topmargin) * ystretch));
906: }
907: }
908: }
909:
910: void dag_spline()
911: {
912: struct tms begtm, endtm;
913: if(Verbose)
914: {
915: #ifndef TIMING
916: fprintf(stderr,"Making splines\n");
917: #endif
918: times(&begtm);
919: }
920:
921: // reset margins, scale picture
922: setmargins();
923:
924: // make splines for flat and self edges
925: if(Noedges)
926: {
927: assignside();
928:
929: for(int v = 0; v < N_real_nodes; ++v)
930: for(edge_t *e = Noedges[v]; e; e = e->next)
931: if(e->node == v)
932: selfedge(v,e);
933: else flatedge(v,e);
934: }
935:
936: // space to sort edges
937: edge_t **edges = new edge_t*[N_nodes];
938:
939: // compute splines for cross-level edges
940: for(int v = 0; v < N_real_nodes; v++)
941: {
942: // these tell where we can aim without causing crossings
943: int left_y = Levelpos[Level[v]], right_y = left_y;
944:
945: // make a sorted list of adjacent forward edges
946: int n_forward = 0;
947: for(edge_t *e = Outedges[v]; e; e = e->next)
948: edges[n_forward++] = e;
949: if(n_forward >= 2)
950: qsort((char*)edges,n_forward,sizeof(edges[0]),(qsortcmpfun)adjcmp);
951:
952: // initialize the places in v that we can aim at
953: left_y = Levelpos[Level[v]];
954: right_y = left_y;
955:
956: for(int n = 0, m = n_forward-1; n <= m;)
957: {
958: if(Nodepos[edges[n]->node] <= Nodepos[v])
959: downspline(v,edges[n++],left_y,right_y);
960: if(m >= n && Nodepos[edges[m]->node] > Nodepos[v])
961: downspline(v,edges[m--],left_y,right_y);
962: }
963: }
964:
965: // fix up the down end-points of edges so they won't intersect
966: for(v = 0; v < N_real_nodes; ++v)
967: {
968: int n_forward = 0;
969: for(edge_t *e = Inedges[v]; e; e = e->next)
970: edges[n_forward++] = e;
971: if(n_forward >= 2)
972: qsort((char*)edges,n_forward,sizeof(edges[0]),(qsortcmpfun)adjcmp);
973:
974: // initialize the places in v that we can aim at
975: int left_y = Levelpos[Level[v]], right_y;
976: right_y = left_y;
977:
978: for(int n = 0, m = n_forward-1; n <= m;)
979: {
980: if(Nodepos[edges[n]->node] <= Nodepos[v])
981: upspline(v,edges[n++],left_y,right_y);
982: if(m >= n && Nodepos[edges[m]->node] > Nodepos[v])
983: upspline(v,edges[m--],left_y,right_y);
984: }
985: }
986: delete edges;
987:
988: if(Verbose)
989: {
990: times(&endtm);
991: int total = (endtm.tms_utime-begtm.tms_utime) +
992: (endtm.tms_stime-begtm.tms_stime);
993: int percent = (total - (total/TIC)*TIC)*100/TIC;
994: #ifdef TIMING
995: fprintf(stderr,"%d.%02d\t",total/TIC,percent);
996: #else
997: fprintf(stderr,"Time in making splines: %d.%02ds\n",
998: total/TIC, percent);
999: #endif
1000: }
1001: }
1002:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.