1 /***************************************************************************
2 *
3 * Project: OpenCPN
4 *
5 ***************************************************************************
6 * Portins Copyright (C) 2010 by David S. Register *
7 * *
8 * This program is free software; you can redistribute it and/or modify *
9 * it under the terms of the GNU General Public License as published by *
10 * the Free Software Foundation; either version 2 of the License, or *
11 * (at your option) any later version. *
12 * *
13 * This program is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16 * GNU General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU General Public License *
19 * along with this program; if not, write to the *
20 * Free Software Foundation, Inc., *
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *
22 ***************************************************************************
23 */
24
25 /////////////////////////////////////////////////////////////////////////////
26 // Name: src/gtk/region.cpp
27 // Purpose:
28 // Author: Robert Roebling
29 // Modified: VZ at 05.10.00: use AllocExclusive(), comparison fixed
30 // Id: $Id: region.cpp 42903 2006-11-01 12:56:38Z RR $
31 // Copyright: (c) 1998 Robert Roebling
32 // Licence: wxWindows licence
33 /////////////////////////////////////////////////////////////////////////////
34
35 // ============================================================================
36 // declarations
37 // ============================================================================
38
39 // ----------------------------------------------------------------------------
40 // headers
41 // ----------------------------------------------------------------------------
42
43 // For compilers that support precompilation, includes "wx.h".
44 #include "wx/wxprec.h"
45
46 #include "wx/region.h"
47 #include "OCPNRegion.h"
48
49 #ifndef WX_PRECOMP
50 #include "wx/log.h"
51 #endif
52
53
54 typedef enum
55 {
56 OGDK_EVEN_ODD_RULE,
57 OGDK_WINDING_RULE
58 } OGdkFillRule;
59
60 typedef enum
61 {
62 OGDK_OVERLAP_RECTANGLE_IN,
63 OGDK_OVERLAP_RECTANGLE_OUT,
64 OGDK_OVERLAP_RECTANGLE_PART
65 } OGdkOverlapType;
66
67 #define EMPTY_REGION(pReg) pReg->numRects = 0
68 #define REGION_NOT_EMPTY(pReg) pReg->numRects
69
70
71 typedef struct _OGdkPoint OGdkPoint;
72 struct _OGdkPoint
73 {
74 int x;
75 int y;
76 };
77
78
79
80 typedef struct _OGdkRectangle OGdkRectangle;
81 struct _OGdkRectangle
82 {
83 int x;
84 int y;
85 int width;
86 int height;
87 };
88
89 //#define gboolean bool;
90
91 typedef struct _OGdkSegment OGdkSegment;
92 struct _OGdkSegment
93 {
94 int x1;
95 int y1;
96 int x2;
97 int y2;
98 };
99
100 typedef OGdkSegment OGdkRegionBox;
101
102
103 typedef struct _OGdkRegion OGdkRegion;
104 struct _OGdkRegion
105 {
106 long size;
107 long numRects;
108 OGdkRegionBox *rects;
109 OGdkRegionBox extents;
110 };
111
112 /*
113 * number of points to buffer before sending them off
114 * to scanlines() : Must be an even number
115 */
116 #define NUMPTSTOBUFFER 200
117
118 /*
119 * used to allocate buffers for points and link
120 * the buffers together
121 */
122 typedef struct _OPOINTBLOCK {
123 OGdkPoint pts[NUMPTSTOBUFFER];
124 struct _OPOINTBLOCK *next;
125 } OPOINTBLOCK;
126
127 #define INBOX(r, x, y) \
128 ( ( ((r).x2 > x)) && \
129 ( ((r).x1 <= x)) && \
130 ( ((r).y2 > y)) && \
131 ( ((r).y1 <= y)) )
132
133
134 /* 1 if two BOXs overlap.
135 * 0 if two BOXs do not overlap.
136 * Remember, x2 and y2 are not in the region
137 */
138 #define EXTENTCHECK(r1, r2) \
139 ((r1)->x2 > (r2)->x1 && \
140 (r1)->x1 < (r2)->x2 && \
141 (r1)->y2 > (r2)->y1 && \
142 (r1)->y1 < (r2)->y2)
143
144
145 /*
146 * #define _OG_NEW(struct_type, n_structs, func) \
147 * ((struct_type *) malloc ((n_structs), sizeof (struct_type)))
148 * #define _OG_RENEW(struct_type, mem, n_structs, func) \
149 * ((struct_type *) realloc (mem, (n_structs), sizeof (struct_type)))
150 *
151 * #define og_new(struct_type, n_structs) _OG_NEW (struct_type, n_structs, malloc)
152 * #define og_renew(struct_type, mem, n_structs) _OG_RENEW (struct_type, mem, n_structs, realloc)
153 */
154
155
156 #define OGROWREGION(reg, nRects) { \
157 if ((nRects) == 0) { \
158 if ((reg)->rects != &(reg)->extents) { \
159 free ((reg)->rects); \
160 (reg)->rects = &(reg)->extents; \
161 } \
162 } \
163 else if ((reg)->rects == &(reg)->extents) { \
164 (reg)->rects = (OGdkRegionBox *)malloc(nRects * sizeof(OGdkRegionBox)); \
165 (reg)->rects[0] = (reg)->extents; \
166 } \
167 else \
168 (reg)->rects = (OGdkRegionBox *)realloc((reg)->rects, sizeof(OGdkRegionBox) * nRects); \
169 (reg)->size = (nRects); \
170 }
171
172 /*
173 * Check to see if there is enough memory in the present region.
174 */
175 #define OMEMCHECK(reg, rect, firstrect){ \
176 if ((reg)->numRects >= ((reg)->size - 1)) { \
177 OGROWREGION(reg,2*(reg)->size); \
178 (rect) = &(firstrect)[(reg)->numRects]; \
179 } \
180 }
181
182 #ifndef MIN
183 #define MIN(a,b) wxMin(a,b)
184 #endif
185
186 #ifndef MAX
187 #define MAX(a,b) wxMax(a,b)
188 #endif
189
190
191 /*
192 * In scan converting polygons, we want to choose those pixels
193 * which are inside the polygon. Thus, we add .5 to the starting
194 * x coordinate for both left and right edges. Now we choose the
195 * first pixel which is inside the pgon for the left edge and the
196 * first pixel which is outside the pgon for the right edge.
197 * Draw the left pixel, but not the right.
198 *
199 * How to add .5 to the starting x coordinate:
200 * If the edge is moving to the right, then subtract dy from the
201 * error term from the general form of the algorithm.
202 * If the edge is moving to the left, then add dy to the error term.
203 *
204 * The reason for the difference between edges moving to the left
205 * and edges moving to the right is simple: If an edge is moving
206 * to the right, then we want the algorithm to flip immediately.
207 * If it is moving to the left, then we don't want it to flip until
208 * we traverse an entire pixel.
209 */
210 #define OBRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
211 int dx; /* local storage */ \
212 \
213 /* \
214 * if the edge is horizontal, then it is ignored \
215 * and assumed not to be processed. Otherwise, do this stuff. \
216 */ \
217 if ((dy) != 0) { \
218 xStart = (x1); \
219 dx = (x2) - xStart; \
220 if (dx < 0) { \
221 m = dx / (dy); \
222 m1 = m - 1; \
223 incr1 = -2 * dx + 2 * (dy) * m1; \
224 incr2 = -2 * dx + 2 * (dy) * m; \
225 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
226 } else { \
227 m = dx / (dy); \
228 m1 = m + 1; \
229 incr1 = 2 * dx - 2 * (dy) * m1; \
230 incr2 = 2 * dx - 2 * (dy) * m; \
231 d = -2 * m * (dy) + 2 * dx; \
232 } \
233 } \
234 }
235
236 #define OBRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
237 if (m1 > 0) { \
238 if (d > 0) { \
239 minval += m1; \
240 d += incr1; \
241 } \
242 else { \
243 minval += m; \
244 d += incr2; \
245 } \
246 } else {\
247 if (d >= 0) { \
248 minval += m1; \
249 d += incr1; \
250 } \
251 else { \
252 minval += m; \
253 d += incr2; \
254 } \
255 } \
256 }
257
258 /*
259 * This structure contains all of the information needed
260 * to run the bresenham algorithm.
261 * The variables may be hardcoded into the declarations
262 * instead of using this structure to make use of
263 * register declarations.
264 */
265 typedef struct {
266 int minor_axis; /* minor axis */
267 int d; /* decision variable */
268 int m, m1; /* slope and slope+1 */
269 int incr1, incr2; /* error increments */
270 } OBRESINFO;
271
272 #define OBRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
273 OBRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
274 bres.m, bres.m1, bres.incr1, bres.incr2)
275
276 #define OBRESINCRPGONSTRUCT(bres) \
277 OBRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
278
279
280 /*
281 * for the winding number rule
282 */
283 #define CLOCKWISE 1
284 #define COUNTERCLOCKWISE -1
285
286 typedef struct _OEdgeTableEntry {
287 int ymax; /* ycoord at which we exit this edge. */
288 OBRESINFO bres; /* Bresenham info to run the edge */
289 struct _OEdgeTableEntry *next; /* next in the list */
290 struct _OEdgeTableEntry *back; /* for insertion sort */
291 struct _OEdgeTableEntry *nextWETE; /* for winding num rule */
292 int ClockWise; /* flag for winding number rule */
293 } OEdgeTableEntry;
294
295
296 typedef struct _OScanLineList{
297 int scanline; /* the scanline represented */
298 OEdgeTableEntry *edgelist; /* header node */
299 struct _OScanLineList *next; /* next in the list */
300 } OScanLineList;
301
302
303 typedef struct {
304 int ymax; /* ymax for the polygon */
305 int ymin; /* ymin for the polygon */
306 OScanLineList scanlines; /* header node */
307 } OEdgeTable;
308
309 /*
310 * Here is a struct to help with storage allocation
311 * so we can allocate a big chunk at a time, and then take
312 * pieces from this heap when we need to.
313 */
314 #define SLLSPERBLOCK 25
315
316 typedef struct _OScanLineListBlock {
317 OScanLineList SLLs[SLLSPERBLOCK];
318 struct _OScanLineListBlock *next;
319 } OScanLineListBlock;
320
321
322 /*
323 *
324 * a few macros for the inner loops of the fill code where
325 * performance considerations don't allow a procedure call.
326 *
327 * Evaluate the given edge at the given scanline.
328 * If the edge has expired, then we leave it and fix up
329 * the active edge table; otherwise, we increment the
330 * x value to be ready for the next scanline.
331 * The winding number rule is in effect, so we must notify
332 * the caller when the edge has been removed so he
333 * can reorder the Winding Active Edge Table.
334 */
335 #define OEVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
336 if (pAET->ymax == y) { /* leaving this edge */ \
337 pPrevAET->next = pAET->next; \
338 pAET = pPrevAET->next; \
339 fixWAET = 1; \
340 if (pAET) \
341 pAET->back = pPrevAET; \
342 } \
343 else { \
344 OBRESINCRPGONSTRUCT(pAET->bres); \
345 pPrevAET = pAET; \
346 pAET = pAET->next; \
347 } \
348 }
349
350
351 /*
352 * Evaluate the given edge at the given scanline.
353 * If the edge has expired, then we leave it and fix up
354 * the active edge table; otherwise, we increment the
355 * x value to be ready for the next scanline.
356 * The even-odd rule is in effect.
357 */
358 #define OEVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
359 if (pAET->ymax == y) { /* leaving this edge */ \
360 pPrevAET->next = pAET->next; \
361 pAET = pPrevAET->next; \
362 if (pAET) \
363 pAET->back = pPrevAET; \
364 } \
365 else { \
366 OBRESINCRPGONSTRUCT(pAET->bres); \
367 pPrevAET = pAET; \
368 pAET = pAET->next; \
369 } \
370 }
371
372
373
374
375 OGdkRegion * gdk_region_copy (const OGdkRegion *region);
376 void gdk_region_destroy (OGdkRegion *region);
377 OGdkRegion * gdk_region_rectangle (const OGdkRectangle *rectangle);
378 bool ogdk_region_equal (const OGdkRegion *region1,
379 const OGdkRegion *region2);
380 bool gdk_region_point_in (const OGdkRegion *region,
381 int x,
382 int y);
383 OGdkOverlapType gdk_region_rect_in (const OGdkRegion *region,
384 const OGdkRectangle *rectangle);
385 void gdk_region_offset (OGdkRegion *region,
386 int dx,
387 int dy);
388 void gdk_region_union_with_rect (OGdkRegion *region,
389 const OGdkRectangle *rect);
390 void gdk_region_union (OGdkRegion *source1,
391 const OGdkRegion *source2);
392 void gdk_region_intersect (OGdkRegion *source1,
393 const OGdkRegion *source2);
394 OGdkRegion * gdk_region_polygon (const OGdkPoint *points,
395 int n_points,
396 OGdkFillRule fill_rule);
397
398 OGdkRegion * gdk_region_new (void);
399 void gdk_region_subtract (OGdkRegion *source1,
400 const OGdkRegion *source2);
401 bool gdk_region_empty (const OGdkRegion *region);
402
403 void gdk_region_get_rectangles (const OGdkRegion *region,
404 OGdkRectangle **rectangles,
405 int *n_rectangles);
406 void gdk_region_get_clipbox (const OGdkRegion *region,
407 OGdkRectangle *rectangle);
408
409 // ----------------------------------------------------------------------------
410 // OCPNRegionRefData: private class containing the information about the region
411 // ----------------------------------------------------------------------------
412
413 class OCPNRegionRefData : public wxObjectRefData
414 {
415 public:
OCPNRegionRefData()416 OCPNRegionRefData()
417 {
418 m_region = NULL;
419 }
420
OCPNRegionRefData(const OCPNRegionRefData & refData)421 OCPNRegionRefData(const OCPNRegionRefData& refData)
422 : wxObjectRefData()
423 {
424 m_region = gdk_region_copy(refData.m_region);
425 }
426
~OCPNRegionRefData()427 virtual ~OCPNRegionRefData()
428 {
429 if (m_region)
430 gdk_region_destroy( m_region );
431 free( m_region );
432 }
433
434 OGdkRegion *m_region;
435 };
436
437 // ----------------------------------------------------------------------------
438 // macros
439 // ----------------------------------------------------------------------------
440
441 #define M_REGIONDATA ((OCPNRegionRefData *)m_refData)
442 #define M_REGIONDATA_OF(rgn) ((OCPNRegionRefData *)(rgn.m_refData))
443
IMPLEMENT_DYNAMIC_CLASS(OCPNRegion,wxGDIObject)444 IMPLEMENT_DYNAMIC_CLASS(OCPNRegion, wxGDIObject)
445
446 // ----------------------------------------------------------------------------
447 // OCPNRegion construction
448 // ----------------------------------------------------------------------------
449
450 #define M_REGIONDATA ((OCPNRegionRefData *)m_refData)
451
452 #ifndef USE_NEW_REGION
453
454 OCPNRegion::OCPNRegion( wxCoord x, wxCoord y, wxCoord w, wxCoord h ) : wxRegion(x,y,w,h)
455
456 {
457 }
458
OCPNRegion(const wxPoint & topLeft,const wxPoint & bottomRight)459 OCPNRegion::OCPNRegion( const wxPoint& topLeft, const wxPoint& bottomRight ) : wxRegion(topLeft.x, topLeft.y, bottomRight.x - topLeft.x, bottomRight.y - topLeft.y)
460 {
461 }
462
OCPNRegion(const wxRect & rect)463 OCPNRegion::OCPNRegion( const wxRect& rect ) : wxRegion(rect.x, rect.y, rect.width, rect.height)
464 {
465 }
466
OCPNRegion(const wxRegion & region)467 OCPNRegion::OCPNRegion( const wxRegion& region ) : wxRegion(region)
468 {
469 }
470
OCPNRegion(size_t n,const wxPoint * points,int fillStyle)471 OCPNRegion::OCPNRegion( size_t n, const wxPoint *points, int fillStyle )
472 : wxRegion(n, points,
473 #if wxCHECK_VERSION(2,9,0)
474 (wxPolygonFillMode)
475 #endif
476 fillStyle)
477 {
478 }
479
GetNew_wxRegion() const480 wxRegion *OCPNRegion::GetNew_wxRegion() const
481 {
482 return new wxRegion(this);
483 }
484
485 #endif
486
487 #ifdef USE_NEW_REGION
488
OCPNRegion(wxCoord x,wxCoord y,wxCoord w,wxCoord h)489 OCPNRegion::OCPNRegion( wxCoord x, wxCoord y, wxCoord w, wxCoord h )
490 {
491 InitRect(x, y, w, h);
492 }
493
OCPNRegion(const wxPoint & topLeft,const wxPoint & bottomRight)494 OCPNRegion::OCPNRegion( const wxPoint& topLeft, const wxPoint& bottomRight )
495 {
496 InitRect(topLeft.x, topLeft.y,
497 bottomRight.x - topLeft.x, bottomRight.y - topLeft.y);
498 }
499
OCPNRegion(const wxRect & rect)500 OCPNRegion::OCPNRegion( const wxRect& rect )
501 {
502 InitRect(rect.x, rect.y, rect.width, rect.height);
503 }
504
OCPNRegion(const wxRegion & region)505 OCPNRegion::OCPNRegion( const wxRegion& region )
506 {
507 wxRegionIterator ri(region);
508 if(!ri.HaveRects())
509 return;
510
511 wxRect rect = ri.GetRect();
512 InitRect(rect.x, rect.y, rect.width, rect.height);
513 ri++;
514
515 while(ri.HaveRects()) {
516 Union(ri.GetRect());
517 ri++;
518 }
519 }
520
~OCPNRegion()521 OCPNRegion::~OCPNRegion()
522 {
523 }
524
525
InitRect(wxCoord x,wxCoord y,wxCoord w,wxCoord h)526 void OCPNRegion::InitRect(wxCoord x, wxCoord y, wxCoord w, wxCoord h)
527 {
528 OGdkRectangle rect;
529 rect.x = x;
530 rect.y = y;
531 rect.width = w;
532 rect.height = h;
533
534 m_refData = new OCPNRegionRefData();
535
536 M_REGIONDATA->m_region = gdk_region_rectangle( &rect );
537 }
538
539 //OCPNRegion::OCPNRegion( GdkRegion *region )
540 //{
541 // m_refData = new OCPNRegionRefData();
542 // M_REGIONDATA->m_region = gdk_region_copy( region );
543 //}
544
OCPNRegion(size_t n,const wxPoint * points,int fillStyle)545 OCPNRegion::OCPNRegion( size_t n, const wxPoint *points, int fillStyle )
546 {
547 OGdkPoint *gdkpoints = new OGdkPoint[n];
548 for ( size_t i = 0 ; i < n ; i++ )
549 {
550 gdkpoints[i].x = points[i].x;
551 gdkpoints[i].y = points[i].y;
552 }
553
554 m_refData = new OCPNRegionRefData();
555
556 OGdkRegion* reg = gdk_region_polygon
557 (
558 gdkpoints,
559 n,
560 fillStyle == wxWINDING_RULE ? OGDK_WINDING_RULE
561 : OGDK_EVEN_ODD_RULE
562 );
563
564 M_REGIONDATA->m_region = reg;
565
566 delete [] gdkpoints;
567 }
568
569 //OCPNRegion::~OCPNRegion()
570 //{
571 // m_refData unrefed in ~wxObject
572 //}
573
CreateRefData() const574 wxObjectRefData *OCPNRegion::CreateRefData() const
575 {
576 return new OCPNRegionRefData;
577 }
578
CloneRefData(const wxObjectRefData * data) const579 wxObjectRefData *OCPNRegion::CloneRefData(const wxObjectRefData *data) const
580 {
581 return new OCPNRegionRefData(*(OCPNRegionRefData *)data);
582 }
583
584 // ----------------------------------------------------------------------------
585 // OCPNRegion comparison
586 // ----------------------------------------------------------------------------
587
ODoIsEqual(const OCPNRegion & region) const588 bool OCPNRegion::ODoIsEqual(const OCPNRegion& region) const
589 {
590 if(!region.m_refData)
591 return false;
592
593 return ogdk_region_equal(M_REGIONDATA->m_region, M_REGIONDATA_OF(region)->m_region);
594 }
595
596 // ----------------------------------------------------------------------------
597 // OCPNRegion operations
598 // ----------------------------------------------------------------------------
599
Clear()600 void OCPNRegion::Clear()
601 {
602 UnRef();
603 }
604
ODoUnionWithRect(const wxRect & r)605 bool OCPNRegion::ODoUnionWithRect(const wxRect& r)
606 {
607 // workaround for a strange GTK/X11 bug: taking union with an empty
608 // rectangle results in an empty region which is definitely not what we
609 // want
610 if ( r.IsEmpty() )
611 return true;
612
613 if ( !m_refData )
614 {
615 InitRect(r.x, r.y, r.width, r.height);
616 }
617 else
618 {
619 AllocExclusive();
620
621 OGdkRectangle rect;
622 rect.x = r.x;
623 rect.y = r.y;
624 rect.width = r.width;
625 rect.height = r.height;
626
627 gdk_region_union_with_rect( M_REGIONDATA->m_region, &rect );
628 }
629
630 return true;
631 }
632
ODoUnionWithRegion(const OCPNRegion & region)633 bool OCPNRegion::ODoUnionWithRegion( const OCPNRegion& region )
634 {
635 wxCHECK_MSG( region.Ok(), false, _T("invalid region") );
636
637 if (!m_refData)
638 {
639 m_refData = new OCPNRegionRefData();
640 M_REGIONDATA->m_region = gdk_region_new();
641 }
642 else
643 {
644 AllocExclusive();
645 }
646
647 gdk_region_union( M_REGIONDATA->m_region, (OGdkRegion *)region.GetRegion() );
648
649 return true;
650 }
651
ODoIntersect(const OCPNRegion & region)652 bool OCPNRegion::ODoIntersect( const OCPNRegion& region )
653 {
654 wxCHECK_MSG( region.Ok(), false, _T("invalid region") );
655
656 if (!m_refData)
657 {
658 // intersecting with invalid region doesn't make sense
659 return false;
660 }
661
662 AllocExclusive();
663
664 gdk_region_intersect( M_REGIONDATA->m_region, (OGdkRegion *)region.GetRegion() );
665
666 return true;
667 }
668
ODoSubtract(const OCPNRegion & region)669 bool OCPNRegion::ODoSubtract( const OCPNRegion& region )
670 {
671 wxCHECK_MSG( region.Ok(), false, _T("invalid region") );
672 if (!m_refData)
673 {
674 // subtracting from an invalid region doesn't make sense
675 return false;
676 }
677
678 AllocExclusive();
679
680 gdk_region_subtract( M_REGIONDATA->m_region, (OGdkRegion *)region.GetRegion() );
681
682 return true;
683 }
684
685 #if 0
686 bool OCPNRegion::DoXor( const OCPNRegion& region )
687 {
688 wxCHECK_MSG( region.Ok(), false, _T("invalid region") );
689
690 if (!m_refData)
691 {
692 return false;
693 }
694
695 AllocExclusive();
696
697 /// gdk_region_xor( M_REGIONDATA->m_region, (OGdkRegion *)region.GetRegion() );
698
699 return true;
700 }
701 #endif
702
ODoOffset(wxCoord x,wxCoord y)703 bool OCPNRegion::ODoOffset( wxCoord x, wxCoord y )
704 {
705 if (!m_refData)
706 return false;
707
708 AllocExclusive();
709
710 gdk_region_offset( M_REGIONDATA->m_region, x, y );
711
712 return true;
713 }
714
715 // ----------------------------------------------------------------------------
716 // OCPNRegion tests
717 // ----------------------------------------------------------------------------
718
ODoGetBox(wxCoord & x,wxCoord & y,wxCoord & w,wxCoord & h) const719 bool OCPNRegion::ODoGetBox( wxCoord &x, wxCoord &y, wxCoord &w, wxCoord &h ) const
720 {
721 if ( m_refData )
722 {
723 OGdkRectangle rect;
724 gdk_region_get_clipbox( M_REGIONDATA->m_region, &rect );
725 x = rect.x;
726 y = rect.y;
727 w = rect.width;
728 h = rect.height;
729
730 return true;
731 }
732 else
733 {
734 x = 0;
735 y = 0;
736 w = -1;
737 h = -1;
738
739 return false;
740 }
741 }
742
IsEmpty() const743 bool OCPNRegion::IsEmpty() const
744 {
745 if (!m_refData)
746 return true;
747
748 return gdk_region_empty( M_REGIONDATA->m_region );
749 }
750
ODoContainsPoint(wxCoord x,wxCoord y) const751 wxRegionContain OCPNRegion::ODoContainsPoint( wxCoord x, wxCoord y ) const
752 {
753 if (!m_refData)
754 return wxOutRegion;
755
756 if (gdk_region_point_in( M_REGIONDATA->m_region, x, y ))
757 return wxInRegion;
758 else
759 return wxOutRegion;
760 }
761
ODoContainsRect(const wxRect & r) const762 wxRegionContain OCPNRegion::ODoContainsRect(const wxRect& r) const
763 {
764
765 if (!m_refData)
766 return wxOutRegion;
767
768 OGdkRectangle rect;
769 rect.x = r.x;
770 rect.y = r.y;
771 rect.width = r.width;
772 rect.height = r.height;
773 OGdkOverlapType res = gdk_region_rect_in( M_REGIONDATA->m_region, &rect );
774 switch (res)
775 {
776 case OGDK_OVERLAP_RECTANGLE_IN: return wxInRegion;
777 case OGDK_OVERLAP_RECTANGLE_OUT: return wxOutRegion;
778 case OGDK_OVERLAP_RECTANGLE_PART: return wxPartRegion;
779 }
780
781 return wxOutRegion;
782 }
783
784
GetRegion() const785 void *OCPNRegion::GetRegion() const
786 {
787 if (!m_refData)
788 return NULL;
789
790 return M_REGIONDATA->m_region;
791 }
792
GetNew_wxRegion() const793 wxRegion *OCPNRegion::GetNew_wxRegion() const
794 {
795 wxRegion *r = new wxRegion;
796 r->Clear();
797
798 OGdkRectangle *gdkrects = NULL;
799 int numRects = 0;
800 gdk_region_get_rectangles( (OGdkRegion *)GetRegion(), &gdkrects, &numRects );
801
802 if (numRects)
803 {
804 for (int i=0; i < numRects; ++i)
805 {
806 OGdkRectangle &gr = gdkrects[i];
807
808 wxRect wr;
809 wr.x = gr.x;
810 wr.y = gr.y;
811 wr.width = gr.width;
812 wr.height = gr.height;
813
814 r->Union(wr);
815 }
816 }
817 free( gdkrects );
818
819 return r;
820 }
821
822
823 #endif
824 // ----------------------------------------------------------------------------
825 // OCPNRegionIterator
826 // ----------------------------------------------------------------------------
827
828 #ifndef USE_NEW_REGION
829
OCPNRegionIterator(const OCPNRegion & region)830 OCPNRegionIterator::OCPNRegionIterator( const OCPNRegion& region )
831 {
832 m_ri = new wxRegionIterator(region);
833 }
834
~OCPNRegionIterator()835 OCPNRegionIterator::~OCPNRegionIterator()
836 {
837 delete m_ri;
838 }
839
Reset()840 void OCPNRegionIterator::Reset()
841 {
842 m_ri->Reset();
843 }
844
Reset(const OCPNRegion & region)845 void OCPNRegionIterator::Reset(const OCPNRegion& region)
846 {
847 m_ri->Reset(region);
848 }
849
GetRect() const850 wxRect OCPNRegionIterator::GetRect() const
851 {
852 return m_ri->GetRect();
853 }
854
HaveRects() const855 bool OCPNRegionIterator::HaveRects() const
856 {
857 return m_ri->HaveRects();
858 }
859
NextRect()860 void OCPNRegionIterator::NextRect()
861 {
862 ++(*m_ri);
863 }
864
865
866 #endif
867
868
869 #ifdef USE_NEW_REGION
870
OCPNRegionIterator()871 OCPNRegionIterator::OCPNRegionIterator()
872 {
873 Init();
874 Reset();
875 }
876
OCPNRegionIterator(const OCPNRegion & region)877 OCPNRegionIterator::OCPNRegionIterator( const OCPNRegion& region )
878 {
879 Init();
880 Reset(region);
881 }
882
Init()883 void OCPNRegionIterator::Init()
884 {
885 m_rects = NULL;
886 m_numRects = 0;
887 }
888
~OCPNRegionIterator()889 OCPNRegionIterator::~OCPNRegionIterator()
890 {
891 wxDELETEA(m_rects);
892 }
893
Reset()894 void OCPNRegionIterator::Reset()
895 {
896 m_current = 0u;
897 }
898
NextRect()899 void OCPNRegionIterator::NextRect()
900 {
901 if (HaveRects())
902 ++m_current;
903 }
904
CreateRects(const OCPNRegion & region)905 void OCPNRegionIterator::CreateRects( const OCPNRegion& region )
906 {
907 wxDELETEA(m_rects);
908 m_numRects = 0;
909
910 OGdkRegion *gdkregion = (OGdkRegion *)region.GetRegion();
911 if (!gdkregion)
912 return;
913
914 OGdkRectangle *gdkrects = NULL;
915 int numRects = 0;
916 gdk_region_get_rectangles( gdkregion, &gdkrects, &numRects );
917
918 m_numRects = numRects;
919 if (numRects)
920 {
921 m_rects = new wxRect[m_numRects];
922 for (size_t i=0; i < m_numRects; ++i)
923 {
924 OGdkRectangle &gr = gdkrects[i];
925 wxRect &wr = m_rects[i];
926 wr.x = gr.x;
927 wr.y = gr.y;
928 wr.width = gr.width;
929 wr.height = gr.height;
930 }
931 }
932 free( gdkrects );
933 }
934
Reset(const OCPNRegion & region)935 void OCPNRegionIterator::Reset( const OCPNRegion& region )
936 {
937 m_region = region;
938 CreateRects(region);
939 Reset();
940 }
941
HaveRects() const942 bool OCPNRegionIterator::HaveRects() const
943 {
944 return m_current < m_numRects;
945 }
946
947
GetRect() const948 wxRect OCPNRegionIterator::GetRect() const
949 {
950 wxRect r;
951 if( HaveRects() )
952 r = m_rects[m_current];
953
954 return r;
955 }
956
957 #endif
958
959 #ifdef USE_NEW_REGION
960
961 /* $TOG: Region.c /main/31 1998/02/06 17:50:22 kaleb $ */
962 /************************************************************************
963 *
964 * Copyright 1987, 1988, 1998 The Open Group
965 *
966 * All Rights Reserved.
967 *
968 * The above copyright notice and this permission notice shall be included in
969 * all copies or substantial portions of the Software.
970 *
971 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
972 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
973 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
974 * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
975 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
976 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
977 *
978 * Except as contained in this notice, the name of The Open Group shall not be
979 * used in advertising or otherwise to promote the sale, use or other dealings
980 * in this Software without prior written authorization from The Open Group.
981 *
982 *
983 * Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
984 *
985 * All Rights Reserved
986 *
987 * Permission to use, copy, modify, and distribute this software and its
988 * documentation for any purpose and without fee is hereby granted,
989 * provided that the above copyright notice appear in all copies and that
990 * both that copyright notice and this permission notice appear in
991 * supporting documentation, and that the name of Digital not be
992 * used in advertising or publicity pertaining to distribution of the
993 * software without specific, written prior permission.
994 *
995 * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
996 * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
997 * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
998 * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
999 * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1000 * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1001 * SOFTWARE.
1002 *
1003 ************************************************************************/
1004 /* $XFree86: xc/lib/X11/Region.c,v 1.5 1999/05/09 10:50:01 dawes Exp $ */
1005 /*
1006 * The functions in this file implement the Region abstraction, similar to one
1007 * used in the X11 sample server. A Region is simply an area, as the name
1008 * implies, and is implemented as a "y-x-banded" array of rectangles. To
1009 * explain: Each Region is made up of a certain number of rectangles sorted
1010 * by y coordinate first, and then by x coordinate.
1011 *
1012 * Furthermore, the rectangles are banded such that every rectangle with a
1013 * given upper-left y coordinate (y1) will have the same lower-right y
1014 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
1015 * will span the entire vertical distance of the band. This means that some
1016 * areas that could be merged into a taller rectangle will be represented as
1017 * several shorter rectangles to account for shorter rectangles to its left
1018 * or right but within its "vertical scope".
1019 *
1020 * An added constraint on the rectangles is that they must cover as much
1021 * horizontal area as possible. E.g. no two rectangles in a band are allowed
1022 * to touch.
1023 *
1024 * Whenever possible, bands will be merged together to cover a greater vertical
1025 * distance (and thus reduce the number of rectangles). Two bands can be merged
1026 * only if the bottom of one touches the top of the other and they have
1027 * rectangles in the same places (of the same width, of course). This maintains
1028 * the y-x-banding that's so nice to have...
1029 */
1030
1031 //#include "config.h"
1032 //#include <stdlib.h>
1033 //#include <string.h>
1034 //#include <gdkregion.h>
1035 //#include "gdkregion-generic.h"
1036 //#include "gdkalias.h"
1037
1038 typedef void (* overlapFunc) (OGdkRegion *pReg,
1039 OGdkRegionBox *r1,
1040 OGdkRegionBox *r1End,
1041 OGdkRegionBox *r2,
1042 OGdkRegionBox *r2End,
1043 int y1,
1044 int y2);
1045 typedef void (* nonOverlapFunc) (OGdkRegion *pReg,
1046 OGdkRegionBox *r,
1047 OGdkRegionBox *rEnd,
1048 int y1,
1049 int y2);
1050
1051 static void miRegionCopy (OGdkRegion *dstrgn,
1052 const OGdkRegion *rgn);
1053 static void miRegionOp (OGdkRegion *newReg,
1054 OGdkRegion *reg1,
1055 const OGdkRegion *reg2,
1056 overlapFunc overlapFn,
1057 nonOverlapFunc nonOverlap1Fn,
1058 nonOverlapFunc nonOverlap2Fn);
1059
1060 /**
1061 * gdk_region_new:
1062 *
1063 * Creates a new empty #GdkRegion.
1064 *
1065 * Returns: a new empty #GdkRegion
1066 */
1067 OGdkRegion *
gdk_region_new(void)1068 gdk_region_new (void)
1069 {
1070 OGdkRegion *temp;
1071
1072 temp = (OGdkRegion *) malloc(sizeof(OGdkRegion));
1073
1074 temp->numRects = 0;
1075 temp->rects = &temp->extents;
1076 temp->extents.x1 = 0;
1077 temp->extents.y1 = 0;
1078 temp->extents.x2 = 0;
1079 temp->extents.y2 = 0;
1080 temp->size = 1;
1081
1082 return temp;
1083 }
1084
1085 /**
1086 * gdk_region_rectangle:
1087 * @rectangle: a #GdkRectangle
1088 *
1089 * Creates a new region containing the area @rectangle.
1090 *
1091 * Return value: a new region
1092 **/
1093 OGdkRegion *
gdk_region_rectangle(const OGdkRectangle * rectangle)1094 gdk_region_rectangle (const OGdkRectangle *rectangle)
1095 {
1096 OGdkRegion *temp;
1097
1098 /// g_return_val_if_fail (rectangle != NULL, NULL);
1099
1100 if (rectangle->width <= 0 || rectangle->height <= 0)
1101 return gdk_region_new();
1102
1103 temp = gdk_region_new(); /// temp = g_slice_new (GdkRegion);
1104
1105 temp->numRects = 1;
1106 temp->rects = &temp->extents;
1107 temp->extents.x1 = rectangle->x;
1108 temp->extents.y1 = rectangle->y;
1109 temp->extents.x2 = rectangle->x + rectangle->width;
1110 temp->extents.y2 = rectangle->y + rectangle->height;
1111 temp->size = 1;
1112
1113 return temp;
1114 }
1115
1116 /**
1117 * gdk_region_copy:
1118 * @region: a #GdkRegion
1119 *
1120 * Copies @region, creating an identical new region.
1121 *
1122 * Return value: a new region identical to @region
1123 **/
1124 OGdkRegion *
gdk_region_copy(const OGdkRegion * region)1125 gdk_region_copy (const OGdkRegion *region)
1126 {
1127 OGdkRegion *temp;
1128
1129 /// g_return_val_if_fail (region != NULL, NULL);
1130
1131 temp = gdk_region_new ();
1132
1133 miRegionCopy (temp, region);
1134
1135 return temp;
1136 }
1137
1138 /**
1139 * gdk_region_get_clipbox:
1140 * @region: a #GdkRegion
1141 * @rectangle: return location for the clipbox
1142 *
1143 * Obtains the smallest rectangle which includes the entire #GdkRegion.
1144 *
1145 */
1146 void
gdk_region_get_clipbox(const OGdkRegion * region,OGdkRectangle * rectangle)1147 gdk_region_get_clipbox (const OGdkRegion *region,
1148 OGdkRectangle *rectangle)
1149 {
1150 /// g_return_if_fail (region != NULL);
1151 /// g_return_if_fail (rectangle != NULL);
1152
1153 rectangle->x = region->extents.x1;
1154 rectangle->y = region->extents.y1;
1155 rectangle->width = region->extents.x2 - region->extents.x1;
1156 rectangle->height = region->extents.y2 - region->extents.y1;
1157 }
1158
1159
1160 /**
1161 * gdk_region_get_rectangles:
1162 * @region: a #GdkRegion
1163 * @rectangles: return location for an array of rectangles
1164 * @n_rectangles: length of returned array
1165 *
1166 * Obtains the area covered by the region as a list of rectangles.
1167 * The array returned in @rectangles must be freed with g_free().
1168 **/
1169 void
gdk_region_get_rectangles(const OGdkRegion * region,OGdkRectangle ** rectangles,int * n_rectangles)1170 gdk_region_get_rectangles (const OGdkRegion *region,
1171 OGdkRectangle **rectangles,
1172 int *n_rectangles)
1173 {
1174 int i;
1175
1176 /// g_return_if_fail (region != NULL);
1177 /// g_return_if_fail (rectangles != NULL);
1178 /// g_return_if_fail (n_rectangles != NULL);
1179
1180 *n_rectangles = region->numRects;
1181 *rectangles = (OGdkRectangle *)malloc (sizeof(OGdkRectangle) * region->numRects);
1182
1183 for (i = 0; i < region->numRects; i++)
1184 {
1185 OGdkRegionBox rect;
1186 rect = region->rects[i];
1187 (*rectangles)[i].x = rect.x1;
1188 (*rectangles)[i].y = rect.y1;
1189 (*rectangles)[i].width = rect.x2 - rect.x1;
1190 (*rectangles)[i].height = rect.y2 - rect.y1;
1191 }
1192 }
1193
1194 /**
1195 * gdk_region_union_with_rect:
1196 * @region: a #GdkRegion.
1197 * @rect: a #GdkRectangle.
1198 *
1199 * Sets the area of @region to the union of the areas of @region and
1200 * @rect. The resulting area is the set of pixels contained in
1201 * either @region or @rect.
1202 **/
1203 void
gdk_region_union_with_rect(OGdkRegion * region,const OGdkRectangle * rect)1204 gdk_region_union_with_rect (OGdkRegion *region,
1205 const OGdkRectangle *rect)
1206 {
1207 OGdkRegion tmp_region;
1208
1209 // g_return_if_fail (region != NULL);
1210 // g_return_if_fail (rect != NULL);
1211
1212 if (rect->width <= 0 || rect->height <= 0)
1213 return;
1214
1215 tmp_region.rects = &tmp_region.extents;
1216 tmp_region.numRects = 1;
1217 tmp_region.extents.x1 = rect->x;
1218 tmp_region.extents.y1 = rect->y;
1219 tmp_region.extents.x2 = rect->x + rect->width;
1220 tmp_region.extents.y2 = rect->y + rect->height;
1221 tmp_region.size = 1;
1222
1223 gdk_region_union (region, &tmp_region);
1224 }
1225
1226 /*-
1227 * -----------------------------------------------------------------------
1228 * miSetExtents --
1229 * Reset the extents of a region to what they should be. Called by
1230 * miSubtract and miIntersect b/c they can't figure it out along the
1231 * way or do so easily, as miUnion can.
1232 *
1233 * Results:
1234 * None.
1235 *
1236 * Side Effects:
1237 * The region's 'extents' structure is overwritten.
1238 *
1239 *-----------------------------------------------------------------------
1240 */
1241 static void
miSetExtents(OGdkRegion * pReg)1242 miSetExtents (OGdkRegion *pReg)
1243 {
1244 OGdkRegionBox *pBox, *pBoxEnd, *pExtents;
1245
1246 if (pReg->numRects == 0)
1247 {
1248 pReg->extents.x1 = 0;
1249 pReg->extents.y1 = 0;
1250 pReg->extents.x2 = 0;
1251 pReg->extents.y2 = 0;
1252 return;
1253 }
1254
1255 pExtents = &pReg->extents;
1256 pBox = pReg->rects;
1257 pBoxEnd = &pBox[pReg->numRects - 1];
1258
1259 /*
1260 * Since pBox is the first rectangle in the region, it must have the
1261 * smallest y1 and since pBoxEnd is the last rectangle in the region,
1262 * it must have the largest y2, because of banding. Initialize x1 and
1263 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
1264 * to...
1265 */
1266 pExtents->x1 = pBox->x1;
1267 pExtents->y1 = pBox->y1;
1268 pExtents->x2 = pBoxEnd->x2;
1269 pExtents->y2 = pBoxEnd->y2;
1270
1271 /// g_assert(pExtents->y1 < pExtents->y2);
1272 while (pBox <= pBoxEnd)
1273 {
1274 if (pBox->x1 < pExtents->x1)
1275 {
1276 pExtents->x1 = pBox->x1;
1277 }
1278 if (pBox->x2 > pExtents->x2)
1279 {
1280 pExtents->x2 = pBox->x2;
1281 }
1282 pBox++;
1283 }
1284 /// g_assert(pExtents->x1 < pExtents->x2);
1285 }
1286
1287 /**
1288 * gdk_region_destroy:
1289 * @region: a #GdkRegion
1290 *
1291 * Destroys a #GdkRegion.
1292 */
1293 void
gdk_region_destroy(OGdkRegion * region)1294 gdk_region_destroy (OGdkRegion *region)
1295 {
1296 /// g_return_if_fail (region != NULL);
1297
1298 if (region->rects != ®ion->extents)
1299 free (region->rects);
1300 /// g_slice_free (GdkRegion, region);
1301 }
1302
1303
1304 /**
1305 * gdk_region_offset:
1306 * @region: a #GdkRegion
1307 * @dx: the distance to move the region horizontally
1308 * @dy: the distance to move the region vertically
1309 *
1310 * Moves a region the specified distance.
1311 */
1312 void
gdk_region_offset(OGdkRegion * region,int x,int y)1313 gdk_region_offset (OGdkRegion *region,
1314 int x,
1315 int y)
1316 {
1317 int nbox;
1318 OGdkRegionBox *pbox;
1319
1320 /// g_return_if_fail (region != NULL);
1321
1322 pbox = region->rects;
1323 nbox = region->numRects;
1324
1325 while(nbox--)
1326 {
1327 pbox->x1 += x;
1328 pbox->x2 += x;
1329 pbox->y1 += y;
1330 pbox->y2 += y;
1331 pbox++;
1332 }
1333 if (region->rects != ®ion->extents)
1334 {
1335 region->extents.x1 += x;
1336 region->extents.x2 += x;
1337 region->extents.y1 += y;
1338 region->extents.y2 += y;
1339 }
1340 }
1341
1342 /*
1343 * Utility procedure Compress:
1344 * Replace r by the region r', where
1345 * p in r' iff (Quantifer m <= dx) (p + m in r), and
1346 * Quantifier is Exists if grow is TRUE, For all if grow is FALSE, and
1347 * (x,y) + m = (x+m,y) if xdir is TRUE; (x,y+m) if xdir is FALSE.
1348 *
1349 * Thus, if xdir is TRUE and grow is FALSE, r is replaced by the region
1350 * of all points p such that p and the next dx points on the same
1351 * horizontal scan line are all in r. We do this using by noting
1352 * that p is the head of a run of length 2^i + k iff p is the head
1353 * of a run of length 2^i and p+2^i is the head of a run of length
1354 * k. Thus, the loop invariant: s contains the region corresponding
1355 * to the runs of length shift. r contains the region corresponding
1356 * to the runs of length 1 + dxo & (shift-1), where dxo is the original
1357 * value of dx. dx = dxo & ~(shift-1). As parameters, s and t are
1358 * scratch regions, so that we don't have to allocate them on every
1359 * call.
1360 */
1361
1362 #define ZOpRegion(a,b) if (grow) gdk_region_union (a, b); \
1363 else gdk_region_intersect (a,b)
1364 #define ZShiftRegion(a,b) if (xdir) gdk_region_offset (a,b,0); \
1365 else gdk_region_offset (a,0,b)
1366
1367 static void
Compress(OGdkRegion * r,OGdkRegion * s,OGdkRegion * t,unsigned int dx,int xdir,int grow)1368 Compress(OGdkRegion *r,
1369 OGdkRegion *s,
1370 OGdkRegion *t,
1371 unsigned int dx,
1372 int xdir,
1373 int grow)
1374 {
1375 unsigned int shift = 1;
1376
1377 miRegionCopy (s, r);
1378 while (dx)
1379 {
1380 if (dx & shift)
1381 {
1382 ZShiftRegion(r, -(int)shift);
1383 ZOpRegion(r, s);
1384 dx -= shift;
1385 if (!dx) break;
1386 }
1387 miRegionCopy (t, s);
1388 ZShiftRegion(s, -(int)shift);
1389 ZOpRegion(s, t);
1390 shift <<= 1;
1391 }
1392 }
1393
1394 #undef ZOpRegion
1395 #undef ZShiftRegion
1396 #undef ZCopyRegion
1397
1398 /**
1399 * gdk_region_shrink:
1400 * @region: a #GdkRegion
1401 * @dx: the number of pixels to shrink the region horizontally
1402 * @dy: the number of pixels to shrink the region vertically
1403 *
1404 * Resizes a region by the specified amount.
1405 * Positive values shrink the region. Negative values expand it.
1406 */
1407 void
gdk_region_shrink(OGdkRegion * region,int dx,int dy)1408 gdk_region_shrink (OGdkRegion *region,
1409 int dx,
1410 int dy)
1411 {
1412 OGdkRegion *s, *t;
1413 int grow;
1414
1415 /// g_return_if_fail (region != NULL);
1416
1417 if (!dx && !dy)
1418 return;
1419
1420 s = gdk_region_new ();
1421 t = gdk_region_new ();
1422
1423 grow = (dx < 0);
1424 if (grow)
1425 dx = -dx;
1426 if (dx)
1427 Compress(region, s, t, (unsigned) 2*dx, TRUE, grow);
1428
1429 grow = (dy < 0);
1430 if (grow)
1431 dy = -dy;
1432 if (dy)
1433 Compress(region, s, t, (unsigned) 2*dy, FALSE, grow);
1434
1435 gdk_region_offset (region, dx, dy);
1436 gdk_region_destroy (s);
1437 gdk_region_destroy (t);
1438 }
1439
1440
1441 /*======================================================================
1442 * Region Intersection
1443 *====================================================================*/
1444 /*-
1445 * -----------------------------------------------------------------------
1446 * miIntersectO --
1447 * Handle an overlapping band for miIntersect.
1448 *
1449 * Results:
1450 * None.
1451 *
1452 * Side Effects:
1453 * Rectangles may be added to the region.
1454 *
1455 *-----------------------------------------------------------------------
1456 */
1457 /* static void*/
1458 static void
miIntersectO(OGdkRegion * pReg,OGdkRegionBox * r1,OGdkRegionBox * r1End,OGdkRegionBox * r2,OGdkRegionBox * r2End,int y1,int y2)1459 miIntersectO (OGdkRegion *pReg,
1460 OGdkRegionBox *r1,
1461 OGdkRegionBox *r1End,
1462 OGdkRegionBox *r2,
1463 OGdkRegionBox *r2End,
1464 int y1,
1465 int y2)
1466 {
1467 int x1;
1468 int x2;
1469 OGdkRegionBox *pNextRect;
1470
1471 pNextRect = &pReg->rects[pReg->numRects];
1472
1473 while ((r1 != r1End) && (r2 != r2End))
1474 {
1475 x1 = MAX (r1->x1,r2->x1);
1476 x2 = MIN (r1->x2,r2->x2);
1477
1478 /*
1479 * If there's any overlap between the two rectangles, add that
1480 * overlap to the new region.
1481 * There's no need to check for subsumption because the only way
1482 * such a need could arise is if some region has two rectangles
1483 * right next to each other. Since that should never happen...
1484 */
1485 if (x1 < x2)
1486 {
1487 /// g_assert (y1<y2);
1488
1489 OMEMCHECK (pReg, pNextRect, pReg->rects);
1490 pNextRect->x1 = x1;
1491 pNextRect->y1 = y1;
1492 pNextRect->x2 = x2;
1493 pNextRect->y2 = y2;
1494 pReg->numRects += 1;
1495 pNextRect++;
1496 // g_assert (pReg->numRects <= pReg->size);
1497 }
1498
1499 /*
1500 * Need to advance the pointers. Shift the one that extends
1501 * to the right the least, since the other still has a chance to
1502 * overlap with that region's next rectangle, if you see what I mean.
1503 */
1504 if (r1->x2 < r2->x2)
1505 {
1506 r1++;
1507 }
1508 else if (r2->x2 < r1->x2)
1509 {
1510 r2++;
1511 }
1512 else
1513 {
1514 r1++;
1515 r2++;
1516 }
1517 }
1518 }
1519
1520 /**
1521 * gdk_region_intersect:
1522 * @source1: a #GdkRegion
1523 * @source2: another #GdkRegion
1524 *
1525 * Sets the area of @source1 to the intersection of the areas of @source1
1526 * and @source2. The resulting area is the set of pixels contained in
1527 * both @source1 and @source2.
1528 **/
1529 void
gdk_region_intersect(OGdkRegion * source1,const OGdkRegion * source2)1530 gdk_region_intersect (OGdkRegion *source1,
1531 const OGdkRegion *source2)
1532 {
1533 /// g_return_if_fail (source1 != NULL);
1534 /// g_return_if_fail (source2 != NULL);
1535
1536 /* check for trivial reject */
1537 if ((!(source1->numRects)) || (!(source2->numRects)) ||
1538 (!EXTENTCHECK(&source1->extents, &source2->extents)))
1539 source1->numRects = 0;
1540 else
1541 miRegionOp (source1, source1, source2,
1542 miIntersectO, (nonOverlapFunc) NULL, (nonOverlapFunc) NULL);
1543
1544 /*
1545 * Can't alter source1's extents before miRegionOp depends on the
1546 * extents of the regions being unchanged. Besides, this way there's
1547 * no checking against rectangles that will be nuked due to
1548 * coalescing, so we have to examine fewer rectangles.
1549 */
1550 miSetExtents(source1);
1551 }
1552
1553 static void
miRegionCopy(OGdkRegion * dstrgn,const OGdkRegion * rgn)1554 miRegionCopy (OGdkRegion *dstrgn,
1555 const OGdkRegion *rgn)
1556 {
1557 if (dstrgn != rgn) /* don't want to copy to itself */
1558 {
1559 if (dstrgn->size < rgn->numRects)
1560 {
1561 if (dstrgn->rects != &dstrgn->extents)
1562 free (dstrgn->rects);
1563
1564 dstrgn->rects = (OGdkRegionBox *)malloc(sizeof(OGdkRegionBox) * rgn->numRects);
1565 dstrgn->size = rgn->numRects;
1566 }
1567
1568 dstrgn->numRects = rgn->numRects;
1569 dstrgn->extents = rgn->extents;
1570
1571 memcpy (dstrgn->rects, rgn->rects, rgn->numRects * sizeof (OGdkRegionBox));
1572 }
1573 }
1574
1575
1576 /*======================================================================
1577 * Generic Region Operator
1578 *====================================================================*/
1579
1580 /*-
1581 * -----------------------------------------------------------------------
1582 * miCoalesce --
1583 * Attempt to merge the boxes in the current band with those in the
1584 * previous one. Used only by miRegionOp.
1585 *
1586 * Results:
1587 * The new index for the previous band.
1588 *
1589 * Side Effects:
1590 * If coalescing takes place:
1591 * - rectangles in the previous band will have their y2 fields
1592 * altered.
1593 * - pReg->numRects will be decreased.
1594 *
1595 *-----------------------------------------------------------------------
1596 */
1597 /* static int*/
1598 static int
miCoalesce(OGdkRegion * pReg,int prevStart,int curStart)1599 miCoalesce (OGdkRegion *pReg, /* Region to coalesce */
1600 int prevStart, /* Index of start of previous band */
1601 int curStart) /* Index of start of current band */
1602 {
1603 OGdkRegionBox *pPrevBox; /* Current box in previous band */
1604 OGdkRegionBox *pCurBox; /* Current box in current band */
1605 OGdkRegionBox *pRegEnd; /* End of region */
1606 int curNumRects; /* Number of rectangles in current
1607 * band */
1608 int prevNumRects; /* Number of rectangles in previous
1609 * band */
1610 int bandY1; /* Y1 coordinate for current band */
1611
1612 pRegEnd = &pReg->rects[pReg->numRects];
1613
1614 pPrevBox = &pReg->rects[prevStart];
1615 prevNumRects = curStart - prevStart;
1616
1617 /*
1618 * Figure out how many rectangles are in the current band. Have to do
1619 * this because multiple bands could have been added in miRegionOp
1620 * at the end when one region has been exhausted.
1621 */
1622 pCurBox = &pReg->rects[curStart];
1623 bandY1 = pCurBox->y1;
1624 for (curNumRects = 0;
1625 (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
1626 curNumRects++)
1627 {
1628 pCurBox++;
1629 }
1630
1631 if (pCurBox != pRegEnd)
1632 {
1633 /*
1634 * If more than one band was added, we have to find the start
1635 * of the last band added so the next coalescing job can start
1636 * at the right place... (given when multiple bands are added,
1637 * this may be pointless -- see above).
1638 */
1639 pRegEnd--;
1640 while (pRegEnd[-1].y1 == pRegEnd->y1)
1641 {
1642 pRegEnd--;
1643 }
1644 curStart = pRegEnd - pReg->rects;
1645 pRegEnd = pReg->rects + pReg->numRects;
1646 }
1647
1648 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1649 pCurBox -= curNumRects;
1650 /*
1651 * The bands may only be coalesced if the bottom of the previous
1652 * matches the top scanline of the current.
1653 */
1654 if (pPrevBox->y2 == pCurBox->y1)
1655 {
1656 /*
1657 * Make sure the bands have boxes in the same places. This
1658 * assumes that boxes have been added in such a way that they
1659 * cover the most area possible. I.e. two boxes in a band must
1660 * have some horizontal space between them.
1661 */
1662 do
1663 {
1664 if ((pPrevBox->x1 != pCurBox->x1) ||
1665 (pPrevBox->x2 != pCurBox->x2))
1666 {
1667 /*
1668 * The bands don't line up so they can't be coalesced.
1669 */
1670 return (curStart);
1671 }
1672 pPrevBox++;
1673 pCurBox++;
1674 prevNumRects -= 1;
1675 } while (prevNumRects != 0);
1676
1677 pReg->numRects -= curNumRects;
1678 pCurBox -= curNumRects;
1679 pPrevBox -= curNumRects;
1680
1681 /*
1682 * The bands may be merged, so set the bottom y of each box
1683 * in the previous band to that of the corresponding box in
1684 * the current band.
1685 */
1686 do
1687 {
1688 pPrevBox->y2 = pCurBox->y2;
1689 pPrevBox++;
1690 pCurBox++;
1691 curNumRects -= 1;
1692 }
1693 while (curNumRects != 0);
1694
1695 /*
1696 * If only one band was added to the region, we have to backup
1697 * curStart to the start of the previous band.
1698 *
1699 * If more than one band was added to the region, copy the
1700 * other bands down. The assumption here is that the other bands
1701 * came from the same region as the current one and no further
1702 * coalescing can be done on them since it's all been done
1703 * already... curStart is already in the right place.
1704 */
1705 if (pCurBox == pRegEnd)
1706 {
1707 curStart = prevStart;
1708 }
1709 else
1710 {
1711 do
1712 {
1713 *pPrevBox++ = *pCurBox++;
1714 }
1715 while (pCurBox != pRegEnd);
1716 }
1717
1718 }
1719 }
1720 return curStart;
1721 }
1722
1723 /*-
1724 * -----------------------------------------------------------------------
1725 * miRegionOp --
1726 * Apply an operation to two regions. Called by miUnion, miInverse,
1727 * miSubtract, miIntersect...
1728 *
1729 * Results:
1730 * None.
1731 *
1732 * Side Effects:
1733 * The new region is overwritten.
1734 *
1735 * Notes:
1736 * The idea behind this function is to view the two regions as sets.
1737 * Together they cover a rectangle of area that this function divides
1738 * into horizontal bands where points are covered only by one region
1739 * or by both. For the first case, the nonOverlapFunc is called with
1740 * each the band and the band's upper and lower extents. For the
1741 * second, the overlapFunc is called to process the entire band. It
1742 * is responsible for clipping the rectangles in the band, though
1743 * this function provides the boundaries.
1744 * At the end of each band, the new region is coalesced, if possible,
1745 * to reduce the number of rectangles in the region.
1746 *
1747 *-----------------------------------------------------------------------
1748 */
1749 /* static void*/
1750 static void
miRegionOp(OGdkRegion * newReg,OGdkRegion * reg1,const OGdkRegion * reg2,overlapFunc overlapFn,nonOverlapFunc nonOverlap1Fn,nonOverlapFunc nonOverlap2Fn)1751 miRegionOp(OGdkRegion *newReg,
1752 OGdkRegion *reg1,
1753 const OGdkRegion *reg2,
1754 overlapFunc overlapFn, /* Function to call for over-
1755 * lapping bands */
1756 nonOverlapFunc nonOverlap1Fn, /* Function to call for non-
1757 * overlapping bands in region
1758 * 1 */
1759 nonOverlapFunc nonOverlap2Fn) /* Function to call for non-
1760 * overlapping bands in region
1761 * 2 */
1762 {
1763 OGdkRegionBox *r1; /* Pointer into first region */
1764 OGdkRegionBox *r2; /* Pointer into 2d region */
1765 OGdkRegionBox *r1End; /* End of 1st region */
1766 OGdkRegionBox *r2End; /* End of 2d region */
1767 int ybot; /* Bottom of intersection */
1768 int ytop; /* Top of intersection */
1769 OGdkRegionBox *oldRects; /* Old rects for newReg */
1770 int prevBand; /* Index of start of
1771 * previous band in newReg */
1772 int curBand; /* Index of start of current
1773 * band in newReg */
1774 OGdkRegionBox *r1BandEnd; /* End of current band in r1 */
1775 OGdkRegionBox *r2BandEnd; /* End of current band in r2 */
1776 int top; /* Top of non-overlapping
1777 * band */
1778 int bot; /* Bottom of non-overlapping
1779 * band */
1780
1781 /*
1782 * Initialization:
1783 * set r1, r2, r1End and r2End appropriately, preserve the important
1784 * parts of the destination region until the end in case it's one of
1785 * the two source regions, then mark the "new" region empty, allocating
1786 * another array of rectangles for it to use.
1787 */
1788 r1 = reg1->rects;
1789 r2 = reg2->rects;
1790 r1End = r1 + reg1->numRects;
1791 r2End = r2 + reg2->numRects;
1792
1793 oldRects = newReg->rects;
1794
1795 EMPTY_REGION(newReg);
1796
1797 /*
1798 * Allocate a reasonable number of rectangles for the new region. The idea
1799 * is to allocate enough so the individual functions don't need to
1800 * reallocate and copy the array, which is time consuming, yet we don't
1801 * have to worry about using too much memory. I hope to be able to
1802 * nuke the Xrealloc() at the end of this function eventually.
1803 */
1804 newReg->size = MAX (reg1->numRects, reg2->numRects) * 2;
1805 newReg->rects = (OGdkRegionBox *)malloc(sizeof(OGdkRegionBox) * newReg->size);
1806
1807 /*
1808 * Initialize ybot and ytop.
1809 * In the upcoming loop, ybot and ytop serve different functions depending
1810 * on whether the band being handled is an overlapping or non-overlapping
1811 * band.
1812 * In the case of a non-overlapping band (only one of the regions
1813 * has points in the band), ybot is the bottom of the most recent
1814 * intersection and thus clips the top of the rectangles in that band.
1815 * ytop is the top of the next intersection between the two regions and
1816 * serves to clip the bottom of the rectangles in the current band.
1817 * For an overlapping band (where the two regions intersect), ytop clips
1818 * the top of the rectangles of both regions and ybot clips the bottoms.
1819 */
1820 if (reg1->extents.y1 < reg2->extents.y1)
1821 ybot = reg1->extents.y1;
1822 else
1823 ybot = reg2->extents.y1;
1824
1825 /*
1826 * prevBand serves to mark the start of the previous band so rectangles
1827 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1828 * In the beginning, there is no previous band, so prevBand == curBand
1829 * (curBand is set later on, of course, but the first band will always
1830 * start at index 0). prevBand and curBand must be indices because of
1831 * the possible expansion, and resultant moving, of the new region's
1832 * array of rectangles.
1833 */
1834 prevBand = 0;
1835
1836 do
1837 {
1838 curBand = newReg->numRects;
1839
1840 /*
1841 * This algorithm proceeds one source-band (as opposed to a
1842 * destination band, which is determined by where the two regions
1843 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1844 * rectangle after the last one in the current band for their
1845 * respective regions.
1846 */
1847 r1BandEnd = r1;
1848 while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
1849 {
1850 r1BandEnd++;
1851 }
1852
1853 r2BandEnd = r2;
1854 while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
1855 {
1856 r2BandEnd++;
1857 }
1858
1859 /*
1860 * First handle the band that doesn't intersect, if any.
1861 *
1862 * Note that attention is restricted to one band in the
1863 * non-intersecting region at once, so if a region has n
1864 * bands between the current position and the next place it overlaps
1865 * the other, this entire loop will be passed through n times.
1866 */
1867 if (r1->y1 < r2->y1)
1868 {
1869 top = MAX (r1->y1,ybot);
1870 bot = MIN (r1->y2,r2->y1);
1871
1872 if ((top != bot) && (nonOverlap1Fn != (void (*)(OGdkRegion *, OGdkRegionBox *, OGdkRegionBox *, int,int))NULL))
1873 {
1874 (* nonOverlap1Fn) (newReg, r1, r1BandEnd, top, bot);
1875 }
1876
1877 ytop = r2->y1;
1878 }
1879 else if (r2->y1 < r1->y1)
1880 {
1881 top = MAX (r2->y1,ybot);
1882 bot = MIN (r2->y2,r1->y1);
1883
1884 if ((top != bot) && (nonOverlap2Fn != (void (*)(OGdkRegion *, OGdkRegionBox *, OGdkRegionBox *, int,int))NULL))
1885 {
1886 (* nonOverlap2Fn) (newReg, r2, r2BandEnd, top, bot);
1887 }
1888
1889 ytop = r1->y1;
1890 }
1891 else
1892 {
1893 ytop = r1->y1;
1894 }
1895
1896 /*
1897 * If any rectangles got added to the region, try and coalesce them
1898 * with rectangles from the previous band. Note we could just do
1899 * this test in miCoalesce, but some machines incur a not
1900 * inconsiderable cost for function calls, so...
1901 */
1902 if (newReg->numRects != curBand)
1903 {
1904 prevBand = miCoalesce (newReg, prevBand, curBand);
1905 }
1906
1907 /*
1908 * Now see if we've hit an intersecting band. The two bands only
1909 * intersect if ybot > ytop
1910 */
1911 ybot = MIN (r1->y2, r2->y2);
1912 curBand = newReg->numRects;
1913 if (ybot > ytop)
1914 {
1915 (* overlapFn) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1916
1917 }
1918
1919 if (newReg->numRects != curBand)
1920 {
1921 prevBand = miCoalesce (newReg, prevBand, curBand);
1922 }
1923
1924 /*
1925 * If we've finished with a band (y2 == ybot) we skip forward
1926 * in the region to the next band.
1927 */
1928 if (r1->y2 == ybot)
1929 {
1930 r1 = r1BandEnd;
1931 }
1932 if (r2->y2 == ybot)
1933 {
1934 r2 = r2BandEnd;
1935 }
1936 } while ((r1 != r1End) && (r2 != r2End));
1937
1938 /*
1939 * Deal with whichever region still has rectangles left.
1940 */
1941 curBand = newReg->numRects;
1942 if (r1 != r1End)
1943 {
1944 if (nonOverlap1Fn != (nonOverlapFunc )NULL)
1945 {
1946 do
1947 {
1948 r1BandEnd = r1;
1949 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
1950 {
1951 r1BandEnd++;
1952 }
1953 (* nonOverlap1Fn) (newReg, r1, r1BandEnd,
1954 MAX (r1->y1,ybot), r1->y2);
1955 r1 = r1BandEnd;
1956 } while (r1 != r1End);
1957 }
1958 }
1959 else if ((r2 != r2End) && (nonOverlap2Fn != (nonOverlapFunc) NULL))
1960 {
1961 do
1962 {
1963 r2BandEnd = r2;
1964 while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
1965 {
1966 r2BandEnd++;
1967 }
1968 (* nonOverlap2Fn) (newReg, r2, r2BandEnd,
1969 MAX (r2->y1,ybot), r2->y2);
1970 r2 = r2BandEnd;
1971 } while (r2 != r2End);
1972 }
1973
1974 if (newReg->numRects != curBand)
1975 {
1976 (void) miCoalesce (newReg, prevBand, curBand);
1977 }
1978
1979 /*
1980 * A bit of cleanup. To keep regions from growing without bound,
1981 * we shrink the array of rectangles to match the new number of
1982 * rectangles in the region. This never goes to 0, however...
1983 *
1984 * Only do this stuff if the number of rectangles allocated is more than
1985 * twice the number of rectangles in the region (a simple optimization...).
1986 */
1987 if (newReg->numRects < (newReg->size >> 1))
1988 {
1989 if (REGION_NOT_EMPTY (newReg))
1990 {
1991 newReg->size = newReg->numRects;
1992 // newReg->rects = g_renew (GdkRegionBox, newReg->rects, newReg->size);
1993 newReg->rects = (OGdkRegionBox *)realloc(newReg->rects, sizeof(OGdkRegionBox) * newReg->size);
1994 }
1995 else
1996 {
1997 /*
1998 * No point in doing the extra work involved in an Xrealloc if
1999 * the region is empty
2000 */
2001 newReg->size = 1;
2002 free (newReg->rects);
2003 newReg->rects = &newReg->extents;
2004 }
2005 }
2006
2007 if (oldRects != &newReg->extents)
2008 free (oldRects);
2009 }
2010
2011
2012 /*======================================================================
2013 * Region Union
2014 *====================================================================*/
2015
2016 /*-
2017 * -----------------------------------------------------------------------
2018 * miUnionNonO --
2019 * Handle a non-overlapping band for the union operation. Just
2020 * Adds the rectangles into the region. Doesn't have to check for
2021 * subsumption or anything.
2022 *
2023 * Results:
2024 * None.
2025 *
2026 * Side Effects:
2027 * pReg->numRects is incremented and the final rectangles overwritten
2028 * with the rectangles we're passed.
2029 *
2030 *-----------------------------------------------------------------------
2031 */
2032 static void
miUnionNonO(OGdkRegion * pReg,OGdkRegionBox * r,OGdkRegionBox * rEnd,int y1,int y2)2033 miUnionNonO (OGdkRegion *pReg,
2034 OGdkRegionBox *r,
2035 OGdkRegionBox *rEnd,
2036 int y1,
2037 int y2)
2038 {
2039 OGdkRegionBox *pNextRect;
2040
2041 pNextRect = &pReg->rects[pReg->numRects];
2042
2043 /// g_assert(y1 < y2);
2044
2045 while (r != rEnd)
2046 {
2047 /// g_assert(r->x1 < r->x2);
2048 OMEMCHECK(pReg, pNextRect, pReg->rects);
2049 pNextRect->x1 = r->x1;
2050 pNextRect->y1 = y1;
2051 pNextRect->x2 = r->x2;
2052 pNextRect->y2 = y2;
2053 pReg->numRects += 1;
2054 pNextRect++;
2055
2056 /// g_assert(pReg->numRects<=pReg->size);
2057 r++;
2058 }
2059 }
2060
2061
2062 /*-
2063 * -----------------------------------------------------------------------
2064 * miUnionO --
2065 * Handle an overlapping band for the union operation. Picks the
2066 * left-most rectangle each time and merges it into the region.
2067 *
2068 * Results:
2069 * None.
2070 *
2071 * Side Effects:
2072 * Rectangles are overwritten in pReg->rects and pReg->numRects will
2073 * be changed.
2074 *
2075 *-----------------------------------------------------------------------
2076 */
2077
2078 /* static void*/
2079 static void
miUnionO(OGdkRegion * pReg,OGdkRegionBox * r1,OGdkRegionBox * r1End,OGdkRegionBox * r2,OGdkRegionBox * r2End,int y1,int y2)2080 miUnionO (OGdkRegion *pReg,
2081 OGdkRegionBox *r1,
2082 OGdkRegionBox *r1End,
2083 OGdkRegionBox *r2,
2084 OGdkRegionBox *r2End,
2085 int y1,
2086 int y2)
2087 {
2088 OGdkRegionBox * pNextRect;
2089
2090 pNextRect = &pReg->rects[pReg->numRects];
2091
2092 #define MERGERECT(r) \
2093 if ((pReg->numRects != 0) && \
2094 (pNextRect[-1].y1 == y1) && \
2095 (pNextRect[-1].y2 == y2) && \
2096 (pNextRect[-1].x2 >= r->x1)) \
2097 { \
2098 if (pNextRect[-1].x2 < r->x2) \
2099 { \
2100 pNextRect[-1].x2 = r->x2; \
2101 /*g_assert(pNextRect[-1].x1<pNextRect[-1].x2);*/ \
2102 } \
2103 } \
2104 else \
2105 { \
2106 OMEMCHECK(pReg, pNextRect, pReg->rects); \
2107 pNextRect->y1 = y1; \
2108 pNextRect->y2 = y2; \
2109 pNextRect->x1 = r->x1; \
2110 pNextRect->x2 = r->x2; \
2111 pReg->numRects += 1; \
2112 pNextRect += 1; \
2113 } \
2114 /*g_assert(pReg->numRects<=pReg->size);*/ \
2115 r++;
2116
2117 /// g_assert (y1<y2);
2118 while ((r1 != r1End) && (r2 != r2End))
2119 {
2120 if (r1->x1 < r2->x1)
2121 {
2122 MERGERECT(r1);
2123 }
2124 else
2125 {
2126 MERGERECT(r2);
2127 }
2128 }
2129
2130 if (r1 != r1End)
2131 {
2132 do
2133 {
2134 MERGERECT(r1);
2135 } while (r1 != r1End);
2136 }
2137 else while (r2 != r2End)
2138 {
2139 MERGERECT(r2);
2140 }
2141 }
2142
2143 /**
2144 * gdk_region_union:
2145 * @source1: a #GdkRegion
2146 * @source2: a #GdkRegion
2147 *
2148 * Sets the area of @source1 to the union of the areas of @source1 and
2149 * @source2. The resulting area is the set of pixels contained in
2150 * either @source1 or @source2.
2151 **/
2152 void
gdk_region_union(OGdkRegion * source1,const OGdkRegion * source2)2153 gdk_region_union (OGdkRegion *source1,
2154 const OGdkRegion *source2)
2155 {
2156 /// g_return_if_fail (source1 != NULL);
2157 /// g_return_if_fail (source2 != NULL);
2158
2159 /* checks all the simple cases */
2160
2161 /*
2162 * source1 and source2 are the same or source2 is empty
2163 */
2164 if ((source1 == source2) || (!(source2->numRects)))
2165 return;
2166
2167 /*
2168 * source1 is empty
2169 */
2170 if (!(source1->numRects))
2171 {
2172 miRegionCopy (source1, source2);
2173 return;
2174 }
2175
2176 /*
2177 * source1 completely subsumes source2
2178 */
2179 if ((source1->numRects == 1) &&
2180 (source1->extents.x1 <= source2->extents.x1) &&
2181 (source1->extents.y1 <= source2->extents.y1) &&
2182 (source1->extents.x2 >= source2->extents.x2) &&
2183 (source1->extents.y2 >= source2->extents.y2))
2184 return;
2185
2186 /*
2187 * source2 completely subsumes source1
2188 */
2189 if ((source2->numRects == 1) &&
2190 (source2->extents.x1 <= source1->extents.x1) &&
2191 (source2->extents.y1 <= source1->extents.y1) &&
2192 (source2->extents.x2 >= source1->extents.x2) &&
2193 (source2->extents.y2 >= source1->extents.y2))
2194 {
2195 miRegionCopy(source1, source2);
2196 return;
2197 }
2198
2199 miRegionOp (source1, source1, source2, miUnionO,
2200 miUnionNonO, miUnionNonO);
2201
2202 source1->extents.x1 = MIN (source1->extents.x1, source2->extents.x1);
2203 source1->extents.y1 = MIN (source1->extents.y1, source2->extents.y1);
2204 source1->extents.x2 = MAX (source1->extents.x2, source2->extents.x2);
2205 source1->extents.y2 = MAX (source1->extents.y2, source2->extents.y2);
2206 }
2207
2208
2209 /*======================================================================
2210 * Region Subtraction
2211 *====================================================================*/
2212
2213 /*-
2214 * -----------------------------------------------------------------------
2215 * miSubtractNonO --
2216 * Deal with non-overlapping band for subtraction. Any parts from
2217 * region 2 we discard. Anything from region 1 we add to the region.
2218 *
2219 * Results:
2220 * None.
2221 *
2222 * Side Effects:
2223 * pReg may be affected.
2224 *
2225 *-----------------------------------------------------------------------
2226 */
2227 /* static void*/
2228 static void
miSubtractNonO1(OGdkRegion * pReg,OGdkRegionBox * r,OGdkRegionBox * rEnd,int y1,int y2)2229 miSubtractNonO1 (OGdkRegion *pReg,
2230 OGdkRegionBox *r,
2231 OGdkRegionBox *rEnd,
2232 int y1,
2233 int y2)
2234 {
2235 OGdkRegionBox * pNextRect;
2236
2237 pNextRect = &pReg->rects[pReg->numRects];
2238
2239 /// g_assert(y1<y2);
2240
2241 while (r != rEnd)
2242 {
2243 /// g_assert (r->x1<r->x2);
2244 OMEMCHECK (pReg, pNextRect, pReg->rects);
2245 pNextRect->x1 = r->x1;
2246 pNextRect->y1 = y1;
2247 pNextRect->x2 = r->x2;
2248 pNextRect->y2 = y2;
2249 pReg->numRects += 1;
2250 pNextRect++;
2251
2252 /// g_assert (pReg->numRects <= pReg->size);
2253
2254 r++;
2255 }
2256 }
2257
2258 /*-
2259 * -----------------------------------------------------------------------
2260 * miSubtractO --
2261 * Overlapping band subtraction. x1 is the left-most point not yet
2262 * checked.
2263 *
2264 * Results:
2265 * None.
2266 *
2267 * Side Effects:
2268 * pReg may have rectangles added to it.
2269 *
2270 *-----------------------------------------------------------------------
2271 */
2272 /* static void*/
2273 static void
miSubtractO(OGdkRegion * pReg,OGdkRegionBox * r1,OGdkRegionBox * r1End,OGdkRegionBox * r2,OGdkRegionBox * r2End,int y1,int y2)2274 miSubtractO (OGdkRegion *pReg,
2275 OGdkRegionBox *r1,
2276 OGdkRegionBox *r1End,
2277 OGdkRegionBox *r2,
2278 OGdkRegionBox *r2End,
2279 int y1,
2280 int y2)
2281 {
2282 OGdkRegionBox * pNextRect;
2283 int x1;
2284
2285 x1 = r1->x1;
2286
2287 /// g_assert(y1<y2);
2288 pNextRect = &pReg->rects[pReg->numRects];
2289
2290 while ((r1 != r1End) && (r2 != r2End))
2291 {
2292 if (r2->x2 <= x1)
2293 {
2294 /*
2295 * Subtrahend missed the boat: go to next subtrahend.
2296 */
2297 r2++;
2298 }
2299 else if (r2->x1 <= x1)
2300 {
2301 /*
2302 * Subtrahend preceeds minuend: nuke left edge of minuend.
2303 */
2304 x1 = r2->x2;
2305 if (x1 >= r1->x2)
2306 {
2307 /*
2308 * Minuend completely covered: advance to next minuend and
2309 * reset left fence to edge of new minuend.
2310 */
2311 r1++;
2312 if (r1 != r1End)
2313 x1 = r1->x1;
2314 }
2315 else
2316 {
2317 /*
2318 * Subtrahend now used up since it doesn't extend beyond
2319 * minuend
2320 */
2321 r2++;
2322 }
2323 }
2324 else if (r2->x1 < r1->x2)
2325 {
2326 /*
2327 * Left part of subtrahend covers part of minuend: add uncovered
2328 * part of minuend to region and skip to next subtrahend.
2329 */
2330 /// g_assert(x1<r2->x1);
2331 OMEMCHECK(pReg, pNextRect, pReg->rects);
2332 pNextRect->x1 = x1;
2333 pNextRect->y1 = y1;
2334 pNextRect->x2 = r2->x1;
2335 pNextRect->y2 = y2;
2336 pReg->numRects += 1;
2337 pNextRect++;
2338
2339 /// g_assert(pReg->numRects<=pReg->size);
2340
2341 x1 = r2->x2;
2342 if (x1 >= r1->x2)
2343 {
2344 /*
2345 * Minuend used up: advance to new...
2346 */
2347 r1++;
2348 if (r1 != r1End)
2349 x1 = r1->x1;
2350 }
2351 else
2352 {
2353 /*
2354 * Subtrahend used up
2355 */
2356 r2++;
2357 }
2358 }
2359 else
2360 {
2361 /*
2362 * Minuend used up: add any remaining piece before advancing.
2363 */
2364 if (r1->x2 > x1)
2365 {
2366 OMEMCHECK(pReg, pNextRect, pReg->rects);
2367 pNextRect->x1 = x1;
2368 pNextRect->y1 = y1;
2369 pNextRect->x2 = r1->x2;
2370 pNextRect->y2 = y2;
2371 pReg->numRects += 1;
2372 pNextRect++;
2373 /// g_assert(pReg->numRects<=pReg->size);
2374 }
2375 r1++;
2376 if (r1 != r1End)
2377 x1 = r1->x1;
2378 }
2379 }
2380
2381 /*
2382 * Add remaining minuend rectangles to region.
2383 */
2384 while (r1 != r1End)
2385 {
2386 /// g_assert(x1<r1->x2);
2387 OMEMCHECK(pReg, pNextRect, pReg->rects);
2388 pNextRect->x1 = x1;
2389 pNextRect->y1 = y1;
2390 pNextRect->x2 = r1->x2;
2391 pNextRect->y2 = y2;
2392 pReg->numRects += 1;
2393 pNextRect++;
2394
2395 /// g_assert(pReg->numRects<=pReg->size);
2396
2397 r1++;
2398 if (r1 != r1End)
2399 {
2400 x1 = r1->x1;
2401 }
2402 }
2403 }
2404
2405 /**
2406 * gdk_region_subtract:
2407 * @source1: a #GdkRegion
2408 * @source2: another #GdkRegion
2409 *
2410 * Subtracts the area of @source2 from the area @source1. The resulting
2411 * area is the set of pixels contained in @source1 but not in @source2.
2412 **/
2413 void
gdk_region_subtract(OGdkRegion * source1,const OGdkRegion * source2)2414 gdk_region_subtract (OGdkRegion *source1,
2415 const OGdkRegion *source2)
2416 {
2417 // g_return_if_fail (source1 != NULL);
2418 // g_return_if_fail (source2 != NULL);
2419
2420 /* check for trivial reject */
2421 if ((!(source1->numRects)) || (!(source2->numRects)) ||
2422 (!EXTENTCHECK(&source1->extents, &source2->extents)))
2423 return;
2424
2425 miRegionOp (source1, source1, source2, miSubtractO,
2426 miSubtractNonO1, (nonOverlapFunc) NULL);
2427
2428 /*
2429 * Can't alter source1's extents before we call miRegionOp because miRegionOp
2430 * depends on the extents of those regions being the unaltered. Besides, this
2431 * way there's no checking against rectangles that will be nuked
2432 * due to coalescing, so we have to examine fewer rectangles.
2433 */
2434 miSetExtents (source1);
2435 }
2436
2437 /**
2438 * gdk_region_xor:
2439 * @source1: a #GdkRegion
2440 * @source2: another #GdkRegion
2441 *
2442 * Sets the area of @source1 to the exclusive-OR of the areas of @source1
2443 * and @source2. The resulting area is the set of pixels contained in one
2444 * or the other of the two sources but not in both.
2445 **/
2446 void
gdk_region_xor(OGdkRegion * source1,const OGdkRegion * source2)2447 gdk_region_xor (OGdkRegion *source1,
2448 const OGdkRegion *source2)
2449 {
2450 OGdkRegion *trb;
2451
2452 // g_return_if_fail (source1 != NULL);
2453 // g_return_if_fail (source2 != NULL);
2454
2455 trb = gdk_region_copy (source2);
2456
2457 gdk_region_subtract (trb, source1);
2458 gdk_region_subtract (source1, source2);
2459
2460 gdk_region_union (source1, trb);
2461
2462 gdk_region_destroy (trb);
2463 }
2464
2465 /**
2466 * gdk_region_empty:
2467 * @region: a #GdkRegion
2468 *
2469 * Finds out if the #GdkRegion is empty.
2470 *
2471 * Returns: %TRUE if @region is empty.
2472 */
2473 bool
gdk_region_empty(const OGdkRegion * region)2474 gdk_region_empty (const OGdkRegion *region)
2475 {
2476 // g_return_val_if_fail (region != NULL, FALSE);
2477
2478 if (region->numRects == 0)
2479 return TRUE;
2480 else
2481 return FALSE;
2482 }
2483
2484 /**
2485 * gdk_region_equal:
2486 * @region1: a #GdkRegion
2487 * @region2: a #GdkRegion
2488 *
2489 * Finds out if the two regions are the same.
2490 *
2491 * Returns: %TRUE if @region1 and @region2 are equal.
2492 */
2493 bool
ogdk_region_equal(const OGdkRegion * region1,const OGdkRegion * region2)2494 ogdk_region_equal (const OGdkRegion *region1,
2495 const OGdkRegion *region2)
2496 {
2497 int i;
2498
2499 // g_return_val_if_fail (region1 != NULL, FALSE);
2500 // g_return_val_if_fail (region2 != NULL, FALSE);
2501
2502 if (region1->numRects != region2->numRects) return FALSE;
2503 if (region1->numRects == 0) return TRUE;
2504 if (region1->extents.x1 != region2->extents.x1) return FALSE;
2505 if (region1->extents.x2 != region2->extents.x2) return FALSE;
2506 if (region1->extents.y1 != region2->extents.y1) return FALSE;
2507 if (region1->extents.y2 != region2->extents.y2) return FALSE;
2508 for(i = 0; i < region1->numRects; i++ )
2509 {
2510 if (region1->rects[i].x1 != region2->rects[i].x1) return FALSE;
2511 if (region1->rects[i].x2 != region2->rects[i].x2) return FALSE;
2512 if (region1->rects[i].y1 != region2->rects[i].y1) return FALSE;
2513 if (region1->rects[i].y2 != region2->rects[i].y2) return FALSE;
2514 }
2515 return TRUE;
2516 }
2517
2518 /**
2519 * gdk_region_point_in:
2520 * @region: a #GdkRegion
2521 * @x: the x coordinate of a point
2522 * @y: the y coordinate of a point
2523 *
2524 * Finds out if a point is in a region.
2525 *
2526 * Returns: %TRUE if the point is in @region.
2527 */
2528 bool
gdk_region_point_in(const OGdkRegion * region,int x,int y)2529 gdk_region_point_in (const OGdkRegion *region,
2530 int x,
2531 int y)
2532 {
2533 int i;
2534
2535 // g_return_val_if_fail (region != NULL, FALSE);
2536
2537 if (region->numRects == 0)
2538 return FALSE;
2539 if (!INBOX(region->extents, x, y))
2540 return FALSE;
2541 for (i = 0; i < region->numRects; i++)
2542 {
2543 if (INBOX (region->rects[i], x, y))
2544 return TRUE;
2545 }
2546 return FALSE;
2547 }
2548
2549
2550 /**
2551 * gdk_region_rect_in:
2552 * @region: a #GdkRegion.
2553 * @rectangle: a #GdkRectangle.
2554 *
2555 * Tests whether a rectangle is within a region.
2556 *
2557 * Returns: %GDK_OVERLAP_RECTANGLE_IN, %GDK_OVERLAP_RECTANGLE_OUT, or
2558 * %GDK_OVERLAP_RECTANGLE_PART, depending on whether the rectangle is inside,
2559 * outside, or partly inside the #GdkRegion, respectively.
2560 */
2561 OGdkOverlapType
gdk_region_rect_in(const OGdkRegion * region,const OGdkRectangle * rectangle)2562 gdk_region_rect_in (const OGdkRegion *region,
2563 const OGdkRectangle *rectangle)
2564 {
2565 OGdkRegionBox *pbox;
2566 OGdkRegionBox *pboxEnd;
2567 OGdkRegionBox rect;
2568 OGdkRegionBox *prect = ▭
2569 bool partIn, partOut;
2570 int rx, ry;
2571
2572 // g_return_val_if_fail (region != NULL, GDK_OVERLAP_RECTANGLE_OUT);
2573 // g_return_val_if_fail (rectangle != NULL, GDK_OVERLAP_RECTANGLE_OUT);
2574
2575 rx = rectangle->x;
2576 ry = rectangle->y;
2577
2578 prect->x1 = rx;
2579 prect->y1 = ry;
2580 prect->x2 = rx + rectangle->width;
2581 prect->y2 = ry + rectangle->height;
2582
2583 /* this is (just) a useful optimization */
2584 if ((region->numRects == 0) || !EXTENTCHECK (®ion->extents, prect))
2585 return OGDK_OVERLAP_RECTANGLE_OUT;
2586
2587 partOut = FALSE;
2588 partIn = FALSE;
2589
2590 /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
2591 for (pbox = region->rects, pboxEnd = pbox + region->numRects; pbox < pboxEnd; pbox++)
2592 {
2593
2594 if (pbox->y2 <= ry)
2595 continue; /* getting up to speed or skipping remainder of band */
2596
2597 if (pbox->y1 > ry)
2598 {
2599 partOut = TRUE; /* missed part of rectangle above */
2600 if (partIn || (pbox->y1 >= prect->y2))
2601 break;
2602 ry = pbox->y1; /* x guaranteed to be == prect->x1 */
2603 }
2604
2605 if (pbox->x2 <= rx)
2606 continue; /* not far enough over yet */
2607
2608 if (pbox->x1 > rx)
2609 {
2610 partOut = TRUE; /* missed part of rectangle to left */
2611 if (partIn)
2612 break;
2613 }
2614
2615 if (pbox->x1 < prect->x2)
2616 {
2617 partIn = TRUE; /* definitely overlap */
2618 if (partOut)
2619 break;
2620 }
2621
2622 if (pbox->x2 >= prect->x2)
2623 {
2624 ry = pbox->y2; /* finished with this band */
2625 if (ry >= prect->y2)
2626 break;
2627 rx = prect->x1; /* reset x out to left again */
2628 }
2629 else
2630 {
2631 /*
2632 * Because boxes in a band are maximal width, if the first box
2633 * to overlap the rectangle doesn't completely cover it in that
2634 * band, the rectangle must be partially out, since some of it
2635 * will be uncovered in that band. partIn will have been set true
2636 * by now...
2637 */
2638 break;
2639 }
2640
2641 }
2642
2643 return (partIn ?
2644 ((ry < prect->y2) ?
2645 OGDK_OVERLAP_RECTANGLE_PART : OGDK_OVERLAP_RECTANGLE_IN) :
2646 OGDK_OVERLAP_RECTANGLE_OUT);
2647 }
2648
2649 #if 0
2650 static void
2651 gdk_region_unsorted_spans_intersect_foreach (GdkRegion *region,
2652 const GdkSpan *spans,
2653 int n_spans,
2654 GdkSpanFunc function,
2655 gpointer data)
2656 {
2657 gint i, left, right, y;
2658 gint clipped_left, clipped_right;
2659 GdkRegionBox *pbox;
2660 GdkRegionBox *pboxEnd;
2661
2662 if (!region->numRects)
2663 return;
2664
2665 for (i=0;i<n_spans;i++)
2666 {
2667 y = spans[i].y;
2668 left = spans[i].x;
2669 right = left + spans[i].width; /* right is not in the span! */
2670
2671 if (! ((region->extents.y1 <= y) &&
2672 (region->extents.y2 > y) &&
2673 (region->extents.x1 < right) &&
2674 (region->extents.x2 > left)) )
2675 continue;
2676
2677 /* can stop when we passed y */
2678 for (pbox = region->rects, pboxEnd = pbox + region->numRects;
2679 pbox < pboxEnd;
2680 pbox++)
2681 {
2682 if (pbox->y2 <= y)
2683 continue; /* Not quite there yet */
2684
2685 if (pbox->y1 > y)
2686 break; /* passed the spanline */
2687
2688 if ((right > pbox->x1) && (left < pbox->x2))
2689 {
2690 GdkSpan out_span;
2691
2692 clipped_left = MAX (left, pbox->x1);
2693 clipped_right = MIN (right, pbox->x2);
2694
2695 out_span.y = y;
2696 out_span.x = clipped_left;
2697 out_span.width = clipped_right - clipped_left;
2698 (*function) (&out_span, data);
2699 }
2700 }
2701 }
2702 }
2703 #endif
2704
2705 #if 0
2706 /**
2707 * gdk_region_spans_intersect_foreach:
2708 * @region: a #GdkRegion
2709 * @spans: an array of #GdkSpans
2710 * @n_spans: the length of @spans
2711 * @sorted: %TRUE if @spans is sorted wrt. the y coordinate
2712 * @function: function to call on each span in the intersection
2713 * @data: data to pass to @function
2714 *
2715 * Calls a function on each span in the intersection of @region and @spans.
2716 */
2717 void
2718 gdk_region_spans_intersect_foreach (GdkRegion *region,
2719 const GdkSpan *spans,
2720 int n_spans,
2721 gboolean sorted,
2722 GdkSpanFunc function,
2723 gpointer data)
2724 {
2725 gint left, right, y;
2726 gint clipped_left, clipped_right;
2727 GdkRegionBox *pbox;
2728 GdkRegionBox *pboxEnd;
2729 const GdkSpan *span, *tmpspan;
2730 const GdkSpan *end_span;
2731
2732 g_return_if_fail (region != NULL);
2733 g_return_if_fail (spans != NULL);
2734
2735 if (!sorted)
2736 {
2737 gdk_region_unsorted_spans_intersect_foreach (region,
2738 spans,
2739 n_spans,
2740 function,
2741 data);
2742 return;
2743 }
2744
2745 if ((!region->numRects) || (n_spans == 0))
2746 return;
2747
2748 /* The main method here is to step along the
2749 * sorted rectangles and spans in lock step, and
2750 * clipping the spans that are in the current
2751 * rectangle before going on to the next rectangle.
2752 */
2753
2754 span = spans;
2755 end_span = spans + n_spans;
2756 pbox = region->rects;
2757 pboxEnd = pbox + region->numRects;
2758 while (pbox < pboxEnd)
2759 {
2760 while ((pbox->y2 < span->y) || (span->y < pbox->y1))
2761 {
2762 /* Skip any rectangles that are above the current span */
2763 if (pbox->y2 < span->y)
2764 {
2765 pbox++;
2766 if (pbox == pboxEnd)
2767 return;
2768 }
2769 /* Skip any spans that are above the current rectangle */
2770 if (span->y < pbox->y1)
2771 {
2772 span++;
2773 if (span == end_span)
2774 return;
2775 }
2776 }
2777
2778 /* Ok, we got at least one span that might intersect this rectangle. */
2779 tmpspan = span;
2780 while ((tmpspan < end_span) &&
2781 (tmpspan->y < pbox->y2))
2782 {
2783 y = tmpspan->y;
2784 left = tmpspan->x;
2785 right = left + tmpspan->width; /* right is not in the span! */
2786
2787 if ((right > pbox->x1) && (left < pbox->x2))
2788 {
2789 GdkSpan out_span;
2790
2791 clipped_left = MAX (left, pbox->x1);
2792 clipped_right = MIN (right, pbox->x2);
2793
2794 out_span.y = y;
2795 out_span.x = clipped_left;
2796 out_span.width = clipped_right - clipped_left;
2797 (*function) (&out_span, data);
2798 }
2799
2800 tmpspan++;
2801 }
2802
2803 /* Finished this rectangle.
2804 * The spans could still intersect the next one
2805 */
2806 pbox++;
2807 }
2808 }
2809 #endif
2810
2811
2812 /* $TOG: PolyReg.c /main/15 1998/02/06 17:47:08 kaleb $ */
2813 /************************************************************************
2814 *
2815 * Copyright 1987, 1998 The Open Group
2816 *
2817 * All Rights Reserved.
2818 *
2819 * The above copyright notice and this permission notice shall be included in
2820 * all copies or substantial portions of the Software.
2821 *
2822 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2823 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2824 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2825 * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
2826 * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
2827 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
2828 *
2829 * Except as contained in this notice, the name of The Open Group shall not be
2830 * used in advertising or otherwise to promote the sale, use or other dealings
2831 * in this Software without prior written authorization from The Open Group.
2832 *
2833 *
2834 * Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
2835 *
2836 * All Rights Reserved
2837 *
2838 * Permission to use, copy, modify, and distribute this software and its
2839 * documentation for any purpose and without fee is hereby granted,
2840 * provided that the above copyright notice appear in all copies and that
2841 * both that copyright notice and this permission notice appear in
2842 * supporting documentation, and that the name of Digital not be
2843 * used in advertising or publicity pertaining to distribution of the
2844 * software without specific, written prior permission.
2845 *
2846 * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
2847 * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
2848 * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
2849 * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
2850 * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
2851 * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
2852 * SOFTWARE.
2853 *
2854 ************************************************************************/
2855 /* $XFree86: xc/lib/X11/PolyReg.c,v 1.4 1998/10/03 08:41:21 dawes Exp $ */
2856
2857 #define LARGE_COORDINATE 1000000
2858 #define SMALL_COORDINATE -LARGE_COORDINATE
2859
2860 // #include "config.h"
2861 // #include <gdkregion.h>
2862 // #include "gdkregion-generic.h"
2863 // #include "gdkpoly-generic.h"
2864 // #include "gdkalias.h"
2865
2866 /*
2867 * InsertEdgeInET
2868 *
2869 * Insert the given edge into the edge table.
2870 * First we must find the correct bucket in the
2871 * Edge table, then find the right slot in the
2872 * bucket. Finally, we can insert it.
2873 *
2874 */
2875 static void
InsertEdgeInET(OEdgeTable * ET,OEdgeTableEntry * ETE,int scanline,OScanLineListBlock ** SLLBlock,int * iSLLBlock)2876 InsertEdgeInET (OEdgeTable *ET,
2877 OEdgeTableEntry *ETE,
2878 int scanline,
2879 OScanLineListBlock **SLLBlock,
2880 int *iSLLBlock)
2881 {
2882 OEdgeTableEntry *start, *prev;
2883 OScanLineList *pSLL, *pPrevSLL;
2884 OScanLineListBlock *tmpSLLBlock;
2885
2886 /*
2887 * find the right bucket to put the edge into
2888 */
2889 pPrevSLL = &ET->scanlines;
2890 pSLL = pPrevSLL->next;
2891 while (pSLL && (pSLL->scanline < scanline))
2892 {
2893 pPrevSLL = pSLL;
2894 pSLL = pSLL->next;
2895 }
2896
2897 /*
2898 * reassign pSLL (pointer to ScanLineList) if necessary
2899 */
2900 if ((!pSLL) || (pSLL->scanline > scanline))
2901 {
2902 if (*iSLLBlock > SLLSPERBLOCK-1)
2903 {
2904 tmpSLLBlock =
2905 (OScanLineListBlock *)malloc(sizeof(OScanLineListBlock));
2906 (*SLLBlock)->next = tmpSLLBlock;
2907 tmpSLLBlock->next = (OScanLineListBlock *)NULL;
2908 *SLLBlock = tmpSLLBlock;
2909 *iSLLBlock = 0;
2910 }
2911 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2912
2913 pSLL->next = pPrevSLL->next;
2914 pSLL->edgelist = (OEdgeTableEntry *)NULL;
2915 pPrevSLL->next = pSLL;
2916 }
2917 pSLL->scanline = scanline;
2918
2919 /*
2920 * now insert the edge in the right bucket
2921 */
2922 prev = (OEdgeTableEntry *)NULL;
2923 start = pSLL->edgelist;
2924 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2925 {
2926 prev = start;
2927 start = start->next;
2928 }
2929 ETE->next = start;
2930
2931 if (prev)
2932 prev->next = ETE;
2933 else
2934 pSLL->edgelist = ETE;
2935 }
2936
2937 /*
2938 * CreateEdgeTable
2939 *
2940 * This routine creates the edge table for
2941 * scan converting polygons.
2942 * The Edge Table (ET) looks like:
2943 *
2944 * EdgeTable
2945 * --------
2946 * | ymax | ScanLineLists
2947 * |scanline|-->------------>-------------->...
2948 * -------- |scanline| |scanline|
2949 * |edgelist| |edgelist|
2950 * --------- ---------
2951 * | |
2952 * | |
2953 * V V
2954 * list of ETEs list of ETEs
2955 *
2956 * where ETE is an EdgeTableEntry data structure,
2957 * and there is one ScanLineList per scanline at
2958 * which an edge is initially entered.
2959 *
2960 */
2961
2962 static void
CreateETandAET(int count,const OGdkPoint * pts,OEdgeTable * ET,OEdgeTableEntry * AET,OEdgeTableEntry * pETEs,OScanLineListBlock * pSLLBlock)2963 CreateETandAET (int count,
2964 const OGdkPoint *pts,
2965 OEdgeTable *ET,
2966 OEdgeTableEntry *AET,
2967 OEdgeTableEntry *pETEs,
2968 OScanLineListBlock *pSLLBlock)
2969 {
2970 const OGdkPoint *top, *bottom;
2971 const OGdkPoint *PrevPt, *CurrPt;
2972 int iSLLBlock = 0;
2973 int dy;
2974
2975 if (count < 2) return;
2976
2977 /*
2978 * initialize the Active Edge Table
2979 */
2980 AET->next = (OEdgeTableEntry *)NULL;
2981 AET->back = (OEdgeTableEntry *)NULL;
2982 AET->nextWETE = (OEdgeTableEntry *)NULL;
2983 AET->bres.minor_axis = SMALL_COORDINATE;
2984
2985 /*
2986 * initialize the Edge Table.
2987 */
2988 ET->scanlines.next = (OScanLineList *)NULL;
2989 ET->ymax = SMALL_COORDINATE;
2990 ET->ymin = LARGE_COORDINATE;
2991 pSLLBlock->next = (OScanLineListBlock *)NULL;
2992
2993 PrevPt = &pts[count-1];
2994
2995 /*
2996 * for each vertex in the array of points.
2997 * In this loop we are dealing with two vertices at
2998 * a time -- these make up one edge of the polygon.
2999 */
3000 while (count--)
3001 {
3002 CurrPt = pts++;
3003
3004 /*
3005 * find out which point is above and which is below.
3006 */
3007 if (PrevPt->y > CurrPt->y)
3008 {
3009 bottom = PrevPt, top = CurrPt;
3010 pETEs->ClockWise = 0;
3011 }
3012 else
3013 {
3014 bottom = CurrPt, top = PrevPt;
3015 pETEs->ClockWise = 1;
3016 }
3017
3018 /*
3019 * don't add horizontal edges to the Edge table.
3020 */
3021 if (bottom->y != top->y)
3022 {
3023 pETEs->ymax = bottom->y-1; /* -1 so we don't get last scanline */
3024
3025 /*
3026 * initialize integer edge algorithm
3027 */
3028 dy = bottom->y - top->y;
3029 OBRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
3030
3031 InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
3032
3033 if (PrevPt->y > ET->ymax)
3034 ET->ymax = PrevPt->y;
3035 if (PrevPt->y < ET->ymin)
3036 ET->ymin = PrevPt->y;
3037 pETEs++;
3038 }
3039
3040 PrevPt = CurrPt;
3041 }
3042 }
3043
3044 /*
3045 * loadAET
3046 *
3047 * This routine moves EdgeTableEntries from the
3048 * EdgeTable into the Active Edge Table,
3049 * leaving them sorted by smaller x coordinate.
3050 *
3051 */
3052
3053 static void
loadAET(OEdgeTableEntry * AET,OEdgeTableEntry * ETEs)3054 loadAET(OEdgeTableEntry *AET,
3055 OEdgeTableEntry *ETEs)
3056 {
3057 OEdgeTableEntry *pPrevAET;
3058 OEdgeTableEntry *tmp;
3059
3060 pPrevAET = AET;
3061 AET = AET->next;
3062 while (ETEs)
3063 {
3064 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
3065 {
3066 pPrevAET = AET;
3067 AET = AET->next;
3068 }
3069 tmp = ETEs->next;
3070 ETEs->next = AET;
3071 if (AET)
3072 AET->back = ETEs;
3073 ETEs->back = pPrevAET;
3074 pPrevAET->next = ETEs;
3075 pPrevAET = ETEs;
3076
3077 ETEs = tmp;
3078 }
3079 }
3080
3081 /*
3082 * computeWAET
3083 *
3084 * This routine links the AET by the
3085 * nextWETE (winding EdgeTableEntry) link for
3086 * use by the winding number rule. The final
3087 * Active Edge Table (AET) might look something
3088 * like:
3089 *
3090 * AET
3091 * ---------- --------- ---------
3092 * |ymax | |ymax | |ymax |
3093 * | ... | |... | |... |
3094 * |next |->|next |->|next |->...
3095 * |nextWETE| |nextWETE| |nextWETE|
3096 * --------- --------- ^--------
3097 * | | |
3098 * V-------------------> V---> ...
3099 *
3100 */
3101 static void
computeWAET(OEdgeTableEntry * AET)3102 computeWAET (OEdgeTableEntry *AET)
3103 {
3104 OEdgeTableEntry *pWETE;
3105 int inside = 1;
3106 int isInside = 0;
3107
3108 AET->nextWETE = (OEdgeTableEntry *)NULL;
3109 pWETE = AET;
3110 AET = AET->next;
3111 while (AET)
3112 {
3113 if (AET->ClockWise)
3114 isInside++;
3115 else
3116 isInside--;
3117
3118 if ((!inside && !isInside) ||
3119 ( inside && isInside))
3120 {
3121 pWETE->nextWETE = AET;
3122 pWETE = AET;
3123 inside = !inside;
3124 }
3125 AET = AET->next;
3126 }
3127 pWETE->nextWETE = (OEdgeTableEntry *)NULL;
3128 }
3129
3130 /*
3131 * InsertionSort
3132 *
3133 * Just a simple insertion sort using
3134 * pointers and back pointers to sort the Active
3135 * Edge Table.
3136 *
3137 */
3138
3139 static int
InsertionSort(OEdgeTableEntry * AET)3140 InsertionSort (OEdgeTableEntry *AET)
3141 {
3142 OEdgeTableEntry *pETEchase;
3143 OEdgeTableEntry *pETEinsert;
3144 OEdgeTableEntry *pETEchaseBackTMP;
3145 int changed = 0;
3146
3147 AET = AET->next;
3148 while (AET)
3149 {
3150 pETEinsert = AET;
3151 pETEchase = AET;
3152 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
3153 pETEchase = pETEchase->back;
3154
3155 AET = AET->next;
3156 if (pETEchase != pETEinsert)
3157 {
3158 pETEchaseBackTMP = pETEchase->back;
3159 pETEinsert->back->next = AET;
3160 if (AET)
3161 AET->back = pETEinsert->back;
3162 pETEinsert->next = pETEchase;
3163 pETEchase->back->next = pETEinsert;
3164 pETEchase->back = pETEinsert;
3165 pETEinsert->back = pETEchaseBackTMP;
3166 changed = 1;
3167 }
3168 }
3169 return(changed);
3170 }
3171
3172 /*
3173 * Clean up our act.
3174 */
3175 static void
FreeStorage(OScanLineListBlock * pSLLBlock)3176 FreeStorage (OScanLineListBlock *pSLLBlock)
3177 {
3178 OScanLineListBlock *tmpSLLBlock;
3179
3180 while (pSLLBlock)
3181 {
3182 tmpSLLBlock = pSLLBlock->next;
3183 free (pSLLBlock);
3184 pSLLBlock = tmpSLLBlock;
3185 }
3186 }
3187
3188 /*
3189 * Create an array of rectangles from a list of points.
3190 * If indeed these things (POINTS, RECTS) are the same,
3191 * then this proc is still needed, because it allocates
3192 * storage for the array, which was allocated on the
3193 * stack by the calling procedure.
3194 *
3195 */
3196 static int
PtsToRegion(int numFullPtBlocks,int iCurPtBlock,OPOINTBLOCK * FirstPtBlock,OGdkRegion * reg)3197 PtsToRegion (int numFullPtBlocks,
3198 int iCurPtBlock,
3199 OPOINTBLOCK *FirstPtBlock,
3200 OGdkRegion *reg)
3201 {
3202 OGdkRegionBox *rects;
3203 OGdkPoint *pts;
3204 OPOINTBLOCK *CurPtBlock;
3205 int i;
3206 OGdkRegionBox *extents;
3207 int numRects;
3208
3209 extents = ®->extents;
3210
3211 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
3212
3213 OGROWREGION(reg, numRects);
3214
3215 CurPtBlock = FirstPtBlock;
3216 rects = reg->rects - 1;
3217 numRects = 0;
3218 extents->x1 = 1000000 /*G_MAXSHORT*/, extents->x2 = -1000000 /*G_MINSHORT*/;
3219
3220 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
3221 /* the loop uses 2 points per iteration */
3222 i = NUMPTSTOBUFFER >> 1;
3223 if (!numFullPtBlocks)
3224 i = iCurPtBlock >> 1;
3225 for (pts = CurPtBlock->pts; i--; pts += 2) {
3226 if (pts->x == pts[1].x)
3227 continue;
3228 if (numRects && pts->x == rects->x1 && pts->y == rects->y2 &&
3229 pts[1].x == rects->x2 &&
3230 (numRects == 1 || rects[-1].y1 != rects->y1) &&
3231 (i && pts[2].y > pts[1].y)) {
3232 rects->y2 = pts[1].y + 1;
3233 continue;
3234 }
3235 numRects++;
3236 rects++;
3237 rects->x1 = pts->x; rects->y1 = pts->y;
3238 rects->x2 = pts[1].x; rects->y2 = pts[1].y + 1;
3239 if (rects->x1 < extents->x1)
3240 extents->x1 = rects->x1;
3241 if (rects->x2 > extents->x2)
3242 extents->x2 = rects->x2;
3243 }
3244 CurPtBlock = CurPtBlock->next;
3245 }
3246
3247 if (numRects) {
3248 extents->y1 = reg->rects->y1;
3249 extents->y2 = rects->y2;
3250 } else {
3251 extents->x1 = 0;
3252 extents->y1 = 0;
3253 extents->x2 = 0;
3254 extents->y2 = 0;
3255 }
3256 reg->numRects = numRects;
3257
3258 return(TRUE);
3259 }
3260
3261 /**
3262 * gdk_region_polygon:
3263 * @points: an array of #GdkPoint structs
3264 * @n_points: the number of elements in the @points array
3265 * @fill_rule: specifies which pixels are included in the region when the
3266 * polygon overlaps itself.
3267 *
3268 * Creates a new #GdkRegion using the polygon defined by a
3269 * number of points.
3270 *
3271 * Returns: a new #GdkRegion based on the given polygon
3272 */
3273 OGdkRegion *
gdk_region_polygon(const OGdkPoint * points,int n_points,OGdkFillRule fill_rule)3274 gdk_region_polygon (const OGdkPoint *points,
3275 int n_points,
3276 OGdkFillRule fill_rule)
3277 {
3278 OGdkRegion *region;
3279 OEdgeTableEntry *pAET; /* Active Edge Table */
3280 int y; /* current scanline */
3281 int iPts = 0; /* number of pts in buffer */
3282 OEdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
3283 OScanLineList *pSLL; /* current scanLineList */
3284 OGdkPoint *pts; /* output buffer */
3285 OEdgeTableEntry *pPrevAET; /* ptr to previous AET */
3286 OEdgeTable ET = {0}; /* header node for ET */
3287 OEdgeTableEntry AET; /* header node for AET */
3288 OEdgeTableEntry *pETEs; /* EdgeTableEntries pool */
3289 OScanLineListBlock SLLBlock; /* header for scanlinelist */
3290 int fixWAET = FALSE;
3291 OPOINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
3292 OPOINTBLOCK *tmpPtBlock;
3293 int numFullPtBlocks = 0;
3294
3295 region = gdk_region_new ();
3296
3297 /* special case a rectangle */
3298 if (((n_points == 4) ||
3299 ((n_points == 5) && (points[4].x == points[0].x) && (points[4].y == points[0].y))) &&
3300 (((points[0].y == points[1].y) &&
3301 (points[1].x == points[2].x) &&
3302 (points[2].y == points[3].y) &&
3303 (points[3].x == points[0].x)) ||
3304 ((points[0].x == points[1].x) &&
3305 (points[1].y == points[2].y) &&
3306 (points[2].x == points[3].x) &&
3307 (points[3].y == points[0].y)))) {
3308 region->extents.x1 = MIN(points[0].x, points[2].x);
3309 region->extents.y1 = MIN(points[0].y, points[2].y);
3310 region->extents.x2 = MAX(points[0].x, points[2].x);
3311 region->extents.y2 = MAX(points[0].y, points[2].y);
3312 if ((region->extents.x1 != region->extents.x2) &&
3313 (region->extents.y1 != region->extents.y2)) {
3314 region->numRects = 1;
3315 *(region->rects) = region->extents;
3316 }
3317 return(region);
3318 }
3319
3320 pETEs = (OEdgeTableEntry *)malloc(sizeof(OEdgeTableEntry) * n_points);
3321
3322 pts = FirstPtBlock.pts;
3323 CreateETandAET(n_points, points, &ET, &AET, pETEs, &SLLBlock);
3324 pSLL = ET.scanlines.next;
3325 curPtBlock = &FirstPtBlock;
3326
3327 if (fill_rule == OGDK_EVEN_ODD_RULE) {
3328 /*
3329 * for each scanline
3330 */
3331 for (y = ET.ymin; y < ET.ymax; y++) {
3332 /*
3333 * Add a new edge to the active edge table when we
3334 * get to the next edge.
3335 */
3336 if (pSLL != NULL && y == pSLL->scanline) {
3337 loadAET(&AET, pSLL->edgelist);
3338 pSLL = pSLL->next;
3339 }
3340 pPrevAET = &AET;
3341 pAET = AET.next;
3342
3343 /*
3344 * for each active edge
3345 */
3346 while (pAET) {
3347 pts->x = pAET->bres.minor_axis, pts->y = y;
3348 pts++, iPts++;
3349
3350 /*
3351 * send out the buffer
3352 */
3353 if (iPts == NUMPTSTOBUFFER) {
3354 tmpPtBlock = (OPOINTBLOCK *)malloc(sizeof(OPOINTBLOCK));
3355 tmpPtBlock->next = NULL;
3356 curPtBlock->next = tmpPtBlock;
3357 curPtBlock = tmpPtBlock;
3358 pts = curPtBlock->pts;
3359 numFullPtBlocks++;
3360 iPts = 0;
3361 }
3362 OEVALUATEEDGEEVENODD(pAET, pPrevAET, y);
3363 }
3364 (void) InsertionSort(&AET);
3365 }
3366 }
3367 else {
3368 /*
3369 * for each scanline
3370 */
3371 for (y = ET.ymin; y < ET.ymax; y++) {
3372 /*
3373 * Add a new edge to the active edge table when we
3374 * get to the next edge.
3375 */
3376 if (pSLL != NULL && y == pSLL->scanline) {
3377 loadAET(&AET, pSLL->edgelist);
3378 computeWAET(&AET);
3379 pSLL = pSLL->next;
3380 }
3381 pPrevAET = &AET;
3382 pAET = AET.next;
3383 pWETE = pAET;
3384
3385 /*
3386 * for each active edge
3387 */
3388 while (pAET) {
3389 /*
3390 * add to the buffer only those edges that
3391 * are in the Winding active edge table.
3392 */
3393 if (pWETE == pAET) {
3394 pts->x = pAET->bres.minor_axis, pts->y = y;
3395 pts++, iPts++;
3396
3397 /*
3398 * send out the buffer
3399 */
3400 if (iPts == NUMPTSTOBUFFER) {
3401 tmpPtBlock = (OPOINTBLOCK *)malloc(sizeof(OPOINTBLOCK));
3402 tmpPtBlock->next = NULL;
3403 curPtBlock->next = tmpPtBlock;
3404 curPtBlock = tmpPtBlock;
3405 pts = curPtBlock->pts;
3406 numFullPtBlocks++; iPts = 0;
3407 }
3408 pWETE = pWETE->nextWETE;
3409 }
3410 OEVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
3411 }
3412
3413 /*
3414 * recompute the winding active edge table if
3415 * we just resorted or have exited an edge.
3416 */
3417 if (InsertionSort(&AET) || fixWAET) {
3418 computeWAET(&AET);
3419 fixWAET = FALSE;
3420 }
3421 }
3422 }
3423 FreeStorage(SLLBlock.next);
3424 (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3425 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3426 tmpPtBlock = curPtBlock->next;
3427 free (curPtBlock);
3428 curPtBlock = tmpPtBlock;
3429 }
3430 free (pETEs);
3431 return(region);
3432 }
3433
3434 // #define __GDK_POLYREG_GENERIC_C__
3435 // #include "gdkaliasdef.c"
3436 #endif //USE_NEW_REGION
3437