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