1 /* $TOG: Region.c /main/31 1998/02/06 17:50:22 kaleb $ */
2 /************************************************************************
4 Copyright 1987, 1988, 1998 The Open Group
8 The above copyright notice and this permission notice shall be included in
9 all copies or substantial portions of the Software.
11 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
12 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
13 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
14 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
15 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
16 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18 Except as contained in this notice, the name of The Open Group shall not be
19 used in advertising or otherwise to promote the sale, use or other dealings
20 in this Software without prior written authorization from The Open Group.
23 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
27 Permission to use, copy, modify, and distribute this software and its
28 documentation for any purpose and without fee is hereby granted,
29 provided that the above copyright notice appear in all copies and that
30 both that copyright notice and this permission notice appear in
31 supporting documentation, and that the name of Digital not be
32 used in advertising or publicity pertaining to distribution of the
33 software without specific, written prior permission.
35 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
36 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
37 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
38 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
39 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
40 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
43 ************************************************************************/
44 /* $XFree86: xc/lib/X11/Region.c,v 1.5 1999/05/09 10:50:01 dawes Exp $ */
46 * The functions in this file implement the Region abstraction, similar to one
47 * used in the X11 sample server. A Region is simply an area, as the name
48 * implies, and is implemented as a "y-x-banded" array of rectangles. To
49 * explain: Each Region is made up of a certain number of rectangles sorted
50 * by y coordinate first, and then by x coordinate.
52 * Furthermore, the rectangles are banded such that every rectangle with a
53 * given upper-left y coordinate (y1) will have the same lower-right y
54 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
55 * will span the entire vertical distance of the band. This means that some
56 * areas that could be merged into a taller rectangle will be represented as
57 * several shorter rectangles to account for shorter rectangles to its left
58 * or right but within its "vertical scope".
60 * An added constraint on the rectangles is that they must cover as much
61 * horizontal area as possible. E.g. no two rectangles in a band are allowed
64 * Whenever possible, bands will be merged together to cover a greater vertical
65 * distance (and thus reduce the number of rectangles). Two bands can be merged
66 * only if the bottom of one touches the top of the other and they have
67 * rectangles in the same places (of the same width, of course). This maintains
68 * the y-x-banding that's so nice to have...
71 #include <gdkregion.h>
72 #include "gdkregion-generic.h"
76 #define assert(expr) {if (!(expr)) fprintf(stderr,\
77 "Assertion failed file %s, line %d: expr\n", __FILE__, __LINE__); }
82 typedef void (*overlapFunc) (GdkRegion *pReg,
89 typedef void (*nonOverlapFunc) (GdkRegion *pReg,
95 static void miRegionCopy (GdkRegion *dstrgn,
97 static void miRegionOp (GdkRegion *newReg,
100 overlapFunc overlapFn,
101 nonOverlapFunc nonOverlap1Fn,
102 nonOverlapFunc nonOverlap2Fn);
104 /* Create a new empty region */
111 temp = g_new (GdkRegion, 1);
112 temp->rects = g_new (GdkRegionBox, 1);
115 temp->extents.x1 = 0;
116 temp->extents.y1 = 0;
117 temp->extents.x2 = 0;
118 temp->extents.y2 = 0;
125 gdk_region_rectangle (GdkRectangle *rectangle)
129 if (rectangle->width <= 0 || rectangle->height <= 0)
130 return gdk_region_new();
132 temp = g_new (GdkRegion, 1);
133 temp->rects = g_new (GdkRegionBox, 1);
136 temp->extents.x1 = temp->rects[0].x1 = rectangle->x;
137 temp->extents.y1 = temp->rects[0].y1 = rectangle->y;
138 temp->extents.x2 = temp->rects[0].x2 = rectangle->x + rectangle->width;
139 temp->extents.y2 = temp->rects[0].y2 = rectangle->y + rectangle->height;
146 gdk_region_copy (GdkRegion *region)
150 temp = g_new (GdkRegion, 1);
151 temp->rects = g_new (GdkRegionBox, region->numRects);
153 temp->numRects = region->numRects;
154 temp->extents = region->extents;
155 temp->size = region->numRects;
157 memcpy (temp->rects, region->rects, region->numRects * sizeof (GdkRegionBox));
163 gdk_region_get_clipbox (GdkRegion *r, GdkRectangle *rect)
165 rect->x = r->extents.x1;
166 rect->y = r->extents.y1;
167 rect->width = r->extents.x2 - r->extents.x1;
168 rect->height = r->extents.y2 - r->extents.y1;
172 gdk_region_union_with_rect (GdkRegion *region,
175 GdkRegion tmp_region;
177 if (!rect->width || !rect->height)
180 tmp_region.rects = &tmp_region.extents;
181 tmp_region.numRects = 1;
182 tmp_region.extents.x1 = rect->x;
183 tmp_region.extents.y1 = rect->y;
184 tmp_region.extents.x2 = rect->x + rect->width;
185 tmp_region.extents.y2 = rect->y + rect->height;
188 gdk_region_union (region, &tmp_region);
192 *-----------------------------------------------------------------------
194 * Reset the extents of a region to what they should be. Called by
195 * miSubtract and miIntersect b/c they can't figure it out along the
196 * way or do so easily, as miUnion can.
202 * The region's 'extents' structure is overwritten.
204 *-----------------------------------------------------------------------
207 miSetExtents (GdkRegion *pReg)
209 GdkRegionBox *pBox, *pBoxEnd, *pExtents;
211 if (pReg->numRects == 0)
213 pReg->extents.x1 = 0;
214 pReg->extents.y1 = 0;
215 pReg->extents.x2 = 0;
216 pReg->extents.y2 = 0;
220 pExtents = &pReg->extents;
222 pBoxEnd = &pBox[pReg->numRects - 1];
225 * Since pBox is the first rectangle in the region, it must have the
226 * smallest y1 and since pBoxEnd is the last rectangle in the region,
227 * it must have the largest y2, because of banding. Initialize x1 and
228 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
231 pExtents->x1 = pBox->x1;
232 pExtents->y1 = pBox->y1;
233 pExtents->x2 = pBoxEnd->x2;
234 pExtents->y2 = pBoxEnd->y2;
236 assert(pExtents->y1 < pExtents->y2);
237 while (pBox <= pBoxEnd)
239 if (pBox->x1 < pExtents->x1)
241 pExtents->x1 = pBox->x1;
243 if (pBox->x2 > pExtents->x2)
245 pExtents->x2 = pBox->x2;
249 assert(pExtents->x1 < pExtents->x2);
253 gdk_region_destroy (GdkRegion *r)
260 /* TranslateRegion(pRegion, x, y)
266 gdk_region_offset (GdkRegion *region,
273 pbox = region->rects;
274 nbox = region->numRects;
284 region->extents.x1 += x;
285 region->extents.x2 += x;
286 region->extents.y1 += y;
287 region->extents.y2 += y;
291 Utility procedure Compress:
292 Replace r by the region r', where
293 p in r' iff (Quantifer m <= dx) (p + m in r), and
294 Quantifier is Exists if grow is TRUE, For all if grow is FALSE, and
295 (x,y) + m = (x+m,y) if xdir is TRUE; (x,y+m) if xdir is FALSE.
297 Thus, if xdir is TRUE and grow is FALSE, r is replaced by the region
298 of all points p such that p and the next dx points on the same
299 horizontal scan line are all in r. We do this using by noting
300 that p is the head of a run of length 2^i + k iff p is the head
301 of a run of length 2^i and p+2^i is the head of a run of length
302 k. Thus, the loop invariant: s contains the region corresponding
303 to the runs of length shift. r contains the region corresponding
304 to the runs of length 1 + dxo & (shift-1), where dxo is the original
305 value of dx. dx = dxo & ~(shift-1). As parameters, s and t are
306 scratch regions, so that we don't have to allocate them on every
310 #define ZOpRegion(a,b) if (grow) gdk_region_union (a, b); \
311 else gdk_region_intersect (a,b)
312 #define ZShiftRegion(a,b) if (xdir) gdk_region_offset (a,b,0); \
313 else gdk_region_offset (a,0,b)
316 Compress(GdkRegion *r,
330 ZShiftRegion(r, -(int)shift);
336 ZShiftRegion(s, -(int)shift);
347 gdk_region_shrink (GdkRegion *r,
357 s = gdk_region_new ();
358 t = gdk_region_new ();
364 Compress(r, s, t, (unsigned) 2*dx, TRUE, grow);
370 Compress(r, s, t, (unsigned) 2*dy, FALSE, grow);
372 gdk_region_offset (r, dx, dy);
373 gdk_region_destroy (s);
374 gdk_region_destroy (t);
378 /*======================================================================
379 * Region Intersection
380 *====================================================================*/
382 *-----------------------------------------------------------------------
384 * Handle an overlapping band for miIntersect.
390 * Rectangles may be added to the region.
392 *-----------------------------------------------------------------------
396 miIntersectO (GdkRegion *pReg,
406 GdkRegionBox *pNextRect;
408 pNextRect = &pReg->rects[pReg->numRects];
410 while ((r1 != r1End) && (r2 != r2End))
412 x1 = MAX (r1->x1,r2->x1);
413 x2 = MIN (r1->x2,r2->x2);
416 * If there's any overlap between the two rectangles, add that
417 * overlap to the new region.
418 * There's no need to check for subsumption because the only way
419 * such a need could arise is if some region has two rectangles
420 * right next to each other. Since that should never happen...
426 MEMCHECK (pReg, pNextRect, pReg->rects);
433 assert (pReg->numRects <= pReg->size);
437 * Need to advance the pointers. Shift the one that extends
438 * to the right the least, since the other still has a chance to
439 * overlap with that region's next rectangle, if you see what I mean.
445 else if (r2->x2 < r1->x2)
458 gdk_region_intersect (GdkRegion *region,
461 /* check for trivial reject */
462 if ((!(region->numRects)) || (!(other->numRects)) ||
463 (!EXTENTCHECK(®ion->extents, &other->extents)))
464 region->numRects = 0;
466 miRegionOp (region, region, other,
467 miIntersectO, (nonOverlapFunc) NULL, (nonOverlapFunc) NULL);
470 * Can't alter region's extents before miRegionOp depends on the
471 * extents of the regions being unchanged. Besides, this way there's
472 * no checking against rectangles that will be nuked due to
473 * coalescing, so we have to examine fewer rectangles.
475 miSetExtents(region);
479 miRegionCopy(GdkRegion *dstrgn, GdkRegion *rgn)
481 if (dstrgn != rgn) /* don't want to copy to itself */
483 if (dstrgn->size < rgn->numRects)
485 dstrgn->rects = g_renew (GdkRegionBox, dstrgn->rects, rgn->numRects);
486 dstrgn->size = rgn->numRects;
488 dstrgn->numRects = rgn->numRects;
489 dstrgn->extents.x1 = rgn->extents.x1;
490 dstrgn->extents.y1 = rgn->extents.y1;
491 dstrgn->extents.x2 = rgn->extents.x2;
492 dstrgn->extents.y2 = rgn->extents.y2;
494 memcpy (dstrgn->rects, rgn->rects, rgn->numRects * sizeof (GdkRegionBox));
499 /*======================================================================
500 * Generic Region Operator
501 *====================================================================*/
504 *-----------------------------------------------------------------------
506 * Attempt to merge the boxes in the current band with those in the
507 * previous one. Used only by miRegionOp.
510 * The new index for the previous band.
513 * If coalescing takes place:
514 * - rectangles in the previous band will have their y2 fields
516 * - pReg->numRects will be decreased.
518 *-----------------------------------------------------------------------
522 miCoalesce (GdkRegion *pReg, /* Region to coalesce */
523 gint prevStart, /* Index of start of previous band */
524 gint curStart) /* Index of start of current band */
526 GdkRegionBox *pPrevBox; /* Current box in previous band */
527 GdkRegionBox *pCurBox; /* Current box in current band */
528 GdkRegionBox *pRegEnd; /* End of region */
529 int curNumRects; /* Number of rectangles in current
531 int prevNumRects; /* Number of rectangles in previous
533 int bandY1; /* Y1 coordinate for current band */
535 pRegEnd = &pReg->rects[pReg->numRects];
537 pPrevBox = &pReg->rects[prevStart];
538 prevNumRects = curStart - prevStart;
541 * Figure out how many rectangles are in the current band. Have to do
542 * this because multiple bands could have been added in miRegionOp
543 * at the end when one region has been exhausted.
545 pCurBox = &pReg->rects[curStart];
546 bandY1 = pCurBox->y1;
547 for (curNumRects = 0;
548 (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
554 if (pCurBox != pRegEnd)
557 * If more than one band was added, we have to find the start
558 * of the last band added so the next coalescing job can start
559 * at the right place... (given when multiple bands are added,
560 * this may be pointless -- see above).
563 while (pRegEnd[-1].y1 == pRegEnd->y1)
567 curStart = pRegEnd - pReg->rects;
568 pRegEnd = pReg->rects + pReg->numRects;
571 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
572 pCurBox -= curNumRects;
574 * The bands may only be coalesced if the bottom of the previous
575 * matches the top scanline of the current.
577 if (pPrevBox->y2 == pCurBox->y1)
580 * Make sure the bands have boxes in the same places. This
581 * assumes that boxes have been added in such a way that they
582 * cover the most area possible. I.e. two boxes in a band must
583 * have some horizontal space between them.
587 if ((pPrevBox->x1 != pCurBox->x1) ||
588 (pPrevBox->x2 != pCurBox->x2))
591 * The bands don't line up so they can't be coalesced.
598 } while (prevNumRects != 0);
600 pReg->numRects -= curNumRects;
601 pCurBox -= curNumRects;
602 pPrevBox -= curNumRects;
605 * The bands may be merged, so set the bottom y of each box
606 * in the previous band to that of the corresponding box in
611 pPrevBox->y2 = pCurBox->y2;
616 while (curNumRects != 0);
619 * If only one band was added to the region, we have to backup
620 * curStart to the start of the previous band.
622 * If more than one band was added to the region, copy the
623 * other bands down. The assumption here is that the other bands
624 * came from the same region as the current one and no further
625 * coalescing can be done on them since it's all been done
626 * already... curStart is already in the right place.
628 if (pCurBox == pRegEnd)
630 curStart = prevStart;
636 *pPrevBox++ = *pCurBox++;
638 while (pCurBox != pRegEnd);
647 *-----------------------------------------------------------------------
649 * Apply an operation to two regions. Called by miUnion, miInverse,
650 * miSubtract, miIntersect...
656 * The new region is overwritten.
659 * The idea behind this function is to view the two regions as sets.
660 * Together they cover a rectangle of area that this function divides
661 * into horizontal bands where points are covered only by one region
662 * or by both. For the first case, the nonOverlapFunc is called with
663 * each the band and the band's upper and lower extents. For the
664 * second, the overlapFunc is called to process the entire band. It
665 * is responsible for clipping the rectangles in the band, though
666 * this function provides the boundaries.
667 * At the end of each band, the new region is coalesced, if possible,
668 * to reduce the number of rectangles in the region.
670 *-----------------------------------------------------------------------
674 miRegionOp(GdkRegion *newReg,
677 overlapFunc overlapFn, /* Function to call for over-
679 nonOverlapFunc nonOverlap1Fn, /* Function to call for non-
680 * overlapping bands in region
682 nonOverlapFunc nonOverlap2Fn) /* Function to call for non-
683 * overlapping bands in region
686 GdkRegionBox *r1; /* Pointer into first region */
687 GdkRegionBox *r2; /* Pointer into 2d region */
688 GdkRegionBox *r1End; /* End of 1st region */
689 GdkRegionBox *r2End; /* End of 2d region */
690 int ybot; /* Bottom of intersection */
691 int ytop; /* Top of intersection */
692 GdkRegionBox *oldRects; /* Old rects for newReg */
693 int prevBand; /* Index of start of
694 * previous band in newReg */
695 int curBand; /* Index of start of current
697 GdkRegionBox *r1BandEnd; /* End of current band in r1 */
698 GdkRegionBox *r2BandEnd; /* End of current band in r2 */
699 int top; /* Top of non-overlapping
701 int bot; /* Bottom of non-overlapping
706 * set r1, r2, r1End and r2End appropriately, preserve the important
707 * parts of the destination region until the end in case it's one of
708 * the two source regions, then mark the "new" region empty, allocating
709 * another array of rectangles for it to use.
713 r1End = r1 + reg1->numRects;
714 r2End = r2 + reg2->numRects;
716 oldRects = newReg->rects;
718 EMPTY_REGION(newReg);
721 * Allocate a reasonable number of rectangles for the new region. The idea
722 * is to allocate enough so the individual functions don't need to
723 * reallocate and copy the array, which is time consuming, yet we don't
724 * have to worry about using too much memory. I hope to be able to
725 * nuke the Xrealloc() at the end of this function eventually.
727 newReg->size = MAX (reg1->numRects, reg2->numRects) * 2;
728 newReg->rects = g_new (GdkRegionBox, newReg->size);
731 * Initialize ybot and ytop.
732 * In the upcoming loop, ybot and ytop serve different functions depending
733 * on whether the band being handled is an overlapping or non-overlapping
735 * In the case of a non-overlapping band (only one of the regions
736 * has points in the band), ybot is the bottom of the most recent
737 * intersection and thus clips the top of the rectangles in that band.
738 * ytop is the top of the next intersection between the two regions and
739 * serves to clip the bottom of the rectangles in the current band.
740 * For an overlapping band (where the two regions intersect), ytop clips
741 * the top of the rectangles of both regions and ybot clips the bottoms.
743 if (reg1->extents.y1 < reg2->extents.y1)
744 ybot = reg1->extents.y1;
746 ybot = reg2->extents.y1;
749 * prevBand serves to mark the start of the previous band so rectangles
750 * can be coalesced into larger rectangles. qv. miCoalesce, above.
751 * In the beginning, there is no previous band, so prevBand == curBand
752 * (curBand is set later on, of course, but the first band will always
753 * start at index 0). prevBand and curBand must be indices because of
754 * the possible expansion, and resultant moving, of the new region's
755 * array of rectangles.
761 curBand = newReg->numRects;
764 * This algorithm proceeds one source-band (as opposed to a
765 * destination band, which is determined by where the two regions
766 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
767 * rectangle after the last one in the current band for their
768 * respective regions.
771 while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
777 while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
783 * First handle the band that doesn't intersect, if any.
785 * Note that attention is restricted to one band in the
786 * non-intersecting region at once, so if a region has n
787 * bands between the current position and the next place it overlaps
788 * the other, this entire loop will be passed through n times.
792 top = MAX (r1->y1,ybot);
793 bot = MIN (r1->y2,r2->y1);
795 if ((top != bot) && (nonOverlap1Fn != (void (*)())NULL))
797 (* nonOverlap1Fn) (newReg, r1, r1BandEnd, top, bot);
802 else if (r2->y1 < r1->y1)
804 top = MAX (r2->y1,ybot);
805 bot = MIN (r2->y2,r1->y1);
807 if ((top != bot) && (nonOverlap2Fn != (void (*)())NULL))
809 (* nonOverlap2Fn) (newReg, r2, r2BandEnd, top, bot);
820 * If any rectangles got added to the region, try and coalesce them
821 * with rectangles from the previous band. Note we could just do
822 * this test in miCoalesce, but some machines incur a not
823 * inconsiderable cost for function calls, so...
825 if (newReg->numRects != curBand)
827 prevBand = miCoalesce (newReg, prevBand, curBand);
831 * Now see if we've hit an intersecting band. The two bands only
832 * intersect if ybot > ytop
834 ybot = MIN (r1->y2, r2->y2);
835 curBand = newReg->numRects;
838 (* overlapFn) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
842 if (newReg->numRects != curBand)
844 prevBand = miCoalesce (newReg, prevBand, curBand);
848 * If we've finished with a band (y2 == ybot) we skip forward
849 * in the region to the next band.
859 } while ((r1 != r1End) && (r2 != r2End));
862 * Deal with whichever region still has rectangles left.
864 curBand = newReg->numRects;
867 if (nonOverlap1Fn != (nonOverlapFunc )NULL)
872 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
876 (* nonOverlap1Fn) (newReg, r1, r1BandEnd,
877 MAX (r1->y1,ybot), r1->y2);
879 } while (r1 != r1End);
882 else if ((r2 != r2End) && (nonOverlap2Fn != (nonOverlapFunc) NULL))
887 while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
891 (* nonOverlap2Fn) (newReg, r2, r2BandEnd,
892 MAX (r2->y1,ybot), r2->y2);
894 } while (r2 != r2End);
897 if (newReg->numRects != curBand)
899 (void) miCoalesce (newReg, prevBand, curBand);
903 * A bit of cleanup. To keep regions from growing without bound,
904 * we shrink the array of rectangles to match the new number of
905 * rectangles in the region. This never goes to 0, however...
907 * Only do this stuff if the number of rectangles allocated is more than
908 * twice the number of rectangles in the region (a simple optimization...).
910 if (newReg->numRects < (newReg->size >> 1))
912 if (REGION_NOT_EMPTY (newReg))
914 newReg->size = newReg->numRects;
915 newReg->rects = g_renew (GdkRegionBox, newReg->rects, newReg->size);
920 * No point in doing the extra work involved in an Xrealloc if
921 * the region is empty
924 g_free (newReg->rects);
925 newReg->rects = g_new (GdkRegionBox, 1);
932 /*======================================================================
934 *====================================================================*/
937 *-----------------------------------------------------------------------
939 * Handle a non-overlapping band for the union operation. Just
940 * Adds the rectangles into the region. Doesn't have to check for
941 * subsumption or anything.
947 * pReg->numRects is incremented and the final rectangles overwritten
948 * with the rectangles we're passed.
950 *-----------------------------------------------------------------------
953 miUnionNonO (GdkRegion *pReg,
959 GdkRegionBox *pNextRect;
961 pNextRect = &pReg->rects[pReg->numRects];
967 assert(r->x1 < r->x2);
968 MEMCHECK(pReg, pNextRect, pReg->rects);
969 pNextRect->x1 = r->x1;
971 pNextRect->x2 = r->x2;
976 assert(pReg->numRects<=pReg->size);
983 *-----------------------------------------------------------------------
985 * Handle an overlapping band for the union operation. Picks the
986 * left-most rectangle each time and merges it into the region.
992 * Rectangles are overwritten in pReg->rects and pReg->numRects will
995 *-----------------------------------------------------------------------
1000 miUnionO (GdkRegion *pReg,
1002 GdkRegionBox *r1End,
1004 GdkRegionBox *r2End,
1008 GdkRegionBox * pNextRect;
1010 pNextRect = &pReg->rects[pReg->numRects];
1012 #define MERGERECT(r) \
1013 if ((pReg->numRects != 0) && \
1014 (pNextRect[-1].y1 == y1) && \
1015 (pNextRect[-1].y2 == y2) && \
1016 (pNextRect[-1].x2 >= r->x1)) \
1018 if (pNextRect[-1].x2 < r->x2) \
1020 pNextRect[-1].x2 = r->x2; \
1021 assert(pNextRect[-1].x1<pNextRect[-1].x2); \
1026 MEMCHECK(pReg, pNextRect, pReg->rects); \
1027 pNextRect->y1 = y1; \
1028 pNextRect->y2 = y2; \
1029 pNextRect->x1 = r->x1; \
1030 pNextRect->x2 = r->x2; \
1031 pReg->numRects += 1; \
1034 assert(pReg->numRects<=pReg->size); \
1038 while ((r1 != r1End) && (r2 != r2End))
1040 if (r1->x1 < r2->x1)
1055 } while (r1 != r1End);
1057 else while (r2 != r2End)
1064 gdk_region_union (GdkRegion *region,
1067 /* checks all the simple cases */
1070 * region and other are the same or other is empty
1072 if ((region == other) || (!(other->numRects)))
1078 if (!(region->numRects))
1080 miRegionCopy (region, other);
1085 * region completely subsumes otehr
1087 if ((region->numRects == 1) &&
1088 (region->extents.x1 <= other->extents.x1) &&
1089 (region->extents.y1 <= other->extents.y1) &&
1090 (region->extents.x2 >= other->extents.x2) &&
1091 (region->extents.y2 >= other->extents.y2))
1095 * other completely subsumes region
1097 if ((other->numRects == 1) &&
1098 (other->extents.x1 <= region->extents.x1) &&
1099 (other->extents.y1 <= region->extents.y1) &&
1100 (other->extents.x2 >= region->extents.x2) &&
1101 (other->extents.y2 >= region->extents.y2))
1103 miRegionCopy(region, other);
1107 miRegionOp (region, region, other, miUnionO,
1108 miUnionNonO, miUnionNonO);
1110 region->extents.x1 = MIN (region->extents.x1, other->extents.x1);
1111 region->extents.y1 = MIN (region->extents.y1, other->extents.y1);
1112 region->extents.x2 = MAX (region->extents.x2, other->extents.x2);
1113 region->extents.y2 = MAX (region->extents.y2, other->extents.y2);
1117 /*======================================================================
1118 * Region Subtraction
1119 *====================================================================*/
1122 *-----------------------------------------------------------------------
1124 * Deal with non-overlapping band for subtraction. Any parts from
1125 * region 2 we discard. Anything from region 1 we add to the region.
1131 * pReg may be affected.
1133 *-----------------------------------------------------------------------
1137 miSubtractNonO1 (GdkRegion *pReg,
1143 GdkRegionBox * pNextRect;
1145 pNextRect = &pReg->rects[pReg->numRects];
1151 assert (r->x1<r->x2);
1152 MEMCHECK (pReg, pNextRect, pReg->rects);
1153 pNextRect->x1 = r->x1;
1155 pNextRect->x2 = r->x2;
1157 pReg->numRects += 1;
1160 assert (pReg->numRects <= pReg->size);
1167 *-----------------------------------------------------------------------
1169 * Overlapping band subtraction. x1 is the left-most point not yet
1176 * pReg may have rectangles added to it.
1178 *-----------------------------------------------------------------------
1182 miSubtractO (GdkRegion *pReg,
1184 GdkRegionBox *r1End,
1186 GdkRegionBox *r2End,
1190 GdkRegionBox * pNextRect;
1196 pNextRect = &pReg->rects[pReg->numRects];
1198 while ((r1 != r1End) && (r2 != r2End))
1203 * Subtrahend missed the boat: go to next subtrahend.
1207 else if (r2->x1 <= x1)
1210 * Subtrahend preceeds minuend: nuke left edge of minuend.
1216 * Minuend completely covered: advance to next minuend and
1217 * reset left fence to edge of new minuend.
1226 * Subtrahend now used up since it doesn't extend beyond
1232 else if (r2->x1 < r1->x2)
1235 * Left part of subtrahend covers part of minuend: add uncovered
1236 * part of minuend to region and skip to next subtrahend.
1239 MEMCHECK(pReg, pNextRect, pReg->rects);
1242 pNextRect->x2 = r2->x1;
1244 pReg->numRects += 1;
1247 assert(pReg->numRects<=pReg->size);
1253 * Minuend used up: advance to new...
1262 * Subtrahend used up
1270 * Minuend used up: add any remaining piece before advancing.
1274 MEMCHECK(pReg, pNextRect, pReg->rects);
1277 pNextRect->x2 = r1->x2;
1279 pReg->numRects += 1;
1281 assert(pReg->numRects<=pReg->size);
1289 * Add remaining minuend rectangles to region.
1294 MEMCHECK(pReg, pNextRect, pReg->rects);
1297 pNextRect->x2 = r1->x2;
1299 pReg->numRects += 1;
1302 assert(pReg->numRects<=pReg->size);
1313 *-----------------------------------------------------------------------
1314 * gdk_region_subtract --
1315 * Subtract other from region and leave the result in region.
1321 * region is overwritten.
1323 *-----------------------------------------------------------------------
1327 gdk_region_subtract (GdkRegion *region,
1330 /* check for trivial reject */
1331 if ((!(region->numRects)) || (!(other->numRects)) ||
1332 (!EXTENTCHECK(®ion->extents, &other->extents)))
1335 miRegionOp (region, region, other, miSubtractO,
1336 miSubtractNonO1, (nonOverlapFunc) NULL);
1339 * Can't alter region's extents before we call miRegionOp because miRegionOp
1340 * depends on the extents of those regions being the unaltered. Besides, this
1341 * way there's no checking against rectangles that will be nuked
1342 * due to coalescing, so we have to examine fewer rectangles.
1344 miSetExtents (region);
1348 gdk_region_xor (GdkRegion *sra,
1353 trb = gdk_region_copy (srb);
1355 gdk_region_subtract (trb, sra);
1356 gdk_region_subtract (sra, srb);
1358 gdk_region_union (sra,trb);
1360 gdk_region_destroy (trb);
1364 * Check to see if the region is empty. Assumes a region is passed
1368 gdk_region_empty (GdkRegion *r)
1370 if (r->numRects == 0)
1377 * Check to see if two regions are equal
1380 gdk_region_equal (GdkRegion *r1,
1385 if (r1->numRects != r2->numRects) return FALSE;
1386 else if (r1->numRects == 0) return TRUE;
1387 else if (r1->extents.x1 != r2->extents.x1) return FALSE;
1388 else if (r1->extents.x2 != r2->extents.x2) return FALSE;
1389 else if (r1->extents.y1 != r2->extents.y1) return FALSE;
1390 else if (r1->extents.y2 != r2->extents.y2) return FALSE;
1392 for(i=0; i < r1->numRects; i++ )
1394 if (r1->rects[i].x1 != r2->rects[i].x1) return FALSE;
1395 else if (r1->rects[i].x2 != r2->rects[i].x2) return FALSE;
1396 else if (r1->rects[i].y1 != r2->rects[i].y1) return FALSE;
1397 else if (r1->rects[i].y2 != r2->rects[i].y2) return FALSE;
1403 gdk_region_point_in (GdkRegion *region,
1409 if (region->numRects == 0)
1411 if (!INBOX(region->extents, x, y))
1413 for (i=0; i<region->numRects; i++)
1415 if (INBOX (region->rects[i], x, y))
1422 gdk_region_rect_in (GdkRegion *region,
1423 GdkRectangle *rectangle)
1426 GdkRegionBox *pboxEnd;
1428 GdkRegionBox *prect = ▭
1429 gboolean partIn, partOut;
1431 gint rx = rectangle->x;
1432 gint ry = rectangle->y;
1436 prect->x2 = rx + rectangle->width;
1437 prect->y2 = ry + rectangle->height;
1439 /* this is (just) a useful optimization */
1440 if ((region->numRects == 0) || !EXTENTCHECK (®ion->extents, prect))
1441 return GDK_OVERLAP_RECTANGLE_OUT;
1446 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1447 for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1453 continue; /* getting up to speed or skipping remainder of band */
1457 partOut = TRUE; /* missed part of rectangle above */
1458 if (partIn || (pbox->y1 >= prect->y2))
1460 ry = pbox->y1; /* x guaranteed to be == prect->x1 */
1464 continue; /* not far enough over yet */
1468 partOut = TRUE; /* missed part of rectangle to left */
1473 if (pbox->x1 < prect->x2)
1475 partIn = TRUE; /* definitely overlap */
1480 if (pbox->x2 >= prect->x2)
1482 ry = pbox->y2; /* finished with this band */
1483 if (ry >= prect->y2)
1485 rx = prect->x1; /* reset x out to left again */
1490 * Because boxes in a band are maximal width, if the first box
1491 * to overlap the rectangle doesn't completely cover it in that
1492 * band, the rectangle must be partially out, since some of it
1493 * will be uncovered in that band. partIn will have been set true
1503 GDK_OVERLAP_RECTANGLE_PART : GDK_OVERLAP_RECTANGLE_IN) :
1504 GDK_OVERLAP_RECTANGLE_OUT);