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: regiong.cpp 41444 2006-09-25 18:18:26Z VZ $ 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 30typedef struct Box 31{ 32 wxCoord x1, x2, y1, y2; 33} Box, BOX, BoxRec, *BoxPtr; 34 35typedef struct REGION *Region; 36 37struct REGION 38{ 39public: 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 91protected: 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); 168protected: 169 long size; 170 long numRects; 171 Box *rects; 172 Box extents; 173}; 174 175// ======================================================================== 176// wxRegionRefData 177// ======================================================================== 178 179class wxRegionRefData : public wxObjectRefData, 180 public REGION 181{ 182public: 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 234private: 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 251wxRegionGeneric::wxRegionGeneric() 252{ 253} 254 255wxRegionGeneric::~wxRegionGeneric() 256{ 257} 258 259wxRegionGeneric::wxRegionGeneric(wxCoord x, wxCoord y, wxCoord w, wxCoord h) 260{ 261 m_refData = new wxRegionRefData(wxRect(x,y,w,h)); 262} 263 264wxRegionGeneric::wxRegionGeneric(const wxRect& rect) 265{ 266 m_refData = new wxRegionRefData(rect); 267} 268 269wxRegionGeneric::wxRegionGeneric(const wxPoint& topLeft, const wxPoint& bottomRight) 270{ 271 m_refData = new wxRegionRefData(topLeft, bottomRight); 272} 273 274void wxRegionGeneric::Clear() 275{ 276 UnRef(); 277} 278 279wxObjectRefData *wxRegionGeneric::CreateRefData() const 280{ 281 return new wxRegionRefData; 282} 283 284wxObjectRefData *wxRegionGeneric::CloneRefData(const wxObjectRefData *data) const 285{ 286 return new wxRegionRefData(*(wxRegionRefData *)data); 287} 288 289bool wxRegionGeneric::DoIsEqual(const wxRegion& region) const 290{ 291 return REGION::XEqualRegion(M_REGIONDATA,M_REGIONDATA_OF(region)); 292} 293 294bool 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 312bool 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(®ion,M_REGIONDATA,M_REGIONDATA); 323} 324 325bool wxRegionGeneric::DoUnionWithRegion(const wxRegion& region) 326{ 327 AllocExclusive(); 328 return REGION::XUnionRegion(M_REGIONDATA_OF(region),M_REGIONDATA,M_REGIONDATA); 329} 330 331bool wxRegionGeneric::DoIntersect(const wxRegion& region) 332{ 333 AllocExclusive(); 334 return REGION::XIntersectRegion(M_REGIONDATA_OF(region),M_REGIONDATA,M_REGIONDATA); 335} 336 337bool 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 348bool wxRegionGeneric::DoXor(const wxRegion& region) 349{ 350 AllocExclusive(); 351 return REGION::XXorRegion(M_REGIONDATA_OF(region),M_REGIONDATA,M_REGIONDATA); 352} 353 354bool 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 364bool 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)? 371wxRegionContain 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? 378wxRegionContain 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 389wxRegionIteratorGeneric::wxRegionIteratorGeneric() 390{ 391 m_current = 0; 392} 393 394wxRegionIteratorGeneric::wxRegionIteratorGeneric(const wxRegionGeneric& region) 395: m_region(region) 396{ 397 m_current = 0; 398} 399 400wxRegionIteratorGeneric::wxRegionIteratorGeneric(const wxRegionIteratorGeneric& iterator) 401: m_region(iterator.m_region) 402{ 403 m_current = iterator.m_current; 404} 405 406void wxRegionIteratorGeneric::Reset(const wxRegionGeneric& region) 407{ 408 m_region = region; 409 m_current = 0; 410} 411 412bool wxRegionIteratorGeneric::HaveRects() const 413{ 414 return M_REGIONDATA_OF(m_region)->GetBox(m_current); 415} 416 417wxRegionIteratorGeneric& wxRegionIteratorGeneric::operator++() 418{ 419 ++m_current; 420 return *this; 421} 422 423wxRegionIteratorGeneric wxRegionIteratorGeneric::operator++(int) 424{ 425 wxRegionIteratorGeneric copy(*this); 426 ++*this; 427 return copy; 428} 429 430wxRect 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 443long 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 451long 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 459long 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 467long 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 475wxRegionIteratorGeneric::~wxRegionIteratorGeneric() 476{ 477} 478 479 480// ======================================================================== 481// The guts (from X.org) 482// ======================================================================== 483 484/************************************************************************ 485 486Copyright 1987, 1988, 1998 The Open Group 487 488Permission to use, copy, modify, distribute, and sell this software and its 489documentation for any purpose is hereby granted without fee, provided that 490the above copyright notice appear in all copies and that both that 491copyright notice and this permission notice appear in supporting 492documentation. 493 494The above copyright notice and this permission notice shall be included in 495all copies or substantial portions of the Software. 496 497THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 498IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 499FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 500OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 501AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 502CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 503 504Except as contained in this notice, the name of The Open Group shall not be 505used in advertising or otherwise to promote the sale, use or other dealings 506in this Software without prior written authorization from The Open Group. 507 508 509Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts. 510 511 All Rights Reserved 512 513Permission to use, copy, modify, and distribute this software and its 514documentation for any purpose and without fee is hereby granted, 515provided that the above copyright notice appear in all copies and that 516both that copyright notice and this permission notice appear in 517supporting documentation, and that the name of Digital not be 518used in advertising or publicity pertaining to distribution of the 519software without specific, written prior permission. 520 521DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING 522ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL 523DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR 524ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 525WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 526ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 527SOFTWARE. 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 */ 592Region 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 615bool 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 */ 639void REGION:: 640miSetExtents (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 687bool REGION:: 688XDestroyRegion( 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 701bool REGION:: 702XOffsetRegion( 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*/ 745int REGION:: 746miIntersectO ( 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 809bool REGION:: 810XIntersectRegion( 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(®1->extents, ®2->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 834void REGION:: 835miRegionCopy( 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*/ 892int REGION:: 893miCoalesce( 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*/ 1044void REGION:: 1045miRegionOp( 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*/ 1353int REGION:: 1354miUnionNonO ( 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*/ 1402int REGION:: 1403miUnionO ( 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 1468bool REGION:: 1469XUnionRegion( 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*/ 1554int REGION:: 1555miSubtractNonO1 ( 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*/ 1601int REGION:: 1602miSubtractO ( 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 1750bool REGION::XSubtractRegion(Region regM, Region regS, register Region regD) 1751{ 1752 /* check for trivial reject */ 1753 if ( (!(regM->numRects)) || (!(regS->numRects)) || 1754 (!EXTENTCHECK(®M->extents, ®S->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 1774bool 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 */ 1796bool 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 */ 1805bool 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 1824bool 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 1840wxRegionContain 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 = ▭ 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(®ion->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} 1920