regiong.cpp

来自「A*算法 A*算法 A*算法 A*算法A*算法A*算法」· C++ 代码 · 共 1,957 行 · 第 1/4 页

    {
        if (r1->x1 < r2->x1)
        {
            MERGERECT(r1);
        }
        else
        {
            MERGERECT(r2);
        }
    }

    if (r1 != r1End)
    {
        do
        {
            MERGERECT(r1);
        } while (r1 != r1End);
    }
    else while (r2 != r2End)
    {
        MERGERECT(r2);
    }
    return 0;        /* lint */
}

bool REGION::
XUnionRegion(
    Region           reg1,
    Region          reg2,             /* source regions     */
    Region           newReg)                  /* destination Region */
{
    /*  checks all the simple cases */

    /*
     * Region 1 and 2 are the same or region 1 is empty
     */
    if ( (reg1 == reg2) || (!(reg1->numRects)) )
    {
        if (newReg != reg2)
            miRegionCopy(newReg, reg2);
        return 1;
    }

    /*
     * if nothing to union (region 2 empty)
     */
    if (!(reg2->numRects))
    {
        if (newReg != reg1)
            miRegionCopy(newReg, reg1);
        return 1;
    }

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

    /*
     * 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, miUnionO,
                    miUnionNonO, miUnionNonO);

    newReg->extents.x1 = wxMin(reg1->extents.x1, reg2->extents.x1);
    newReg->extents.y1 = wxMin(reg1->extents.y1, reg2->extents.y1);
    newReg->extents.x2 = wxMax(reg1->extents.x2, reg2->extents.x2);
    newReg->extents.y2 = wxMax(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*/
int REGION::
miSubtractNonO1 (
    register Region        pReg,
    register BoxPtr        r,
    BoxPtr                    rEnd,
    register wxCoord          y1,
    register wxCoord           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*/
int REGION::
miSubtractO (
    register Region        pReg,
    register BoxPtr        r1,
    BoxPtr                    r1End,
    register BoxPtr        r2,
    BoxPtr                    r2End,
    register wxCoord          y1,
    register wxCoord          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.
 *
 *-----------------------------------------------------------------------
 */

bool REGION::
XSubtractRegion(
    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 true;
    }

    miRegionOp (regD, regM, regS, miSubtractO,
                    miSubtractNonO1, 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 true;
}

bool REGION::
XXorRegion(Region sra, Region srb, Region 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
 */
bool REGION::
XEmptyRegion(
    Region r)
{
    if( r->numRects == 0 ) return true;
    else  return false;
}

/*
 *        Check to see if two regions are equal
 */
bool REGION::
XEqualRegion(Region r1, Region 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;
}

bool REGION::
XPointInRegion(
    Region pRegion,
    int x, int 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;
}

wxRegionContain REGION::
XRectInRegion(
    register Region        region,
    int rx, int ry,
    unsigned int rwidth, unsigned int 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(wxOutRegion);

    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) ? wxPartRegion : wxInRegion) :
                wxOutRegion);
}