miregion.c

远程桌面连接工具

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

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

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

        if (pbox->x1 > x)
        {
           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)
        {
           y = pbox->y2;        /* finished with this band */
           if (y >= prect->y2)
              break;
           x = 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...
	     */
	    partOut = TRUE;
	    break;
	}
    }

    return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
}

/* TranslateRegion(pReg, x, y)
   translates in place
*/

void
miTranslateRegion(pReg, x, y)
    register RegionPtr pReg;
    register int x;
    register int y;
{
    int x1, x2, y1, y2;
    register int nbox;
    register BoxPtr pbox;

    good(pReg);
    pReg->extents.x1 = x1 = pReg->extents.x1 + x;
    pReg->extents.y1 = y1 = pReg->extents.y1 + y;
    pReg->extents.x2 = x2 = pReg->extents.x2 + x;
    pReg->extents.y2 = y2 = pReg->extents.y2 + y;
    if (((x1 - MINSHORT)|(y1 - MINSHORT)|(MAXSHORT - x2)|(MAXSHORT - y2)) >= 0)
    {
	if (pReg->data && (nbox = pReg->data->numRects))
	{
	    for (pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
	    {
		pbox->x1 += x;
		pbox->y1 += y;
		pbox->x2 += x;
		pbox->y2 += y;
	    }
	}
	return;
    }
    if (((x2 - MINSHORT)|(y2 - MINSHORT)|(MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
    {
	pReg->extents.x2 = pReg->extents.x1;
	pReg->extents.y2 = pReg->extents.y1;
	xfreeData(pReg);
	pReg->data = &miEmptyData;
	return;
    }
    if (x1 < MINSHORT)
	pReg->extents.x1 = MINSHORT;
    else if (x2 > MAXSHORT)
	pReg->extents.x2 = MAXSHORT;
    if (y1 < MINSHORT)
	pReg->extents.y1 = MINSHORT;
    else if (y2 > MAXSHORT)
	pReg->extents.y2 = MAXSHORT;
    if (pReg->data && (nbox = pReg->data->numRects))
    {
	register BoxPtr pboxout;

	for (pboxout = pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
	{
	    pboxout->x1 = x1 = pbox->x1 + x;
	    pboxout->y1 = y1 = pbox->y1 + y;
	    pboxout->x2 = x2 = pbox->x2 + x;
	    pboxout->y2 = y2 = pbox->y2 + y;
	    if (((x2 - MINSHORT)|(y2 - MINSHORT)|
		 (MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
	    {
		pReg->data->numRects--;
		continue;
	    }
	    if (x1 < MINSHORT)
		pboxout->x1 = MINSHORT;
	    else if (x2 > MAXSHORT)
		pboxout->x2 = MAXSHORT;
	    if (y1 < MINSHORT)
		pboxout->y1 = MINSHORT;
	    else if (y2 > MAXSHORT)
		pboxout->y2 = MAXSHORT;
	    pboxout++;
	}
	if (pboxout != pbox)
	{
	    if (pReg->data->numRects == 1)
	    {
		pReg->extents = *REGION_BOXPTR(pReg);
		xfreeData(pReg);
		pReg->data = (RegDataPtr)NULL;
	    }
	    else
		miSetExtents(pReg);
	}
    }
}

void
miRegionReset(pReg, pBox)
    RegionPtr pReg;
    BoxPtr pBox;
{
    good(pReg);
    assert(pBox->x1<=pBox->x2);
    assert(pBox->y1<=pBox->y2);
    pReg->extents = *pBox;
    xfreeData(pReg);
    pReg->data = (RegDataPtr)NULL;
}

Bool
miPointInRegion(pReg, x, y, box)
    register RegionPtr pReg;
    register int x, y;
    BoxPtr box;     /* "return" value */
{
    register BoxPtr pbox, pboxEnd;
    int numRects;

    good(pReg);
    numRects = REGION_NUM_RECTS(pReg);
    if (!numRects || !INBOX(&pReg->extents, x, y))
        return(FALSE);
    if (numRects == 1)
    {
	*box = pReg->extents;
	return(TRUE);
    }
    for (pbox = REGION_BOXPTR(pReg), pboxEnd = pbox + numRects;
	 pbox != pboxEnd;
	 pbox++)
    {
        if (y >= pbox->y2)
	   continue;		/* not there yet */
	if ((y < pbox->y1) || (x < pbox->x1))
	   break;		/* missed it */
	if (x >= pbox->x2)
	   continue;		/* not there yet */
	*box = *pbox;
	return(TRUE);
    }
    return(FALSE);
}

Bool
miRegionNotEmpty(pReg)
    RegionPtr pReg;
{
    good(pReg);
    return(!REGION_NIL(pReg));
}


void
miRegionEmpty(pReg)
    RegionPtr pReg;
{
    good(pReg);
    xfreeData(pReg);
    pReg->extents.x2 = pReg->extents.x1;
    pReg->extents.y2 = pReg->extents.y1;
    pReg->data = &miEmptyData;
}

BoxPtr
miRegionExtents(pReg)
    RegionPtr pReg;
{
    good(pReg);
    return(&pReg->extents);
}

#define ExchangeSpans(a, b)				    \
{							    \
    DDXPointRec     tpt;				    \
    register int    tw;					    \
							    \
    tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt;    \
    tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
}

/* ||| I should apply the merge sort code to rectangle sorting above, and see
   if mapping time can be improved.  But right now I've been at work 12 hours,
   so forget it.
*/

static void QuickSortSpans(spans, widths, numSpans)
    register DDXPointRec    spans[];
    register int	    widths[];
    register int	    numSpans;
{
    register int	    y;
    register int	    i, j, m;
    register DDXPointPtr    r;

    /* Always called with numSpans > 1 */
    /* Sorts only by y, doesn't bother to sort by x */

    do
    {
	if (numSpans < 9)
	{
	    /* Do insertion sort */
	    register int yprev;

	    yprev = spans[0].y;
	    i = 1;
	    do
	    { /* while i != numSpans */
		y = spans[i].y;
		if (yprev > y)
		{
		    /* spans[i] is out of order.  Move into proper location. */
		    DDXPointRec tpt;
		    int	    tw, k;

		    for (j = 0; y >= spans[j].y; j++) {}
		    tpt = spans[i];
		    tw  = widths[i];
		    for (k = i; k != j; k--)
		    {
			spans[k] = spans[k-1];
			widths[k] = widths[k-1];
		    }
		    spans[j] = tpt;
		    widths[j] = tw;
		    y = spans[i].y;
		} /* if out of order */
		yprev = y;
		i++;
	    } while (i != numSpans);
	    return;
	}

	/* Choose partition element, stick in location 0 */
	m = numSpans / 2;
	if (spans[m].y > spans[0].y)		ExchangeSpans(m, 0);
	if (spans[m].y > spans[numSpans-1].y)   ExchangeSpans(m, numSpans-1);
	if (spans[m].y > spans[0].y)		ExchangeSpans(m, 0);
	y = spans[0].y;

        /* Partition array */
        i = 0;
        j = numSpans;
        do
	{
	    r = &(spans[i]);
	    do
	    {
		r++;
		i++;
            } while (i != numSpans && r->y < y);
	    r = &(spans[j]);
	    do
	    {
		r--;
		j--;
            } while (y < r->y);
            if (i < j)
		ExchangeSpans(i, j);
        } while (i < j);

        /* Move partition element back to middle */
        ExchangeSpans(0, j);

	/* Recurse */
        if (numSpans-j-1 > 1)
	    QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
        numSpans = j;
    } while (numSpans > 1);
}

#define NextBand()						    \
{								    \
    clipy1 = pboxBandStart->y1;					    \
    clipy2 = pboxBandStart->y2;					    \
    pboxBandEnd = pboxBandStart + 1;				    \
    while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) {  \
	pboxBandEnd++;						    \
    }								    \
    for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
}

/*
    Clip a list of scanlines to a region.  The caller has allocated the
    space.  FSorted is non-zero if the scanline origins are in ascending
    order.
    returns the number of new, clipped scanlines.
*/

int
miClipSpans(prgnDst, ppt, pwidth, nspans, pptNew, pwidthNew, fSorted)
    RegionPtr		    prgnDst;
    register DDXPointPtr    ppt;
    register int	    *pwidth;
    int			    nspans;
    register DDXPointPtr    pptNew;
    int			    *pwidthNew;
    int			    fSorted;
{
    register DDXPointPtr pptLast;
    int			*pwidthNewStart;	/* the vengeance of Xerox! */
    register int	y, x1, x2;
    register int	numRects;

    good(prgnDst);
    pptLast = ppt + nspans;
    pwidthNewStart = pwidthNew;

    if (!prgnDst->data)
    {
	/* Do special fast code with clip boundaries in registers(?) */
	/* It doesn't pay much to make use of fSorted in this case, 
	   so we lump everything together. */

	register    int clipx1, clipx2, clipy1, clipy2;

	clipx1 = prgnDst->extents.x1;
	clipy1 = prgnDst->extents.y1;
	clipx2 = prgnDst->extents.x2;
	clipy2 = prgnDst->extents.y2;
	    
	for (; ppt != pptLast; ppt++, pwidth++)
	{
	    y = ppt->y;
	    x1 = ppt->x;
	    if (clipy1 <= y && y < clipy2)
	    {
		x2 = x1 + *pwidth;
		if (x1 < clipx1)    x1 = clipx1;
		if (x2 > clipx2)    x2 = clipx2;
		if (x1 < x2)
		{
		    /* part of span in clip rectangle */
		    pptNew->x = x1;
		    pptNew->y = y;
		    *pwidthNew = x2 - x1;
		    pptNew++;
		    pwidthNew++;
		}
	    }
	} /* end for */

    }
    else if (numRects = prgnDst->data->numRects)
    {
	/* Have to clip against many boxes */
	BoxPtr		pboxBandStart, pboxBandEnd;
	register BoxPtr pbox;
	register BoxPtr pboxLast;
	register int	clipy1, clipy2;

	/* In this case, taking advantage of sorted spans gains more than
	   the sorting costs. */
	if ((! fSorted) && (nspans > 1))
	    QuickSortSpans(ppt, pwidth, nspans);

	pboxBandStart = REGION_BOXPTR(prgnDst);
	pboxLast = pboxBandStart + numRects;
    
	NextBand();

	for (; ppt != pptLast; )
	{
	    y = ppt->y;
	    if (y < clipy2)
	    {
		/* span is in the current band */
		pbox = pboxBandStart;
		x1 = ppt->x;
		x2 = x1 + *pwidth;
		do
		{ /* For each box in band */
		    register int    newx1, newx2;

		    newx1 = x1;
		    newx2 = x2;
		    if (newx1 < pbox->x1)   newx1 = pbox->x1;
		    if (newx2 > pbox->x2)   newx2 = pbox->x2;
		    if (newx1 < newx2)
		    {
			/* Part of span in clip rectangle */
			pptNew->x = newx1;
			pptNew->y = y;
			*pwidthNew = newx2 - newx1;
			pptNew++;
			pwidthNew++;
		    }
		    pbox++;
		} while (pbox != pboxBandEnd);
		ppt++;
		pwidth++;
	    }
	    else
	    {
		/* Move to next band, adjust ppt as needed */
		pboxBandStart = pboxBandEnd;
		if (pboxBandStart == pboxLast)
		    break; /* We're completely done */
		NextBand();
	    }
	}
    }
    return (pwidthNew - pwidthNewStart);
}

/* find the band in a region with the most rectangles */
int
miFindMaxBand(prgn)
    RegionPtr prgn;
{
    register int nbox;
    register BoxPtr pbox;
    register int nThisBand;
    register int nMaxBand = 0;
    short yThisBand;

    good(prgn);
    nbox = REGION_NUM_RECTS(prgn);
    pbox = REGION_RECTS(prgn);

    while(nbox > 0)
    {
	yThisBand = pbox->y1;
	nThisBand = 0;
	while((nbox > 0) && (pbox->y1 == yThisBand))
	{
	    nbox--;
	    pbox++;
	    nThisBand++;
	}
	if (nThisBand > nMaxBand)
	    nMaxBand = nThisBand;
    }
    return (nMaxBand);
}