region.c

teamviewer source code vc++

    /*
     * Region 2 completely subsumes region 1
     */
    if ((reg2->numRects == 1) && 
	(reg2->extents.x1 <= reg1->extents.x1) &&
	(reg2->extents.y1 <= reg1->extents.y1) &&
	(reg2->extents.x2 >= reg1->extents.x2) &&
	(reg2->extents.y2 >= reg1->extents.y2))
    {
        if (newReg != reg2)
            miRegionCopy(newReg, reg2);
        return 1;
    }

    miRegionOp (newReg, reg1, reg2, (voidProcp) miUnionO, 
    		(voidProcp) miUnionNonO, (voidProcp) miUnionNonO);

    newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
    newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
    newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
    newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);

    return 1;
}


/*======================================================================
 * 	    	  Region Subtraction
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * miSubtractNonO --
 *	Deal with non-overlapping band for subtraction. Any parts from
 *	region 2 we discard. Anything from region 1 we add to the region.
 *
 * Results:
 *	None.
 *
 * Side Effects:
 *	pReg may be affected.
 *
 *-----------------------------------------------------------------------
 */
/* static void*/
static int
miSubtractNonO1 (pReg, r, rEnd, y1, y2)
    register Region	pReg;
    register BoxPtr	r;
    BoxPtr  	  	rEnd;
    register short  	y1;
    register short   	y2;
{
    register BoxPtr	pNextRect;
	
    pNextRect = &pReg->rects[pReg->numRects];
	
    assert(y1<y2);

    while (r != rEnd)
    {
	assert(r->x1<r->x2);
	MEMCHECK(pReg, pNextRect, pReg->rects);
	pNextRect->x1 = r->x1;
	pNextRect->y1 = y1;
	pNextRect->x2 = r->x2;
	pNextRect->y2 = y2;
	pReg->numRects += 1;
	pNextRect++;

	assert(pReg->numRects <= pReg->size);

	r++;
    }
    return 0;	/* lint */
}

/*-
 *-----------------------------------------------------------------------
 * miSubtractO --
 *	Overlapping band subtraction. x1 is the left-most point not yet
 *	checked.
 *
 * Results:
 *	None.
 *
 * Side Effects:
 *	pReg may have rectangles added to it.
 *
 *-----------------------------------------------------------------------
 */
/* static void*/
static int
miSubtractO (pReg, r1, r1End, r2, r2End, y1, y2)
    register Region	pReg;
    register BoxPtr	r1;
    BoxPtr  	  	r1End;
    register BoxPtr	r2;
    BoxPtr  	  	r2End;
    register short  	y1;
    register short  	y2;
{
    register BoxPtr	pNextRect;
    register int  	x1;
    
    x1 = r1->x1;
    
    assert(y1<y2);
    pNextRect = &pReg->rects[pReg->numRects];

    while ((r1 != r1End) && (r2 != r2End))
    {
	if (r2->x2 <= x1)
	{
	    /*
	     * Subtrahend missed the boat: go to next subtrahend.
	     */
	    r2++;
	}
	else if (r2->x1 <= x1)
	{
	    /*
	     * Subtrahend preceeds minuend: nuke left edge of minuend.
	     */
	    x1 = r2->x2;
	    if (x1 >= r1->x2)
	    {
		/*
		 * Minuend completely covered: advance to next minuend and
		 * reset left fence to edge of new minuend.
		 */
		r1++;
		if (r1 != r1End)
		    x1 = r1->x1;
	    }
	    else
	    {
		/*
		 * Subtrahend now used up since it doesn't extend beyond
		 * minuend
		 */
		r2++;
	    }
	}
	else if (r2->x1 < r1->x2)
	{
	    /*
	     * Left part of subtrahend covers part of minuend: add uncovered
	     * part of minuend to region and skip to next subtrahend.
	     */
	    assert(x1<r2->x1);
	    MEMCHECK(pReg, pNextRect, pReg->rects);
	    pNextRect->x1 = x1;
	    pNextRect->y1 = y1;
	    pNextRect->x2 = r2->x1;
	    pNextRect->y2 = y2;
	    pReg->numRects += 1;
	    pNextRect++;

	    assert(pReg->numRects<=pReg->size);

	    x1 = r2->x2;
	    if (x1 >= r1->x2)
	    {
		/*
		 * Minuend used up: advance to new...
		 */
		r1++;
		if (r1 != r1End)
		    x1 = r1->x1;
	    }
	    else
	    {
		/*
		 * Subtrahend used up
		 */
		r2++;
	    }
	}
	else
	{
	    /*
	     * Minuend used up: add any remaining piece before advancing.
	     */
	    if (r1->x2 > x1)
	    {
		MEMCHECK(pReg, pNextRect, pReg->rects);
		pNextRect->x1 = x1;
		pNextRect->y1 = y1;
		pNextRect->x2 = r1->x2;
		pNextRect->y2 = y2;
		pReg->numRects += 1;
		pNextRect++;
		assert(pReg->numRects<=pReg->size);
	    }
	    r1++;
            if (r1 != r1End)
              x1 = r1->x1;
	}
    }

    /*
     * Add remaining minuend rectangles to region.
     */
    while (r1 != r1End)
    {
	assert(x1<r1->x2);
	MEMCHECK(pReg, pNextRect, pReg->rects);
	pNextRect->x1 = x1;
	pNextRect->y1 = y1;
	pNextRect->x2 = r1->x2;
	pNextRect->y2 = y2;
	pReg->numRects += 1;
	pNextRect++;

	assert(pReg->numRects<=pReg->size);

	r1++;
	if (r1 != r1End)
	{
	    x1 = r1->x1;
	}
    }
    return 0;	/* lint */
}
	
/*-
 *-----------------------------------------------------------------------
 * miSubtract --
 *	Subtract regS from regM and leave the result in regD.
 *	S stands for subtrahend, M for minuend and D for difference.
 *
 * Results:
 *	TRUE.
 *
 * Side Effects:
 *	regD is overwritten.
 *
 *-----------------------------------------------------------------------
 */

int
XSubtractRegion(regM, regS, regD)
    Region 	  	regM;
    Region	  	regS;          
    register Region	regD;
{
   /* check for trivial reject */
    if ( (!(regM->numRects)) || (!(regS->numRects))  ||
	(!EXTENTCHECK(&regM->extents, &regS->extents)) )
    {
	miRegionCopy(regD, regM);
        return 1;
    }
 
    miRegionOp (regD, regM, regS, (voidProcp) miSubtractO, 
    		(voidProcp) miSubtractNonO1, (voidProcp) NULL);

    /*
     * Can't alter newReg's extents before we call miRegionOp because
     * it might be one of the source regions and miRegionOp depends
     * on the extents of those regions being the unaltered. Besides, this
     * way there's no checking against rectangles that will be nuked
     * due to coalescing, so we have to examine fewer rectangles.
     */
    miSetExtents (regD);
    return 1;
}

int
XXorRegion( sra, srb, dr )
    Region sra, srb, dr;
{
    Region tra, trb;

    if ((! (tra = XCreateRegion())) || (! (trb = XCreateRegion())))
	return 0;
    (void) XSubtractRegion(sra,srb,tra);
    (void) XSubtractRegion(srb,sra,trb);
    (void) XUnionRegion(tra,trb,dr);
    XDestroyRegion(tra);
    XDestroyRegion(trb);
    return 0;
}

/*
 * Check to see if the region is empty.  Assumes a region is passed 
 * as a parameter
 */
int 
XEmptyRegion( r )
    Region r;
{
    if( r->numRects == 0 ) return TRUE;
    else  return FALSE;
}

/*
 *	Check to see if two regions are equal	
 */
int 
XEqualRegion( r1, r2 )
    Region r1, r2;
{
    int i;

    if( r1->numRects != r2->numRects ) return FALSE;
    else if( r1->numRects == 0 ) return TRUE;
    else if ( r1->extents.x1 != r2->extents.x1 ) return FALSE;
    else if ( r1->extents.x2 != r2->extents.x2 ) return FALSE;
    else if ( r1->extents.y1 != r2->extents.y1 ) return FALSE;
    else if ( r1->extents.y2 != r2->extents.y2 ) return FALSE;
    else for( i=0; i < r1->numRects; i++ ) {
    	if ( r1->rects[i].x1 != r2->rects[i].x1 ) return FALSE;
    	else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return FALSE;
    	else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return FALSE;
    	else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return FALSE;
    }
    return TRUE;
}

int 
XPointInRegion( pRegion, x, y )
    Region pRegion;
    int x, y;
{
    int i;

    if (pRegion->numRects == 0)
        return FALSE;
    if (!INBOX(pRegion->extents, x, y))
        return FALSE;
    for (i=0; i<pRegion->numRects; i++)
    {
        if (INBOX (pRegion->rects[i], x, y))
	    return TRUE;
    }
    return FALSE;
}

int 
XRectInRegion(region, rx, ry, rwidth, rheight)
    register Region	region;
    int rx, ry;
    unsigned int rwidth, rheight;
{
    register BoxPtr pbox;
    register BoxPtr pboxEnd;
    Box rect;
    register BoxPtr prect = &rect;
    int      partIn, partOut;

    prect->x1 = rx;
    prect->y1 = ry;
    prect->x2 = rwidth + rx;
    prect->y2 = rheight + ry;
    
    /* this is (just) a useful optimization */
    if ((region->numRects == 0) || !EXTENTCHECK(&region->extents, prect))
        return(RectangleOut);

    partOut = FALSE;
    partIn = FALSE;

    /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
    for (pbox = region->rects, pboxEnd = pbox + region->numRects;
	 pbox < pboxEnd;
	 pbox++)
    {

	if (pbox->y2 <= ry)
	   continue;	/* getting up to speed or skipping remainder of band */

	if (pbox->y1 > ry)
	{
	   partOut = TRUE;	/* missed part of rectangle above */
	   if (partIn || (pbox->y1 >= prect->y2))
	      break;
	   ry = pbox->y1;	/* x guaranteed to be == prect->x1 */
	}

	if (pbox->x2 <= rx)
	   continue;		/* not far enough over yet */

	if (pbox->x1 > rx)
	{
	   partOut = TRUE;	/* missed part of rectangle to left */
	   if (partIn)
	      break;
	}

	if (pbox->x1 < prect->x2)
	{
	    partIn = TRUE;	/* definitely overlap */
	    if (partOut)
	       break;
	}

	if (pbox->x2 >= prect->x2)
	{
	   ry = pbox->y2;	/* finished with this band */
	   if (ry >= prect->y2)
	      break;
	   rx = prect->x1;	/* reset x out to left again */
	} else
	{
	    /*
	     * Because boxes in a band are maximal width, if the first box
	     * to overlap the rectangle doesn't completely cover it in that
	     * band, the rectangle must be partially out, since some of it
	     * will be uncovered in that band. partIn will have been set true
	     * by now...
	     */
	    break;
	}

    }

    return(partIn ? ((ry < prect->y2) ? RectanglePart : RectangleIn) : 
		RectangleOut);
}