Return to dag_spline.c CVS log

Up to [Research Unix] / researchv10dc / cmd / dag

Annotation of researchv10dc/cmd/dag/dag_spline.c, revision 1.1

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.