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