1 /************************************************************************
2
3 Copyright 1987, 1988, 1998 The Open Group
4
5 Permission to use, copy, modify, distribute, and sell this software and its
6 documentation for any purpose is hereby granted without fee, provided that
7 the above copyright notice appear in all copies and that both that
8 copyright notice and this permission notice appear in supporting
9 documentation.
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21 Except as contained in this notice, the name of The Open Group shall not be
22 used in advertising or otherwise to promote the sale, use or other dealings
23 in this Software without prior written authorization from The Open Group.
24
25
26 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
27
28 All Rights Reserved
29
30 Permission to use, copy, modify, and distribute this software and its
31 documentation for any purpose and without fee is hereby granted,
32 provided that the above copyright notice appear in all copies and that
33 both that copyright notice and this permission notice appear in
34 supporting documentation, and that the name of Digital not be
35 used in advertising or publicity pertaining to distribution of the
36 software without specific, written prior permission.
37
38 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
44 SOFTWARE.
45
46 ************************************************************************/
47 /*
48 * The functions in this file implement the Region abstraction, similar to one
49 * used in the X11 sample server. A Region is simply an area, as the name
50 * implies, and is implemented as a "y-x-banded" array of rectangles. To
51 * explain: Each Region is made up of a certain number of rectangles sorted
52 * by y coordinate first, and then by x coordinate.
53 *
54 * Furthermore, the rectangles are banded such that every rectangle with a
55 * given upper-left y coordinate (y1) will have the same lower-right y
56 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
57 * will span the entire vertical distance of the band. This means that some
58 * areas that could be merged into a taller rectangle will be represented as
59 * several shorter rectangles to account for shorter rectangles to its left
60 * or right but within its "vertical scope".
61 *
62 * An added constraint on the rectangles is that they must cover as much
63 * horizontal area as possible. E.g. no two rectangles in a band are allowed
64 * to touch.
65 *
66 * Whenever possible, bands will be merged together to cover a greater vertical
67 * distance (and thus reduce the number of rectangles). Two bands can be merged
68 * only if the bottom of one touches the top of the other and they have
69 * rectangles in the same places (of the same width, of course). This maintains
70 * the y-x-banding that's so nice to have...
71 */
72
73 #ifdef HAVE_CONFIG_H
74 #include <config.h>
75 #endif
76 #include "Xlibint.h"
77 #include "Xutil.h"
78 #include <X11/Xregion.h>
79 #include "poly.h"
80 #include "reallocarray.h"
81
82 #ifdef DEBUG
83 #include <stdio.h>
84 #define assert(expr) {if (!(expr)) fprintf(stderr,\
85 "Assertion failed file %s, line %d: expr\n", __FILE__, __LINE__); }
86 #else
87 #define assert(expr)
88 #endif
89
90 typedef int (*overlapProcp)(
91 register Region pReg,
92 register BoxPtr r1,
93 BoxPtr r1End,
94 register BoxPtr r2,
95 BoxPtr r2End,
96 short y1,
97 short y2);
98
99 typedef int (*nonOverlapProcp)(
100 register Region pReg,
101 register BoxPtr r,
102 BoxPtr rEnd,
103 register short y1,
104 register short y2);
105
106 static void miRegionOp(
107 register Region newReg, /* Place to store result */
108 Region reg1, /* First region in operation */
109 Region reg2, /* 2d region in operation */
110 int (*overlapFunc)(
111 register Region pReg,
112 register BoxPtr r1,
113 BoxPtr r1End,
114 register BoxPtr r2,
115 BoxPtr r2End,
116 short y1,
117 short y2), /* Function to call for over-
118 * lapping bands */
119 int (*nonOverlap1Func)(
120 register Region pReg,
121 register BoxPtr r,
122 BoxPtr rEnd,
123 register short y1,
124 register short y2), /* Function to call for non-
125 * overlapping bands in region
126 * 1 */
127 int (*nonOverlap2Func)(
128 register Region pReg,
129 register BoxPtr r,
130 BoxPtr rEnd,
131 register short y1,
132 register short y2)); /* Function to call for non-
133 * overlapping bands in region
134 * 2 */
135
136
137 /* Create a new empty region */
138 Region
XCreateRegion(void)139 XCreateRegion(void)
140 {
141 Region temp;
142
143 if (! (temp = Xmalloc(sizeof( REGION ))))
144 return (Region) NULL;
145 if (! (temp->rects = Xmalloc(sizeof( BOX )))) {
146 Xfree(temp);
147 return (Region) NULL;
148 }
149 temp->numRects = 0;
150 temp->extents.x1 = 0;
151 temp->extents.y1 = 0;
152 temp->extents.x2 = 0;
153 temp->extents.y2 = 0;
154 temp->size = 1;
155 return( temp );
156 }
157
158 int
XClipBox(Region r,XRectangle * rect)159 XClipBox(
160 Region r,
161 XRectangle *rect)
162 {
163 rect->x = r->extents.x1;
164 rect->y = r->extents.y1;
165 rect->width = r->extents.x2 - r->extents.x1;
166 rect->height = r->extents.y2 - r->extents.y1;
167 return 1;
168 }
169
170 int
XUnionRectWithRegion(register XRectangle * rect,Region source,Region dest)171 XUnionRectWithRegion(
172 register XRectangle *rect,
173 Region source, Region dest)
174 {
175 REGION region;
176
177 if (!rect->width || !rect->height)
178 return 0;
179 region.rects = ®ion.extents;
180 region.numRects = 1;
181 region.extents.x1 = rect->x;
182 region.extents.y1 = rect->y;
183 region.extents.x2 = rect->x + rect->width;
184 region.extents.y2 = rect->y + rect->height;
185 region.size = 1;
186
187 return XUnionRegion(®ion, source, dest);
188 }
189
190 /*-
191 *-----------------------------------------------------------------------
192 * miSetExtents --
193 * Reset the extents of a region to what they should be. Called by
194 * miSubtract and miIntersect b/c they can't figure it out along the
195 * way or do so easily, as miUnion can.
196 *
197 * Results:
198 * None.
199 *
200 * Side Effects:
201 * The region's 'extents' structure is overwritten.
202 *
203 *-----------------------------------------------------------------------
204 */
205 static void
miSetExtents(Region pReg)206 miSetExtents (
207 Region pReg)
208 {
209 register BoxPtr pBox,
210 pBoxEnd,
211 pExtents;
212
213 if (pReg->numRects == 0)
214 {
215 pReg->extents.x1 = 0;
216 pReg->extents.y1 = 0;
217 pReg->extents.x2 = 0;
218 pReg->extents.y2 = 0;
219 return;
220 }
221
222 pExtents = &pReg->extents;
223 pBox = pReg->rects;
224 pBoxEnd = &pBox[pReg->numRects - 1];
225
226 /*
227 * Since pBox is the first rectangle in the region, it must have the
228 * smallest y1 and since pBoxEnd is the last rectangle in the region,
229 * it must have the largest y2, because of banding. Initialize x1 and
230 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
231 * to...
232 */
233 pExtents->x1 = pBox->x1;
234 pExtents->y1 = pBox->y1;
235 pExtents->x2 = pBoxEnd->x2;
236 pExtents->y2 = pBoxEnd->y2;
237
238 assert(pExtents->y1 < pExtents->y2);
239 while (pBox <= pBoxEnd)
240 {
241 if (pBox->x1 < pExtents->x1)
242 {
243 pExtents->x1 = pBox->x1;
244 }
245 if (pBox->x2 > pExtents->x2)
246 {
247 pExtents->x2 = pBox->x2;
248 }
249 pBox++;
250 }
251 assert(pExtents->x1 < pExtents->x2);
252 }
253
254 int
XSetRegion(Display * dpy,GC gc,register Region r)255 XSetRegion(
256 Display *dpy,
257 GC gc,
258 register Region r)
259 {
260 register int i;
261 register XRectangle *xr, *pr;
262 register BOX *pb;
263 unsigned long total;
264
265 LockDisplay (dpy);
266 total = r->numRects * sizeof (XRectangle);
267 if ((xr = (XRectangle *) _XAllocTemp(dpy, total))) {
268 for (pr = xr, pb = r->rects, i = r->numRects; --i >= 0; pr++, pb++) {
269 pr->x = pb->x1;
270 pr->y = pb->y1;
271 pr->width = pb->x2 - pb->x1;
272 pr->height = pb->y2 - pb->y1;
273 }
274 }
275 if (xr || !r->numRects)
276 _XSetClipRectangles(dpy, gc, 0, 0, xr, r->numRects, YXBanded);
277 if (xr)
278 _XFreeTemp(dpy, (char *)xr, total);
279 UnlockDisplay(dpy);
280 SyncHandle();
281 return 1;
282 }
283
284 int
XDestroyRegion(Region r)285 XDestroyRegion(
286 Region r)
287 {
288 Xfree( (char *) r->rects );
289 Xfree( (char *) r );
290 return 1;
291 }
292
293
294 /* TranslateRegion(pRegion, x, y)
295 translates in place
296 added by raymond
297 */
298
299 int
XOffsetRegion(register Region pRegion,register int x,register int y)300 XOffsetRegion(
301 register Region pRegion,
302 register int x,
303 register int y)
304 {
305 register int nbox;
306 register BOX *pbox;
307
308 pbox = pRegion->rects;
309 nbox = pRegion->numRects;
310
311 while(nbox--)
312 {
313 pbox->x1 += x;
314 pbox->x2 += x;
315 pbox->y1 += y;
316 pbox->y2 += y;
317 pbox++;
318 }
319 pRegion->extents.x1 += x;
320 pRegion->extents.x2 += x;
321 pRegion->extents.y1 += y;
322 pRegion->extents.y2 += y;
323 return 1;
324 }
325
326 /*
327 Utility procedure Compress:
328 Replace r by the region r', where
329 p in r' iff (Quantifer m <= dx) (p + m in r), and
330 Quantifier is Exists if grow is TRUE, For all if grow is FALSE, and
331 (x,y) + m = (x+m,y) if xdir is TRUE; (x,y+m) if xdir is FALSE.
332
333 Thus, if xdir is TRUE and grow is FALSE, r is replaced by the region
334 of all points p such that p and the next dx points on the same
335 horizontal scan line are all in r. We do this using by noting
336 that p is the head of a run of length 2^i + k iff p is the head
337 of a run of length 2^i and p+2^i is the head of a run of length
338 k. Thus, the loop invariant: s contains the region corresponding
339 to the runs of length shift. r contains the region corresponding
340 to the runs of length 1 + dxo & (shift-1), where dxo is the original
341 value of dx. dx = dxo & ~(shift-1). As parameters, s and t are
342 scratch regions, so that we don't have to allocate them on every
343 call.
344 */
345
346 #define ZOpRegion(a,b,c) if (grow) XUnionRegion(a,b,c); \
347 else XIntersectRegion(a,b,c)
348 #define ZShiftRegion(a,b) if (xdir) XOffsetRegion(a,b,0); \
349 else XOffsetRegion(a,0,b)
350 #define ZCopyRegion(a,b) XUnionRegion(a,a,b)
351
352 static void
Compress(Region r,Region s,Region t,register unsigned dx,register int xdir,register int grow)353 Compress(
354 Region r, Region s, Region t,
355 register unsigned dx,
356 register int xdir, register int grow)
357 {
358 register unsigned shift = 1;
359
360 ZCopyRegion(r, s);
361 while (dx) {
362 if (dx & shift) {
363 ZShiftRegion(r, -(int)shift);
364 ZOpRegion(r, s, r);
365 dx -= shift;
366 if (!dx) break;
367 }
368 ZCopyRegion(s, t);
369 ZShiftRegion(s, -(int)shift);
370 ZOpRegion(s, t, s);
371 shift <<= 1;
372 }
373 }
374
375 #undef ZOpRegion
376 #undef ZShiftRegion
377 #undef ZCopyRegion
378
379 int
XShrinkRegion(Region r,int dx,int dy)380 XShrinkRegion(
381 Region r,
382 int dx, int dy)
383 {
384 Region s, t;
385 int grow;
386
387 if (!dx && !dy) return 0;
388 if (! (s = XCreateRegion()) )
389 return 0;
390 if (! (t = XCreateRegion()) ) {
391 XDestroyRegion(s);
392 return 0;
393 }
394 if ((grow = (dx < 0))) dx = -dx;
395 if (dx) Compress(r, s, t, (unsigned) 2*dx, TRUE, grow);
396 if ((grow = (dy < 0))) dy = -dy;
397 if (dy) Compress(r, s, t, (unsigned) 2*dy, FALSE, grow);
398 XOffsetRegion(r, dx, dy);
399 XDestroyRegion(s);
400 XDestroyRegion(t);
401 return 0;
402 }
403
404
405 /*======================================================================
406 * Region Intersection
407 *====================================================================*/
408 /*-
409 *-----------------------------------------------------------------------
410 * miIntersectO --
411 * Handle an overlapping band for miIntersect.
412 *
413 * Results:
414 * None.
415 *
416 * Side Effects:
417 * Rectangles may be added to the region.
418 *
419 *-----------------------------------------------------------------------
420 */
421 /* static void*/
422 static int
miIntersectO(register Region pReg,register BoxPtr r1,BoxPtr r1End,register BoxPtr r2,BoxPtr r2End,short y1,short y2)423 miIntersectO (
424 register Region pReg,
425 register BoxPtr r1,
426 BoxPtr r1End,
427 register BoxPtr r2,
428 BoxPtr r2End,
429 short y1,
430 short y2)
431 {
432 register short x1;
433 register short x2;
434 register BoxPtr pNextRect;
435
436 pNextRect = &pReg->rects[pReg->numRects];
437
438 while ((r1 != r1End) && (r2 != r2End))
439 {
440 x1 = max(r1->x1,r2->x1);
441 x2 = min(r1->x2,r2->x2);
442
443 /*
444 * If there's any overlap between the two rectangles, add that
445 * overlap to the new region.
446 * There's no need to check for subsumption because the only way
447 * such a need could arise is if some region has two rectangles
448 * right next to each other. Since that should never happen...
449 */
450 if (x1 < x2)
451 {
452 assert(y1<y2);
453
454 MEMCHECK(pReg, pNextRect, pReg->rects);
455 pNextRect->x1 = x1;
456 pNextRect->y1 = y1;
457 pNextRect->x2 = x2;
458 pNextRect->y2 = y2;
459 pReg->numRects += 1;
460 pNextRect++;
461 assert(pReg->numRects <= pReg->size);
462 }
463
464 /*
465 * Need to advance the pointers. Shift the one that extends
466 * to the right the least, since the other still has a chance to
467 * overlap with that region's next rectangle, if you see what I mean.
468 */
469 if (r1->x2 < r2->x2)
470 {
471 r1++;
472 }
473 else if (r2->x2 < r1->x2)
474 {
475 r2++;
476 }
477 else
478 {
479 r1++;
480 r2++;
481 }
482 }
483 return 0; /* lint */
484 }
485
486 int
XIntersectRegion(Region reg1,Region reg2,register Region newReg)487 XIntersectRegion(
488 Region reg1,
489 Region reg2, /* source regions */
490 register Region newReg) /* destination Region */
491 {
492 /* check for trivial reject */
493 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
494 (!EXTENTCHECK(®1->extents, ®2->extents)))
495 newReg->numRects = 0;
496 else
497 miRegionOp (newReg, reg1, reg2,
498 miIntersectO, NULL, NULL);
499
500 /*
501 * Can't alter newReg's extents before we call miRegionOp because
502 * it might be one of the source regions and miRegionOp depends
503 * on the extents of those regions being the same. Besides, this
504 * way there's no checking against rectangles that will be nuked
505 * due to coalescing, so we have to examine fewer rectangles.
506 */
507 miSetExtents(newReg);
508 return 1;
509 }
510
511 static int
miRegionCopy(register Region dstrgn,register Region rgn)512 miRegionCopy(
513 register Region dstrgn,
514 register Region rgn)
515
516 {
517 if (dstrgn != rgn) /* don't want to copy to itself */
518 {
519 if (dstrgn->size < rgn->numRects)
520 {
521 if (dstrgn->rects)
522 {
523 BOX *prevRects = dstrgn->rects;
524
525 dstrgn->rects = Xreallocarray(dstrgn->rects,
526 rgn->numRects, sizeof(BOX));
527 if (! dstrgn->rects) {
528 Xfree(prevRects);
529 dstrgn->size = 0;
530 return 0;
531 }
532 }
533 dstrgn->size = rgn->numRects;
534 }
535 dstrgn->numRects = rgn->numRects;
536 dstrgn->extents.x1 = rgn->extents.x1;
537 dstrgn->extents.y1 = rgn->extents.y1;
538 dstrgn->extents.x2 = rgn->extents.x2;
539 dstrgn->extents.y2 = rgn->extents.y2;
540
541 memcpy((char *) dstrgn->rects, (char *) rgn->rects,
542 (int) (rgn->numRects * sizeof(BOX)));
543 }
544 return 1;
545 }
546
547 /*======================================================================
548 * Generic Region Operator
549 *====================================================================*/
550
551 /*-
552 *-----------------------------------------------------------------------
553 * miCoalesce --
554 * Attempt to merge the boxes in the current band with those in the
555 * previous one. Used only by miRegionOp.
556 *
557 * Results:
558 * The new index for the previous band.
559 *
560 * Side Effects:
561 * If coalescing takes place:
562 * - rectangles in the previous band will have their y2 fields
563 * altered.
564 * - pReg->numRects will be decreased.
565 *
566 *-----------------------------------------------------------------------
567 */
568 /* static int*/
569 static int
miCoalesce(register Region pReg,int prevStart,int curStart)570 miCoalesce(
571 register Region pReg, /* Region to coalesce */
572 int prevStart, /* Index of start of previous band */
573 int curStart) /* Index of start of current band */
574 {
575 register BoxPtr pPrevBox; /* Current box in previous band */
576 register BoxPtr pCurBox; /* Current box in current band */
577 register BoxPtr pRegEnd; /* End of region */
578 int curNumRects; /* Number of rectangles in current
579 * band */
580 int prevNumRects; /* Number of rectangles in previous
581 * band */
582 int bandY1; /* Y1 coordinate for current band */
583
584 pRegEnd = &pReg->rects[pReg->numRects];
585
586 pPrevBox = &pReg->rects[prevStart];
587 prevNumRects = curStart - prevStart;
588
589 /*
590 * Figure out how many rectangles are in the current band. Have to do
591 * this because multiple bands could have been added in miRegionOp
592 * at the end when one region has been exhausted.
593 */
594 pCurBox = &pReg->rects[curStart];
595 bandY1 = pCurBox->y1;
596 for (curNumRects = 0;
597 (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
598 curNumRects++)
599 {
600 pCurBox++;
601 }
602
603 if (pCurBox != pRegEnd)
604 {
605 /*
606 * If more than one band was added, we have to find the start
607 * of the last band added so the next coalescing job can start
608 * at the right place... (given when multiple bands are added,
609 * this may be pointless -- see above).
610 */
611 pRegEnd--;
612 while (pRegEnd[-1].y1 == pRegEnd->y1)
613 {
614 pRegEnd--;
615 }
616 curStart = pRegEnd - pReg->rects;
617 pRegEnd = pReg->rects + pReg->numRects;
618 }
619
620 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
621 pCurBox -= curNumRects;
622 /*
623 * The bands may only be coalesced if the bottom of the previous
624 * matches the top scanline of the current.
625 */
626 if (pPrevBox->y2 == pCurBox->y1)
627 {
628 /*
629 * Make sure the bands have boxes in the same places. This
630 * assumes that boxes have been added in such a way that they
631 * cover the most area possible. I.e. two boxes in a band must
632 * have some horizontal space between them.
633 */
634 do
635 {
636 if ((pPrevBox->x1 != pCurBox->x1) ||
637 (pPrevBox->x2 != pCurBox->x2))
638 {
639 /*
640 * The bands don't line up so they can't be coalesced.
641 */
642 return (curStart);
643 }
644 pPrevBox++;
645 pCurBox++;
646 prevNumRects -= 1;
647 } while (prevNumRects != 0);
648
649 pReg->numRects -= curNumRects;
650 pCurBox -= curNumRects;
651 pPrevBox -= curNumRects;
652
653 /*
654 * The bands may be merged, so set the bottom y of each box
655 * in the previous band to that of the corresponding box in
656 * the current band.
657 */
658 do
659 {
660 pPrevBox->y2 = pCurBox->y2;
661 pPrevBox++;
662 pCurBox++;
663 curNumRects -= 1;
664 } while (curNumRects != 0);
665
666 /*
667 * If only one band was added to the region, we have to backup
668 * curStart to the start of the previous band.
669 *
670 * If more than one band was added to the region, copy the
671 * other bands down. The assumption here is that the other bands
672 * came from the same region as the current one and no further
673 * coalescing can be done on them since it's all been done
674 * already... curStart is already in the right place.
675 */
676 if (pCurBox == pRegEnd)
677 {
678 curStart = prevStart;
679 }
680 else
681 {
682 do
683 {
684 *pPrevBox++ = *pCurBox++;
685 } while (pCurBox != pRegEnd);
686 }
687
688 }
689 }
690 return (curStart);
691 }
692
693 /*-
694 *-----------------------------------------------------------------------
695 * miRegionOp --
696 * Apply an operation to two regions. Called by miUnion, miInverse,
697 * miSubtract, miIntersect...
698 *
699 * Results:
700 * None.
701 *
702 * Side Effects:
703 * The new region is overwritten.
704 *
705 * Notes:
706 * The idea behind this function is to view the two regions as sets.
707 * Together they cover a rectangle of area that this function divides
708 * into horizontal bands where points are covered only by one region
709 * or by both. For the first case, the nonOverlapFunc is called with
710 * each the band and the band's upper and lower extents. For the
711 * second, the overlapFunc is called to process the entire band. It
712 * is responsible for clipping the rectangles in the band, though
713 * this function provides the boundaries.
714 * At the end of each band, the new region is coalesced, if possible,
715 * to reduce the number of rectangles in the region.
716 *
717 *-----------------------------------------------------------------------
718 */
719 /* static void*/
720 static void
miRegionOp(register Region newReg,Region reg1,Region reg2,int (* overlapFunc)(register Region pReg,register BoxPtr r1,BoxPtr r1End,register BoxPtr r2,BoxPtr r2End,short y1,short y2),int (* nonOverlap1Func)(register Region pReg,register BoxPtr r,BoxPtr rEnd,register short y1,register short y2),int (* nonOverlap2Func)(register Region pReg,register BoxPtr r,BoxPtr rEnd,register short y1,register short y2))721 miRegionOp(
722 register Region newReg, /* Place to store result */
723 Region reg1, /* First region in operation */
724 Region reg2, /* 2d region in operation */
725 int (*overlapFunc)(
726 register Region pReg,
727 register BoxPtr r1,
728 BoxPtr r1End,
729 register BoxPtr r2,
730 BoxPtr r2End,
731 short y1,
732 short y2), /* Function to call for over-
733 * lapping bands */
734 int (*nonOverlap1Func)(
735 register Region pReg,
736 register BoxPtr r,
737 BoxPtr rEnd,
738 register short y1,
739 register short y2), /* Function to call for non-
740 * overlapping bands in region
741 * 1 */
742 int (*nonOverlap2Func)(
743 register Region pReg,
744 register BoxPtr r,
745 BoxPtr rEnd,
746 register short y1,
747 register short y2)) /* Function to call for non-
748 * overlapping bands in region
749 * 2 */
750 {
751 register BoxPtr r1; /* Pointer into first region */
752 register BoxPtr r2; /* Pointer into 2d region */
753 BoxPtr r1End; /* End of 1st region */
754 BoxPtr r2End; /* End of 2d region */
755 register short ybot; /* Bottom of intersection */
756 register short ytop; /* Top of intersection */
757 BoxPtr oldRects; /* Old rects for newReg */
758 int prevBand; /* Index of start of
759 * previous band in newReg */
760 int curBand; /* Index of start of current
761 * band in newReg */
762 register BoxPtr r1BandEnd; /* End of current band in r1 */
763 register BoxPtr r2BandEnd; /* End of current band in r2 */
764 short top; /* Top of non-overlapping
765 * band */
766 short bot; /* Bottom of non-overlapping
767 * band */
768
769 /*
770 * Initialization:
771 * set r1, r2, r1End and r2End appropriately, preserve the important
772 * parts of the destination region until the end in case it's one of
773 * the two source regions, then mark the "new" region empty, allocating
774 * another array of rectangles for it to use.
775 */
776 r1 = reg1->rects;
777 r2 = reg2->rects;
778 r1End = r1 + reg1->numRects;
779 r2End = r2 + reg2->numRects;
780
781 oldRects = newReg->rects;
782
783 EMPTY_REGION(newReg);
784
785 /*
786 * Allocate a reasonable number of rectangles for the new region. The idea
787 * is to allocate enough so the individual functions don't need to
788 * reallocate and copy the array, which is time consuming, yet we don't
789 * have to worry about using too much memory. I hope to be able to
790 * nuke the Xrealloc() at the end of this function eventually.
791 */
792 newReg->size = max(reg1->numRects,reg2->numRects) * 2;
793
794 if (! (newReg->rects = Xmallocarray (newReg->size, sizeof(BoxRec)))) {
795 newReg->size = 0;
796 return;
797 }
798
799 /*
800 * Initialize ybot and ytop.
801 * In the upcoming loop, ybot and ytop serve different functions depending
802 * on whether the band being handled is an overlapping or non-overlapping
803 * band.
804 * In the case of a non-overlapping band (only one of the regions
805 * has points in the band), ybot is the bottom of the most recent
806 * intersection and thus clips the top of the rectangles in that band.
807 * ytop is the top of the next intersection between the two regions and
808 * serves to clip the bottom of the rectangles in the current band.
809 * For an overlapping band (where the two regions intersect), ytop clips
810 * the top of the rectangles of both regions and ybot clips the bottoms.
811 */
812 if (reg1->extents.y1 < reg2->extents.y1)
813 ybot = reg1->extents.y1;
814 else
815 ybot = reg2->extents.y1;
816
817 /*
818 * prevBand serves to mark the start of the previous band so rectangles
819 * can be coalesced into larger rectangles. qv. miCoalesce, above.
820 * In the beginning, there is no previous band, so prevBand == curBand
821 * (curBand is set later on, of course, but the first band will always
822 * start at index 0). prevBand and curBand must be indices because of
823 * the possible expansion, and resultant moving, of the new region's
824 * array of rectangles.
825 */
826 prevBand = 0;
827
828 do
829 {
830 curBand = newReg->numRects;
831
832 /*
833 * This algorithm proceeds one source-band (as opposed to a
834 * destination band, which is determined by where the two regions
835 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
836 * rectangle after the last one in the current band for their
837 * respective regions.
838 */
839 r1BandEnd = r1;
840 while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
841 {
842 r1BandEnd++;
843 }
844
845 r2BandEnd = r2;
846 while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
847 {
848 r2BandEnd++;
849 }
850
851 /*
852 * First handle the band that doesn't intersect, if any.
853 *
854 * Note that attention is restricted to one band in the
855 * non-intersecting region at once, so if a region has n
856 * bands between the current position and the next place it overlaps
857 * the other, this entire loop will be passed through n times.
858 */
859 if (r1->y1 < r2->y1)
860 {
861 top = max(r1->y1,ybot);
862 bot = min(r1->y2,r2->y1);
863
864 if ((top != bot) && (nonOverlap1Func != NULL))
865 {
866 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
867 }
868
869 ytop = r2->y1;
870 }
871 else if (r2->y1 < r1->y1)
872 {
873 top = max(r2->y1,ybot);
874 bot = min(r2->y2,r1->y1);
875
876 if ((top != bot) && (nonOverlap2Func != NULL))
877 {
878 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
879 }
880
881 ytop = r1->y1;
882 }
883 else
884 {
885 ytop = r1->y1;
886 }
887
888 /*
889 * If any rectangles got added to the region, try and coalesce them
890 * with rectangles from the previous band. Note we could just do
891 * this test in miCoalesce, but some machines incur a not
892 * inconsiderable cost for function calls, so...
893 */
894 if (newReg->numRects != curBand)
895 {
896 prevBand = miCoalesce (newReg, prevBand, curBand);
897 }
898
899 /*
900 * Now see if we've hit an intersecting band. The two bands only
901 * intersect if ybot > ytop
902 */
903 ybot = min(r1->y2, r2->y2);
904 curBand = newReg->numRects;
905 if (ybot > ytop)
906 {
907 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
908
909 }
910
911 if (newReg->numRects != curBand)
912 {
913 prevBand = miCoalesce (newReg, prevBand, curBand);
914 }
915
916 /*
917 * If we've finished with a band (y2 == ybot) we skip forward
918 * in the region to the next band.
919 */
920 if (r1->y2 == ybot)
921 {
922 r1 = r1BandEnd;
923 }
924 if (r2->y2 == ybot)
925 {
926 r2 = r2BandEnd;
927 }
928 } while ((r1 != r1End) && (r2 != r2End));
929
930 /*
931 * Deal with whichever region still has rectangles left.
932 */
933 curBand = newReg->numRects;
934 if (r1 != r1End)
935 {
936 if (nonOverlap1Func != NULL)
937 {
938 do
939 {
940 r1BandEnd = r1;
941 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
942 {
943 r1BandEnd++;
944 }
945 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
946 max(r1->y1,ybot), r1->y2);
947 r1 = r1BandEnd;
948 } while (r1 != r1End);
949 }
950 }
951 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
952 {
953 do
954 {
955 r2BandEnd = r2;
956 while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
957 {
958 r2BandEnd++;
959 }
960 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
961 max(r2->y1,ybot), r2->y2);
962 r2 = r2BandEnd;
963 } while (r2 != r2End);
964 }
965
966 if (newReg->numRects != curBand)
967 {
968 (void) miCoalesce (newReg, prevBand, curBand);
969 }
970
971 /*
972 * A bit of cleanup. To keep regions from growing without bound,
973 * we shrink the array of rectangles to match the new number of
974 * rectangles in the region. This never goes to 0, however...
975 *
976 * Only do this stuff if the number of rectangles allocated is more than
977 * twice the number of rectangles in the region (a simple optimization...).
978 */
979 if (newReg->numRects < (newReg->size >> 1))
980 {
981 if (REGION_NOT_EMPTY(newReg))
982 {
983 BoxPtr prev_rects = newReg->rects;
984 newReg->rects = Xreallocarray (newReg->rects,
985 newReg->numRects, sizeof(BoxRec));
986 if (! newReg->rects)
987 newReg->rects = prev_rects;
988 else
989 newReg->size = newReg->numRects;
990 }
991 else
992 {
993 /*
994 * No point in doing the extra work involved in an Xrealloc if
995 * the region is empty
996 */
997 newReg->size = 1;
998 Xfree(newReg->rects);
999 newReg->rects = Xmalloc(sizeof(BoxRec));
1000 }
1001 }
1002 Xfree (oldRects);
1003 return;
1004 }
1005
1006
1007 /*======================================================================
1008 * Region Union
1009 *====================================================================*/
1010
1011 /*-
1012 *-----------------------------------------------------------------------
1013 * miUnionNonO --
1014 * Handle a non-overlapping band for the union operation. Just
1015 * Adds the rectangles into the region. Doesn't have to check for
1016 * subsumption or anything.
1017 *
1018 * Results:
1019 * None.
1020 *
1021 * Side Effects:
1022 * pReg->numRects is incremented and the final rectangles overwritten
1023 * with the rectangles we're passed.
1024 *
1025 *-----------------------------------------------------------------------
1026 */
1027 /* static void*/
1028 static int
miUnionNonO(register Region pReg,register BoxPtr r,BoxPtr rEnd,register short y1,register short y2)1029 miUnionNonO (
1030 register Region pReg,
1031 register BoxPtr r,
1032 BoxPtr rEnd,
1033 register short y1,
1034 register short y2)
1035 {
1036 register BoxPtr pNextRect;
1037
1038 pNextRect = &pReg->rects[pReg->numRects];
1039
1040 assert(y1 < y2);
1041
1042 while (r != rEnd)
1043 {
1044 assert(r->x1 < r->x2);
1045 MEMCHECK(pReg, pNextRect, pReg->rects);
1046 pNextRect->x1 = r->x1;
1047 pNextRect->y1 = y1;
1048 pNextRect->x2 = r->x2;
1049 pNextRect->y2 = y2;
1050 pReg->numRects += 1;
1051 pNextRect++;
1052
1053 assert(pReg->numRects<=pReg->size);
1054 r++;
1055 }
1056 return 0; /* lint */
1057 }
1058
1059
1060 /*-
1061 *-----------------------------------------------------------------------
1062 * miUnionO --
1063 * Handle an overlapping band for the union operation. Picks the
1064 * left-most rectangle each time and merges it into the region.
1065 *
1066 * Results:
1067 * None.
1068 *
1069 * Side Effects:
1070 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1071 * be changed.
1072 *
1073 *-----------------------------------------------------------------------
1074 */
1075
1076 /* static void*/
1077 static int
miUnionO(register Region pReg,register BoxPtr r1,BoxPtr r1End,register BoxPtr r2,BoxPtr r2End,register short y1,register short y2)1078 miUnionO (
1079 register Region pReg,
1080 register BoxPtr r1,
1081 BoxPtr r1End,
1082 register BoxPtr r2,
1083 BoxPtr r2End,
1084 register short y1,
1085 register short y2)
1086 {
1087 register BoxPtr pNextRect;
1088
1089 pNextRect = &pReg->rects[pReg->numRects];
1090
1091 #define MERGERECT(r) \
1092 if ((pReg->numRects != 0) && \
1093 (pNextRect[-1].y1 == y1) && \
1094 (pNextRect[-1].y2 == y2) && \
1095 (pNextRect[-1].x2 >= r->x1)) \
1096 { \
1097 if (pNextRect[-1].x2 < r->x2) \
1098 { \
1099 pNextRect[-1].x2 = r->x2; \
1100 assert(pNextRect[-1].x1<pNextRect[-1].x2); \
1101 } \
1102 } \
1103 else \
1104 { \
1105 MEMCHECK(pReg, pNextRect, pReg->rects); \
1106 pNextRect->y1 = y1; \
1107 pNextRect->y2 = y2; \
1108 pNextRect->x1 = r->x1; \
1109 pNextRect->x2 = r->x2; \
1110 pReg->numRects += 1; \
1111 pNextRect += 1; \
1112 } \
1113 assert(pReg->numRects<=pReg->size);\
1114 r++;
1115
1116 assert (y1<y2);
1117 while ((r1 != r1End) && (r2 != r2End))
1118 {
1119 if (r1->x1 < r2->x1)
1120 {
1121 MERGERECT(r1);
1122 }
1123 else
1124 {
1125 MERGERECT(r2);
1126 }
1127 }
1128
1129 if (r1 != r1End)
1130 {
1131 do
1132 {
1133 MERGERECT(r1);
1134 } while (r1 != r1End);
1135 }
1136 else while (r2 != r2End)
1137 {
1138 MERGERECT(r2);
1139 }
1140 return 0; /* lint */
1141 }
1142
1143 int
XUnionRegion(Region reg1,Region reg2,Region newReg)1144 XUnionRegion(
1145 Region reg1,
1146 Region reg2, /* source regions */
1147 Region newReg) /* destination Region */
1148 {
1149 /* checks all the simple cases */
1150
1151 /*
1152 * Region 1 and 2 are the same or region 1 is empty
1153 */
1154 if ( (reg1 == reg2) || (!(reg1->numRects)) )
1155 {
1156 if (newReg != reg2)
1157 return miRegionCopy(newReg, reg2);
1158 return 1;
1159 }
1160
1161 /*
1162 * if nothing to union (region 2 empty)
1163 */
1164 if (!(reg2->numRects))
1165 {
1166 if (newReg != reg1)
1167 return miRegionCopy(newReg, reg1);
1168 return 1;
1169 }
1170
1171 /*
1172 * Region 1 completely subsumes region 2
1173 */
1174 if ((reg1->numRects == 1) &&
1175 (reg1->extents.x1 <= reg2->extents.x1) &&
1176 (reg1->extents.y1 <= reg2->extents.y1) &&
1177 (reg1->extents.x2 >= reg2->extents.x2) &&
1178 (reg1->extents.y2 >= reg2->extents.y2))
1179 {
1180 if (newReg != reg1)
1181 return miRegionCopy(newReg, reg1);
1182 return 1;
1183 }
1184
1185 /*
1186 * Region 2 completely subsumes region 1
1187 */
1188 if ((reg2->numRects == 1) &&
1189 (reg2->extents.x1 <= reg1->extents.x1) &&
1190 (reg2->extents.y1 <= reg1->extents.y1) &&
1191 (reg2->extents.x2 >= reg1->extents.x2) &&
1192 (reg2->extents.y2 >= reg1->extents.y2))
1193 {
1194 if (newReg != reg2)
1195 return miRegionCopy(newReg, reg2);
1196 return 1;
1197 }
1198
1199 miRegionOp (newReg, reg1, reg2, miUnionO,
1200 miUnionNonO, miUnionNonO);
1201
1202 newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
1203 newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
1204 newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
1205 newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
1206
1207 return 1;
1208 }
1209
1210
1211 /*======================================================================
1212 * Region Subtraction
1213 *====================================================================*/
1214
1215 /*-
1216 *-----------------------------------------------------------------------
1217 * miSubtractNonO --
1218 * Deal with non-overlapping band for subtraction. Any parts from
1219 * region 2 we discard. Anything from region 1 we add to the region.
1220 *
1221 * Results:
1222 * None.
1223 *
1224 * Side Effects:
1225 * pReg may be affected.
1226 *
1227 *-----------------------------------------------------------------------
1228 */
1229 /* static void*/
1230 static int
miSubtractNonO1(register Region pReg,register BoxPtr r,BoxPtr rEnd,register short y1,register short y2)1231 miSubtractNonO1 (
1232 register Region pReg,
1233 register BoxPtr r,
1234 BoxPtr rEnd,
1235 register short y1,
1236 register short y2)
1237 {
1238 register BoxPtr pNextRect;
1239
1240 pNextRect = &pReg->rects[pReg->numRects];
1241
1242 assert(y1<y2);
1243
1244 while (r != rEnd)
1245 {
1246 assert(r->x1<r->x2);
1247 MEMCHECK(pReg, pNextRect, pReg->rects);
1248 pNextRect->x1 = r->x1;
1249 pNextRect->y1 = y1;
1250 pNextRect->x2 = r->x2;
1251 pNextRect->y2 = y2;
1252 pReg->numRects += 1;
1253 pNextRect++;
1254
1255 assert(pReg->numRects <= pReg->size);
1256
1257 r++;
1258 }
1259 return 0; /* lint */
1260 }
1261
1262 /*-
1263 *-----------------------------------------------------------------------
1264 * miSubtractO --
1265 * Overlapping band subtraction. x1 is the left-most point not yet
1266 * checked.
1267 *
1268 * Results:
1269 * None.
1270 *
1271 * Side Effects:
1272 * pReg may have rectangles added to it.
1273 *
1274 *-----------------------------------------------------------------------
1275 */
1276 /* static void*/
1277 static int
miSubtractO(register Region pReg,register BoxPtr r1,BoxPtr r1End,register BoxPtr r2,BoxPtr r2End,register short y1,register short y2)1278 miSubtractO (
1279 register Region pReg,
1280 register BoxPtr r1,
1281 BoxPtr r1End,
1282 register BoxPtr r2,
1283 BoxPtr r2End,
1284 register short y1,
1285 register short y2)
1286 {
1287 register BoxPtr pNextRect;
1288 register int x1;
1289
1290 x1 = r1->x1;
1291
1292 assert(y1<y2);
1293 pNextRect = &pReg->rects[pReg->numRects];
1294
1295 while ((r1 != r1End) && (r2 != r2End))
1296 {
1297 if (r2->x2 <= x1)
1298 {
1299 /*
1300 * Subtrahend missed the boat: go to next subtrahend.
1301 */
1302 r2++;
1303 }
1304 else if (r2->x1 <= x1)
1305 {
1306 /*
1307 * Subtrahend precedes minuend: nuke left edge of minuend.
1308 */
1309 x1 = r2->x2;
1310 if (x1 >= r1->x2)
1311 {
1312 /*
1313 * Minuend completely covered: advance to next minuend and
1314 * reset left fence to edge of new minuend.
1315 */
1316 r1++;
1317 if (r1 != r1End)
1318 x1 = r1->x1;
1319 }
1320 else
1321 {
1322 /*
1323 * Subtrahend now used up since it doesn't extend beyond
1324 * minuend
1325 */
1326 r2++;
1327 }
1328 }
1329 else if (r2->x1 < r1->x2)
1330 {
1331 /*
1332 * Left part of subtrahend covers part of minuend: add uncovered
1333 * part of minuend to region and skip to next subtrahend.
1334 */
1335 assert(x1<r2->x1);
1336 MEMCHECK(pReg, pNextRect, pReg->rects);
1337 pNextRect->x1 = x1;
1338 pNextRect->y1 = y1;
1339 pNextRect->x2 = r2->x1;
1340 pNextRect->y2 = y2;
1341 pReg->numRects += 1;
1342 pNextRect++;
1343
1344 assert(pReg->numRects<=pReg->size);
1345
1346 x1 = r2->x2;
1347 if (x1 >= r1->x2)
1348 {
1349 /*
1350 * Minuend used up: advance to new...
1351 */
1352 r1++;
1353 if (r1 != r1End)
1354 x1 = r1->x1;
1355 }
1356 else
1357 {
1358 /*
1359 * Subtrahend used up
1360 */
1361 r2++;
1362 }
1363 }
1364 else
1365 {
1366 /*
1367 * Minuend used up: add any remaining piece before advancing.
1368 */
1369 if (r1->x2 > x1)
1370 {
1371 MEMCHECK(pReg, pNextRect, pReg->rects);
1372 pNextRect->x1 = x1;
1373 pNextRect->y1 = y1;
1374 pNextRect->x2 = r1->x2;
1375 pNextRect->y2 = y2;
1376 pReg->numRects += 1;
1377 pNextRect++;
1378 assert(pReg->numRects<=pReg->size);
1379 }
1380 r1++;
1381 if (r1 != r1End)
1382 x1 = r1->x1;
1383 }
1384 }
1385
1386 /*
1387 * Add remaining minuend rectangles to region.
1388 */
1389 while (r1 != r1End)
1390 {
1391 assert(x1<r1->x2);
1392 MEMCHECK(pReg, pNextRect, pReg->rects);
1393 pNextRect->x1 = x1;
1394 pNextRect->y1 = y1;
1395 pNextRect->x2 = r1->x2;
1396 pNextRect->y2 = y2;
1397 pReg->numRects += 1;
1398 pNextRect++;
1399
1400 assert(pReg->numRects<=pReg->size);
1401
1402 r1++;
1403 if (r1 != r1End)
1404 {
1405 x1 = r1->x1;
1406 }
1407 }
1408 return 0; /* lint */
1409 }
1410
1411 /*-
1412 *-----------------------------------------------------------------------
1413 * miSubtract --
1414 * Subtract regS from regM and leave the result in regD.
1415 * S stands for subtrahend, M for minuend and D for difference.
1416 *
1417 * Results:
1418 * TRUE.
1419 *
1420 * Side Effects:
1421 * regD is overwritten.
1422 *
1423 *-----------------------------------------------------------------------
1424 */
1425
1426 int
XSubtractRegion(Region regM,Region regS,register Region regD)1427 XSubtractRegion(
1428 Region regM,
1429 Region regS,
1430 register Region regD)
1431 {
1432 /* check for trivial reject */
1433 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
1434 (!EXTENTCHECK(®M->extents, ®S->extents)) )
1435 {
1436 return miRegionCopy(regD, regM);
1437 }
1438
1439 miRegionOp (regD, regM, regS, miSubtractO,
1440 miSubtractNonO1, NULL);
1441
1442 /*
1443 * Can't alter newReg's extents before we call miRegionOp because
1444 * it might be one of the source regions and miRegionOp depends
1445 * on the extents of those regions being the unaltered. Besides, this
1446 * way there's no checking against rectangles that will be nuked
1447 * due to coalescing, so we have to examine fewer rectangles.
1448 */
1449 miSetExtents (regD);
1450 return 1;
1451 }
1452
1453 int
XXorRegion(Region sra,Region srb,Region dr)1454 XXorRegion(Region sra, Region srb, Region dr)
1455 {
1456 Region tra, trb;
1457
1458 if (! (tra = XCreateRegion()) )
1459 return 0;
1460 if (! (trb = XCreateRegion()) ) {
1461 XDestroyRegion(tra);
1462 return 0;
1463 }
1464 (void) XSubtractRegion(sra,srb,tra);
1465 (void) XSubtractRegion(srb,sra,trb);
1466 (void) XUnionRegion(tra,trb,dr);
1467 XDestroyRegion(tra);
1468 XDestroyRegion(trb);
1469 return 0;
1470 }
1471
1472 /*
1473 * Check to see if the region is empty. Assumes a region is passed
1474 * as a parameter
1475 */
1476 int
XEmptyRegion(Region r)1477 XEmptyRegion(
1478 Region r)
1479 {
1480 if( r->numRects == 0 ) return TRUE;
1481 else return FALSE;
1482 }
1483
1484 /*
1485 * Check to see if two regions are equal
1486 */
1487 int
XEqualRegion(Region r1,Region r2)1488 XEqualRegion(Region r1, Region r2)
1489 {
1490 int i;
1491
1492 if( r1->numRects != r2->numRects ) return FALSE;
1493 else if( r1->numRects == 0 ) return TRUE;
1494 else if ( r1->extents.x1 != r2->extents.x1 ) return FALSE;
1495 else if ( r1->extents.x2 != r2->extents.x2 ) return FALSE;
1496 else if ( r1->extents.y1 != r2->extents.y1 ) return FALSE;
1497 else if ( r1->extents.y2 != r2->extents.y2 ) return FALSE;
1498 else for( i=0; i < r1->numRects; i++ ) {
1499 if ( r1->rects[i].x1 != r2->rects[i].x1 ) return FALSE;
1500 else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return FALSE;
1501 else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return FALSE;
1502 else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return FALSE;
1503 }
1504 return TRUE;
1505 }
1506
1507 int
XPointInRegion(Region pRegion,int x,int y)1508 XPointInRegion(
1509 Region pRegion,
1510 int x, int y)
1511 {
1512 int i;
1513
1514 if (pRegion->numRects == 0)
1515 return FALSE;
1516 if (!INBOX(pRegion->extents, x, y))
1517 return FALSE;
1518 for (i=0; i<pRegion->numRects; i++)
1519 {
1520 if (INBOX (pRegion->rects[i], x, y))
1521 return TRUE;
1522 }
1523 return FALSE;
1524 }
1525
1526 int
XRectInRegion(register Region region,int rx,int ry,unsigned int rwidth,unsigned int rheight)1527 XRectInRegion(
1528 register Region region,
1529 int rx, int ry,
1530 unsigned int rwidth, unsigned int rheight)
1531 {
1532 register BoxPtr pbox;
1533 register BoxPtr pboxEnd;
1534 Box rect;
1535 register BoxPtr prect = ▭
1536 int partIn, partOut;
1537
1538 prect->x1 = rx;
1539 prect->y1 = ry;
1540 prect->x2 = rwidth + rx;
1541 prect->y2 = rheight + ry;
1542
1543 /* this is (just) a useful optimization */
1544 if ((region->numRects == 0) || !EXTENTCHECK(®ion->extents, prect))
1545 return(RectangleOut);
1546
1547 partOut = FALSE;
1548 partIn = FALSE;
1549
1550 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1551 for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1552 pbox < pboxEnd;
1553 pbox++)
1554 {
1555
1556 if (pbox->y2 <= ry)
1557 continue; /* getting up to speed or skipping remainder of band */
1558
1559 if (pbox->y1 > ry)
1560 {
1561 partOut = TRUE; /* missed part of rectangle above */
1562 if (partIn || (pbox->y1 >= prect->y2))
1563 break;
1564 ry = pbox->y1; /* x guaranteed to be == prect->x1 */
1565 }
1566
1567 if (pbox->x2 <= rx)
1568 continue; /* not far enough over yet */
1569
1570 if (pbox->x1 > rx)
1571 {
1572 partOut = TRUE; /* missed part of rectangle to left */
1573 if (partIn)
1574 break;
1575 }
1576
1577 if (pbox->x1 < prect->x2)
1578 {
1579 partIn = TRUE; /* definitely overlap */
1580 if (partOut)
1581 break;
1582 }
1583
1584 if (pbox->x2 >= prect->x2)
1585 {
1586 ry = pbox->y2; /* finished with this band */
1587 if (ry >= prect->y2)
1588 break;
1589 rx = prect->x1; /* reset x out to left again */
1590 } else
1591 {
1592 /*
1593 * Because boxes in a band are maximal width, if the first box
1594 * to overlap the rectangle doesn't completely cover it in that
1595 * band, the rectangle must be partially out, since some of it
1596 * will be uncovered in that band. partIn will have been set true
1597 * by now...
1598 */
1599 break;
1600 }
1601
1602 }
1603
1604 return(partIn ? ((ry < prect->y2) ? RectanglePart : RectangleIn) :
1605 RectangleOut);
1606 }
1607