regiong.cpp

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

        {
        /*
         * Make sure the bands have boxes in the same places. This
         * assumes that boxes have been added in such a way that they
         * cover the most area possible. I.e. two boxes in a band must
         * have some horizontal space between them.
         */
            do
            {
                if ((pPrevBox->x1 != pCurBox->x1) ||
                    (pPrevBox->x2 != pCurBox->x2))
                {
                    /*
                     * The bands don't line up so they can't be coalesced.
                     */
                    return (curStart);
                }
                pPrevBox++;
                pCurBox++;
                prevNumRects -= 1;
            } while (prevNumRects != 0);

            pReg->numRects -= curNumRects;
            pCurBox -= curNumRects;
            pPrevBox -= curNumRects;

            /*
             * The bands may be merged, so set the bottom y of each box
             * in the previous band to that of the corresponding box in
             * the current band.
             */
            do
            {
                pPrevBox->y2 = pCurBox->y2;
                pPrevBox++;
                pCurBox++;
                curNumRects -= 1;
            } while (curNumRects != 0);

            /*
             * If only one band was added to the region, we have to backup
             * curStart to the start of the previous band.
             *
             * If more than one band was added to the region, copy the
             * other bands down. The assumption here is that the other bands
             * came from the same region as the current one and no further
             * coalescing can be done on them since it's all been done
             * already... curStart is already in the right place.
             */
            if (pCurBox == pRegEnd)
            {
                curStart = prevStart;
            }
            else
            {
                do
                {
                    *pPrevBox++ = *pCurBox++;
                } while (pCurBox != pRegEnd);
            }

        }
    }
    return (curStart);
}

/*-
 *-----------------------------------------------------------------------
 * miRegionOp --
 *        Apply an operation to two regions. Called by miUnion, miInverse,
 *        miSubtract, miIntersect...
 *
 * Results:
 *        None.
 *
 * Side Effects:
 *        The new region is overwritten.
 *
 * Notes:
 *        The idea behind this function is to view the two regions as sets.
 *        Together they cover a rectangle of area that this function divides
 *        into horizontal bands where points are covered only by one region
 *        or by both. For the first case, the nonOverlapFunc is called with
 *        each the band and the band's upper and lower extents. For the
 *        second, the overlapFunc is called to process the entire band. It
 *        is responsible for clipping the rectangles in the band, though
 *        this function provides the boundaries.
 *        At the end of each band, the new region is coalesced, if possible,
 *        to reduce the number of rectangles in the region.
 *
 *-----------------------------------------------------------------------
 */
/* static void*/
void REGION::
miRegionOp(
    register Region         newReg,                              /* Place to store result */
    Region                  reg1,                                /* First region in operation */
    Region                  reg2,                                /* 2d region in operation */
    int                      (*overlapFunc)(
        register Region     pReg,
        register BoxPtr     r1,
        BoxPtr              r1End,
        register BoxPtr     r2,
        BoxPtr              r2End,
        wxCoord               y1,
        wxCoord               y2),              /* Function to call for over-
                                                 * lapping bands */
    int                      (*nonOverlap1Func)(
        register Region     pReg,
        register BoxPtr     r,
        BoxPtr              rEnd,
        register wxCoord      y1,
        register wxCoord      y2),              /* Function to call for non-
                                                 * overlapping bands in region
                                                 * 1 */
    int                      (*nonOverlap2Func)(
        register Region     pReg,
        register BoxPtr     r,
        BoxPtr              rEnd,
        register wxCoord      y1,
        register wxCoord      y2))              /* Function to call for non-
                                                 * overlapping bands in region
                                                 * 2 */
{
    register BoxPtr        r1; /* Pointer into first region */
    register BoxPtr        r2; /* Pointer into 2d region */
    BoxPtr              r1End; /* End of 1st region */
    BoxPtr              r2End; /* End of 2d region */
    register wxCoord     ybot; /* Bottom of intersection */
    register wxCoord     ytop; /* Top of intersection */
    BoxPtr           oldRects; /* Old rects for newReg */
    int              prevBand; /* Index of start of
                                * previous band in newReg */
    int               curBand; /* Index of start of current
                                * band in newReg */
    register BoxPtr r1BandEnd; /* End of current band in r1 */
    register BoxPtr r2BandEnd; /* End of current band in r2 */
    wxCoord               top; /* Top of non-overlapping
                                * band */
    wxCoord               bot; /* Bottom of non-overlapping
                                * band */

    /*
     * Initialization:
     *        set r1, r2, r1End and r2End appropriately, preserve the important
     * parts of the destination region until the end in case it's one of
     * the two source regions, then mark the "new" region empty, allocating
     * another array of rectangles for it to use.
     */
    r1 = reg1->rects;
    r2 = reg2->rects;
    r1End = r1 + reg1->numRects;
    r2End = r2 + reg2->numRects;

    oldRects = newReg->rects;

    EMPTY_REGION(newReg);

    /*
     * Allocate a reasonable number of rectangles for the new region. The idea
     * is to allocate enough so the individual functions don't need to
     * reallocate and copy the array, which is time consuming, yet we don't
     * have to worry about using too much memory. I hope to be able to
     * nuke the realloc() at the end of this function eventually.
     */
    newReg->size = wxMax(reg1->numRects,reg2->numRects) * 2;

    if (! (newReg->rects = (BoxPtr)
           malloc ((unsigned) (sizeof(BoxRec) * newReg->size)))) {
        newReg->size = 0;
        return;
    }

    /*
     * Initialize ybot and ytop.
     * In the upcoming loop, ybot and ytop serve different functions depending
     * on whether the band being handled is an overlapping or non-overlapping
     * band.
     *         In the case of a non-overlapping band (only one of the regions
     * has points in the band), ybot is the bottom of the most recent
     * intersection and thus clips the top of the rectangles in that band.
     * ytop is the top of the next intersection between the two regions and
     * serves to clip the bottom of the rectangles in the current band.
     *        For an overlapping band (where the two regions intersect), ytop clips
     * the top of the rectangles of both regions and ybot clips the bottoms.
     */
    if (reg1->extents.y1 < reg2->extents.y1)
        ybot = reg1->extents.y1;
    else
        ybot = reg2->extents.y1;

    /*
     * prevBand serves to mark the start of the previous band so rectangles
     * can be coalesced into larger rectangles. qv. miCoalesce, above.
     * In the beginning, there is no previous band, so prevBand == curBand
     * (curBand is set later on, of course, but the first band will always
     * start at index 0). prevBand and curBand must be indices because of
     * the possible expansion, and resultant moving, of the new region's
     * array of rectangles.
     */
    prevBand = 0;

    do
    {
        curBand = newReg->numRects;

        /*
         * This algorithm proceeds one source-band (as opposed to a
         * destination band, which is determined by where the two regions
         * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
         * rectangle after the last one in the current band for their
         * respective regions.
         */
        r1BandEnd = r1;
        while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
        {
            r1BandEnd++;
        }

        r2BandEnd = r2;
        while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
        {
            r2BandEnd++;
        }

        /*
         * First handle the band that doesn't intersect, if any.
         *
         * Note that attention is restricted to one band in the
         * non-intersecting region at once, so if a region has n
         * bands between the current position and the next place it overlaps
         * the other, this entire loop will be passed through n times.
         */
        if (r1->y1 < r2->y1)
        {
            top = wxMax(r1->y1,ybot);
            bot = wxMin(r1->y2,r2->y1);

            if ((top != bot) && (nonOverlap1Func != NULL))
            {
                (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
            }

            ytop = r2->y1;
        }
        else if (r2->y1 < r1->y1)
        {
            top = wxMax(r2->y1,ybot);
            bot = wxMin(r2->y2,r1->y1);

            if ((top != bot) && (nonOverlap2Func != NULL))
            {
                (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
            }

            ytop = r1->y1;
        }
        else
        {
            ytop = r1->y1;
        }

        /*
         * If any rectangles got added to the region, try and coalesce them
         * with rectangles from the previous band. Note we could just do
         * this test in miCoalesce, but some machines incur a not
         * inconsiderable cost for function calls, so...
         */
        if (newReg->numRects != curBand)
        {
            prevBand = miCoalesce (newReg, prevBand, curBand);
        }

        /*
         * Now see if we've hit an intersecting band. The two bands only
         * intersect if ybot > ytop
         */
        ybot = wxMin(r1->y2, r2->y2);
        curBand = newReg->numRects;
        if (ybot > ytop)
        {
            (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);

        }

        if (newReg->numRects != curBand)
        {
            prevBand = miCoalesce (newReg, prevBand, curBand);
        }

        /*
         * If we've finished with a band (y2 == ybot) we skip forward
         * in the region to the next band.
         */
        if (r1->y2 == ybot)
        {
            r1 = r1BandEnd;
        }
        if (r2->y2 == ybot)
        {
            r2 = r2BandEnd;
        }
    } while ((r1 != r1End) && (r2 != r2End));

    /*
     * Deal with whichever region still has rectangles left.
     */
    curBand = newReg->numRects;
    if (r1 != r1End)
    {
        if (nonOverlap1Func != NULL)
        {
            do
            {
                r1BandEnd = r1;
                while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
                {
                    r1BandEnd++;
                }
                (* nonOverlap1Func) (newReg, r1, r1BandEnd,
                                     wxMax(r1->y1,ybot), r1->y2);
                r1 = r1BandEnd;
            } while (r1 != r1End);
        }
    }
    else if ((r2 != r2End) && (nonOverlap2Func != NULL))
    {
        do
        {
            r2BandEnd = r2;
            while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
            {
                 r2BandEnd++;
            }
            (* nonOverlap2Func) (newReg, r2, r2BandEnd,
                                wxMax(r2->y1,ybot), r2->y2);
            r2 = r2BandEnd;
        } while (r2 != r2End);
    }

    if (newReg->numRects != curBand)
    {
        (void) miCoalesce (newReg, prevBand, curBand);
    }

    /*
     * A bit of cleanup. To keep regions from growing without bound,
     * we shrink the array of rectangles to match the new number of
     * rectangles in the region. This never goes to 0, however...
     *
     * Only do this stuff if the number of rectangles allocated is more than
     * twice the number of rectangles in the region (a simple optimization...).
     */
    if (newReg->numRects < (newReg->size >> 1))
    {
        if (REGION_NOT_EMPTY(newReg))
        {
            BoxPtr prev_rects = newReg->rects;
            newReg->size = newReg->numRects;
            newReg->rects = (BoxPtr) realloc ((char *) newReg->rects,
                                   (unsigned) (sizeof(BoxRec) * newReg->size));
            if (! newReg->rects)
                newReg->rects = prev_rects;
        }
        else
        {
            /*
             * No point in doing the extra work involved in an realloc if
             * the region is empty
             */
            newReg->size = 1;
            free((char *) newReg->rects);
            newReg->rects = (BoxPtr) malloc(sizeof(BoxRec));
        }
    }
    free ((char *) oldRects);
    return;
}

/*======================================================================
 *            Region Union
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * miUnionNonO --
 *        Handle a non-overlapping band for the union operation. Just
 *        Adds the rectangles into the region. Doesn't have to check for
 *        subsumption or anything.
 *
 * Results:
 *        None.
 *
 * Side Effects:
 *        pReg->numRects is incremented and the final rectangles overwritten
 *        with the rectangles we're passed.
 *
 *-----------------------------------------------------------------------
 */
/* static void*/
int REGION::
miUnionNonO (
    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 */
}


/*-
 *-----------------------------------------------------------------------
 * miUnionO --
 *        Handle an overlapping band for the union operation. Picks the
 *        left-most rectangle each time and merges it into the region.
 *
 * Results:
 *        None.
 *
 * Side Effects:
 *        Rectangles are overwritten in pReg->rects and pReg->numRects will
 *        be changed.
 *
 *-----------------------------------------------------------------------
 */

/* static void*/
int REGION::
miUnionO (
    register Region        pReg,
    register BoxPtr        r1,
    BoxPtr                 r1End,
    register BoxPtr        r2,
    BoxPtr                 r2End,
    register wxCoord       y1,
    register wxCoord       y2)
{
    register BoxPtr        pNextRect;

    pNextRect = &pReg->rects[pReg->numRects];

#define MERGERECT(r) \
    if ((pReg->numRects != 0) &&  \
        (pNextRect[-1].y1 == y1) &&  \
        (pNextRect[-1].y2 == y2) &&  \
        (pNextRect[-1].x2 >= r->x1))  \
    {  \
        if (pNextRect[-1].x2 < r->x2)  \
        {  \
            pNextRect[-1].x2 = r->x2;  \
            assert(pNextRect[-1].x1<pNextRect[-1].x2); \
        }  \
    }  \
    else  \
    {  \
        MEMCHECK(pReg, pNextRect, pReg->rects);  \
        pNextRect->y1 = y1;  \
        pNextRect->y2 = y2;  \
        pNextRect->x1 = r->x1;  \
        pNextRect->x2 = r->x2;  \
        pReg->numRects += 1;  \
        pNextRect += 1;  \
    }  \
    assert(pReg->numRects<=pReg->size);\
    r++;

    assert (y1<y2);
    while ((r1 != r1End) && (r2 != r2End))