Return to XRegion.c CVS log

Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / lib / X

Annotation of researchv9/X11/src/X.V11R1/lib/X/XRegion.c, revision 1.1

1.1     ! root        1: /* $Header: XRegion.c,v 11.13 87/09/03 17:20:59 newman Exp $ */
        !             2: /************************************************************************
        !             3: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
        !             4: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
        !             5: 
        !             6:                         All Rights Reserved
        !             7: 
        !             8: Permission to use, copy, modify, and distribute this software and its 
        !             9: documentation for any purpose and without fee is hereby granted, 
        !            10: provided that the above copyright notice appear in all copies and that
        !            11: both that copyright notice and this permission notice appear in 
        !            12: supporting documentation, and that the names of Digital or MIT not be
        !            13: used in advertising or publicity pertaining to distribution of the
        !            14: software without specific, written prior permission.  
        !            15: 
        !            16: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
        !            17: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
        !            18: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
        !            19: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
        !            20: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
        !            21: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
        !            22: SOFTWARE.
        !            23: 
        !            24: ************************************************************************/
        !            25: /*
        !            26:  * The functions in this file implement the Region abstraction used extensively
        !            27:  * throughout the X11 sample server. A Region is simply an area, as the name
        !            28:  * implies, and is implemented as a "y-x-banded" array of rectangles. To
        !            29:  * explain: Each Region is made up of a certain number of rectangles sorted
        !            30:  * by y coordinate first, and then by x coordinate.
        !            31:  *
        !            32:  * Furthermore, the rectangles are banded such that every rectangle with a
        !            33:  * given upper-left y coordinate (y1) will have the same lower-right y
        !            34:  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
        !            35:  * will span the entire vertical distance of the band. This means that some
        !            36:  * areas that could be merged into a taller rectangle will be represented as
        !            37:  * several shorter rectangles to account for shorter rectangles to its left
        !            38:  * or right but within its "vertical scope".
        !            39:  *
        !            40:  * An added constraint on the rectangles is that they must cover as much
        !            41:  * horizontal area as possible. E.g. no two rectangles in a band are allowed
        !            42:  * to touch.
        !            43:  *
        !            44:  * Whenever possible, bands will be merged together to cover a greater vertical
        !            45:  * distance (and thus reduce the number of rectangles). Two bands can be merged
        !            46:  * only if the bottom of one touches the top of the other and they have
        !            47:  * rectangles in the same places (of the same width, of course). This maintains
        !            48:  * the y-x-banding that's so nice to have...
        !            49:  */
        !            50: 
        !            51: #include "Xlib.h"
        !            52: #include "Xutil.h"
        !            53: #include "region.h"
        !            54: #include "poly.h"
        !            55: 
        !            56: #ifdef DEBUG
        !            57: #define assert(expr) {if (!(expr)) FatalError("Assertion failed file
        !            58: %s, line %d: expr\n", __FILE__, __LINE__); }
        !            59: #else
        !            60: #define assert(expr)
        !            61: #endif
        !            62: 
        !            63: extern char *_XAllocScratch();
        !            64: /*     Create a new empty region       */
        !            65: Region
        !            66: XCreateRegion()
        !            67: {
        !            68:     Region temp;
        !            69: 
        !            70:     temp = ( Region )Xmalloc( (unsigned) sizeof( REGION ));
        !            71:     temp->rects = ( BOX * )Xmalloc( (unsigned) sizeof( BOX ));
        !            72:     temp->numRects = 0;
        !            73:     temp->extents.x1 = 0;
        !            74:     temp->extents.y1 = 0;
        !            75:     temp->extents.x2 = 0;
        !            76:     temp->extents.y2 = 0;
        !            77:     temp->size = 1;
        !            78:     return( temp );
        !            79: }
        !            80: 
        !            81: XClipBox( r, rect )
        !            82:     Region r;
        !            83:     XRectangle *rect;
        !            84: {
        !            85:     rect->x = r->extents.x1;
        !            86:     rect->y = r->extents.y1;
        !            87:     rect->width = r->extents.x2 - r->extents.x1;
        !            88:     rect->height = r->extents.y2 - r->extents.y1;
        !            89: }
        !            90: 
        !            91: 
        !            92: /*-
        !            93:  *-----------------------------------------------------------------------
        !            94:  * miSetExtents --
        !            95:  *     Reset the extents of a region to what they should be. Called by
        !            96:  *     miSubtract and miIntersect b/c they can't figure it out along the
        !            97:  *     way or do so easily, as miUnion can.
        !            98:  *
        !            99:  * Results:
        !           100:  *     None.
        !           101:  *
        !           102:  * Side Effects:
        !           103:  *     The region's 'extents' structure is overwritten.
        !           104:  *
        !           105:  *-----------------------------------------------------------------------
        !           106:  */
        !           107: /* static void*/
        !           108: miSetExtents (pReg)
        !           109:     Region             pReg;
        !           110: {
        !           111:     register BoxPtr    pBox,
        !           112:                        pBoxEnd,
        !           113:                        pExtents;
        !           114: 
        !           115:     pExtents = &pReg->extents;
        !           116:     pBox = pReg->rects;
        !           117:     pBoxEnd = &pBox[pReg->numRects - 1];
        !           118: 
        !           119:     /*
        !           120:      * Since pBox is the first rectangle in the region, it must have the
        !           121:      * smallest y1 and since pBoxEnd is the last rectangle in the region,
        !           122:      * it must have the largest y2, because of banding. Initialize x1 and
        !           123:      * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
        !           124:      * to...
        !           125:      */
        !           126:     pExtents->x1 = pBox->x1;
        !           127:     pExtents->y1 = pBox->y1;
        !           128:     pExtents->x2 = pBoxEnd->x2;
        !           129:     pExtents->y2 = pBoxEnd->y2;
        !           130: 
        !           131:     assert(pExtents->y1 < pExtents->y2);
        !           132:     while (pBox <= pBoxEnd)
        !           133:     {
        !           134:        if (pBox->x1 < pExtents->x1)
        !           135:        {
        !           136:            pExtents->x1 = pBox->x1;
        !           137:        }
        !           138:        if (pBox->x2 > pExtents->x2)
        !           139:        {
        !           140:            pExtents->x2 = pBox->x2;
        !           141:        }
        !           142:        pBox++;
        !           143:     }
        !           144:     assert(pExtents->x1 < pExtents->x2);
        !           145: }
        !           146: 
        !           147: XSetRegion( dpy, gc, r )
        !           148:     Display *dpy;
        !           149:     GC gc;
        !           150:     register Region r;
        !           151: {
        !           152:     register int i;
        !           153:     register XRectangle *xr;
        !           154:     LockDisplay (dpy);
        !           155:     xr = (XRectangle *) 
        !           156:        _XAllocScratch(dpy, (unsigned long)(r->numRects * sizeof (XRectangle)));
        !           157:     for (i = 0; i < r->numRects; i++) {
        !           158:         xr->x = r->rects[i].x1;
        !           159:        xr->y = r->rects[i].y1;
        !           160:        xr->width = r->rects[i].x2 - r->rects[i].x1;
        !           161:        xr->height = r->rects[i].y2 - r->rects[i].y1;
        !           162:       }
        !           163:     _XSetClipRectangles(dpy, gc,r->extents.x1,r->extents.y1, xr,
        !           164:        r->numRects,Unsorted);
        !           165:     UnlockDisplay(dpy);
        !           166:     SyncHandle();
        !           167: }
        !           168: 
        !           169: XDestroyRegion( r )
        !           170:     Region r;
        !           171: {
        !           172:     Xfree( (char *) r->rects );
        !           173:     Xfree( (char *) r );
        !           174: }
        !           175: 
        !           176: 
        !           177: /* TranslateRegion(pRegion, x, y)
        !           178:    translates in place
        !           179:    added by raymond
        !           180: */
        !           181: 
        !           182: void
        !           183: XOffsetRegion(pRegion, x, y)
        !           184:     register Region pRegion;
        !           185:     register int x;
        !           186:     register int y;
        !           187: {
        !           188:     register int nbox;
        !           189:     register BOX *pbox;
        !           190: 
        !           191:     pbox = pRegion->rects;
        !           192:     nbox = pRegion->numRects;
        !           193: 
        !           194:     while(nbox--)
        !           195:     {
        !           196:        pbox->x1 += x;
        !           197:        pbox->x2 += x;
        !           198:        pbox->y1 += y;
        !           199:        pbox->y2 += y;
        !           200:        pbox++;
        !           201:     }
        !           202:     pRegion->extents.x1 += x;
        !           203:     pRegion->extents.x2 += x;
        !           204:     pRegion->extents.y1 += y;
        !           205:     pRegion->extents.y2 += y;
        !           206: }
        !           207: 
        !           208: XShrinkRegion( r, dx, dy )
        !           209:     Region r;
        !           210:     int dx, dy;
        !           211: {
        !           212:     int i,h,w;
        !           213:     float sx,sy;
        !           214:     int cx,cy,newcx,newcy;
        !           215:     BoxPtr rect;
        !           216: 
        !           217:     /* figure out ratios */
        !           218:     h = r->extents.y2 - r->extents.y1;
        !           219:     w = r->extents.x2 - r->extents.x1;
        !           220:     sx = ((float)(w+dx))/w;
        !           221:     sy = ((float)(h+dy))/h;
        !           222:     rect = &(r->rects[0]);
        !           223:     for(i=0; i<r->numRects; i++)
        !           224:     {
        !           225:        cx = (rect->x1 + rect->x2)/2;
        !           226:        cy = (rect->y1 + rect->y2)/2;
        !           227: 
        !           228:        /* shrink or expand box */
        !           229:        rect->x1 = rect->x1 * sx;
        !           230:        rect->x2 = rect->x2 * sx;
        !           231:        rect->y1 = rect->y1 * sy;
        !           232:        rect->y2 = rect->y2 * sy;
        !           233: 
        !           234:        /* recenter box around old center */
        !           235:        newcx = (rect->x1 + rect->x2)/2;
        !           236:        newcy = (rect->y1 + rect->y2)/2;
        !           237:        rect->x1 = rect->x1 - (newcx - cx);
        !           238:        rect->x2 = rect->x2 - (newcx - cx);
        !           239:        rect->y1 = rect->y1 - (newcy - cy);
        !           240:        rect->y2 = rect->y2 - (newcy - cy);
        !           241: 
        !           242:        /* adjust for shrinkage problems */
        !           243:        if ( dx < 0 )
        !           244:        {
        !           245:                if ( rect->x1 > cx ) rect->x1 = cx;
        !           246:                if ( rect->x2 < cx ) rect->x2 = cx;
        !           247:        }
        !           248:        if ( dy < 0 )
        !           249:        {
        !           250:                if ( rect->y1 > cy ) rect->y1 = cy;
        !           251:                if ( rect->y2 < cy ) rect->y2 = cy;
        !           252:        }
        !           253:        EXTENTS(rect,r);
        !           254:        (rect)++;
        !           255:     }
        !           256: }
        !           257: 
        !           258: #ifdef notdef
        !           259: /***********************************************************
        !           260:  *     Bop down the array of rects until we have passed
        !           261:  *     scanline y.  numRects is the size of the array.
        !           262:  ***********************************************************/
        !           263: 
        !           264: static BOX 
        !           265: *IndexRects(rects, numRects, y)
        !           266:     register BOX *rects;
        !           267:     register int numRects;
        !           268:     register int y;
        !           269: {
        !           270:      while ((numRects--) && (rects->y2 <= y))
        !           271:         rects++;
        !           272:      return(rects);
        !           273: }
        !           274: #endif
        !           275: 
        !           276: /*======================================================================
        !           277:  *         Region Intersection
        !           278:  *====================================================================*/
        !           279: /*-
        !           280:  *-----------------------------------------------------------------------
        !           281:  * miIntersectO --
        !           282:  *     Handle an overlapping band for miIntersect.
        !           283:  *
        !           284:  * Results:
        !           285:  *     None.
        !           286:  *
        !           287:  * Side Effects:
        !           288:  *     Rectangles may be added to the region.
        !           289:  *
        !           290:  *-----------------------------------------------------------------------
        !           291:  */
        !           292: /* static void*/
        !           293: miIntersectO (pReg, r1, r1End, r2, r2End, y1, y2)
        !           294:     register Region    pReg;
        !           295:     register BoxPtr    r1;
        !           296:     BoxPtr             r1End;
        !           297:     register BoxPtr    r2;
        !           298:     BoxPtr             r2End;
        !           299:     short              y1;
        !           300:     short              y2;
        !           301: {
        !           302:     register short     x1;
        !           303:     register short     x2;
        !           304:     register BoxPtr    pNextRect;
        !           305: 
        !           306:     pNextRect = &pReg->rects[pReg->numRects];
        !           307: 
        !           308:     while ((r1 != r1End) && (r2 != r2End))
        !           309:     {
        !           310:        x1 = max(r1->x1,r2->x1);
        !           311:        x2 = min(r1->x2,r2->x2);
        !           312: 
        !           313:        /*
        !           314:         * If there's any overlap between the two rectangles, add that
        !           315:         * overlap to the new region.
        !           316:         * There's no need to check for subsumption because the only way
        !           317:         * such a need could arise is if some region has two rectangles
        !           318:         * right next to each other. Since that should never happen...
        !           319:         */
        !           320:        if (x1 < x2)
        !           321:        {
        !           322:            assert(y1<y2);
        !           323: 
        !           324:            MEMCHECK(pReg, pNextRect, pReg->rects);
        !           325:            pNextRect->x1 = x1;
        !           326:            pNextRect->y1 = y1;
        !           327:            pNextRect->x2 = x2;
        !           328:            pNextRect->y2 = y2;
        !           329:            pReg->numRects += 1;
        !           330:            pNextRect++;
        !           331:            assert(pReg->numRects <= pReg->size);
        !           332:        }
        !           333: 
        !           334:        /*
        !           335:         * Need to advance the pointers. Shift the one that extends
        !           336:         * to the right the least, since the other still has a chance to
        !           337:         * overlap with that region's next rectangle, if you see what I mean.
        !           338:         */
        !           339:        if (r1->x2 < r2->x2)
        !           340:        {
        !           341:            r1++;
        !           342:        }
        !           343:        else if (r2->x2 < r1->x2)
        !           344:        {
        !           345:            r2++;
        !           346:        }
        !           347:        else
        !           348:        {
        !           349:            r1++;
        !           350:            r2++;
        !           351:        }
        !           352:     }
        !           353: }
        !           354: 
        !           355: XIntersectRegion(reg1, reg2, newReg)
        !           356:     Region             reg1;
        !           357:     Region             reg2;          /* source regions     */
        !           358:     register Region    newReg;               /* destination Region */
        !           359: {
        !           360:    /* check for trivial reject */
        !           361:     if ( (!(reg1->numRects)) || (!(reg2->numRects))  ||
        !           362:        (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
        !           363:     {
        !           364:         newReg->numRects = 0;
        !           365:         return(1);
        !           366:     }
        !           367: 
        !           368:     miRegionOp (newReg, reg1, reg2, miIntersectO, NULL, NULL);
        !           369:     
        !           370:     if (newReg->numRects != 0)
        !           371:     {
        !           372:        /*
        !           373:         * Can't alter newReg's extents before we call miRegionOp because
        !           374:         * it might be one of the source regions and miRegionOp depends
        !           375:         * on the extents of those regions being the same. Besides, this
        !           376:         * way there's no checking against rectangles that will be nuked
        !           377:         * due to coalescing, so we have to examine fewer rectangles.
        !           378:         */
        !           379:        miSetExtents(newReg);
        !           380:     }
        !           381:     return(1);
        !           382: }
        !           383: 
        !           384: void bcopy();
        !           385: void
        !           386: miRegionCopy(dstrgn, rgn)
        !           387:     register Region dstrgn;
        !           388:     register Region rgn;
        !           389: 
        !           390: {
        !           391:     if (dstrgn != rgn) /*  don't want to copy to itself */
        !           392:     {  
        !           393:         if (dstrgn->size < rgn->numRects)
        !           394:         {
        !           395:             if (dstrgn->rects)
        !           396:             {
        !           397:                 dstrgn->rects = (BOX *) Xrealloc(dstrgn->rects, 
        !           398:                                  rgn->numRects * (sizeof(BOX)));
        !           399:             }
        !           400:             dstrgn->size = rgn->numRects;
        !           401:        }
        !           402:         dstrgn->numRects = rgn->numRects;
        !           403:         dstrgn->extents.x1 = rgn->extents.x1;
        !           404:         dstrgn->extents.y1 = rgn->extents.y1;
        !           405:         dstrgn->extents.x2 = rgn->extents.x2;
        !           406:         dstrgn->extents.y2 = rgn->extents.y2;
        !           407: 
        !           408:        bcopy(rgn->rects, dstrgn->rects, rgn->numRects * sizeof(BOX));   
        !           409:     }
        !           410: }
        !           411: 
        !           412: /*
        !           413:  *  combinRegs(newReg, reg1, reg2)
        !           414:  *    if one region is above or below the other.
        !           415: */ 
        !           416: 
        !           417: /* static void*/
        !           418: combineRegs(newReg, reg1, reg2)
        !           419:     register Region newReg;
        !           420:     Region reg1;
        !           421:     Region reg2;
        !           422: {
        !           423:     register Region tempReg;
        !           424:     register BOX *rects;
        !           425:     register BOX *rects1;
        !           426:     register BOX *rects2;
        !           427:     register int total;
        !           428: 
        !           429:     rects1 = reg1->rects;
        !           430:     rects2 = reg2->rects;
        !           431: 
        !           432:     total = reg1->numRects + reg2->numRects;
        !           433:     tempReg = XCreateRegion();
        !           434:     tempReg->size = total;
        !           435:     /*  region 1 is below region 2  */
        !           436:     if (reg1->extents.y1 > reg2->extents.y1)
        !           437:     {
        !           438:         miRegionCopy(tempReg, reg2);
        !           439:         rects = &tempReg->rects[tempReg->numRects];
        !           440:         total -= tempReg->numRects;
        !           441:         while (total--)
        !           442:             *rects++ = *rects1++;
        !           443:     }
        !           444:     else
        !           445:     {
        !           446:         miRegionCopy(tempReg, reg1);
        !           447:         rects = &tempReg->rects[tempReg->numRects];
        !           448:         total -= tempReg->numRects;
        !           449:         while (total--)
        !           450:             *rects++ = *rects2++;
        !           451:     }
        !           452:     tempReg->extents = reg1->extents;
        !           453:     tempReg->numRects = reg1->numRects + reg2->numRects;
        !           454:     EXTENTS(&reg2->extents, tempReg);  
        !           455:     miRegionCopy(newReg, tempReg);
        !           456:     Xfree((char *)tempReg);
        !           457: }
        !           458: 
        !           459: #ifdef notdef
        !           460: /*
        !           461:  *  QuickCheck checks to see if it does not have to go through all the
        !           462:  *  the ugly code for the region call.  It returns 1 if it did all
        !           463:  *  the work for Union, otherwise 0 - still work to be done.
        !           464: */ 
        !           465: 
        !           466: static int
        !           467: QuickCheck(newReg, reg1, reg2)
        !           468:     Region newReg, reg1, reg2;
        !           469: {
        !           470: 
        !           471:     /*  if unioning with itself or no rects to union with  */
        !           472:     if ( (reg1 == reg2) || (!(reg1->numRects)) )
        !           473:     {
        !           474:         miRegionCopy(newReg, reg2);
        !           475:         return(TRUE);
        !           476:     }
        !           477: 
        !           478:     /*   if nothing to union   */
        !           479:     if (!(reg2->numRects))
        !           480:     {
        !           481:         miRegionCopy(newReg, reg1);
        !           482:         return(TRUE);
        !           483:     }
        !           484: 
        !           485:     /*   could put an extent check to see if add above or below */
        !           486: 
        !           487:     if ((reg1->extents.y1 >= reg2->extents.y2) ||
        !           488:         (reg2->extents.y1 >= reg1->extents.y2) )
        !           489:     {
        !           490:         combineRegs(newReg, reg1, reg2);
        !           491:         return(TRUE);
        !           492:     }
        !           493:     return(FALSE);
        !           494: }
        !           495: #endif
        !           496: 
        !           497: #ifdef notdef
        !           498: /*   TopRects(rects, reg1, reg2)
        !           499:  * N.B. We now assume that reg1 and reg2 intersect.  Therefore we are
        !           500:  * NOT checking in the two while loops for stepping off the end of the
        !           501:  * region.  
        !           502:  */ 
        !           503: 
        !           504: static int
        !           505: TopRects(newReg, rects, reg1, reg2, FirstRect)
        !           506:     register Region newReg;
        !           507:     register BOX *rects;
        !           508:     register Region reg1;
        !           509:     register Region reg2; 
        !           510:     BOX *FirstRect;
        !           511: {
        !           512:     register BOX *tempRects;
        !           513: 
        !           514:     /*  need to add some rects from region 1 */
        !           515:     if (reg1->extents.y1 < reg2->extents.y1)
        !           516:     {
        !           517:         tempRects = reg1->rects;
        !           518:         while(tempRects->y1 < reg2->extents.y1)
        !           519:        {
        !           520:            MEMCHECK(newReg, rects, FirstRect);
        !           521:             ADDRECTNOX(newReg,rects, tempRects->x1, tempRects->y1, 
        !           522:                       tempRects->x2, MIN(tempRects->y2, reg2->extents.y1));
        !           523:             tempRects++;
        !           524:        }
        !           525:     }
        !           526:     /*  need to add some rects from region 2 */
        !           527:     if (reg2->extents.y1 < reg1->extents.y1)
        !           528:     {
        !           529:         tempRects = reg2->rects;
        !           530:         while (tempRects->y1 < reg1->extents.y1)
        !           531:         {
        !           532:             MEMCHECK(newReg, rects, FirstRect);
        !           533:             ADDRECTNOX(newReg, rects, tempRects->x1,tempRects->y1, 
        !           534:                       tempRects->x2, MIN(tempRects->y2, reg1->extents.y1));
        !           535:             tempRects++;
        !           536:        }
        !           537:     }
        !           538:     return(1);
        !           539: }
        !           540: #endif
        !           541: 
        !           542: /*======================================================================
        !           543:  *         Generic Region Operator
        !           544:  *====================================================================*/
        !           545: 
        !           546: /*-
        !           547:  *-----------------------------------------------------------------------
        !           548:  * miCoalesce --
        !           549:  *     Attempt to merge the boxes in the current band with those in the
        !           550:  *     previous one. Used only by miRegionOp.
        !           551:  *
        !           552:  * Results:
        !           553:  *     The new index for the previous band.
        !           554:  *
        !           555:  * Side Effects:
        !           556:  *     If coalescing takes place:
        !           557:  *         - rectangles in the previous band will have their y2 fields
        !           558:  *           altered.
        !           559:  *         - pReg->numRects will be decreased.
        !           560:  *
        !           561:  *-----------------------------------------------------------------------
        !           562:  */
        !           563: /* static int*/
        !           564: miCoalesce (pReg, prevStart, curStart)
        !           565:     register Region    pReg;           /* Region to coalesce */
        !           566:     int                        prevStart;      /* Index of start of previous band */
        !           567:     int                        curStart;       /* Index of start of current band */
        !           568: {
        !           569:     register BoxPtr    pPrevBox;       /* Current box in previous band */
        !           570:     register BoxPtr    pCurBox;        /* Current box in current band */
        !           571:     register BoxPtr    pRegEnd;        /* End of region */
        !           572:     int                        curNumRects;    /* Number of rectangles in current
        !           573:                                         * band */
        !           574:     int                        prevNumRects;   /* Number of rectangles in previous
        !           575:                                         * band */
        !           576:     int                        bandY1;         /* Y1 coordinate for current band */
        !           577: 
        !           578:     pRegEnd = &pReg->rects[pReg->numRects];
        !           579: 
        !           580:     pPrevBox = &pReg->rects[prevStart];
        !           581:     prevNumRects = curStart - prevStart;
        !           582: 
        !           583:     /*
        !           584:      * Figure out how many rectangles are in the current band. Have to do
        !           585:      * this because multiple bands could have been added in miRegionOp
        !           586:      * at the end when one region has been exhausted.
        !           587:      */
        !           588:     pCurBox = &pReg->rects[curStart];
        !           589:     bandY1 = pCurBox->y1;
        !           590:     for (curNumRects = 0;
        !           591:         (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
        !           592:         curNumRects++)
        !           593:     {
        !           594:        pCurBox++;
        !           595:     }
        !           596:     
        !           597:     if (pCurBox != pRegEnd)
        !           598:     {
        !           599:        /*
        !           600:         * If more than one band was added, we have to find the start
        !           601:         * of the last band added so the next coalescing job can start
        !           602:         * at the right place... (given when multiple bands are added,
        !           603:         * this may be pointless -- see above).
        !           604:         */
        !           605:        pRegEnd--;
        !           606:        while (pRegEnd[-1].y1 == pRegEnd->y1)
        !           607:        {
        !           608:            pRegEnd--;
        !           609:        }
        !           610:        curStart = pRegEnd - pReg->rects;
        !           611:        pRegEnd = pReg->rects + pReg->numRects;
        !           612:     }
        !           613:        
        !           614:     if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
        !           615:        pCurBox -= curNumRects;
        !           616:        /*
        !           617:         * The bands may only be coalesced if the bottom of the previous
        !           618:         * matches the top scanline of the current.
        !           619:         */
        !           620:        if (pPrevBox->y2 == pCurBox->y1)
        !           621:        {
        !           622:            /*
        !           623:             * Make sure the bands have boxes in the same places. This
        !           624:             * assumes that boxes have been added in such a way that they
        !           625:             * cover the most area possible. I.e. two boxes in a band must
        !           626:             * have some horizontal space between them.
        !           627:             */
        !           628:            do
        !           629:            {
        !           630:                if ((pPrevBox->x1 != pCurBox->x1) ||
        !           631:                    (pPrevBox->x2 != pCurBox->x2))
        !           632:                {
        !           633:                    /*
        !           634:                     * The bands don't line up so they can't be coalesced.
        !           635:                     */
        !           636:                    return (curStart);
        !           637:                }
        !           638:                pPrevBox++;
        !           639:                pCurBox++;
        !           640:                prevNumRects -= 1;
        !           641:            } while (prevNumRects != 0);
        !           642: 
        !           643:            pReg->numRects -= curNumRects;
        !           644:            pCurBox -= curNumRects;
        !           645:            pPrevBox -= curNumRects;
        !           646: 
        !           647:            /*
        !           648:             * The bands may be merged, so set the bottom y of each box
        !           649:             * in the previous band to that of the corresponding box in
        !           650:             * the current band.
        !           651:             */
        !           652:            do
        !           653:            {
        !           654:                pPrevBox->y2 = pCurBox->y2;
        !           655:                pPrevBox++;
        !           656:                pCurBox++;
        !           657:                curNumRects -= 1;
        !           658:            } while (curNumRects != 0);
        !           659: 
        !           660:            /*
        !           661:             * If only one band was added to the region, we have to backup
        !           662:             * curStart to the start of the previous band.
        !           663:             *
        !           664:             * If more than one band was added to the region, copy the
        !           665:             * other bands down. The assumption here is that the other bands
        !           666:             * came from the same region as the current one and no further
        !           667:             * coalescing can be done on them since it's all been done
        !           668:             * already... curStart is already in the right place.
        !           669:             */
        !           670:            if (pCurBox == pRegEnd)
        !           671:            {
        !           672:                curStart = prevStart;
        !           673:            }
        !           674:            else
        !           675:            {
        !           676:                do
        !           677:                {
        !           678:                    *pPrevBox++ = *pCurBox++;
        !           679:                } while (pCurBox != pRegEnd);
        !           680:            }
        !           681:            
        !           682:        }
        !           683:     }
        !           684:     return (curStart);
        !           685: }
        !           686: 
        !           687: /*-
        !           688:  *-----------------------------------------------------------------------
        !           689:  * miRegionOp --
        !           690:  *     Apply an operation to two regions. Called by miUnion, miInverse,
        !           691:  *     miSubtract, miIntersect...
        !           692:  *
        !           693:  * Results:
        !           694:  *     None.
        !           695:  *
        !           696:  * Side Effects:
        !           697:  *     The new region is overwritten.
        !           698:  *
        !           699:  * Notes:
        !           700:  *     The idea behind this function is to view the two regions as sets.
        !           701:  *     Together they cover a rectangle of area that this function divides
        !           702:  *     into horizontal bands where points are covered only by one region
        !           703:  *     or by both. For the first case, the nonOverlapFunc is called with
        !           704:  *     each the band and the band's upper and lower extents. For the
        !           705:  *     second, the overlapFunc is called to process the entire band. It
        !           706:  *     is responsible for clipping the rectangles in the band, though
        !           707:  *     this function provides the boundaries.
        !           708:  *     At the end of each band, the new region is coalesced, if possible,
        !           709:  *     to reduce the number of rectangles in the region.
        !           710:  *
        !           711:  *-----------------------------------------------------------------------
        !           712:  */
        !           713: /* static void*/
        !           714: miRegionOp(newReg, reg1, reg2, overlapFunc,  nonOverlap1Func, nonOverlap2Func)
        !           715:     register Region    newReg;                 /* Place to store result */
        !           716:     Region             reg1;                   /* First region in operation */
        !           717:     Region             reg2;                   /* 2d region in operation */
        !           718:     void               (*overlapFunc)();       /* Function to call for over-
        !           719:                                                 * lapping bands */
        !           720:     void               (*nonOverlap1Func)();   /* Function to call for non-
        !           721:                                                 * overlapping bands in region
        !           722:                                                 * 1 */
        !           723:     void               (*nonOverlap2Func)();   /* Function to call for non-
        !           724:                                                 * overlapping bands in region
        !           725:                                                 * 2 */
        !           726: {
        !           727:     register BoxPtr    r1;                     /* Pointer into first region */
        !           728:     register BoxPtr    r2;                     /* Pointer into 2d region */
        !           729:     BoxPtr             r1End;                  /* End of 1st region */
        !           730:     BoxPtr             r2End;                  /* End of 2d region */
        !           731:     register short     ybot;                   /* Bottom of intersection */
        !           732:     register short     ytop;                   /* Top of intersection */
        !           733:     BoxPtr             oldRects;               /* Old rects for newReg */
        !           734:     int                        prevBand;               /* Index of start of
        !           735:                                                 * previous band in newReg */
        !           736:     int                        curBand;                /* Index of start of current
        !           737:                                                 * band in newReg */
        !           738:     register BoxPtr    r1BandEnd;              /* End of current band in r1 */
        !           739:     register BoxPtr    r2BandEnd;              /* End of current band in r2 */
        !           740:     short              top;                    /* Top of non-overlapping
        !           741:                                                 * band */
        !           742:     short              bot;                    /* Bottom of non-overlapping
        !           743:                                                 * band */
        !           744:     
        !           745:     /*
        !           746:      * Initialization:
        !           747:      * set r1, r2, r1End and r2End appropriately, preserve the important
        !           748:      * parts of the destination region until the end in case it's one of
        !           749:      * the two source regions, then mark the "new" region empty, allocating
        !           750:      * another array of rectangles for it to use.
        !           751:      */
        !           752:     r1 = reg1->rects;
        !           753:     r2 = reg2->rects;
        !           754:     r1End = r1 + reg1->numRects;
        !           755:     r2End = r2 + reg2->numRects;
        !           756:     
        !           757:     oldRects = newReg->rects;
        !           758:     
        !           759:     EMPTY_REGION(newReg);
        !           760: 
        !           761:     /*
        !           762:      * Allocate a reasonable number of rectangles for the new region. The idea
        !           763:      * is to allocate enough so the individual functions don't need to
        !           764:      * reallocate and copy the array, which is time consuming, yet we don't
        !           765:      * have to worry about using too much memory. I hope to be able to
        !           766:      * nuke the Xrealloc() at the end of this function eventually.
        !           767:      */
        !           768:     newReg->size = max(reg1->numRects,reg2->numRects) * 2;
        !           769: 
        !           770:     newReg->rects = (BoxPtr) Xmalloc (sizeof(BoxRec) * newReg->size);
        !           771:     
        !           772:     /*
        !           773:      * Initialize ybot and ytop.
        !           774:      * In the upcoming loop, ybot and ytop serve different functions depending
        !           775:      * on whether the band being handled is an overlapping or non-overlapping
        !           776:      * band.
        !           777:      *         In the case of a non-overlapping band (only one of the regions
        !           778:      * has points in the band), ybot is the bottom of the most recent
        !           779:      * intersection and thus clips the top of the rectangles in that band.
        !           780:      * ytop is the top of the next intersection between the two regions and
        !           781:      * serves to clip the bottom of the rectangles in the current band.
        !           782:      * For an overlapping band (where the two regions intersect), ytop clips
        !           783:      * the top of the rectangles of both regions and ybot clips the bottoms.
        !           784:      */
        !           785:     if (reg1->extents.y1 < reg2->extents.y1)
        !           786:     {
        !           787:        ybot = reg1->extents.y1;
        !           788:        ytop = reg2->extents.y1;
        !           789:     }
        !           790:     else
        !           791:     {
        !           792:        ybot = reg2->extents.y1;
        !           793:        ytop = reg1->extents.y1;
        !           794:     }
        !           795:     
        !           796:     /*
        !           797:      * prevBand serves to mark the start of the previous band so rectangles
        !           798:      * can be coalesced into larger rectangles. qv. miCoalesce, above.
        !           799:      * In the beginning, there is no previous band, so prevBand == curBand
        !           800:      * (curBand is set later on, of course, but the first band will always
        !           801:      * start at index 0). prevBand and curBand must be indices because of
        !           802:      * the possible expansion, and resultant moving, of the new region's
        !           803:      * array of rectangles.
        !           804:      */
        !           805:     prevBand = 0;
        !           806:     
        !           807:     do
        !           808:     {
        !           809:        curBand = newReg->numRects;
        !           810: 
        !           811:        /*
        !           812:         * This algorithm proceeds one source-band (as opposed to a
        !           813:         * destination band, which is determined by where the two regions
        !           814:         * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
        !           815:         * rectangle after the last one in the current band for their
        !           816:         * respective regions.
        !           817:         */
        !           818:        r1BandEnd = r1;
        !           819:        while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
        !           820:        {
        !           821:            r1BandEnd++;
        !           822:        }
        !           823:        
        !           824:        r2BandEnd = r2;
        !           825:        while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
        !           826:        {
        !           827:            r2BandEnd++;
        !           828:        }
        !           829:        
        !           830:        /*
        !           831:         * First handle the band that doesn't intersect, if any.
        !           832:         *
        !           833:         * Note that attention is restricted to one band in the
        !           834:         * non-intersecting region at once, so if a region has n
        !           835:         * bands between the current position and the next place it overlaps
        !           836:         * the other, this entire loop will be passed through n times.
        !           837:         */
        !           838:        if (r1->y1 < r2->y1)
        !           839:        {
        !           840:            top = max(r1->y1,ybot);
        !           841:            bot = min(r1->y2,r2->y1);
        !           842: 
        !           843:            if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
        !           844:            {
        !           845:                (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
        !           846:            }
        !           847: 
        !           848:            ytop = r2->y1;
        !           849:        }
        !           850:        else if (r2->y1 < r1->y1)
        !           851:        {
        !           852:            top = max(r2->y1,ybot);
        !           853:            bot = min(r2->y2,r1->y1);
        !           854: 
        !           855:            if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
        !           856:            {
        !           857:                (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
        !           858:            }
        !           859: 
        !           860:            ytop = r1->y1;
        !           861:        }
        !           862:        else
        !           863:        {
        !           864:            ytop = r1->y1;
        !           865:        }
        !           866: 
        !           867:        /*
        !           868:         * If any rectangles got added to the region, try and coalesce them
        !           869:         * with rectangles from the previous band. Note we could just do
        !           870:         * this test in miCoalesce, but some machines incur a not
        !           871:         * inconsiderable cost for function calls, so...
        !           872:         */
        !           873:        if (newReg->numRects != curBand)
        !           874:        {
        !           875:            prevBand = miCoalesce (newReg, prevBand, curBand);
        !           876:        }
        !           877: 
        !           878:        /*
        !           879:         * Now see if we've hit an intersecting band. The two bands only
        !           880:         * intersect if ybot > ytop
        !           881:         */
        !           882:        ybot = min(r1->y2, r2->y2);
        !           883:        curBand = newReg->numRects;
        !           884:        if (ybot > ytop)
        !           885:        {
        !           886:            (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
        !           887: 
        !           888:        }
        !           889:        
        !           890:        if (newReg->numRects != curBand)
        !           891:        {
        !           892:            prevBand = miCoalesce (newReg, prevBand, curBand);
        !           893:        }
        !           894: 
        !           895:        /*
        !           896:         * If we've finished with a band (y2 == ybot) we skip forward
        !           897:         * in the region to the next band.
        !           898:         */
        !           899:        if (r1->y2 == ybot)
        !           900:        {
        !           901:            r1 = r1BandEnd;
        !           902:        }
        !           903:        if (r2->y2 == ybot)
        !           904:        {
        !           905:            r2 = r2BandEnd;
        !           906:        }
        !           907:     } while ((r1 != r1End) && (r2 != r2End));
        !           908: 
        !           909:     /*
        !           910:      * Deal with whichever region still has rectangles left.
        !           911:      */
        !           912:     curBand = newReg->numRects;
        !           913:     if (r1 != r1End)
        !           914:     {
        !           915:        if (nonOverlap1Func != (void (*)())NULL)
        !           916:        {
        !           917:            do
        !           918:            {
        !           919:                r1BandEnd = r1;
        !           920:                while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
        !           921:                {
        !           922:                    r1BandEnd++;
        !           923:                }
        !           924:                (* nonOverlap1Func) (newReg, r1, r1BandEnd,
        !           925:                                     max(r1->y1,ybot), r1->y2);
        !           926:                r1 = r1BandEnd;
        !           927:            } while (r1 != r1End);
        !           928:        }
        !           929:     }
        !           930:     else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
        !           931:     {
        !           932:        do
        !           933:        {
        !           934:            r2BandEnd = r2;
        !           935:            while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
        !           936:            {
        !           937:                 r2BandEnd++;
        !           938:            }
        !           939:            (* nonOverlap2Func) (newReg, r2, r2BandEnd,
        !           940:                                max(r2->y1,ybot), r2->y2);
        !           941:            r2 = r2BandEnd;
        !           942:        } while (r2 != r2End);
        !           943:     }
        !           944: 
        !           945:     if (newReg->numRects != curBand)
        !           946:     {
        !           947:        (void) miCoalesce (newReg, prevBand, curBand);
        !           948:     }
        !           949: 
        !           950:     /*
        !           951:      * A bit of cleanup. To keep regions from growing without bound,
        !           952:      * we shrink the array of rectangles to match the new number of
        !           953:      * rectangles in the region. This never goes to 0, however...
        !           954:      *
        !           955:      * Only do this stuff if the number of rectangles allocated is more than
        !           956:      * twice the number of rectangles in the region (a simple optimization...).
        !           957:      */
        !           958:     if (newReg->numRects < (newReg->size >> 1))
        !           959:     {
        !           960:        if (REGION_NOT_EMPTY(newReg))
        !           961:        {
        !           962:            newReg->size = newReg->numRects;
        !           963:            newReg->rects = (BoxPtr) Xrealloc (newReg->rects,
        !           964:                                               sizeof(BoxRec) * newReg->size);
        !           965:        }
        !           966:        else
        !           967:        {
        !           968:            /*
        !           969:             * No point in doing the extra work involved in an Xrealloc if
        !           970:             * the region is empty
        !           971:             */
        !           972:            newReg->size = 1;
        !           973:            Xfree((char *) newReg->rects);
        !           974:            newReg->rects = (BoxPtr) Xmalloc(sizeof(BoxRec));
        !           975:        }
        !           976:     }
        !           977:     Xfree ((char *) oldRects);
        !           978: }
        !           979: 
        !           980: 
        !           981: /*======================================================================
        !           982:  *         Region Union
        !           983:  *====================================================================*/
        !           984: 
        !           985: /*-
        !           986:  *-----------------------------------------------------------------------
        !           987:  * miUnionNonO --
        !           988:  *     Handle a non-overlapping band for the union operation. Just
        !           989:  *     Adds the rectangles into the region. Doesn't have to check for
        !           990:  *     subsumption or anything.
        !           991:  *
        !           992:  * Results:
        !           993:  *     None.
        !           994:  *
        !           995:  * Side Effects:
        !           996:  *     pReg->numRects is incremented and the final rectangles overwritten
        !           997:  *     with the rectangles we're passed.
        !           998:  *
        !           999:  *-----------------------------------------------------------------------
        !          1000:  */
        !          1001: /* static void*/
        !          1002: miUnionNonO (pReg, r, rEnd, y1, y2)
        !          1003:     register Region    pReg;
        !          1004:     register BoxPtr    r;
        !          1005:     BoxPtr             rEnd;
        !          1006:     register short     y1;
        !          1007:     register short     y2;
        !          1008: {
        !          1009:     register BoxPtr    pNextRect;
        !          1010: 
        !          1011:     pNextRect = &pReg->rects[pReg->numRects];
        !          1012: 
        !          1013:     assert(y1 < y2);
        !          1014: 
        !          1015:     while (r != rEnd)
        !          1016:     {
        !          1017:        assert(r->x1 < r->x2);
        !          1018:        MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1019:        pNextRect->x1 = r->x1;
        !          1020:        pNextRect->y1 = y1;
        !          1021:        pNextRect->x2 = r->x2;
        !          1022:        pNextRect->y2 = y2;
        !          1023:        pReg->numRects += 1;
        !          1024:        pNextRect++;
        !          1025: 
        !          1026:        assert(pReg->numRects<=pReg->size);
        !          1027:        r++;
        !          1028:     }
        !          1029: 
        !          1030: }
        !          1031: 
        !          1032: 
        !          1033: /*-
        !          1034:  *-----------------------------------------------------------------------
        !          1035:  * miUnionO --
        !          1036:  *     Handle an overlapping band for the union operation. Picks the
        !          1037:  *     left-most rectangle each time and merges it into the region.
        !          1038:  *
        !          1039:  * Results:
        !          1040:  *     None.
        !          1041:  *
        !          1042:  * Side Effects:
        !          1043:  *     Rectangles are overwritten in pReg->rects and pReg->numRects will
        !          1044:  *     be changed.
        !          1045:  *
        !          1046:  *-----------------------------------------------------------------------
        !          1047:  */
        !          1048: 
        !          1049: /* static void*/
        !          1050: miUnionO (pReg, r1, r1End, r2, r2End, y1, y2)
        !          1051:     register Region    pReg;
        !          1052:     register BoxPtr    r1;
        !          1053:     BoxPtr             r1End;
        !          1054:     register BoxPtr    r2;
        !          1055:     BoxPtr             r2End;
        !          1056:     register short     y1;
        !          1057:     register short     y2;
        !          1058: {
        !          1059:     register BoxPtr    pNextRect;
        !          1060:     
        !          1061:     pNextRect = &pReg->rects[pReg->numRects];
        !          1062: 
        !          1063: #define MERGERECT(r) \
        !          1064:     if ((pReg->numRects != 0) &&  \
        !          1065:        (pNextRect[-1].y1 == y1) &&  \
        !          1066:        (pNextRect[-1].y2 == y2) &&  \
        !          1067:        (pNextRect[-1].x2 >= r->x1))  \
        !          1068:     {  \
        !          1069:        if (pNextRect[-1].x2 < r->x2)  \
        !          1070:        {  \
        !          1071:            pNextRect[-1].x2 = r->x2;  \
        !          1072:            assert(pNextRect[-1].x1<pNextRect[-1].x2); \
        !          1073:        }  \
        !          1074:     }  \
        !          1075:     else  \
        !          1076:     {  \
        !          1077:        MEMCHECK(pReg, pNextRect, pReg->rects);  \
        !          1078:        pNextRect->y1 = y1;  \
        !          1079:        pNextRect->y2 = y2;  \
        !          1080:        pNextRect->x1 = r->x1;  \
        !          1081:        pNextRect->x2 = r->x2;  \
        !          1082:        pReg->numRects += 1;  \
        !          1083:         pNextRect += 1;  \
        !          1084:     }  \
        !          1085:     assert(pReg->numRects<=pReg->size);\
        !          1086:     r++;
        !          1087:     
        !          1088:     assert (y1<y2);
        !          1089:     while ((r1 != r1End) && (r2 != r2End))
        !          1090:     {
        !          1091:        if (r1->x1 < r2->x1)
        !          1092:        {
        !          1093:            MERGERECT(r1);
        !          1094:        }
        !          1095:        else
        !          1096:        {
        !          1097:            MERGERECT(r2);
        !          1098:        }
        !          1099:     }
        !          1100:     
        !          1101:     if (r1 != r1End)
        !          1102:     {
        !          1103:        do
        !          1104:        {
        !          1105:            MERGERECT(r1);
        !          1106:        } while (r1 != r1End);
        !          1107:     }
        !          1108:     else while (r2 != r2End)
        !          1109:     {
        !          1110:        MERGERECT(r2);
        !          1111:     }
        !          1112: }
        !          1113: 
        !          1114: XUnionRegion(reg1, reg2, newReg)
        !          1115:     Region       reg1;
        !          1116:     Region       reg2;             /* source regions     */
        !          1117:     Region       newReg;                  /* destination Region */
        !          1118: {
        !          1119:     /*  checks all the simple cases */
        !          1120: 
        !          1121:     /*
        !          1122:      * Region 1 and 2 are the same or region 1 is empty
        !          1123:      */
        !          1124:     if ( (reg1 == reg2) || (!(reg1->numRects)) )
        !          1125:     {
        !          1126:         if (newReg != reg2)
        !          1127:             miRegionCopy(newReg, reg2);
        !          1128:         return(TRUE);
        !          1129:     }
        !          1130: 
        !          1131:     /*
        !          1132:      * if nothing to union (region 2 empty)
        !          1133:      */
        !          1134:     if (!(reg2->numRects))
        !          1135:     {
        !          1136:         if (newReg != reg1)
        !          1137:             miRegionCopy(newReg, reg1);
        !          1138:         return(TRUE);
        !          1139:     }
        !          1140: 
        !          1141:     /*
        !          1142:      * Region 1 completely subsumes region 2
        !          1143:      */
        !          1144:     if ((reg1->numRects == 1) && 
        !          1145:        (reg1->extents.x1 <= reg2->extents.x1) &&
        !          1146:        (reg1->extents.y1 <= reg2->extents.y1) &&
        !          1147:        (reg1->extents.x2 >= reg2->extents.x2) &&
        !          1148:        (reg1->extents.y2 >= reg2->extents.y2))
        !          1149:     {
        !          1150:         if (newReg != reg1)
        !          1151:             miRegionCopy(newReg, reg1);
        !          1152:         return(TRUE);
        !          1153:     }
        !          1154: 
        !          1155:     /*
        !          1156:      * Region 2 completely subsumes region 1
        !          1157:      */
        !          1158:     if ((reg2->numRects == 1) && 
        !          1159:        (reg2->extents.x1 <= reg1->extents.x1) &&
        !          1160:        (reg2->extents.y1 <= reg1->extents.y1) &&
        !          1161:        (reg2->extents.x2 >= reg1->extents.x2) &&
        !          1162:        (reg2->extents.y2 >= reg1->extents.y2))
        !          1163:     {
        !          1164:         if (newReg != reg2)
        !          1165:             miRegionCopy(newReg, reg2);
        !          1166:         return(TRUE);
        !          1167:     }
        !          1168: 
        !          1169:     miRegionOp (newReg, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
        !          1170: 
        !          1171:     newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
        !          1172:     newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
        !          1173:     newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
        !          1174:     newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
        !          1175: 
        !          1176:     return(1);
        !          1177: }
        !          1178: 
        !          1179: 
        !          1180: /*======================================================================
        !          1181:  *               Region Subtraction
        !          1182:  *====================================================================*/
        !          1183: 
        !          1184: /*-
        !          1185:  *-----------------------------------------------------------------------
        !          1186:  * miSubtractNonO --
        !          1187:  *     Deal with non-overlapping band for subtraction. Any parts from
        !          1188:  *     region 2 we discard. Anything from region 1 we add to the region.
        !          1189:  *
        !          1190:  * Results:
        !          1191:  *     None.
        !          1192:  *
        !          1193:  * Side Effects:
        !          1194:  *     pReg may be affected.
        !          1195:  *
        !          1196:  *-----------------------------------------------------------------------
        !          1197:  */
        !          1198: /* static void*/
        !          1199: miSubtractNonO1 (pReg, r, rEnd, y1, y2)
        !          1200:     register Region    pReg;
        !          1201:     register BoxPtr    r;
        !          1202:     BoxPtr             rEnd;
        !          1203:     register short     y1;
        !          1204:     register short     y2;
        !          1205: {
        !          1206:     register BoxPtr    pNextRect;
        !          1207:        
        !          1208:     pNextRect = &pReg->rects[pReg->numRects];
        !          1209:        
        !          1210:     assert(y1<y2);
        !          1211: 
        !          1212:     while (r != rEnd)
        !          1213:     {
        !          1214:        assert(r->x1<r->x2);
        !          1215:        MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1216:        pNextRect->x1 = r->x1;
        !          1217:        pNextRect->y1 = y1;
        !          1218:        pNextRect->x2 = r->x2;
        !          1219:        pNextRect->y2 = y2;
        !          1220:        pReg->numRects += 1;
        !          1221:        pNextRect++;
        !          1222: 
        !          1223:        assert(pReg->numRects <= pReg->size);
        !          1224: 
        !          1225:        r++;
        !          1226:     }
        !          1227: }
        !          1228: 
        !          1229: /*-
        !          1230:  *-----------------------------------------------------------------------
        !          1231:  * miSubtractO --
        !          1232:  *     Overlapping band subtraction. x1 is the left-most point not yet
        !          1233:  *     checked.
        !          1234:  *
        !          1235:  * Results:
        !          1236:  *     None.
        !          1237:  *
        !          1238:  * Side Effects:
        !          1239:  *     pReg may have rectangles added to it.
        !          1240:  *
        !          1241:  *-----------------------------------------------------------------------
        !          1242:  */
        !          1243: /* static void*/
        !          1244: miSubtractO (pReg, r1, r1End, r2, r2End, y1, y2)
        !          1245:     register Region    pReg;
        !          1246:     register BoxPtr    r1;
        !          1247:     BoxPtr             r1End;
        !          1248:     register BoxPtr    r2;
        !          1249:     BoxPtr             r2End;
        !          1250:     register short     y1;
        !          1251:     register short     y2;
        !          1252: {
        !          1253:     register BoxPtr    pNextRect;
        !          1254:     register int       x1;
        !          1255:     
        !          1256:     x1 = r1->x1;
        !          1257:     
        !          1258:     assert(y1<y2);
        !          1259:     pNextRect = &pReg->rects[pReg->numRects];
        !          1260: 
        !          1261:     while ((r1 != r1End) && (r2 != r2End))
        !          1262:     {
        !          1263:        if (r2->x2 <= x1)
        !          1264:        {
        !          1265:            /*
        !          1266:             * Subtrahend missed the boat: go to next subtrahend.
        !          1267:             */
        !          1268:            r2++;
        !          1269:        }
        !          1270:        else if (r2->x1 <= x1)
        !          1271:        {
        !          1272:            /*
        !          1273:             * Subtrahend preceeds minuend: nuke left edge of minuend.
        !          1274:             */
        !          1275:            x1 = r2->x2;
        !          1276:            if (x1 >= r1->x2)
        !          1277:            {
        !          1278:                /*
        !          1279:                 * Minuend completely covered: advance to next minuend and
        !          1280:                 * reset left fence to edge of new minuend.
        !          1281:                 */
        !          1282:                r1++;
        !          1283:                x1 = r1->x1;
        !          1284:            }
        !          1285:            else
        !          1286:            {
        !          1287:                /*
        !          1288:                 * Subtrahend now used up since it doesn't extend beyond
        !          1289:                 * minuend
        !          1290:                 */
        !          1291:                r2++;
        !          1292:            }
        !          1293:        }
        !          1294:        else if (r2->x1 < r1->x2)
        !          1295:        {
        !          1296:            /*
        !          1297:             * Left part of subtrahend covers part of minuend: add uncovered
        !          1298:             * part of minuend to region and skip to next subtrahend.
        !          1299:             */
        !          1300:            assert(x1<r2->x1);
        !          1301:            MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1302:            pNextRect->x1 = x1;
        !          1303:            pNextRect->y1 = y1;
        !          1304:            pNextRect->x2 = r2->x1;
        !          1305:            pNextRect->y2 = y2;
        !          1306:            pReg->numRects += 1;
        !          1307:            pNextRect++;
        !          1308: 
        !          1309:            assert(pReg->numRects<=pReg->size);
        !          1310: 
        !          1311:            x1 = r2->x2;
        !          1312:            if (x1 >= r1->x2)
        !          1313:            {
        !          1314:                /*
        !          1315:                 * Minuend used up: advance to new...
        !          1316:                 */
        !          1317:                r1++;
        !          1318:                x1 = r1->x1;
        !          1319:            }
        !          1320:            else
        !          1321:            {
        !          1322:                /*
        !          1323:                 * Subtrahend used up
        !          1324:                 */
        !          1325:                r2++;
        !          1326:            }
        !          1327:        }
        !          1328:        else
        !          1329:        {
        !          1330:            /*
        !          1331:             * Minuend used up: add any remaining piece before advancing.
        !          1332:             */
        !          1333:            if (r1->x2 > x1)
        !          1334:            {
        !          1335:                MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1336:                pNextRect->x1 = x1;
        !          1337:                pNextRect->y1 = y1;
        !          1338:                pNextRect->x2 = r1->x2;
        !          1339:                pNextRect->y2 = y2;
        !          1340:                pReg->numRects += 1;
        !          1341:                pNextRect++;
        !          1342:                assert(pReg->numRects<=pReg->size);
        !          1343:            }
        !          1344:            r1++;
        !          1345:            x1 = r1->x1;
        !          1346:        }
        !          1347:     }
        !          1348: 
        !          1349:     /*
        !          1350:      * Add remaining minuend rectangles to region.
        !          1351:      */
        !          1352:     while (r1 != r1End)
        !          1353:     {
        !          1354:        assert(x1<r1->x2);
        !          1355:        MEMCHECK(pReg, pNextRect, pReg->rects);
        !          1356:        pNextRect->x1 = x1;
        !          1357:        pNextRect->y1 = y1;
        !          1358:        pNextRect->x2 = r1->x2;
        !          1359:        pNextRect->y2 = y2;
        !          1360:        pReg->numRects += 1;
        !          1361:        pNextRect++;
        !          1362: 
        !          1363:        assert(pReg->numRects<=pReg->size);
        !          1364: 
        !          1365:        r1++;
        !          1366:        if (r1 != r1End)
        !          1367:        {
        !          1368:            x1 = r1->x1;
        !          1369:        }
        !          1370:     }
        !          1371: }
        !          1372:        
        !          1373: /*-
        !          1374:  *-----------------------------------------------------------------------
        !          1375:  * miSubtract --
        !          1376:  *     Subtract regS from regM and leave the result in regD.
        !          1377:  *     S stands for subtrahend, M for minuend and D for difference.
        !          1378:  *
        !          1379:  * Results:
        !          1380:  *     TRUE.
        !          1381:  *
        !          1382:  * Side Effects:
        !          1383:  *     regD is overwritten.
        !          1384:  *
        !          1385:  *-----------------------------------------------------------------------
        !          1386:  */
        !          1387: 
        !          1388: XSubtractRegion(regM, regS, regD)
        !          1389:     Region             regM;
        !          1390:     Region             regS;          
        !          1391:     register Region    regD;
        !          1392: {
        !          1393:    /* check for trivial reject */
        !          1394:     if ( (!(regM->numRects)) || (!(regS->numRects))  ||
        !          1395:        (!EXTENTCHECK(&regM->extents, &regS->extents)) )
        !          1396:     {
        !          1397:        miRegionCopy(regD, regM);
        !          1398:         return(1);
        !          1399:     }
        !          1400:  
        !          1401:     miRegionOp (regD, regM, regS, miSubtractO, miSubtractNonO1, NULL);
        !          1402: 
        !          1403:     if (regD->numRects != 0)
        !          1404:     {
        !          1405:        /*
        !          1406:         * Can't alter newReg's extents before we call miRegionOp because
        !          1407:         * it might be one of the source regions and miRegionOp depends
        !          1408:         * on the extents of those regions being the unaltered. Besides, this
        !          1409:         * way there's no checking against rectangles that will be nuked
        !          1410:         * due to coalescing, so we have to examine fewer rectangles.
        !          1411:         */
        !          1412:        miSetExtents (regD);
        !          1413:     }
        !          1414:     return(1);
        !          1415: }
        !          1416: 
        !          1417: XXorRegion( sra, srb, dr )
        !          1418:     Region sra, srb, dr;
        !          1419: {
        !          1420:     Region tra, trb;
        !          1421: 
        !          1422:     tra = (Region)Xmalloc((unsigned) sizeof(REGION));
        !          1423:     trb = (Region)Xmalloc((unsigned) sizeof(REGION));
        !          1424:     (void) XSubtractRegion(sra,srb,tra);
        !          1425:     (void) XSubtractRegion(srb,sra,trb);
        !          1426:     (void) XUnionRegion(tra,trb,dr);
        !          1427: }
        !          1428: 
        !          1429: /*
        !          1430:  * Check to see if the region is empty.  Assumes a region is passed 
        !          1431:  * as a parameter
        !          1432:  */
        !          1433: int 
        !          1434: XEmptyRegion( r )
        !          1435:     Region r;
        !          1436: {
        !          1437:     if( r->size == 0 && r->numRects == 0 && r->extents.x1 == 0 && 
        !          1438:        r->extents.x2 == 0 && r->extents.y1 == 0 && r->extents.y2 ==0 )
        !          1439:     return( TRUE );
        !          1440:     else  return( FALSE );
        !          1441: }
        !          1442: 
        !          1443: /*
        !          1444:  *     Check to see if two regions are equal   
        !          1445:  */
        !          1446: int 
        !          1447: XEqualRegion( r1, r2 )
        !          1448:     Region r1, r2;
        !          1449: {
        !          1450:     int i;
        !          1451: 
        !          1452:     if ( r1->size != r2->size ) return( FALSE );
        !          1453:     else if( r1->numRects != r2->numRects ) return( FALSE );
        !          1454:     else if ( r1->extents.x1 != r2->extents.x1 ) return( FALSE );
        !          1455:     else if ( r1->extents.x2 != r2->extents.x2 ) return( FALSE );
        !          1456:     else if ( r1->extents.y1 != r2->extents.y1 ) return( FALSE );
        !          1457:     else if ( r1->extents.y2 != r2->extents.y2 ) return( FALSE );
        !          1458:     else for( i=0; i < r1->numRects; i++ ) {
        !          1459:        if ( r1->rects[i].x1 != r2->rects[i].x1 ) return( FALSE );
        !          1460:        else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return( FALSE );
        !          1461:        else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return( FALSE );
        !          1462:        else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return( FALSE );
        !          1463:     }
        !          1464:     return( TRUE );
        !          1465: }
        !          1466: 
        !          1467: int 
        !          1468: XPointInRegion( pRegion, x, y )
        !          1469:     Region pRegion;
        !          1470:     int x, y;
        !          1471: {
        !          1472:     int i;
        !          1473: 
        !          1474:     if (pRegion->numRects == 0)
        !          1475:         return(FALSE);
        !          1476:     if (!INBOX(pRegion->extents, x, y))
        !          1477:         return(FALSE);
        !          1478:     for (i=0; i<pRegion->numRects; i++)
        !          1479:     {
        !          1480:         if (INBOX (pRegion->rects[i], x, y))
        !          1481:            return(TRUE);
        !          1482:     }
        !          1483:     return(FALSE);
        !          1484: }
        !          1485: 
        !          1486: int 
        !          1487: XRectInRegion(region, rx, ry, rwidth, rheight)
        !          1488:     register Region    region;
        !          1489:     int rx, ry;
        !          1490:     unsigned int rwidth, rheight;
        !          1491: {
        !          1492:     register BoxPtr pbox;
        !          1493:     register BoxPtr pboxEnd;
        !          1494:     Box rect;
        !          1495:     register BoxPtr prect = &rect;
        !          1496:     int      partIn, partOut;
        !          1497: 
        !          1498:     prect->x1 = rx;
        !          1499:     prect->y1 = ry;
        !          1500:     prect->x2 = rwidth + rx;
        !          1501:     prect->y2 = rheight + ry;
        !          1502:     
        !          1503:     /* this is (just) a useful optimization */
        !          1504:     if ((region->numRects == 0) || !EXTENTCHECK(&region->extents, prect))
        !          1505:         return(RectangleOut);
        !          1506: 
        !          1507:     partOut = FALSE;
        !          1508:     partIn = FALSE;
        !          1509: 
        !          1510:     /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
        !          1511:     for (pbox = region->rects, pboxEnd = pbox + region->numRects;
        !          1512:         pbox < pboxEnd;
        !          1513:         pbox++)
        !          1514:     {
        !          1515: 
        !          1516:        if (pbox->y2 <= ry)
        !          1517:           continue;    /* getting up to speed or skipping remainder of band */
        !          1518: 
        !          1519:        if (pbox->y1 > ry)
        !          1520:        {
        !          1521:           partOut = TRUE;      /* missed part of rectangle above */
        !          1522:           if (partIn || (pbox->y1 >= prect->y2))
        !          1523:              break;
        !          1524:           ry = pbox->y1;       /* x guaranteed to be == prect->x1 */
        !          1525:        }
        !          1526: 
        !          1527:        if (pbox->x2 <= rx)
        !          1528:           continue;            /* not far enough over yet */
        !          1529: 
        !          1530:        if (pbox->x1 > rx)
        !          1531:        {
        !          1532:           partOut = TRUE;      /* missed part of rectangle to left */
        !          1533:           if (partIn)
        !          1534:              break;
        !          1535:        }
        !          1536: 
        !          1537:        if (pbox->x1 < prect->x2)
        !          1538:        {
        !          1539:            partIn = TRUE;      /* definitely overlap */
        !          1540:            if (partOut)
        !          1541:               break;
        !          1542:        }
        !          1543: 
        !          1544:        if (pbox->x2 >= prect->x2)
        !          1545:        {
        !          1546:           ry = pbox->y2;       /* finished with this band */
        !          1547:           if (ry >= prect->y2)
        !          1548:              break;
        !          1549:           rx = prect->x1;      /* reset x out to left again */
        !          1550:        } else
        !          1551:        {
        !          1552:            /*
        !          1553:             * Because boxes in a band are maximal width, if the first box
        !          1554:             * to overlap the rectangle doesn't completely cover it in that
        !          1555:             * band, the rectangle must be partially out, since some of it
        !          1556:             * will be uncovered in that band. partIn will have been set true
        !          1557:             * by now...
        !          1558:             */
        !          1559:            partOut = TRUE;
        !          1560:            break;
        !          1561:        }
        !          1562: 
        !          1563:     }
        !          1564: 
        !          1565:     return(partIn ? ((ry < prect->y2) ? RectanglePart : RectangleIn) : 
        !          1566:                RectangleOut);
        !          1567: }

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