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...
74 #include <gdkregion.h>
75 #include "gdkregion-generic.h"
78 typedef void (*overlapFunc) (GdkRegion *pReg,
85 typedef void (*nonOverlapFunc) (GdkRegion *pReg,
91 static void miRegionCopy (GdkRegion *dstrgn,
93 static void miRegionOp (GdkRegion *newReg,
96 overlapFunc overlapFn,
97 nonOverlapFunc nonOverlap1Fn,
98 nonOverlapFunc nonOverlap2Fn);
103 * Creates a new empty #GdkRegion.
105 * Returns: a new empty #GdkRegion
108 gdk_region_new (void)
112 temp = g_slice_new (GdkRegion);
115 temp->rects = &temp->extents;
116 temp->extents.x1 = 0;
117 temp->extents.y1 = 0;
118 temp->extents.x2 = 0;
119 temp->extents.y2 = 0;
126 * gdk_region_rectangle:
127 * @rectangle: a #GdkRectangle
129 * Creates a new region containing the area @rectangle.
131 * Return value: a new region
134 gdk_region_rectangle (GdkRectangle *rectangle)
138 g_return_val_if_fail (rectangle != NULL, NULL);
140 if (rectangle->width <= 0 || rectangle->height <= 0)
141 return gdk_region_new();
143 temp = g_slice_new (GdkRegion);
146 temp->rects = &temp->extents;
147 temp->extents.x1 = rectangle->x;
148 temp->extents.y1 = rectangle->y;
149 temp->extents.x2 = rectangle->x + rectangle->width;
150 temp->extents.y2 = rectangle->y + rectangle->height;
158 * @region: a #GdkRegion
160 * Copies @region, creating an identical new region.
162 * Return value: a new region identical to @region
165 gdk_region_copy (GdkRegion *region)
169 g_return_val_if_fail (region != NULL, NULL);
171 temp = gdk_region_new ();
173 miRegionCopy (temp, region);
179 * gdk_region_get_clipbox:
180 * @region: a #GdkRegion
181 * @rectangle: return location for the clipbox
183 * Obtains the smallest rectangle which includes the entire #GdkRegion.
187 gdk_region_get_clipbox (GdkRegion *region,
188 GdkRectangle *rectangle)
190 g_return_if_fail (region != NULL);
191 g_return_if_fail (rectangle != NULL);
193 rectangle->x = region->extents.x1;
194 rectangle->y = region->extents.y1;
195 rectangle->width = region->extents.x2 - region->extents.x1;
196 rectangle->height = region->extents.y2 - region->extents.y1;
201 * gdk_region_get_rectangles:
202 * @region: a #GdkRegion
203 * @rectangles: return location for an array of rectangles
204 * @n_rectangles: length of returned array
206 * Obtains the area covered by the region as a list of rectangles.
207 * The array returned in @rectangles must be freed with g_free().
210 gdk_region_get_rectangles (GdkRegion *region,
211 GdkRectangle **rectangles,
216 g_return_if_fail (region != NULL);
217 g_return_if_fail (rectangles != NULL);
218 g_return_if_fail (n_rectangles != NULL);
220 *n_rectangles = region->numRects;
221 *rectangles = g_new (GdkRectangle, region->numRects);
223 for (i = 0; i < region->numRects; i++)
226 rect = region->rects[i];
227 (*rectangles)[i].x = rect.x1;
228 (*rectangles)[i].y = rect.y1;
229 (*rectangles)[i].width = rect.x2 - rect.x1;
230 (*rectangles)[i].height = rect.y2 - rect.y1;
235 * gdk_region_union_with_rect:
236 * @region: a #GdkRegion.
237 * @rect: a #GdkRectangle.
239 * Sets the area of @region to the union of the areas of @region and
240 * @rect. The resulting area is the set of pixels contained in
241 * either @region or @rect.
244 gdk_region_union_with_rect (GdkRegion *region,
247 GdkRegion tmp_region;
249 g_return_if_fail (region != NULL);
250 g_return_if_fail (rect != NULL);
252 if (rect->width <= 0 || rect->height <= 0)
255 tmp_region.rects = &tmp_region.extents;
256 tmp_region.numRects = 1;
257 tmp_region.extents.x1 = rect->x;
258 tmp_region.extents.y1 = rect->y;
259 tmp_region.extents.x2 = rect->x + rect->width;
260 tmp_region.extents.y2 = rect->y + rect->height;
263 gdk_region_union (region, &tmp_region);
267 *-----------------------------------------------------------------------
269 * Reset the extents of a region to what they should be. Called by
270 * miSubtract and miIntersect b/c they can't figure it out along the
271 * way or do so easily, as miUnion can.
277 * The region's 'extents' structure is overwritten.
279 *-----------------------------------------------------------------------
282 miSetExtents (GdkRegion *pReg)
284 GdkRegionBox *pBox, *pBoxEnd, *pExtents;
286 if (pReg->numRects == 0)
288 pReg->extents.x1 = 0;
289 pReg->extents.y1 = 0;
290 pReg->extents.x2 = 0;
291 pReg->extents.y2 = 0;
295 pExtents = &pReg->extents;
297 pBoxEnd = &pBox[pReg->numRects - 1];
300 * Since pBox is the first rectangle in the region, it must have the
301 * smallest y1 and since pBoxEnd is the last rectangle in the region,
302 * it must have the largest y2, because of banding. Initialize x1 and
303 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
306 pExtents->x1 = pBox->x1;
307 pExtents->y1 = pBox->y1;
308 pExtents->x2 = pBoxEnd->x2;
309 pExtents->y2 = pBoxEnd->y2;
311 g_assert(pExtents->y1 < pExtents->y2);
312 while (pBox <= pBoxEnd)
314 if (pBox->x1 < pExtents->x1)
316 pExtents->x1 = pBox->x1;
318 if (pBox->x2 > pExtents->x2)
320 pExtents->x2 = pBox->x2;
324 g_assert(pExtents->x1 < pExtents->x2);
328 * gdk_region_destroy:
329 * @region: a #GdkRegion
331 * Destroys a #GdkRegion.
334 gdk_region_destroy (GdkRegion *region)
336 g_return_if_fail (region != NULL);
338 if (region->rects != ®ion->extents)
339 g_free (region->rects);
340 g_slice_free (GdkRegion, region);
346 * @region: a #GdkRegion
347 * @dx: the distance to move the region horizontally
348 * @dy: the distance to move the region vertically
350 * Moves a region the specified distance.
353 gdk_region_offset (GdkRegion *region,
360 g_return_if_fail (region != NULL);
362 pbox = region->rects;
363 nbox = region->numRects;
373 if (region->rects != ®ion->extents)
375 region->extents.x1 += x;
376 region->extents.x2 += x;
377 region->extents.y1 += y;
378 region->extents.y2 += y;
383 Utility procedure Compress:
384 Replace r by the region r', where
385 p in r' iff (Quantifer m <= dx) (p + m in r), and
386 Quantifier is Exists if grow is TRUE, For all if grow is FALSE, and
387 (x,y) + m = (x+m,y) if xdir is TRUE; (x,y+m) if xdir is FALSE.
389 Thus, if xdir is TRUE and grow is FALSE, r is replaced by the region
390 of all points p such that p and the next dx points on the same
391 horizontal scan line are all in r. We do this using by noting
392 that p is the head of a run of length 2^i + k iff p is the head
393 of a run of length 2^i and p+2^i is the head of a run of length
394 k. Thus, the loop invariant: s contains the region corresponding
395 to the runs of length shift. r contains the region corresponding
396 to the runs of length 1 + dxo & (shift-1), where dxo is the original
397 value of dx. dx = dxo & ~(shift-1). As parameters, s and t are
398 scratch regions, so that we don't have to allocate them on every
402 #define ZOpRegion(a,b) if (grow) gdk_region_union (a, b); \
403 else gdk_region_intersect (a,b)
404 #define ZShiftRegion(a,b) if (xdir) gdk_region_offset (a,b,0); \
405 else gdk_region_offset (a,0,b)
408 Compress(GdkRegion *r,
422 ZShiftRegion(r, -(int)shift);
428 ZShiftRegion(s, -(int)shift);
440 * @region: a #GdkRegion
441 * @dx: the number of pixels to shrink the region horizontally
442 * @dy: the number of pixels to shrink the region vertically
444 * Resizes a region by the specified amount.
445 * Positive values shrink the region. Negative values expand it.
448 gdk_region_shrink (GdkRegion *region,
455 g_return_if_fail (region != NULL);
460 s = gdk_region_new ();
461 t = gdk_region_new ();
467 Compress(region, s, t, (unsigned) 2*dx, TRUE, grow);
473 Compress(region, s, t, (unsigned) 2*dy, FALSE, grow);
475 gdk_region_offset (region, dx, dy);
476 gdk_region_destroy (s);
477 gdk_region_destroy (t);
481 /*======================================================================
482 * Region Intersection
483 *====================================================================*/
485 *-----------------------------------------------------------------------
487 * Handle an overlapping band for miIntersect.
493 * Rectangles may be added to the region.
495 *-----------------------------------------------------------------------
499 miIntersectO (GdkRegion *pReg,
509 GdkRegionBox *pNextRect;
511 pNextRect = &pReg->rects[pReg->numRects];
513 while ((r1 != r1End) && (r2 != r2End))
515 x1 = MAX (r1->x1,r2->x1);
516 x2 = MIN (r1->x2,r2->x2);
519 * If there's any overlap between the two rectangles, add that
520 * overlap to the new region.
521 * There's no need to check for subsumption because the only way
522 * such a need could arise is if some region has two rectangles
523 * right next to each other. Since that should never happen...
529 MEMCHECK (pReg, pNextRect, pReg->rects);
536 g_assert (pReg->numRects <= pReg->size);
540 * Need to advance the pointers. Shift the one that extends
541 * to the right the least, since the other still has a chance to
542 * overlap with that region's next rectangle, if you see what I mean.
548 else if (r2->x2 < r1->x2)
561 * gdk_region_intersect:
562 * @source1: a #GdkRegion
563 * @source2: another #GdkRegion
565 * Sets the area of @source1 to the intersection of the areas of @source1
566 * and @source2. The resulting area is the set of pixels contained in
567 * both @source1 and @source2.
570 gdk_region_intersect (GdkRegion *source1,
573 g_return_if_fail (source1 != NULL);
574 g_return_if_fail (source2 != NULL);
576 /* check for trivial reject */
577 if ((!(source1->numRects)) || (!(source2->numRects)) ||
578 (!EXTENTCHECK(&source1->extents, &source2->extents)))
579 source1->numRects = 0;
581 miRegionOp (source1, source1, source2,
582 miIntersectO, (nonOverlapFunc) NULL, (nonOverlapFunc) NULL);
585 * Can't alter source1's extents before miRegionOp depends on the
586 * extents of the regions being unchanged. Besides, this way there's
587 * no checking against rectangles that will be nuked due to
588 * coalescing, so we have to examine fewer rectangles.
590 miSetExtents(source1);
594 miRegionCopy (GdkRegion *dstrgn,
597 if (dstrgn != rgn) /* don't want to copy to itself */
599 if (dstrgn->size < rgn->numRects)
601 if (dstrgn->rects != &dstrgn->extents)
602 g_free (dstrgn->rects);
604 dstrgn->rects = g_new (GdkRegionBox, rgn->numRects);
605 dstrgn->size = rgn->numRects;
608 dstrgn->numRects = rgn->numRects;
609 dstrgn->extents = rgn->extents;
611 memcpy (dstrgn->rects, rgn->rects, rgn->numRects * sizeof (GdkRegionBox));
616 /*======================================================================
617 * Generic Region Operator
618 *====================================================================*/
621 *-----------------------------------------------------------------------
623 * Attempt to merge the boxes in the current band with those in the
624 * previous one. Used only by miRegionOp.
627 * The new index for the previous band.
630 * If coalescing takes place:
631 * - rectangles in the previous band will have their y2 fields
633 * - pReg->numRects will be decreased.
635 *-----------------------------------------------------------------------
639 miCoalesce (GdkRegion *pReg, /* Region to coalesce */
640 gint prevStart, /* Index of start of previous band */
641 gint curStart) /* Index of start of current band */
643 GdkRegionBox *pPrevBox; /* Current box in previous band */
644 GdkRegionBox *pCurBox; /* Current box in current band */
645 GdkRegionBox *pRegEnd; /* End of region */
646 int curNumRects; /* Number of rectangles in current
648 int prevNumRects; /* Number of rectangles in previous
650 int bandY1; /* Y1 coordinate for current band */
652 pRegEnd = &pReg->rects[pReg->numRects];
654 pPrevBox = &pReg->rects[prevStart];
655 prevNumRects = curStart - prevStart;
658 * Figure out how many rectangles are in the current band. Have to do
659 * this because multiple bands could have been added in miRegionOp
660 * at the end when one region has been exhausted.
662 pCurBox = &pReg->rects[curStart];
663 bandY1 = pCurBox->y1;
664 for (curNumRects = 0;
665 (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
671 if (pCurBox != pRegEnd)
674 * If more than one band was added, we have to find the start
675 * of the last band added so the next coalescing job can start
676 * at the right place... (given when multiple bands are added,
677 * this may be pointless -- see above).
680 while (pRegEnd[-1].y1 == pRegEnd->y1)
684 curStart = pRegEnd - pReg->rects;
685 pRegEnd = pReg->rects + pReg->numRects;
688 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
689 pCurBox -= curNumRects;
691 * The bands may only be coalesced if the bottom of the previous
692 * matches the top scanline of the current.
694 if (pPrevBox->y2 == pCurBox->y1)
697 * Make sure the bands have boxes in the same places. This
698 * assumes that boxes have been added in such a way that they
699 * cover the most area possible. I.e. two boxes in a band must
700 * have some horizontal space between them.
704 if ((pPrevBox->x1 != pCurBox->x1) ||
705 (pPrevBox->x2 != pCurBox->x2))
708 * The bands don't line up so they can't be coalesced.
715 } while (prevNumRects != 0);
717 pReg->numRects -= curNumRects;
718 pCurBox -= curNumRects;
719 pPrevBox -= curNumRects;
722 * The bands may be merged, so set the bottom y of each box
723 * in the previous band to that of the corresponding box in
728 pPrevBox->y2 = pCurBox->y2;
733 while (curNumRects != 0);
736 * If only one band was added to the region, we have to backup
737 * curStart to the start of the previous band.
739 * If more than one band was added to the region, copy the
740 * other bands down. The assumption here is that the other bands
741 * came from the same region as the current one and no further
742 * coalescing can be done on them since it's all been done
743 * already... curStart is already in the right place.
745 if (pCurBox == pRegEnd)
747 curStart = prevStart;
753 *pPrevBox++ = *pCurBox++;
755 while (pCurBox != pRegEnd);
764 *-----------------------------------------------------------------------
766 * Apply an operation to two regions. Called by miUnion, miInverse,
767 * miSubtract, miIntersect...
773 * The new region is overwritten.
776 * The idea behind this function is to view the two regions as sets.
777 * Together they cover a rectangle of area that this function divides
778 * into horizontal bands where points are covered only by one region
779 * or by both. For the first case, the nonOverlapFunc is called with
780 * each the band and the band's upper and lower extents. For the
781 * second, the overlapFunc is called to process the entire band. It
782 * is responsible for clipping the rectangles in the band, though
783 * this function provides the boundaries.
784 * At the end of each band, the new region is coalesced, if possible,
785 * to reduce the number of rectangles in the region.
787 *-----------------------------------------------------------------------
791 miRegionOp(GdkRegion *newReg,
794 overlapFunc overlapFn, /* Function to call for over-
796 nonOverlapFunc nonOverlap1Fn, /* Function to call for non-
797 * overlapping bands in region
799 nonOverlapFunc nonOverlap2Fn) /* Function to call for non-
800 * overlapping bands in region
803 GdkRegionBox *r1; /* Pointer into first region */
804 GdkRegionBox *r2; /* Pointer into 2d region */
805 GdkRegionBox *r1End; /* End of 1st region */
806 GdkRegionBox *r2End; /* End of 2d region */
807 int ybot; /* Bottom of intersection */
808 int ytop; /* Top of intersection */
809 GdkRegionBox *oldRects; /* Old rects for newReg */
810 int prevBand; /* Index of start of
811 * previous band in newReg */
812 int curBand; /* Index of start of current
814 GdkRegionBox *r1BandEnd; /* End of current band in r1 */
815 GdkRegionBox *r2BandEnd; /* End of current band in r2 */
816 int top; /* Top of non-overlapping
818 int bot; /* Bottom of non-overlapping
823 * set r1, r2, r1End and r2End appropriately, preserve the important
824 * parts of the destination region until the end in case it's one of
825 * the two source regions, then mark the "new" region empty, allocating
826 * another array of rectangles for it to use.
830 r1End = r1 + reg1->numRects;
831 r2End = r2 + reg2->numRects;
833 oldRects = newReg->rects;
835 EMPTY_REGION(newReg);
838 * Allocate a reasonable number of rectangles for the new region. The idea
839 * is to allocate enough so the individual functions don't need to
840 * reallocate and copy the array, which is time consuming, yet we don't
841 * have to worry about using too much memory. I hope to be able to
842 * nuke the Xrealloc() at the end of this function eventually.
844 newReg->size = MAX (reg1->numRects, reg2->numRects) * 2;
845 newReg->rects = g_new (GdkRegionBox, newReg->size);
848 * Initialize ybot and ytop.
849 * In the upcoming loop, ybot and ytop serve different functions depending
850 * on whether the band being handled is an overlapping or non-overlapping
852 * In the case of a non-overlapping band (only one of the regions
853 * has points in the band), ybot is the bottom of the most recent
854 * intersection and thus clips the top of the rectangles in that band.
855 * ytop is the top of the next intersection between the two regions and
856 * serves to clip the bottom of the rectangles in the current band.
857 * For an overlapping band (where the two regions intersect), ytop clips
858 * the top of the rectangles of both regions and ybot clips the bottoms.
860 if (reg1->extents.y1 < reg2->extents.y1)
861 ybot = reg1->extents.y1;
863 ybot = reg2->extents.y1;
866 * prevBand serves to mark the start of the previous band so rectangles
867 * can be coalesced into larger rectangles. qv. miCoalesce, above.
868 * In the beginning, there is no previous band, so prevBand == curBand
869 * (curBand is set later on, of course, but the first band will always
870 * start at index 0). prevBand and curBand must be indices because of
871 * the possible expansion, and resultant moving, of the new region's
872 * array of rectangles.
878 curBand = newReg->numRects;
881 * This algorithm proceeds one source-band (as opposed to a
882 * destination band, which is determined by where the two regions
883 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
884 * rectangle after the last one in the current band for their
885 * respective regions.
888 while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
894 while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
900 * First handle the band that doesn't intersect, if any.
902 * Note that attention is restricted to one band in the
903 * non-intersecting region at once, so if a region has n
904 * bands between the current position and the next place it overlaps
905 * the other, this entire loop will be passed through n times.
909 top = MAX (r1->y1,ybot);
910 bot = MIN (r1->y2,r2->y1);
912 if ((top != bot) && (nonOverlap1Fn != (void (*)())NULL))
914 (* nonOverlap1Fn) (newReg, r1, r1BandEnd, top, bot);
919 else if (r2->y1 < r1->y1)
921 top = MAX (r2->y1,ybot);
922 bot = MIN (r2->y2,r1->y1);
924 if ((top != bot) && (nonOverlap2Fn != (void (*)())NULL))
926 (* nonOverlap2Fn) (newReg, r2, r2BandEnd, top, bot);
937 * If any rectangles got added to the region, try and coalesce them
938 * with rectangles from the previous band. Note we could just do
939 * this test in miCoalesce, but some machines incur a not
940 * inconsiderable cost for function calls, so...
942 if (newReg->numRects != curBand)
944 prevBand = miCoalesce (newReg, prevBand, curBand);
948 * Now see if we've hit an intersecting band. The two bands only
949 * intersect if ybot > ytop
951 ybot = MIN (r1->y2, r2->y2);
952 curBand = newReg->numRects;
955 (* overlapFn) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
959 if (newReg->numRects != curBand)
961 prevBand = miCoalesce (newReg, prevBand, curBand);
965 * If we've finished with a band (y2 == ybot) we skip forward
966 * in the region to the next band.
976 } while ((r1 != r1End) && (r2 != r2End));
979 * Deal with whichever region still has rectangles left.
981 curBand = newReg->numRects;
984 if (nonOverlap1Fn != (nonOverlapFunc )NULL)
989 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
993 (* nonOverlap1Fn) (newReg, r1, r1BandEnd,
994 MAX (r1->y1,ybot), r1->y2);
996 } while (r1 != r1End);
999 else if ((r2 != r2End) && (nonOverlap2Fn != (nonOverlapFunc) NULL))
1004 while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
1008 (* nonOverlap2Fn) (newReg, r2, r2BandEnd,
1009 MAX (r2->y1,ybot), r2->y2);
1011 } while (r2 != r2End);
1014 if (newReg->numRects != curBand)
1016 (void) miCoalesce (newReg, prevBand, curBand);
1020 * A bit of cleanup. To keep regions from growing without bound,
1021 * we shrink the array of rectangles to match the new number of
1022 * rectangles in the region. This never goes to 0, however...
1024 * Only do this stuff if the number of rectangles allocated is more than
1025 * twice the number of rectangles in the region (a simple optimization...).
1027 if (newReg->numRects < (newReg->size >> 1))
1029 if (REGION_NOT_EMPTY (newReg))
1031 newReg->size = newReg->numRects;
1032 newReg->rects = g_renew (GdkRegionBox, newReg->rects, newReg->size);
1037 * No point in doing the extra work involved in an Xrealloc if
1038 * the region is empty
1041 g_free (newReg->rects);
1042 newReg->rects = &newReg->extents;
1046 if (oldRects != &newReg->extents)
1051 /*======================================================================
1053 *====================================================================*/
1056 *-----------------------------------------------------------------------
1058 * Handle a non-overlapping band for the union operation. Just
1059 * Adds the rectangles into the region. Doesn't have to check for
1060 * subsumption or anything.
1066 * pReg->numRects is incremented and the final rectangles overwritten
1067 * with the rectangles we're passed.
1069 *-----------------------------------------------------------------------
1072 miUnionNonO (GdkRegion *pReg,
1078 GdkRegionBox *pNextRect;
1080 pNextRect = &pReg->rects[pReg->numRects];
1086 g_assert(r->x1 < r->x2);
1087 MEMCHECK(pReg, pNextRect, pReg->rects);
1088 pNextRect->x1 = r->x1;
1090 pNextRect->x2 = r->x2;
1092 pReg->numRects += 1;
1095 g_assert(pReg->numRects<=pReg->size);
1102 *-----------------------------------------------------------------------
1104 * Handle an overlapping band for the union operation. Picks the
1105 * left-most rectangle each time and merges it into the region.
1111 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1114 *-----------------------------------------------------------------------
1119 miUnionO (GdkRegion *pReg,
1121 GdkRegionBox *r1End,
1123 GdkRegionBox *r2End,
1127 GdkRegionBox * pNextRect;
1129 pNextRect = &pReg->rects[pReg->numRects];
1131 #define MERGERECT(r) \
1132 if ((pReg->numRects != 0) && \
1133 (pNextRect[-1].y1 == y1) && \
1134 (pNextRect[-1].y2 == y2) && \
1135 (pNextRect[-1].x2 >= r->x1)) \
1137 if (pNextRect[-1].x2 < r->x2) \
1139 pNextRect[-1].x2 = r->x2; \
1140 g_assert(pNextRect[-1].x1<pNextRect[-1].x2); \
1145 MEMCHECK(pReg, pNextRect, pReg->rects); \
1146 pNextRect->y1 = y1; \
1147 pNextRect->y2 = y2; \
1148 pNextRect->x1 = r->x1; \
1149 pNextRect->x2 = r->x2; \
1150 pReg->numRects += 1; \
1153 g_assert(pReg->numRects<=pReg->size); \
1157 while ((r1 != r1End) && (r2 != r2End))
1159 if (r1->x1 < r2->x1)
1174 } while (r1 != r1End);
1176 else while (r2 != r2End)
1184 * @source1: a #GdkRegion
1185 * @source2: a #GdkRegion
1187 * Sets the area of @source1 to the union of the areas of @source1 and
1188 * @source2. The resulting area is the set of pixels contained in
1189 * either @source1 or @source2.
1192 gdk_region_union (GdkRegion *source1,
1195 g_return_if_fail (source1 != NULL);
1196 g_return_if_fail (source2 != NULL);
1198 /* checks all the simple cases */
1201 * source1 and source2 are the same or source2 is empty
1203 if ((source1 == source2) || (!(source2->numRects)))
1209 if (!(source1->numRects))
1211 miRegionCopy (source1, source2);
1216 * source1 completely subsumes source2
1218 if ((source1->numRects == 1) &&
1219 (source1->extents.x1 <= source2->extents.x1) &&
1220 (source1->extents.y1 <= source2->extents.y1) &&
1221 (source1->extents.x2 >= source2->extents.x2) &&
1222 (source1->extents.y2 >= source2->extents.y2))
1226 * source2 completely subsumes source1
1228 if ((source2->numRects == 1) &&
1229 (source2->extents.x1 <= source1->extents.x1) &&
1230 (source2->extents.y1 <= source1->extents.y1) &&
1231 (source2->extents.x2 >= source1->extents.x2) &&
1232 (source2->extents.y2 >= source1->extents.y2))
1234 miRegionCopy(source1, source2);
1238 miRegionOp (source1, source1, source2, miUnionO,
1239 miUnionNonO, miUnionNonO);
1241 source1->extents.x1 = MIN (source1->extents.x1, source2->extents.x1);
1242 source1->extents.y1 = MIN (source1->extents.y1, source2->extents.y1);
1243 source1->extents.x2 = MAX (source1->extents.x2, source2->extents.x2);
1244 source1->extents.y2 = MAX (source1->extents.y2, source2->extents.y2);
1248 /*======================================================================
1249 * Region Subtraction
1250 *====================================================================*/
1253 *-----------------------------------------------------------------------
1255 * Deal with non-overlapping band for subtraction. Any parts from
1256 * region 2 we discard. Anything from region 1 we add to the region.
1262 * pReg may be affected.
1264 *-----------------------------------------------------------------------
1268 miSubtractNonO1 (GdkRegion *pReg,
1274 GdkRegionBox * pNextRect;
1276 pNextRect = &pReg->rects[pReg->numRects];
1282 g_assert (r->x1<r->x2);
1283 MEMCHECK (pReg, pNextRect, pReg->rects);
1284 pNextRect->x1 = r->x1;
1286 pNextRect->x2 = r->x2;
1288 pReg->numRects += 1;
1291 g_assert (pReg->numRects <= pReg->size);
1298 *-----------------------------------------------------------------------
1300 * Overlapping band subtraction. x1 is the left-most point not yet
1307 * pReg may have rectangles added to it.
1309 *-----------------------------------------------------------------------
1313 miSubtractO (GdkRegion *pReg,
1315 GdkRegionBox *r1End,
1317 GdkRegionBox *r2End,
1321 GdkRegionBox * pNextRect;
1327 pNextRect = &pReg->rects[pReg->numRects];
1329 while ((r1 != r1End) && (r2 != r2End))
1334 * Subtrahend missed the boat: go to next subtrahend.
1338 else if (r2->x1 <= x1)
1341 * Subtrahend preceeds minuend: nuke left edge of minuend.
1347 * Minuend completely covered: advance to next minuend and
1348 * reset left fence to edge of new minuend.
1357 * Subtrahend now used up since it doesn't extend beyond
1363 else if (r2->x1 < r1->x2)
1366 * Left part of subtrahend covers part of minuend: add uncovered
1367 * part of minuend to region and skip to next subtrahend.
1369 g_assert(x1<r2->x1);
1370 MEMCHECK(pReg, pNextRect, pReg->rects);
1373 pNextRect->x2 = r2->x1;
1375 pReg->numRects += 1;
1378 g_assert(pReg->numRects<=pReg->size);
1384 * Minuend used up: advance to new...
1393 * Subtrahend used up
1401 * Minuend used up: add any remaining piece before advancing.
1405 MEMCHECK(pReg, pNextRect, pReg->rects);
1408 pNextRect->x2 = r1->x2;
1410 pReg->numRects += 1;
1412 g_assert(pReg->numRects<=pReg->size);
1421 * Add remaining minuend rectangles to region.
1425 g_assert(x1<r1->x2);
1426 MEMCHECK(pReg, pNextRect, pReg->rects);
1429 pNextRect->x2 = r1->x2;
1431 pReg->numRects += 1;
1434 g_assert(pReg->numRects<=pReg->size);
1445 * gdk_region_subtract:
1446 * @source1: a #GdkRegion
1447 * @source2: another #GdkRegion
1449 * Subtracts the area of @source2 from the area @source1. The resulting
1450 * area is the set of pixels contained in @source1 but not in @source2.
1453 gdk_region_subtract (GdkRegion *source1,
1456 g_return_if_fail (source1 != NULL);
1457 g_return_if_fail (source2 != NULL);
1459 /* check for trivial reject */
1460 if ((!(source1->numRects)) || (!(source2->numRects)) ||
1461 (!EXTENTCHECK(&source1->extents, &source2->extents)))
1464 miRegionOp (source1, source1, source2, miSubtractO,
1465 miSubtractNonO1, (nonOverlapFunc) NULL);
1468 * Can't alter source1's extents before we call miRegionOp because miRegionOp
1469 * depends on the extents of those regions being the unaltered. Besides, this
1470 * way there's no checking against rectangles that will be nuked
1471 * due to coalescing, so we have to examine fewer rectangles.
1473 miSetExtents (source1);
1478 * @source1: a #GdkRegion
1479 * @source2: another #GdkRegion
1481 * Sets the area of @source1 to the exclusive-OR of the areas of @source1
1482 * and @source2. The resulting area is the set of pixels contained in one
1483 * or the other of the two sources but not in both.
1486 gdk_region_xor (GdkRegion *source1,
1491 g_return_if_fail (source1 != NULL);
1492 g_return_if_fail (source2 != NULL);
1494 trb = gdk_region_copy (source2);
1496 gdk_region_subtract (trb, source1);
1497 gdk_region_subtract (source1, source2);
1499 gdk_region_union (source1, trb);
1501 gdk_region_destroy (trb);
1506 * @region: a #GdkRegion
1508 * Finds out if the #GdkRegion is empty.
1510 * Returns: %TRUE if @region is empty.
1513 gdk_region_empty (GdkRegion *region)
1515 g_return_val_if_fail (region != NULL, FALSE);
1517 if (region->numRects == 0)
1525 * @region1: a #GdkRegion
1526 * @region2: a #GdkRegion
1528 * Finds out if the two regions are the same.
1530 * Returns: %TRUE if @region1 and @region2 are equal.
1533 gdk_region_equal (GdkRegion *region1,
1538 g_return_val_if_fail (region1 != NULL, FALSE);
1539 g_return_val_if_fail (region2 != NULL, FALSE);
1541 if (region1->numRects != region2->numRects) return FALSE;
1542 else if (region1->numRects == 0) return TRUE;
1543 else if (region1->extents.x1 != region2->extents.x1) return FALSE;
1544 else if (region1->extents.x2 != region2->extents.x2) return FALSE;
1545 else if (region1->extents.y1 != region2->extents.y1) return FALSE;
1546 else if (region1->extents.y2 != region2->extents.y2) return FALSE;
1548 for(i = 0; i < region1->numRects; i++ )
1550 if (region1->rects[i].x1 != region2->rects[i].x1) return FALSE;
1551 else if (region1->rects[i].x2 != region2->rects[i].x2) return FALSE;
1552 else if (region1->rects[i].y1 != region2->rects[i].y1) return FALSE;
1553 else if (region1->rects[i].y2 != region2->rects[i].y2) return FALSE;
1559 * gdk_region_point_in:
1560 * @region: a #GdkRegion
1561 * @x: the x coordinate of a point
1562 * @y: the y coordinate of a point
1564 * Finds out if a point is in a region.
1566 * Returns: %TRUE if the point is in @region.
1569 gdk_region_point_in (GdkRegion *region,
1575 g_return_val_if_fail (region != NULL, FALSE);
1577 if (region->numRects == 0)
1579 if (!INBOX(region->extents, x, y))
1581 for (i = 0; i < region->numRects; i++)
1583 if (INBOX (region->rects[i], x, y))
1590 * gdk_region_rect_in:
1591 * @region: a #GdkRegion.
1592 * @rectangle: a #GdkRectangle.
1594 * Tests whether a rectangle is within a region.
1596 * Returns: %GDK_OVERLAP_RECTANGLE_IN, %GDK_OVERLAP_RECTANGLE_OUT, or
1597 * %GDK_OVERLAP_RECTANGLE_PART, depending on whether the rectangle is inside,
1598 * outside, or partly inside the #GdkRegion, respectively.
1601 gdk_region_rect_in (GdkRegion *region,
1602 GdkRectangle *rectangle)
1605 GdkRegionBox *pboxEnd;
1607 GdkRegionBox *prect = ▭
1608 gboolean partIn, partOut;
1611 g_return_val_if_fail (region != NULL, GDK_OVERLAP_RECTANGLE_OUT);
1612 g_return_val_if_fail (rectangle != NULL, GDK_OVERLAP_RECTANGLE_OUT);
1619 prect->x2 = rx + rectangle->width;
1620 prect->y2 = ry + rectangle->height;
1622 /* this is (just) a useful optimization */
1623 if ((region->numRects == 0) || !EXTENTCHECK (®ion->extents, prect))
1624 return GDK_OVERLAP_RECTANGLE_OUT;
1629 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1630 for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1636 continue; /* getting up to speed or skipping remainder of band */
1640 partOut = TRUE; /* missed part of rectangle above */
1641 if (partIn || (pbox->y1 >= prect->y2))
1643 ry = pbox->y1; /* x guaranteed to be == prect->x1 */
1647 continue; /* not far enough over yet */
1651 partOut = TRUE; /* missed part of rectangle to left */
1656 if (pbox->x1 < prect->x2)
1658 partIn = TRUE; /* definitely overlap */
1663 if (pbox->x2 >= prect->x2)
1665 ry = pbox->y2; /* finished with this band */
1666 if (ry >= prect->y2)
1668 rx = prect->x1; /* reset x out to left again */
1673 * Because boxes in a band are maximal width, if the first box
1674 * to overlap the rectangle doesn't completely cover it in that
1675 * band, the rectangle must be partially out, since some of it
1676 * will be uncovered in that band. partIn will have been set true
1686 GDK_OVERLAP_RECTANGLE_PART : GDK_OVERLAP_RECTANGLE_IN) :
1687 GDK_OVERLAP_RECTANGLE_OUT);
1692 gdk_region_unsorted_spans_intersect_foreach (GdkRegion *region,
1695 GdkSpanFunc function,
1698 gint i, left, right, y;
1699 gint clipped_left, clipped_right;
1701 GdkRegionBox *pboxEnd;
1704 if (!region->numRects)
1707 for (i=0;i<n_spans;i++)
1711 right = left + spans[i].width; /* right is not in the span! */
1713 if (! ((region->extents.y1 <= y) &&
1714 (region->extents.y2 > y) &&
1715 (region->extents.x1 < right) &&
1716 (region->extents.x2 > left)) )
1719 /* can stop when we passed y */
1720 for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1725 continue; /* Not quite there yet */
1728 break; /* passed the spanline */
1730 if ((right > pbox->x1) && (left < pbox->x2))
1732 clipped_left = MAX (left, pbox->x1);
1733 clipped_right = MIN (right, pbox->x2);
1736 out_span.x = clipped_left;
1737 out_span.width = clipped_right - clipped_left;
1738 (*function) (&out_span, data);
1745 * gdk_region_spans_intersect_foreach:
1746 * @region: a #GdkRegion
1747 * @spans: an array of #GdkSpans
1748 * @n_spans: the length of @spans
1749 * @sorted: %TRUE if @spans is sorted wrt. the y coordinate
1750 * @function: function to call on each span in the intersection
1751 * @data: data to pass to @function
1753 * Calls a function on each span in the intersection of @region and @spans.
1756 gdk_region_spans_intersect_foreach (GdkRegion *region,
1760 GdkSpanFunc function,
1763 gint left, right, y;
1764 gint clipped_left, clipped_right;
1766 GdkRegionBox *pboxEnd;
1767 GdkSpan *span, *tmpspan;
1771 g_return_if_fail (region != NULL);
1772 g_return_if_fail (spans != NULL);
1776 gdk_region_unsorted_spans_intersect_foreach (region,
1784 if ((!region->numRects) || (n_spans == 0))
1787 /* The main method here is to step along the
1788 * sorted rectangles and spans in lock step, and
1789 * clipping the spans that are in the current
1790 * rectangle before going on to the next rectangle.
1794 end_span = spans + n_spans;
1795 pbox = region->rects;
1796 pboxEnd = pbox + region->numRects;
1797 while (pbox < pboxEnd)
1799 while ((pbox->y2 < span->y) || (span->y < pbox->y1))
1801 /* Skip any rectangles that are above the current span */
1802 if (pbox->y2 < span->y)
1805 if (pbox == pboxEnd)
1808 /* Skip any spans that are above the current rectangle */
1809 if (span->y < pbox->y1)
1812 if (span == end_span)
1817 /* Ok, we got at least one span that might intersect this rectangle. */
1819 while ((tmpspan < end_span) &&
1820 (tmpspan->y < pbox->y2))
1824 right = left + tmpspan->width; /* right is not in the span! */
1826 if ((right > pbox->x1) && (left < pbox->x2))
1828 clipped_left = MAX (left, pbox->x1);
1829 clipped_right = MIN (right, pbox->x2);
1832 out_span.x = clipped_left;
1833 out_span.width = clipped_right - clipped_left;
1834 (*function) (&out_span, data);
1840 /* Finished this rectangle.
1841 * The spans could still intersect the next one
1847 #define __GDK_REGION_GENERIC_C__
1848 #include "gdkaliasdef.c"