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
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"
added
removed
gdk/gdkregion-generic.c
