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