Return to circle.c CVS log

Up to [Research Unix] / researchv9 / jtools / src / sunlib

Annotation of researchv9/jtools/src/sunlib/circle.c, revision 1.1

1.1     ! root        1: 
        !             2: #include "jerq.h"
        !             3: 
        !             4: /*     jerq routines: circle, disc, ellipse, eldisc, arc       */
        !             5: 
        !             6: /*     circle:
        !             7:        Form a circle of radius r centered at x1,y1
        !             8:        The boundary is a sequence of vertically, horizontally,
        !             9:        or diagonally adjacent points that minimize 
        !            10:        abs(x^2+y^2-r^2).
        !            11:        The circle is guaranteed to be symmetric about
        !            12:        the horizontal, vertical, and diagonal axes
        !            13:  */
        !            14: circle (b, p, r, f)
        !            15: Bitmap *b;
        !            16: Point p;
        !            17: {
        !            18:        int x1=p.x;
        !            19:        register y1 = p.y;
        !            20:        register eps = 0;       /* x^2 + y^2 - r^2 */
        !            21:        register dxsq = 1;      /* (x+dx)^2-x^2*/
        !            22:        register dysq = 1 - 2*r;
        !            23:        register exy;
        !            24:        int x0 = x1;
        !            25:        register y0 = y1 - r;
        !            26:        y1 += r;
        !            27:        initpoints(b, f);
        !            28:        if(f == F_XOR){         /* endpoints coincide */
        !            29:                points(Pt(x0,y0));
        !            30:                points(Pt(x0,y1));
        !            31:        }
        !            32:        while(y1 > y0){
        !            33:                points(Pt(x0,y0));
        !            34:                points(Pt(x0,y1));
        !            35:                points(Pt(x1,y0));
        !            36:                points(Pt(x1,y1));
        !            37:                exy = eps + dxsq + dysq;
        !            38:                if(-exy <= eps + dxsq){
        !            39:                        y1--;
        !            40:                        y0++;
        !            41:                        eps += dysq;
        !            42:                        dysq += 2;
        !            43:                }
        !            44:                if(exy <= -eps){
        !            45:                        x1++;
        !            46:                        x0--;
        !            47:                        eps += dxsq;
        !            48:                        dxsq += 2;
        !            49:                }
        !            50:        }
        !            51:        points(Pt(x0,y0));
        !            52:        points(Pt(x1,y0));
        !            53:        endpoints();
        !            54: }
        !            55: 
        !            56: /*     Fill a disc of radius r centered at x1,y1
        !            57:        The boundary is a sequence of vertically, horizontally,
        !            58:        or diagonally adjacent points that minimize 
        !            59:        abs(x^2+y^2-r^2).
        !            60:        The circle is guaranteed to be symmetric about
        !            61:        the horizontal, vertical, and diagonal axes
        !            62: */
        !            63: disc (b, p, r, f)
        !            64: Bitmap *b;
        !            65: Point p;
        !            66: int r;
        !            67: int f;
        !            68: {
        !            69:        register x1, y1;
        !            70:        register eps = 0;               /* x^2 + y^2 - r^2 */
        !            71:        int dxsq = 1;                   /* (x+dx)^2-x^2 */
        !            72:        int dysq = 1 - 2 * r;
        !            73:        int exy;
        !            74:        register x0;
        !            75:        register y0;
        !            76: 
        !            77:        if(b->flag & BI_OFFSCREEN)
        !            78:                p = sub(p, b->rect.origin);
        !            79:        x1 = p.x;
        !            80:        y1 = p.y;
        !            81:        x0 = x1;
        !            82:        y0 = y1 - r;
        !            83:        x1++;                   /* to offset jerq's half-open lines */
        !            84:        y1 += r;
        !            85:        while(y1 > y0){
        !            86:                exy = eps + dxsq + dysq;
        !            87:                if(-exy <= eps + dxsq){
        !            88:                        rectf(b, Rect(x0, y0, x1, y0+1), f);
        !            89:                        rectf(b, Rect(x0, y1, x1, y1+1), f);
        !            90:                        y1--;
        !            91:                        y0++;
        !            92:                        eps += dysq;
        !            93:                        dysq += 2;
        !            94:                }
        !            95:                if(exy <= -eps){
        !            96:                        x1++;
        !            97:                        x0--;
        !            98:                        eps += dxsq;
        !            99:                        dxsq += 2;
        !           100:                }
        !           101:        }
        !           102:        rectf(b, Rect(x0, y0, x1, y0+1), f);
        !           103: }
        !           104: 
        !           105: /*     arc:
        !           106:        draw an approximate arc centered at x0,y0 of an
        !           107:        integer grid and running anti-clockwise from
        !           108:        x1,y1 to the vicinity of x2,y2.
        !           109:        If the endpoints coincide, draw a complete circle.
        !           110:        The "arc" is a sequence of vertically, horizontally,
        !           111:        or diagonally adjacent points that minimize 
        !           112:        abs(x^2+y^2-r^2).
        !           113:        The circle is guaranteed to be symmetric about
        !           114:        the horizontal, vertical, and diagonal axes
        !           115: */
        !           116: #define sq(x)          ((long)(x)*(x))
        !           117: #define        sgn(x)          ((x) < 0 ? -1 : (x)==0 ? 0 : 1)
        !           118: #define mabs(x)        (x < 0 ? -x : x)
        !           119: 
        !           120: static
        !           121: Point
        !           122: nearby (p1, p2)                /* called by arc()      */
        !           123: Point p1, p2;
        !           124: {
        !           125:        long eps, exy;  /*integers but many bits*/
        !           126:        int d;
        !           127:        register dy;
        !           128:        register dx;
        !           129:        register x1 = p1.x;
        !           130:        register y1 = p1.y;
        !           131:        register x2 = p2.x;
        !           132:        register y2 = p2.y;
        !           133:        eps = sq(x2) + sq(y2) - sq(x1) - sq(y1);
        !           134:        d = eps>0? -1: 1;
        !           135:        for( ; ; eps=exy, x2+=dx, y2+=dy){
        !           136:                if(abs(y2) > abs(x2)){
        !           137:                        dy = d*sgn(y2);
        !           138:                        dx = 0;
        !           139:                }
        !           140:                else{
        !           141:                        dy = 0;
        !           142:                        dx = d*sgn(x2);
        !           143:                        if(dx==0)
        !           144:                                dx = 1;
        !           145:                }
        !           146:                exy = eps + (2*x2+dx)*dx + (2*y2+dy)*dy;
        !           147:                if(mabs(eps) <= mabs(exy))
        !           148:                        break;
        !           149:        }
        !           150:        p2.x = x2;
        !           151:        p2.y = y2;
        !           152:        return(p2);
        !           153: }
        !           154: 
        !           155: arc (bp, p0, p2, p1, f)
        !           156: register Bitmap *bp;
        !           157: Point p0, p1, p2;
        !           158: {
        !           159:        register dx, dy;
        !           160:        register eps;   /* x^2 + y^2 - r^2 */
        !           161:        int dxsq, dysq; /* (x+dx)^2-x^2, ...*/
        !           162:        int ex, ey, exy;
        !           163:        p1 = sub(p1, p0);
        !           164:        p2 = sub(p2, p0);
        !           165:        p2 = nearby(p1, p2);
        !           166:        dx = -sgn(p1.y);        /* y1==0 is soon fixed */
        !           167:        dy = sgn(p1.x);
        !           168:        dxsq = (2*p1.x + dx)*dx;
        !           169:        dysq = (2*p1.y + dy)*dy;
        !           170:        eps = 0;
        !           171:        initpoints(bp, f);
        !           172:        do{
        !           173:                if(p1.x == 0){
        !           174:                        dy = -sgn(p1.y);
        !           175:                        dysq = (2*p1.y + dy)*dy;
        !           176:                }
        !           177:                else if(p1.y == 0){
        !           178:                        dx = -sgn(p1.x);
        !           179:                        dxsq = (2*p1.x + dx)*dx;
        !           180:                }
        !           181:                ex = abs(eps + dxsq);
        !           182:                ey = abs(eps + dysq);
        !           183:                exy = abs(eps + dxsq + dysq);
        !           184:                if(ex<ey || exy<=ey){
        !           185:                        p1.x += dx;
        !           186:                        eps += dxsq;
        !           187:                        dxsq += 2;
        !           188:                }
        !           189:                if(ey<ex || exy<=ex){
        !           190:                        p1.y += dy;
        !           191:                        eps += dysq;
        !           192:                        dysq += 2;
        !           193:                }
        !           194:                points(Pt(p0.x+p1.x, p0.y+p1.y));
        !           195:        } while(!(p1.x==p2.x && p1.y==p2.y));
        !           196: /*     the equality end test is justified
        !           197:        because it is impossible that
        !           198:        abs(x^2+y^2-r^2)==abs((x++-1)^2+y^2-r^2) or
        !           199:        abs(x^2+y^2-r^2)==abs(x^2+(y++-1)-r^2),
        !           200:        and no values of x or y are skipped.    */
        !           201:        endpoints();
        !           202: }
        !           203: 
        !           204: ellipse (bp, p, a, b, f)
        !           205: Bitmap *bp;
        !           206: Point p;
        !           207: long a, b;
        !           208: Code f;
        !           209: {
        !           210:        if(a==0 || b==0)
        !           211:                segment(bp, Pt(p.x-a, p.y-b), Pt(p.x+a, p.y+b), f);
        !           212:        else
        !           213:                ellip2(bp, p, a, b, Pt(0, b), Pt(0, b), f);
        !           214: }
        !           215: 
        !           216: #define                BIG             077777
        !           217: #define                HUGE            07777777777L
        !           218: /*
        !           219:        resid: calculate b*b*x*x + a*a*y*y - a*a*b*b avoiding ovfl
        !           220:                called by ellip1() and ellip2()
        !           221: */
        !           222: static long
        !           223: resid (a,b,x,y)
        !           224: register long a, b;
        !           225: long x, y;
        !           226: {
        !           227:        long e = 0;
        !           228:        long u = b*(a*a - x*x);
        !           229:        long v = a*y*y;
        !           230:        register q = u>BIG? HUGE/u: BIG;
        !           231:        register r = v>BIG? HUGE/v: BIG;
        !           232:        while(a || b){
        !           233:                if(e>=0 && b){
        !           234:                        if(q>b) q = b;
        !           235:                        e -= q*u;
        !           236:                        b -= q;
        !           237:                }
        !           238:                else{
        !           239:                        if(r>a) r = a;
        !           240:                        e += r*v;
        !           241:                        a -= r;
        !           242:                }
        !           243:        }
        !           244:        return(e);
        !           245: }
        !           246: 
        !           247: #define                labs(x,y)       if((x=y)<0) x = -x
        !           248: #define                samesign(x,y)   (((int)(x)^(int)(y)) > 0)
        !           249: 
        !           250: ellip2 (bp, p0, a, b, p1, p2, f)
        !           251: Point p0, p1, p2;
        !           252: long a, b;
        !           253: register Bitmap *bp;
        !           254: Code f;
        !           255: {
        !           256:        int dx = p1.y>0 ? 1 : p1.y<0 ? -1 : p1.x>0 ? -1 : 1;
        !           257:        int dy = p1.x>0 ? -1 : p1.x<0 ? 1 : p1.y>0 ? -1 : 1;
        !           258:        long a2 = a*a;
        !           259:        long b2 = b*b;
        !           260:        register long dex = b2*(2*dx*p1.x+1);
        !           261:        register long e;
        !           262:        register long dey = a2*(2*dy*p1.y+1);
        !           263:        register long ex, ey, exy;
        !           264:        int partial = !eqpt(p1, p2);
        !           265: 
        !           266:        if(partial &&
        !           267:           (p1.x==0 && p2.x==0 && samesign(p1.y, p2.y) ||
        !           268:            p1.y==0 && p2.y==0 && samesign(p1.x, p2.x))) {
        !           269:                segment(bp, add(p0, p1), add(p0,p2), f);
        !           270:                return;
        !           271:        }
        !           272:        e = resid(a, b, p1.x, p1.y);
        !           273:        a2 *= 2;
        !           274:        b2 *= 2;
        !           275:        initpoints(bp, f);
        !           276:        do{
        !           277:                labs(ex, e+dex);
        !           278:                labs(ey, e+dey);
        !           279:                labs(exy, e+dex+dey);
        !           280:                if(exy<=ex || ey<ex){
        !           281:                        p1.y += dy;
        !           282:                        e += dey;
        !           283:                        dey += a2;
        !           284:                }
        !           285:                if(exy<=ey || ex<ey){
        !           286:                        p1.x += dx;
        !           287:                        e += dex;
        !           288:                        dex += b2;
        !           289:                }
        !           290:                if(p1.x == 0){
        !           291:                        if(abs(p1.y) == b){
        !           292:                                dy = -dy;
        !           293:                                dey = -dey + a2;
        !           294:                                partial = 0;
        !           295:                        }
        !           296:                        /* don't double-draw skinny ends */
        !           297:                        else if(!samesign(p1.y, dy) && !partial)
        !           298:                                continue;
        !           299:                }
        !           300:                else if(p1.y == 0){
        !           301:                        if(abs(p1.x) == a){
        !           302:                                dx = -dx;
        !           303:                                dex = -dex + b2;
        !           304:                                partial = 0;
        !           305:                        }
        !           306:                        else if(!samesign(p1.x, dx) && !partial)
        !           307:                                continue;
        !           308:                }
        !           309:                points(add(p0, p1));
        !           310:        } while(! eqpt(p1, p2));
        !           311:        endpoints();
        !           312: }
        !           313: 
        !           314: ellip1 (bp, p0, a, b, action, p1, p2, f)
        !           315: Bitmap *bp;
        !           316: Point p0, p1, p2;
        !           317: long a, b;
        !           318: register void (*action) ();
        !           319: int f;
        !           320: {
        !           321:        int dx = p1.y > 0 ? 1 : p1.y < 0 ? -1 : p1.x > 0 ? -1 : 1;
        !           322:        int dy = p1.x > 0 ? -1 : p1.x < 0 ? 1 : p1.y > 0 ? -1 : 1;
        !           323:        long a2 = a * a;
        !           324:        long b2 = b * b;
        !           325:        register long dex = b2 * (2 * dx * p1.x + 1);
        !           326:        register long e;
        !           327:        register long dey = a2 * (2 * dy * p1.y + 1);
        !           328:        register long ex, ey, exy;
        !           329:        int partial = !eqpt (p1, p2);
        !           330:        
        !           331:        if(partial &&
        !           332:            (p1.x == 0 && p2.x == 0 && samesign (p1.y, p2.y) ||
        !           333:             p1.y == 0 && p2.y == 0 && samesign (p1.x, p2.x))){
        !           334:                segment(bp, add (p0, p1), add (p0, p2), f);
        !           335:                return;
        !           336:        }
        !           337:        e = resid(a, b, p1.x, p1.y);
        !           338:        a2 *= 2;
        !           339:        b2 *= 2;
        !           340:        do{
        !           341:                labs(ex, e + dex);
        !           342:                labs(ey, e + dey);
        !           343:                labs(exy, e + dex + dey);
        !           344:                if(exy <= ex || ey < ex){
        !           345:                        p1.y += dy;
        !           346:                        e += dey;
        !           347:                        dey += a2;
        !           348:                }
        !           349:                if(exy <= ey || ex < ey){
        !           350:                        p1.x += dx;
        !           351:                        e += dex;
        !           352:                        dex += b2;
        !           353:                }
        !           354:                if(p1.x == 0){
        !           355:                        if(abs(p1.y) == b){
        !           356:                                dy = -dy;
        !           357:                                dey = -dey + a2;
        !           358:                                partial = 0;
        !           359:                        }
        !           360:                        else
        !           361:                                if(!samesign (p1.y, dy) && !partial)
        !           362:                                        continue;
        !           363:                        /* don't double-draw skinny ends */
        !           364:                }
        !           365:                else
        !           366:                        if(p1.y == 0){
        !           367:                                if(abs (p1.x) == a){
        !           368:                                        dx = -dx;
        !           369:                                        dex = -dex + b2;
        !           370:                                        partial = 0;
        !           371:                                }
        !           372:                                else
        !           373:                                        if(!samesign (p1.x, dx) && !partial)
        !           374:                                                continue;
        !           375:                        }
        !           376:                (*action)(bp, add (p0, p1), f);
        !           377:        } while(!eqpt (p1, p2));
        !           378: }
        !           379: 
        !           380: static int yaxis;      /* used in scan and eldisc      */
        !           381: static int xaxis;      /* used in scan and eldisc      */
        !           382: static Point lp;       /* used in scan and eldisc      */
        !           383: 
        !           384: static
        !           385: void
        !           386: scan (bp, p, f)                /* called by eldisc() and ellip1()      */
        !           387: Bitmap *bp;
        !           388: Point p;
        !           389: Code f;
        !           390: {
        !           391:        register x, y;
        !           392: 
        !           393:        if((p.y != lp.y) && (lp.y != -1)){
        !           394:                x = xaxis - lp.x;
        !           395:                y = yaxis - lp.y;
        !           396:                rectf(bp, Rect(lp.x, lp.y, x+1, lp.y+1), f);
        !           397:                rectf(bp, Rect(lp.x, y, x+1, y+1), f);
        !           398:        }
        !           399:        lp = p;
        !           400: }
        !           401: 
        !           402: eldisc (bp, p, a, b, f)
        !           403: Bitmap *bp;
        !           404: Point p;
        !           405: int a, b;
        !           406: Code f;
        !           407: {
        !           408:        register x0 = p.x;
        !           409:        register y0 = p.y;
        !           410: 
        !           411:        yaxis = 2*p.y;
        !           412:        xaxis = 2*p.x;
        !           413:        lp.y = -1;
        !           414:        if(a==0 || b==0)
        !           415:                segment(bp, Pt(x0-a,y0-b), Pt(x0+a,y0+b), f);
        !           416:        else{
        !           417:                ellip1(bp, p, a, b, scan, Pt(0, -b), Pt(-a, 0), f);
        !           418:                scan(bp, Pt(0, -1), f);
        !           419:                rectf(bp, Rect(p.x-a, p.y, p.x+a+1, p.y+1), f);
        !           420:        }
        !           421: }
        !           422: 
        !           423: /*     elarc routines  */
        !           424: 
        !           425: static struct dist {
        !           426:        Point s;
        !           427:        Point m;
        !           428:        long e;
        !           429: } d1, d2;
        !           430: 
        !           431: static
        !           432: void
        !           433: test(x, p)             /* called by survet()   */
        !           434: Point x;
        !           435: register struct dist *p;
        !           436: {
        !           437:        register long dx = x.x - p->s.x;
        !           438:        register long dy = x.y - p->s.y;
        !           439:        register long e = dx*dx+dy*dy;
        !           440: 
        !           441:        if(e <= p->e){
        !           442:                p->m = x;
        !           443:                p->e = e;
        !           444:        }
        !           445: }
        !           446: 
        !           447: static
        !           448: void
        !           449: survey(bp, x, f)       /* called by elarc()    */
        !           450: Bitmap *bp;
        !           451: Point x;
        !           452: Code f;
        !           453: {
        !           454:        test(x, &d1);
        !           455:        test(x, &d2);
        !           456: }
        !           457: 
        !           458: #define HUGE2          017777777777
        !           459: #define        sgn2(x) ((x)<0? -1 : (x)==0? 0 : 1)
        !           460: 
        !           461: /*
        !           462:        elarc(bp,p0,a,b,p1,p2,f) draws in bitmap bp an arc of the ellipse
        !           463:        centered at p0 with half-axes a,b extending counterclockwise
        !           464:        from a point near p1 to a point near p2
        !           465:        args reversed because ellip1 draws clockwise 
        !           466: */
        !           467: elarc (bp, p0, a, b, p1, p2, f)
        !           468: Bitmap *bp;
        !           469: Point p0, p1, p2;
        !           470: Code f;
        !           471: {
        !           472:        if(a==0)
        !           473:                segment(bp, Pt(p0.x, p1.y), Pt(p0.x, p2.y), f);
        !           474:        else if(b==0)
        !           475:                segment(bp, Pt(p1.x, p0.y), Pt(p2.x, p0.y), f);
        !           476:        else{
        !           477:                int sx1;
        !           478:                int sy1;
        !           479:                int sx2;
        !           480:                int sy2;
        !           481: 
        !           482:                d1.s = sub(p1, p0);
        !           483:                d2.s = sub(p2, p0);
        !           484:                sx1 = sgn2(d1.s.x);
        !           485:                sy1 = sgn2(d1.s.y);
        !           486:                sx2 = sgn2(d2.s.x);
        !           487:                sy2 = sgn2(d2.s.y);
        !           488:                d1.s.x *= sx1;
        !           489:                d1.s.y *= sy1;
        !           490:                d2.s.x *= sx2;
        !           491:                d2.s.y *= sy2;
        !           492:                d1.e = d2.e = HUGE2;
        !           493:                survey(bp, Pt(0, b), f);
        !           494:                ellip1(bp, Pt(0, 0), a, b, survey, Pt(0,b), Pt(a, 0), f);
        !           495:                if(!eqpt(d1.m, d2.m))
        !           496:                        point(bp, d1.m, f);
        !           497:                ellip1(bp, p0, a, b, point,
        !           498:                        Pt(d1.m.x*sx1, d1.m.y*sy1),
        !           499:                        Pt(d2.m.x*sx2, d2.m.y*sy2), f);
        !           500:        }
        !           501: }
        !           502: 
        !           503: /*
        !           504:        dak's points routines for buffering X calls
        !           505: */
        !           506: #ifdef X11
        !           507: #define PBSIZE 100
        !           508: #define flushpt()      if (xpcnt) flushpoints();
        !           509: static XPoint xp[PBSIZE];
        !           510: static xpcnt;
        !           511: #endif X11
        !           512: static Code fc;
        !           513: static ispixmap;
        !           514: static Bitmap *bitm;
        !           515: 
        !           516: points (p)
        !           517: Point p;
        !           518: {
        !           519: #ifdef SUNTOOLS
        !           520:        point(bitm,p,fc);
        !           521: #endif SUNTOOLS
        !           522: #ifdef X11
        !           523:        register XPoint *x;
        !           524: 
        !           525:        if(ispixmap)
        !           526:                p = sub(p, bitm->rect.origin);
        !           527:        x = &xp[xpcnt];
        !           528:        x->x = p.x;
        !           529:        x->y = p.y;
        !           530:        if (++xpcnt == PBSIZE)
        !           531:                flushpoints();
        !           532: #endif X11
        !           533: }
        !           534: 
        !           535: initpoints (b, f)
        !           536: Bitmap *b;
        !           537: Code f;
        !           538: {
        !           539:        if(b->flag & BI_OFFSCREEN)
        !           540:                ispixmap = 1;
        !           541:        else {
        !           542: #ifdef SUNTOOLS
        !           543:                struct rect lkrect;
        !           544:                if(!(b->flag & BI_OFFSCREEN)){
        !           545:                        win_getsize(displayfd, &lkrect);
        !           546:                        pw_lock((Pixwin *)b->dr, &lkrect);
        !           547:                }
        !           548: #endif SUNTOOLS
        !           549:                ispixmap = 0;
        !           550:        }
        !           551:        bitm = b;
        !           552: #ifdef X11
        !           553:        XSetFunction(dpy, gc, f);
        !           554: #endif X11
        !           555:        fc = f;
        !           556: }
        !           557: 
        !           558: endpoints()
        !           559: {
        !           560: #ifdef SUNTOOLS
        !           561:        if(!ispixmap)
        !           562:                pw_unlock((Pixwin *)bitm->dr);
        !           563: #endif SUNTOOLS
        !           564: #ifdef X11
        !           565:        flushpt();
        !           566: #endif X11
        !           567: }
        !           568: 
        !           569: #ifdef X11
        !           570: flushpoints()
        !           571: {
        !           572:        if(xpcnt){
        !           573:                XDrawPoints(dpy, bitm->dr, gc, xp, xpcnt, CoordModeOrigin);
        !           574:                xpcnt = 0;
        !           575:        }
        !           576: }
        !           577: #endif X11

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.