source: trunk/src/gui/painting/qregion.cpp@ 769

Last change on this file since 769 was 769, checked in by Dmitry A. Kuminov, 15 years ago

trunk: Merged in qt 4.6.3 sources from branches/vendor/nokia/qt.

File size: 131.9 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
4** All rights reserved.
5** Contact: Nokia Corporation (qt-info@nokia.com)
6**
7** This file is part of the QtGui module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial Usage
11** Licensees holding valid Qt Commercial licenses may use this file in
12** accordance with the Qt Commercial License Agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and Nokia.
15**
16** GNU Lesser General Public License Usage
17** Alternatively, this file may be used under the terms of the GNU Lesser
18** General Public License version 2.1 as published by the Free Software
19** Foundation and appearing in the file LICENSE.LGPL included in the
20** packaging of this file. Please review the following information to
21** ensure the GNU Lesser General Public License version 2.1 requirements
22** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
23**
24** In addition, as a special exception, Nokia gives you certain additional
25** rights. These rights are described in the Nokia Qt LGPL Exception
26** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you have questions regarding the use of this file, please contact
37** Nokia at qt-info@nokia.com.
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42#include "qregion.h"
43#include "qpainterpath.h"
44#include "qpolygon.h"
45#include "qbuffer.h"
46#include "qdatastream.h"
47#include "qvariant.h"
48#include "qvarlengtharray.h"
49
50#include <qdebug.h>
51
52#if defined(Q_OS_UNIX) || defined(Q_WS_WIN)
53#include "qimage.h"
54#include "qbitmap.h"
55#include <stdlib.h>
56#endif
57
58QT_BEGIN_NAMESPACE
59
60/*!
61 \class QRegion
62 \brief The QRegion class specifies a clip region for a painter.
63
64 \ingroup painting
65 \ingroup shared
66
67 QRegion is used with QPainter::setClipRegion() to limit the paint
68 area to what needs to be painted. There is also a QWidget::repaint()
69 function that takes a QRegion parameter. QRegion is the best tool for
70 minimizing the amount of screen area to be updated by a repaint.
71
72 This class is not suitable for constructing shapes for rendering, especially
73 as outlines. Use QPainterPath to create paths and shapes for use with
74 QPainter.
75
76 QRegion is an \l{implicitly shared} class.
77
78 \section1 Creating and Using Regions
79
80 A region can be created from a rectangle, an ellipse, a polygon or
81 a bitmap. Complex regions may be created by combining simple
82 regions using united(), intersected(), subtracted(), or xored() (exclusive
83 or). You can move a region using translate().
84
85 You can test whether a region isEmpty() or if it
86 contains() a QPoint or QRect. The bounding rectangle can be found
87 with boundingRect().
88
89 The function rects() gives a decomposition of the region into
90 rectangles.
91
92 Example of using complex regions:
93 \snippet doc/src/snippets/code/src_gui_painting_qregion.cpp 0
94
95 \section1 Additional License Information
96
97 On Embedded Linux, Windows CE and X11 platforms, parts of this class rely on
98 code obtained under the following licenses:
99
100 \legalese
101 Copyright (c) 1987 X Consortium
102
103 Permission is hereby granted, free of charge, to any person obtaining a copy
104 of this software and associated documentation files (the "Software"), to deal
105 in the Software without restriction, including without limitation the rights
106 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
107 copies of the Software, and to permit persons to whom the Software is
108 furnished to do so, subject to the following conditions:
109
110 The above copyright notice and this permission notice shall be included in
111 all copies or substantial portions of the Software.
112
113 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
114 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
115 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
116 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
117 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
118 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
119
120 Except as contained in this notice, the name of the X Consortium shall not be
121 used in advertising or otherwise to promote the sale, use or other dealings
122 in this Software without prior written authorization from the X Consortium.
123 \endlegalese
124
125 \br
126
127 \legalese
128 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
129
130 All Rights Reserved
131
132 Permission to use, copy, modify, and distribute this software and its
133 documentation for any purpose and without fee is hereby granted,
134 provided that the above copyright notice appear in all copies and that
135 both that copyright notice and this permission notice appear in
136 supporting documentation, and that the name of Digital not be
137 used in advertising or publicity pertaining to distribution of the
138 software without specific, written prior permission.
139
140 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
141 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
142 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
143 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
144 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
145 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
146 SOFTWARE.
147 \endlegalese
148
149 \sa QPainter::setClipRegion(), QPainter::setClipRect(), QPainterPath
150*/
151
152
153/*!
154 \enum QRegion::RegionType
155
156 Specifies the shape of the region to be created.
157
158 \value Rectangle the region covers the entire rectangle.
159 \value Ellipse the region is an ellipse inside the rectangle.
160*/
161
162/*!
163 \fn void QRegion::translate(const QPoint &point)
164
165 \overload
166
167 Translates the region \a{point}\e{.x()} along the x axis and
168 \a{point}\e{.y()} along the y axis, relative to the current
169 position. Positive values move the region to the right and down.
170
171 Translates to the given \a point.
172*/
173
174/*!
175 \fn Handle QRegion::handle() const
176
177 Returns a platform-specific region handle. The \c Handle type is
178 \c HRGN on Windows, \c Region on X11, and \c RgnHandle on Mac OS
179 X. On \l{Qt for Embedded Linux} it is \c {void *}.
180
181 \warning This function is not portable.
182*/
183
184/*****************************************************************************
185 QRegion member functions
186 *****************************************************************************/
187
188/*!
189 \fn QRegion::QRegion()
190
191 Constructs an empty region.
192
193 \sa isEmpty()
194*/
195
196/*!
197 \fn QRegion::QRegion(const QRect &r, RegionType t)
198 \overload
199
200 Create a region based on the rectange \a r with region type \a t.
201
202 If the rectangle is invalid a null region will be created.
203
204 \sa QRegion::RegionType
205*/
206
207/*!
208 \fn QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
209
210 Constructs a polygon region from the point array \a a with the fill rule
211 specified by \a fillRule.
212
213 If \a fillRule is \l{Qt::WindingFill}, the polygon region is defined
214 using the winding algorithm; if it is \l{Qt::OddEvenFill}, the odd-even fill
215 algorithm is used.
216
217 \warning This constructor can be used to create complex regions that will
218 slow down painting when used.
219*/
220
221/*!
222 \fn QRegion::QRegion(const QRegion &r)
223
224 Constructs a new region which is equal to region \a r.
225*/
226
227/*!
228 \fn QRegion::QRegion(const QBitmap &bm)
229
230 Constructs a region from the bitmap \a bm.
231
232 The resulting region consists of the pixels in bitmap \a bm that
233 are Qt::color1, as if each pixel was a 1 by 1 rectangle.
234
235 This constructor may create complex regions that will slow down
236 painting when used. Note that drawing masked pixmaps can be done
237 much faster using QPixmap::setMask().
238*/
239
240/*!
241 Constructs a rectangular or elliptic region.
242
243 If \a t is \c Rectangle, the region is the filled rectangle (\a x,
244 \a y, \a w, \a h). If \a t is \c Ellipse, the region is the filled
245 ellipse with center at (\a x + \a w / 2, \a y + \a h / 2) and size
246 (\a w ,\a h).
247*/
248QRegion::QRegion(int x, int y, int w, int h, RegionType t)
249{
250 QRegion tmp(QRect(x, y, w, h), t);
251 tmp.d->ref.ref();
252 d = tmp.d;
253}
254
255#ifdef QT3_SUPPORT
256/*!
257 Use the constructor tha takes a Qt::FillRule as the second
258 argument instead.
259*/
260QRegion::QRegion(const QPolygon &pa, bool winding)
261{
262 new (this) QRegion(pa, winding ? Qt::WindingFill : Qt::OddEvenFill);
263}
264#endif
265
266/*!
267 \fn QRegion::~QRegion()
268 \internal
269
270 Destroys the region.
271*/
272
273void QRegion::detach()
274{
275 if (d->ref != 1)
276 *this = copy();
277#if defined(Q_WS_X11)
278 else if (d->xrectangles) {
279 free(d->xrectangles);
280 d->xrectangles = 0;
281 }
282#endif
283#if defined(Q_WS_PM)
284 else {
285 // cause a new HRGN to be created when necessary
286 disposeHandle(d->rgn);
287 d->height = 0;
288 }
289#endif
290}
291
292// duplicates in qregion_win.cpp and qregion_wce.cpp
293#define QRGN_SETRECT 1 // region stream commands
294#define QRGN_SETELLIPSE 2 // (these are internal)
295#define QRGN_SETPTARRAY_ALT 3
296#define QRGN_SETPTARRAY_WIND 4
297#define QRGN_TRANSLATE 5
298#define QRGN_OR 6
299#define QRGN_AND 7
300#define QRGN_SUB 8
301#define QRGN_XOR 9
302#define QRGN_RECTS 10
303
304
305#ifndef QT_NO_DATASTREAM
306
307/*
308 Executes region commands in the internal buffer and rebuilds the
309 original region.
310
311 We do this when we read a region from the data stream.
312
313 If \a ver is non-0, uses the format version \a ver on reading the
314 byte array.
315*/
316void QRegion::exec(const QByteArray &buffer, int ver, QDataStream::ByteOrder byteOrder)
317{
318 QByteArray copy = buffer;
319 QDataStream s(&copy, QIODevice::ReadOnly);
320 if (ver)
321 s.setVersion(ver);
322 s.setByteOrder(byteOrder);
323 QRegion rgn;
324#ifndef QT_NO_DEBUG
325 int test_cnt = 0;
326#endif
327 while (!s.atEnd()) {
328 qint32 id;
329 if (s.version() == 1) {
330 int id_int;
331 s >> id_int;
332 id = id_int;
333 } else {
334 s >> id;
335 }
336#ifndef QT_NO_DEBUG
337 if (test_cnt > 0 && id != QRGN_TRANSLATE)
338 qWarning("QRegion::exec: Internal error");
339 test_cnt++;
340#endif
341 if (id == QRGN_SETRECT || id == QRGN_SETELLIPSE) {
342 QRect r;
343 s >> r;
344 rgn = QRegion(r, id == QRGN_SETRECT ? Rectangle : Ellipse);
345 } else if (id == QRGN_SETPTARRAY_ALT || id == QRGN_SETPTARRAY_WIND) {
346 QPolygon a;
347 s >> a;
348 rgn = QRegion(a, id == QRGN_SETPTARRAY_WIND ? Qt::WindingFill : Qt::OddEvenFill);
349 } else if (id == QRGN_TRANSLATE) {
350 QPoint p;
351 s >> p;
352 rgn.translate(p.x(), p.y());
353 } else if (id >= QRGN_OR && id <= QRGN_XOR) {
354 QByteArray bop1, bop2;
355 QRegion r1, r2;
356 s >> bop1;
357 r1.exec(bop1);
358 s >> bop2;
359 r2.exec(bop2);
360
361 switch (id) {
362 case QRGN_OR:
363 rgn = r1.united(r2);
364 break;
365 case QRGN_AND:
366 rgn = r1.intersected(r2);
367 break;
368 case QRGN_SUB:
369 rgn = r1.subtracted(r2);
370 break;
371 case QRGN_XOR:
372 rgn = r1.xored(r2);
373 break;
374 }
375 } else if (id == QRGN_RECTS) {
376 // (This is the only form used in Qt 2.0)
377 quint32 n;
378 s >> n;
379 QRect r;
380 for (int i=0; i<(int)n; i++) {
381 s >> r;
382 rgn = rgn.united(QRegion(r));
383 }
384 }
385 }
386 *this = rgn;
387}
388
389
390/*****************************************************************************
391 QRegion stream functions
392 *****************************************************************************/
393
394/*!
395 \fn QRegion &QRegion::operator=(const QRegion &r)
396
397 Assigns \a r to this region and returns a reference to the region.
398*/
399
400/*!
401 \relates QRegion
402
403 Writes the region \a r to the stream \a s and returns a reference
404 to the stream.
405
406 \sa \link datastreamformat.html Format of the QDataStream operators \endlink
407*/
408
409QDataStream &operator<<(QDataStream &s, const QRegion &r)
410{
411 QVector<QRect> a = r.rects();
412 if (a.isEmpty()) {
413 s << (quint32)0;
414 } else {
415 if (s.version() == 1) {
416 int i;
417 for (i = a.size() - 1; i > 0; --i) {
418 s << (quint32)(12 + i * 24);
419 s << (int)QRGN_OR;
420 }
421 for (i = 0; i < a.size(); ++i) {
422 s << (quint32)(4+8) << (int)QRGN_SETRECT << a[i];
423 }
424 } else {
425 s << (quint32)(4 + 4 + 16 * a.size()); // 16: storage size of QRect
426 s << (qint32)QRGN_RECTS;
427 s << a;
428 }
429 }
430 return s;
431}
432
433/*!
434 \relates QRegion
435
436 Reads a region from the stream \a s into \a r and returns a
437 reference to the stream.
438
439 \sa \link datastreamformat.html Format of the QDataStream operators \endlink
440*/
441
442QDataStream &operator>>(QDataStream &s, QRegion &r)
443{
444 QByteArray b;
445 s >> b;
446 r.exec(b, s.version(), s.byteOrder());
447 return s;
448}
449#endif //QT_NO_DATASTREAM
450
451#ifndef QT_NO_DEBUG_STREAM
452QDebug operator<<(QDebug s, const QRegion &r)
453{
454 QVector<QRect> rects = r.rects();
455 s.nospace() << "QRegion(size=" << rects.size() << "), "
456 << "bounds = " << r.boundingRect() << '\n';
457 for (int i=0; i<rects.size(); ++i)
458 s << "- " << i << rects.at(i) << '\n';
459 return s;
460}
461#endif
462
463
464// These are not inline - they can be implemented better on some platforms
465// (eg. Windows at least provides 3-variable operations). For now, simple.
466
467
468/*!
469 Applies the united() function to this region and \a r. \c r1|r2 is
470 equivalent to \c r1.united(r2).
471
472 \sa united(), operator+()
473*/
474const QRegion QRegion::operator|(const QRegion &r) const
475 { return united(r); }
476
477/*!
478 Applies the united() function to this region and \a r. \c r1+r2 is
479 equivalent to \c r1.united(r2).
480
481 \sa united(), operator|()
482*/
483const QRegion QRegion::operator+(const QRegion &r) const
484 { return united(r); }
485
486/*!
487 \overload
488 \since 4.4
489 */
490const QRegion QRegion::operator+(const QRect &r) const
491 { return united(r); }
492
493/*!
494 Applies the intersected() function to this region and \a r. \c r1&r2
495 is equivalent to \c r1.intersected(r2).
496
497 \sa intersected()
498*/
499const QRegion QRegion::operator&(const QRegion &r) const
500 { return intersected(r); }
501
502/*!
503 \overload
504 \since 4.4
505 */
506const QRegion QRegion::operator&(const QRect &r) const
507{
508 return intersected(r);
509}
510
511/*!
512 Applies the subtracted() function to this region and \a r. \c r1-r2
513 is equivalent to \c r1.subtracted(r2).
514
515 \sa subtracted()
516*/
517const QRegion QRegion::operator-(const QRegion &r) const
518 { return subtracted(r); }
519
520/*!
521 Applies the xored() function to this region and \a r. \c r1^r2 is
522 equivalent to \c r1.xored(r2).
523
524 \sa xored()
525*/
526const QRegion QRegion::operator^(const QRegion &r) const
527 { return xored(r); }
528
529/*!
530 Applies the united() function to this region and \a r and assigns
531 the result to this region. \c r1|=r2 is equivalent to \c
532 {r1 = r1.united(r2)}.
533
534 \sa united()
535*/
536QRegion& QRegion::operator|=(const QRegion &r)
537 { return *this = *this | r; }
538
539/*!
540 \fn QRegion& QRegion::operator+=(const QRect &rect)
541
542 Returns a region that is the union of this region with the specified \a rect.
543
544 \sa united()
545*/
546/*!
547 \fn QRegion& QRegion::operator+=(const QRegion &r)
548
549 Applies the united() function to this region and \a r and assigns
550 the result to this region. \c r1+=r2 is equivalent to \c
551 {r1 = r1.united(r2)}.
552
553 \sa intersected()
554*/
555#if !defined (Q_OS_UNIX) && !defined (Q_WS_WIN) && !defined (Q_WS_PM)
556QRegion& QRegion::operator+=(const QRect &r)
557{
558 return operator+=(QRegion(r));
559}
560#endif
561
562/*!
563 \fn QRegion& QRegion::operator&=(const QRegion &r)
564
565 Applies the intersected() function to this region and \a r and
566 assigns the result to this region. \c r1&=r2 is equivalent to \c
567 r1 = r1.intersected(r2).
568
569 \sa intersected()
570*/
571QRegion& QRegion::operator&=(const QRegion &r)
572 { return *this = *this & r; }
573
574/*!
575 \overload
576 \since 4.4
577 */
578#if defined (Q_OS_UNIX) || defined (Q_WS_WIN) || defined (Q_WS_PM)
579QRegion& QRegion::operator&=(const QRect &r)
580{
581 return *this = *this & r;
582}
583#else
584QRegion& QRegion::operator&=(const QRect &r)
585{
586 return *this &= (QRegion(r));
587}
588#endif
589
590/*!
591 \fn QRegion& QRegion::operator-=(const QRegion &r)
592
593 Applies the subtracted() function to this region and \a r and
594 assigns the result to this region. \c r1-=r2 is equivalent to \c
595 {r1 = r1.subtracted(r2)}.
596
597 \sa subtracted()
598*/
599QRegion& QRegion::operator-=(const QRegion &r)
600 { return *this = *this - r; }
601
602/*!
603 Applies the xored() function to this region and \a r and
604 assigns the result to this region. \c r1^=r2 is equivalent to \c
605 {r1 = r1.xored(r2)}.
606
607 \sa xored()
608*/
609QRegion& QRegion::operator^=(const QRegion &r)
610 { return *this = *this ^ r; }
611
612/*!
613 \fn bool QRegion::operator!=(const QRegion &other) const
614
615 Returns true if this region is different from the \a other region;
616 otherwise returns false.
617*/
618
619/*!
620 Returns the region as a QVariant
621*/
622QRegion::operator QVariant() const
623{
624 return QVariant(QVariant::Region, this);
625}
626
627/*!
628 \fn bool QRegion::operator==(const QRegion &r) const
629
630 Returns true if the region is equal to \a r; otherwise returns
631 false.
632*/
633
634/*!
635 \fn bool QRegion::isNull() const
636
637 Use isEmpty() instead.
638*/
639
640
641/*!
642 \fn void QRegion::translate(int dx, int dy)
643
644 Translates (moves) the region \a dx along the X axis and \a dy
645 along the Y axis.
646*/
647
648/*!
649 \fn QRegion QRegion::translated(const QPoint &p) const
650 \overload
651 \since 4.1
652
653 Returns a copy of the regtion that is translated \a{p}\e{.x()}
654 along the x axis and \a{p}\e{.y()} along the y axis, relative to
655 the current position. Positive values move the rectangle to the
656 right and down.
657
658 \sa translate()
659*/
660
661/*!
662 \since 4.1
663
664 Returns a copy of the region that is translated \a dx along the
665 x axis and \a dy along the y axis, relative to the current
666 position. Positive values move the region to the right and
667 down.
668
669 \sa translate()
670*/
671
672QRegion
673QRegion::translated(int dx, int dy) const
674{
675 QRegion ret(*this);
676 ret.translate(dx, dy);
677 return ret;
678}
679
680
681inline bool rect_intersects(const QRect &r1, const QRect &r2)
682{
683 return (r1.right() >= r2.left() && r1.left() <= r2.right() &&
684 r1.bottom() >= r2.top() && r1.top() <= r2.bottom());
685}
686
687/*!
688 \since 4.2
689
690 Returns true if this region intersects with \a region, otherwise
691 returns false.
692*/
693bool QRegion::intersects(const QRegion &region) const
694{
695 if (isEmpty() || region.isEmpty())
696 return false;
697
698 if (!rect_intersects(boundingRect(), region.boundingRect()))
699 return false;
700 if (rectCount() == 1 && region.rectCount() == 1)
701 return true;
702
703 const QVector<QRect> myRects = rects();
704 const QVector<QRect> otherRects = region.rects();
705
706 for (QVector<QRect>::const_iterator i1 = myRects.constBegin(); i1 < myRects.constEnd(); ++i1)
707 for (QVector<QRect>::const_iterator i2 = otherRects.constBegin(); i2 < otherRects.constEnd(); ++i2)
708 if (rect_intersects(*i1, *i2))
709 return true;
710 return false;
711}
712
713/*!
714 \since 4.2
715
716 Returns true if this region intersects with \a rect, otherwise
717 returns false.
718*/
719bool QRegion::intersects(const QRect &rect) const
720{
721 if (isEmpty() || rect.isNull())
722 return false;
723
724 const QRect r = rect.normalized();
725 if (!rect_intersects(boundingRect(), r))
726 return false;
727 if (rectCount() == 1)
728 return true;
729
730 const QVector<QRect> myRects = rects();
731 for (QVector<QRect>::const_iterator it = myRects.constBegin(); it < myRects.constEnd(); ++it)
732 if (rect_intersects(r, *it))
733 return true;
734 return false;
735}
736
737#if !defined (Q_OS_UNIX) && !defined (Q_WS_WIN) && !defined (Q_WS_PM)
738/*!
739 \overload
740 \since 4.4
741*/
742QRegion QRegion::intersect(const QRect &r) const
743{
744 return intersect(QRegion(r));
745}
746#endif
747
748/*!
749 \obsolete
750 \fn int QRegion::numRects() const
751 \since 4.4
752
753 Returns the number of rectangles that will be returned in rects().
754*/
755
756/*!
757 \fn int QRegion::rectCount() const
758 \since 4.6
759
760 Returns the number of rectangles that will be returned in rects().
761*/
762
763/*!
764 \fn bool QRegion::isEmpty() const
765
766 Returns true if the region is empty; otherwise returns false. An
767 empty region is a region that contains no points.
768
769 Example:
770 \snippet doc/src/snippets/code/src_gui_painting_qregion_unix.cpp 0
771*/
772
773/*!
774 \fn bool QRegion::contains(const QPoint &p) const
775
776 Returns true if the region contains the point \a p; otherwise
777 returns false.
778*/
779
780/*!
781 \fn bool QRegion::contains(const QRect &r) const
782 \overload
783
784 Returns true if the region overlaps the rectangle \a r; otherwise
785 returns false.
786*/
787
788/*!
789 \fn QRegion QRegion::unite(const QRegion &r) const
790 \obsolete
791
792 Use united(\a r) instead.
793*/
794
795/*!
796 \fn QRegion QRegion::unite(const QRect &rect) const
797 \since 4.4
798 \obsolete
799
800 Use united(\a rect) instead.
801*/
802
803/*!
804 \fn QRegion QRegion::united(const QRect &rect) const
805 \since 4.4
806
807 Returns a region which is the union of this region and the given \a rect.
808
809 \sa intersected(), subtracted(), xored()
810*/
811
812/*!
813 \fn QRegion QRegion::united(const QRegion &r) const
814 \since 4.2
815
816 Returns a region which is the union of this region and \a r.
817
818 \img runion.png Region Union
819
820 The figure shows the union of two elliptical regions.
821
822 \sa intersected(), subtracted(), xored()
823*/
824
825/*!
826 \fn QRegion QRegion::intersect(const QRegion &r) const
827 \obsolete
828
829 Use intersected(\a r) instead.
830*/
831
832/*!
833 \fn QRegion QRegion::intersect(const QRect &rect) const
834 \since 4.4
835 \obsolete
836
837 Use intersected(\a rect) instead.
838*/
839
840/*!
841 \fn QRegion QRegion::intersected(const QRect &rect) const
842 \since 4.4
843
844 Returns a region which is the intersection of this region and the given \a rect.
845
846 \sa subtracted(), united(), xored()
847*/
848
849/*!
850 \fn QRegion QRegion::intersected(const QRegion &r) const
851 \since 4.2
852
853 Returns a region which is the intersection of this region and \a r.
854
855 \img rintersect.png Region Intersection
856
857 The figure shows the intersection of two elliptical regions.
858
859 \sa subtracted(), united(), xored()
860*/
861
862/*!
863 \fn QRegion QRegion::subtract(const QRegion &r) const
864 \obsolete
865
866 Use subtracted(\a r) instead.
867*/
868
869/*!
870 \fn QRegion QRegion::subtracted(const QRegion &r) const
871 \since 4.2
872
873 Returns a region which is \a r subtracted from this region.
874
875 \img rsubtract.png Region Subtraction
876
877 The figure shows the result when the ellipse on the right is
878 subtracted from the ellipse on the left (\c {left - right}).
879
880 \sa intersected(), united(), xored()
881*/
882
883/*!
884 \fn QRegion QRegion::eor(const QRegion &r) const
885 \obsolete
886
887 Use xored(\a r) instead.
888*/
889
890/*!
891 \fn QRegion QRegion::xored(const QRegion &r) const
892 \since 4.2
893
894 Returns a region which is the exclusive or (XOR) of this region
895 and \a r.
896
897 \img rxor.png Region XORed
898
899 The figure shows the exclusive or of two elliptical regions.
900
901 \sa intersected(), united(), subtracted()
902*/
903
904/*!
905 \fn QRect QRegion::boundingRect() const
906
907 Returns the bounding rectangle of this region. An empty region
908 gives a rectangle that is QRect::isNull().
909*/
910
911/*!
912 \fn QVector<QRect> QRegion::rects() const
913
914 Returns an array of non-overlapping rectangles that make up the
915 region.
916
917 The union of all the rectangles is equal to the original region.
918*/
919
920/*!
921 \fn void QRegion::setRects(const QRect *rects, int number)
922
923 Sets the region using the array of rectangles specified by \a rects and
924 \a number.
925 The rectangles \e must be optimally Y-X sorted and follow these restrictions:
926
927 \list
928 \o The rectangles must not intersect.
929 \o All rectangles with a given top coordinate must have the same height.
930 \o No two rectangles may abut horizontally (they should be combined
931 into a single wider rectangle in that case).
932 \o The rectangles must be sorted in ascending order, with Y as the major
933 sort key and X as the minor sort key.
934 \endlist
935 \omit
936 Only some platforms have these restrictions (Qt for Embedded Linux, X11 and Mac OS X).
937 \endomit
938*/
939
940namespace {
941
942struct Segment
943{
944 Segment() {}
945 Segment(const QPoint &p)
946 : added(false)
947 , point(p)
948 {
949 }
950
951 int left() const
952 {
953 return qMin(point.x(), next->point.x());
954 }
955
956 int right() const
957 {
958 return qMax(point.x(), next->point.x());
959 }
960
961 bool overlaps(const Segment &other) const
962 {
963 return left() < other.right() && other.left() < right();
964 }
965
966 void connect(Segment &other)
967 {
968 next = &other;
969 other.prev = this;
970
971 horizontal = (point.y() == other.point.y());
972 }
973
974 void merge(Segment &other)
975 {
976 if (right() <= other.right()) {
977 QPoint p = other.point;
978 Segment *oprev = other.prev;
979
980 other.point = point;
981 other.prev = prev;
982 prev->next = &other;
983
984 point = p;
985 prev = oprev;
986 oprev->next = this;
987 } else {
988 Segment *onext = other.next;
989 other.next = next;
990 next->prev = &other;
991
992 next = onext;
993 next->prev = this;
994 }
995 }
996
997 int horizontal : 1;
998 int added : 1;
999
1000 QPoint point;
1001 Segment *prev;
1002 Segment *next;
1003};
1004
1005void mergeSegments(Segment *a, int na, Segment *b, int nb)
1006{
1007 int i = 0;
1008 int j = 0;
1009
1010 while (i != na && j != nb) {
1011 Segment &sa = a[i];
1012 Segment &sb = b[j];
1013 const int ra = sa.right();
1014 const int rb = sb.right();
1015 if (sa.overlaps(sb))
1016 sa.merge(sb);
1017 i += (rb >= ra);
1018 j += (ra >= rb);
1019 }
1020}
1021
1022void addSegmentsToPath(Segment *segment, QPainterPath &path)
1023{
1024 Segment *current = segment;
1025 path.moveTo(current->point);
1026
1027 current->added = true;
1028
1029 Segment *last = current;
1030 current = current->next;
1031 while (current != segment) {
1032 if (current->horizontal != last->horizontal)
1033 path.lineTo(current->point);
1034 current->added = true;
1035 last = current;
1036 current = current->next;
1037 }
1038}
1039
1040}
1041
1042Q_AUTOTEST_EXPORT QPainterPath qt_regionToPath(const QRegion &region)
1043{
1044 QPainterPath result;
1045 if (region.rectCount() == 1) {
1046 result.addRect(region.boundingRect());
1047 return result;
1048 }
1049
1050 const QVector<QRect> rects = region.rects();
1051
1052 QVarLengthArray<Segment> segments;
1053 segments.resize(4 * rects.size());
1054
1055 const QRect *rect = rects.constData();
1056 const QRect *end = rect + rects.size();
1057
1058 int lastRowSegmentCount = 0;
1059 Segment *lastRowSegments = 0;
1060
1061 int lastSegment = 0;
1062 int lastY = 0;
1063 while (rect != end) {
1064 const int y = rect[0].y();
1065 int count = 0;
1066 while (&rect[count] != end && rect[count].y() == y)
1067 ++count;
1068
1069 for (int i = 0; i < count; ++i) {
1070 int offset = lastSegment + i;
1071 segments[offset] = Segment(rect[i].topLeft());
1072 segments[offset += count] = Segment(rect[i].topRight() + QPoint(1, 0));
1073 segments[offset += count] = Segment(rect[i].bottomRight() + QPoint(1, 1));
1074 segments[offset += count] = Segment(rect[i].bottomLeft() + QPoint(0, 1));
1075
1076 offset = lastSegment + i;
1077 for (int j = 0; j < 4; ++j)
1078 segments[offset + j * count].connect(segments[offset + ((j + 1) % 4) * count]);
1079 }
1080
1081 if (lastRowSegments && lastY == y)
1082 mergeSegments(lastRowSegments, lastRowSegmentCount, &segments[lastSegment], count);
1083
1084 lastRowSegments = &segments[lastSegment + 2 * count];
1085 lastRowSegmentCount = count;
1086 lastSegment += 4 * count;
1087 lastY = y + rect[0].height();
1088 rect += count;
1089 }
1090
1091 for (int i = 0; i < lastSegment; ++i) {
1092 Segment *segment = &segments[i];
1093 if (!segment->added)
1094 addSegmentsToPath(segment, result);
1095 }
1096
1097 return result;
1098}
1099
1100#if defined(Q_OS_UNIX) || defined(Q_WS_WIN) || defined(Q_WS_PM)
1101
1102//#define QT_REGION_DEBUG
1103/*
1104 * clip region
1105 */
1106
1107struct QRegionPrivate {
1108 int numRects;
1109 QVector<QRect> rects;
1110 QRect extents;
1111 QRect innerRect;
1112 int innerArea;
1113
1114 inline QRegionPrivate() : numRects(0), innerArea(-1) {}
1115 inline QRegionPrivate(const QRect &r) {
1116 numRects = 1;
1117 extents = r;
1118 innerRect = r;
1119 innerArea = r.width() * r.height();
1120 }
1121
1122 inline QRegionPrivate(const QRegionPrivate &r) {
1123 rects = r.rects;
1124 numRects = r.numRects;
1125 extents = r.extents;
1126 innerRect = r.innerRect;
1127 innerArea = r.innerArea;
1128 }
1129
1130 inline QRegionPrivate &operator=(const QRegionPrivate &r) {
1131 rects = r.rects;
1132 numRects = r.numRects;
1133 extents = r.extents;
1134 innerRect = r.innerRect;
1135 innerArea = r.innerArea;
1136 return *this;
1137 }
1138
1139 void intersect(const QRect &r);
1140
1141 /*
1142 * Returns true if r is guaranteed to be fully contained in this region.
1143 * A false return value does not guarantee the opposite.
1144 */
1145 inline bool contains(const QRegionPrivate &r) const {
1146 return contains(r.extents);
1147 }
1148
1149 inline bool contains(const QRect &r2) const {
1150 const QRect &r1 = innerRect;
1151 return r2.left() >= r1.left() && r2.right() <= r1.right()
1152 && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1153 }
1154
1155 /*
1156 * Returns true if this region is guaranteed to be fully contained in r.
1157 */
1158 inline bool within(const QRect &r1) const {
1159 const QRect &r2 = extents;
1160 return r2.left() >= r1.left() && r2.right() <= r1.right()
1161 && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1162 }
1163
1164 inline void updateInnerRect(const QRect &rect) {
1165 const int area = rect.width() * rect.height();
1166 if (area > innerArea) {
1167 innerArea = area;
1168 innerRect = rect;
1169 }
1170 }
1171
1172 inline void vectorize() {
1173 if (numRects == 1) {
1174 if (!rects.size())
1175 rects.resize(1);
1176 rects[0] = extents;
1177 }
1178 }
1179
1180 inline void append(const QRect *r);
1181 void append(const QRegionPrivate *r);
1182 void prepend(const QRect *r);
1183 void prepend(const QRegionPrivate *r);
1184 inline bool canAppend(const QRect *r) const;
1185 inline bool canAppend(const QRegionPrivate *r) const;
1186 inline bool canPrepend(const QRect *r) const;
1187 inline bool canPrepend(const QRegionPrivate *r) const;
1188
1189 inline bool mergeFromRight(QRect *left, const QRect *right);
1190 inline bool mergeFromLeft(QRect *left, const QRect *right);
1191 inline bool mergeFromBelow(QRect *top, const QRect *bottom,
1192 const QRect *nextToTop,
1193 const QRect *nextToBottom);
1194 inline bool mergeFromAbove(QRect *bottom, const QRect *top,
1195 const QRect *nextToBottom,
1196 const QRect *nextToTop);
1197
1198#ifdef QT_REGION_DEBUG
1199 void selfTest() const;
1200#endif
1201};
1202
1203static inline bool isEmptyHelper(const QRegionPrivate *preg)
1204{
1205 return !preg || preg->numRects == 0;
1206}
1207
1208static inline bool canMergeFromRight(const QRect *left, const QRect *right)
1209{
1210 return (right->top() == left->top()
1211 && right->bottom() == left->bottom()
1212 && right->left() <= (left->right() + 1));
1213}
1214
1215static inline bool canMergeFromLeft(const QRect *right, const QRect *left)
1216{
1217 return canMergeFromRight(left, right);
1218}
1219
1220bool QRegionPrivate::mergeFromRight(QRect *left, const QRect *right)
1221{
1222 if (canMergeFromRight(left, right)) {
1223 left->setRight(right->right());
1224 updateInnerRect(*left);
1225 return true;
1226 }
1227 return false;
1228}
1229
1230bool QRegionPrivate::mergeFromLeft(QRect *right, const QRect *left)
1231{
1232 if (canMergeFromLeft(right, left)) {
1233 right->setLeft(left->left());
1234 updateInnerRect(*right);
1235 return true;
1236 }
1237 return false;
1238}
1239
1240static inline bool canMergeFromBelow(const QRect *top, const QRect *bottom,
1241 const QRect *nextToTop,
1242 const QRect *nextToBottom)
1243{
1244 if (nextToTop && nextToTop->y() == top->y())
1245 return false;
1246 if (nextToBottom && nextToBottom->y() == bottom->y())
1247 return false;
1248
1249 return ((top->bottom() >= (bottom->top() - 1))
1250 && top->left() == bottom->left()
1251 && top->right() == bottom->right());
1252}
1253
1254bool QRegionPrivate::mergeFromBelow(QRect *top, const QRect *bottom,
1255 const QRect *nextToTop,
1256 const QRect *nextToBottom)
1257{
1258 if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1259 top->setBottom(bottom->bottom());
1260 updateInnerRect(*top);
1261 return true;
1262 }
1263 return false;
1264}
1265
1266bool QRegionPrivate::mergeFromAbove(QRect *bottom, const QRect *top,
1267 const QRect *nextToBottom,
1268 const QRect *nextToTop)
1269{
1270 if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1271 bottom->setTop(top->top());
1272 updateInnerRect(*bottom);
1273 return true;
1274 }
1275 return false;
1276}
1277
1278static inline QRect qt_rect_intersect_normalized(const QRect &r1,
1279 const QRect &r2)
1280{
1281 QRect r;
1282 r.setLeft(qMax(r1.left(), r2.left()));
1283 r.setRight(qMin(r1.right(), r2.right()));
1284 r.setTop(qMax(r1.top(), r2.top()));
1285 r.setBottom(qMin(r1.bottom(), r2.bottom()));
1286 return r;
1287}
1288
1289void QRegionPrivate::intersect(const QRect &rect)
1290{
1291 Q_ASSERT(extents.intersects(rect));
1292 Q_ASSERT(numRects > 1);
1293
1294#ifdef QT_REGION_DEBUG
1295 selfTest();
1296#endif
1297
1298 const QRect r = rect.normalized();
1299 extents = QRect();
1300 innerRect = QRect();
1301 innerArea = -1;
1302
1303 QRect *dest = rects.data();
1304 const QRect *src = dest;
1305 int n = numRects;
1306 numRects = 0;
1307 while (n--) {
1308 *dest = qt_rect_intersect_normalized(*src++, r);
1309 if (dest->isEmpty())
1310 continue;
1311
1312 if (numRects == 0) {
1313 extents = *dest;
1314 } else {
1315 extents.setLeft(qMin(extents.left(), dest->left()));
1316 // hw: extents.top() will never change after initialization
1317 //extents.setTop(qMin(extents.top(), dest->top()));
1318 extents.setRight(qMax(extents.right(), dest->right()));
1319 extents.setBottom(qMax(extents.bottom(), dest->bottom()));
1320
1321 const QRect *nextToLast = (numRects > 1 ? dest - 2 : 0);
1322
1323 // mergeFromBelow inlined and optimized
1324 if (canMergeFromBelow(dest - 1, dest, nextToLast, 0)) {
1325 if (!n || src->y() != dest->y() || src->left() > r.right()) {
1326 QRect *prev = dest - 1;
1327 prev->setBottom(dest->bottom());
1328 updateInnerRect(*prev);
1329 continue;
1330 }
1331 }
1332 }
1333 updateInnerRect(*dest);
1334 ++dest;
1335 ++numRects;
1336 }
1337#ifdef QT_REGION_DEBUG
1338 selfTest();
1339#endif
1340}
1341
1342void QRegionPrivate::append(const QRect *r)
1343{
1344 Q_ASSERT(!r->isEmpty());
1345
1346 QRect *myLast = (numRects == 1 ? &extents : rects.data() + (numRects - 1));
1347 if (mergeFromRight(myLast, r)) {
1348 if (numRects > 1) {
1349 const QRect *nextToTop = (numRects > 2 ? myLast - 2 : 0);
1350 if (mergeFromBelow(myLast - 1, myLast, nextToTop, 0))
1351 --numRects;
1352 }
1353 } else if (mergeFromBelow(myLast, r, (numRects > 1 ? myLast - 1 : 0), 0)) {
1354 // nothing
1355 } else {
1356 vectorize();
1357 ++numRects;
1358 updateInnerRect(*r);
1359 if (rects.size() < numRects)
1360 rects.resize(numRects);
1361 rects[numRects - 1] = *r;
1362 }
1363 extents.setCoords(qMin(extents.left(), r->left()),
1364 qMin(extents.top(), r->top()),
1365 qMax(extents.right(), r->right()),
1366 qMax(extents.bottom(), r->bottom()));
1367
1368#ifdef QT_REGION_DEBUG
1369 selfTest();
1370#endif
1371}
1372
1373void QRegionPrivate::append(const QRegionPrivate *r)
1374{
1375 Q_ASSERT(!isEmptyHelper(r));
1376
1377 if (r->numRects == 1) {
1378 append(&r->extents);
1379 return;
1380 }
1381
1382 vectorize();
1383
1384 QRect *destRect = rects.data() + numRects;
1385 const QRect *srcRect = r->rects.constData();
1386 int numAppend = r->numRects;
1387
1388 // try merging
1389 {
1390 const QRect *rFirst = srcRect;
1391 QRect *myLast = destRect - 1;
1392 const QRect *nextToLast = (numRects > 1 ? myLast - 1 : 0);
1393 if (mergeFromRight(myLast, rFirst)) {
1394 ++srcRect;
1395 --numAppend;
1396 const QRect *rNextToFirst = (numAppend > 1 ? rFirst + 2 : 0);
1397 if (mergeFromBelow(myLast, rFirst + 1, nextToLast, rNextToFirst)) {
1398 ++srcRect;
1399 --numAppend;
1400 }
1401 if (numRects > 1) {
1402 nextToLast = (numRects > 2 ? myLast - 2 : 0);
1403 rNextToFirst = (numAppend > 0 ? srcRect : 0);
1404 if (mergeFromBelow(myLast - 1, myLast, nextToLast, rNextToFirst)) {
1405 --destRect;
1406 --numRects;
1407 }
1408 }
1409 } else if (mergeFromBelow(myLast, rFirst, nextToLast, rFirst + 1)) {
1410 ++srcRect;
1411 --numAppend;
1412 }
1413 }
1414
1415 // append rectangles
1416 if (numAppend > 0) {
1417 const int newNumRects = numRects + numAppend;
1418 if (newNumRects > rects.size()) {
1419 rects.resize(newNumRects);
1420 destRect = rects.data() + numRects;
1421 }
1422 memcpy(destRect, srcRect, numAppend * sizeof(QRect));
1423
1424 numRects = newNumRects;
1425 }
1426
1427 // update inner rectangle
1428 if (innerArea < r->innerArea) {
1429 innerArea = r->innerArea;
1430 innerRect = r->innerRect;
1431 }
1432
1433 // update extents
1434 destRect = &extents;
1435 srcRect = &r->extents;
1436 extents.setCoords(qMin(destRect->left(), srcRect->left()),
1437 qMin(destRect->top(), srcRect->top()),
1438 qMax(destRect->right(), srcRect->right()),
1439 qMax(destRect->bottom(), srcRect->bottom()));
1440
1441#ifdef QT_REGION_DEBUG
1442 selfTest();
1443#endif
1444}
1445
1446void QRegionPrivate::prepend(const QRegionPrivate *r)
1447{
1448 Q_ASSERT(!isEmptyHelper(r));
1449
1450 if (r->numRects == 1) {
1451 prepend(&r->extents);
1452 return;
1453 }
1454
1455 vectorize();
1456
1457 int numPrepend = r->numRects;
1458 int numSkip = 0;
1459
1460 // try merging
1461 {
1462 QRect *myFirst = rects.data();
1463 const QRect *nextToFirst = (numRects > 1 ? myFirst + 1 : 0);
1464 const QRect *rLast = r->rects.constData() + r->numRects - 1;
1465 const QRect *rNextToLast = (r->numRects > 1 ? rLast - 1 : 0);
1466 if (mergeFromLeft(myFirst, rLast)) {
1467 --numPrepend;
1468 --rLast;
1469 rNextToLast = (numPrepend > 1 ? rLast - 1 : 0);
1470 if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1471 --numPrepend;
1472 --rLast;
1473 }
1474 if (numRects > 1) {
1475 nextToFirst = (numRects > 2? myFirst + 2 : 0);
1476 rNextToLast = (numPrepend > 0 ? rLast : 0);
1477 if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, rNextToLast)) {
1478 --numRects;
1479 ++numSkip;
1480 }
1481 }
1482 } else if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1483 --numPrepend;
1484 }
1485 }
1486
1487 if (numPrepend > 0) {
1488 const int newNumRects = numRects + numPrepend;
1489 if (newNumRects > rects.size())
1490 rects.resize(newNumRects);
1491
1492 // move existing rectangles
1493 memmove(rects.data() + numPrepend, rects.constData() + numSkip,
1494 numRects * sizeof(QRect));
1495
1496 // prepend new rectangles
1497 memcpy(rects.data(), r->rects.constData(), numPrepend * sizeof(QRect));
1498
1499 numRects = newNumRects;
1500 }
1501
1502 // update inner rectangle
1503 if (innerArea < r->innerArea) {
1504 innerArea = r->innerArea;
1505 innerRect = r->innerRect;
1506 }
1507
1508 // update extents
1509 extents.setCoords(qMin(extents.left(), r->extents.left()),
1510 qMin(extents.top(), r->extents.top()),
1511 qMax(extents.right(), r->extents.right()),
1512 qMax(extents.bottom(), r->extents.bottom()));
1513
1514#ifdef QT_REGION_DEBUG
1515 selfTest();
1516#endif
1517}
1518
1519void QRegionPrivate::prepend(const QRect *r)
1520{
1521 Q_ASSERT(!r->isEmpty());
1522
1523 QRect *myFirst = (numRects == 1 ? &extents : rects.data());
1524 if (mergeFromLeft(myFirst, r)) {
1525 if (numRects > 1) {
1526 const QRect *nextToFirst = (numRects > 2 ? myFirst + 2 : 0);
1527 if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, 0)) {
1528 --numRects;
1529 memmove(rects.data(), rects.constData() + 1,
1530 numRects * sizeof(QRect));
1531 }
1532 }
1533 } else if (mergeFromAbove(myFirst, r, (numRects > 1 ? myFirst + 1 : 0), 0)) {
1534 // nothing
1535 } else {
1536 vectorize();
1537 ++numRects;
1538 updateInnerRect(*r);
1539 rects.prepend(*r);
1540 }
1541 extents.setCoords(qMin(extents.left(), r->left()),
1542 qMin(extents.top(), r->top()),
1543 qMax(extents.right(), r->right()),
1544 qMax(extents.bottom(), r->bottom()));
1545
1546#ifdef QT_REGION_DEBUG
1547 selfTest();
1548#endif
1549}
1550
1551bool QRegionPrivate::canAppend(const QRect *r) const
1552{
1553 Q_ASSERT(!r->isEmpty());
1554
1555 const QRect *myLast = (numRects == 1) ? &extents : (rects.constData() + (numRects - 1));
1556 if (r->top() > myLast->bottom())
1557 return true;
1558 if (r->top() == myLast->top()
1559 && r->height() == myLast->height()
1560 && r->left() > myLast->right())
1561 {
1562 return true;
1563 }
1564
1565 return false;
1566}
1567
1568bool QRegionPrivate::canAppend(const QRegionPrivate *r) const
1569{
1570 return canAppend(r->numRects == 1 ? &r->extents : r->rects.constData());
1571}
1572
1573bool QRegionPrivate::canPrepend(const QRect *r) const
1574{
1575 Q_ASSERT(!r->isEmpty());
1576
1577 const QRect *myFirst = (numRects == 1) ? &extents : rects.constData();
1578 if (r->bottom() < myFirst->top()) // not overlapping
1579 return true;
1580 if (r->top() == myFirst->top()
1581 && r->height() == myFirst->height()
1582 && r->right() < myFirst->left())
1583 {
1584 return true;
1585 }
1586
1587 return false;
1588}
1589
1590bool QRegionPrivate::canPrepend(const QRegionPrivate *r) const
1591{
1592 return canPrepend(r->numRects == 1 ? &r->extents : r->rects.constData() + r->numRects - 1);
1593}
1594
1595#ifdef QT_REGION_DEBUG
1596void QRegionPrivate::selfTest() const
1597{
1598 if (numRects == 0) {
1599 Q_ASSERT(extents.isEmpty());
1600 Q_ASSERT(innerRect.isEmpty());
1601 return;
1602 }
1603
1604 Q_ASSERT(innerArea == (innerRect.width() * innerRect.height()));
1605
1606 if (numRects == 1) {
1607 Q_ASSERT(innerRect == extents);
1608 Q_ASSERT(!innerRect.isEmpty());
1609 return;
1610 }
1611
1612 for (int i = 0; i < numRects; ++i) {
1613 const QRect r = rects.at(i);
1614 if ((r.width() * r.height()) > innerArea)
1615 qDebug() << "selfTest(): innerRect" << innerRect << '<' << r;
1616 }
1617
1618 QRect r = rects.first();
1619 for (int i = 1; i < numRects; ++i) {
1620 const QRect r2 = rects.at(i);
1621 Q_ASSERT(!r2.isEmpty());
1622 if (r2.y() == r.y()) {
1623 Q_ASSERT(r.bottom() == r2.bottom());
1624 Q_ASSERT(r.right() < (r2.left() + 1));
1625 } else {
1626 Q_ASSERT(r2.y() >= r.bottom());
1627 }
1628 r = r2;
1629 }
1630}
1631#endif // QT_REGION_DEBUG
1632
1633#if defined(Q_WS_X11)
1634QT_BEGIN_INCLUDE_NAMESPACE
1635# include "qregion_x11.cpp"
1636QT_END_INCLUDE_NAMESPACE
1637#elif defined(Q_WS_MAC)
1638QT_BEGIN_INCLUDE_NAMESPACE
1639# include "qregion_mac.cpp"
1640QT_END_INCLUDE_NAMESPACE
1641#elif defined(Q_WS_WIN)
1642QT_BEGIN_INCLUDE_NAMESPACE
1643# include "qregion_win.cpp"
1644QT_END_INCLUDE_NAMESPACE
1645#elif defined(Q_WS_PM)
1646QT_BEGIN_INCLUDE_NAMESPACE
1647# include "qregion_pm.cpp"
1648QT_END_INCLUDE_NAMESPACE
1649#elif defined(Q_WS_QWS)
1650static QRegionPrivate qrp;
1651QRegion::QRegionData QRegion::shared_empty = {Q_BASIC_ATOMIC_INITIALIZER(1), &qrp};
1652#endif
1653
1654typedef void (*OverlapFunc)(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1655 register const QRect *r2, const QRect *r2End, register int y1, register int y2);
1656typedef void (*NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
1657 register int y1, register int y2);
1658
1659static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2);
1660static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest);
1661static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
1662 OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
1663 NonOverlapFunc nonOverlap2Func);
1664
1665#define RectangleOut 0
1666#define RectangleIn 1
1667#define RectanglePart 2
1668#define EvenOddRule 0
1669#define WindingRule 1
1670
1671// START OF region.h extract
1672/* $XConsortium: region.h,v 11.14 94/04/17 20:22:20 rws Exp $ */
1673/************************************************************************
1674
1675Copyright (c) 1987 X Consortium
1676
1677Permission is hereby granted, free of charge, to any person obtaining a copy
1678of this software and associated documentation files (the "Software"), to deal
1679in the Software without restriction, including without limitation the rights
1680to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1681copies of the Software, and to permit persons to whom the Software is
1682furnished to do so, subject to the following conditions:
1683
1684The above copyright notice and this permission notice shall be included in
1685all copies or substantial portions of the Software.
1686
1687THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1688IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1689FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1690X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1691AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1692CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1693
1694Except as contained in this notice, the name of the X Consortium shall not be
1695used in advertising or otherwise to promote the sale, use or other dealings
1696in this Software without prior written authorization from the X Consortium.
1697
1698
1699Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1700
1701 All Rights Reserved
1702
1703Permission to use, copy, modify, and distribute this software and its
1704documentation for any purpose and without fee is hereby granted,
1705provided that the above copyright notice appear in all copies and that
1706both that copyright notice and this permission notice appear in
1707supporting documentation, and that the name of Digital not be
1708used in advertising or publicity pertaining to distribution of the
1709software without specific, written prior permission.
1710
1711DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1712ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1713DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1714ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1715WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1716ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1717SOFTWARE.
1718
1719************************************************************************/
1720
1721#ifndef _XREGION_H
1722#define _XREGION_H
1723
1724QT_BEGIN_INCLUDE_NAMESPACE
1725#include <limits.h>
1726QT_END_INCLUDE_NAMESPACE
1727
1728/* 1 if two BOXs overlap.
1729 * 0 if two BOXs do not overlap.
1730 * Remember, x2 and y2 are not in the region
1731 */
1732#define EXTENTCHECK(r1, r2) \
1733 ((r1)->right() >= (r2)->left() && \
1734 (r1)->left() <= (r2)->right() && \
1735 (r1)->bottom() >= (r2)->top() && \
1736 (r1)->top() <= (r2)->bottom())
1737
1738/*
1739 * update region extents
1740 */
1741#define EXTENTS(r,idRect){\
1742 if((r)->left() < (idRect)->extents.left())\
1743 (idRect)->extents.setLeft((r)->left());\
1744 if((r)->top() < (idRect)->extents.top())\
1745 (idRect)->extents.setTop((r)->top());\
1746 if((r)->right() > (idRect)->extents.right())\
1747 (idRect)->extents.setRight((r)->right());\
1748 if((r)->bottom() > (idRect)->extents.bottom())\
1749 (idRect)->extents.setBottom((r)->bottom());\
1750 }
1751
1752/*
1753 * Check to see if there is enough memory in the present region.
1754 */
1755#define MEMCHECK(dest, rect, firstrect){\
1756 if ((dest).numRects >= ((dest).rects.size()-1)){\
1757 firstrect.resize(firstrect.size() * 2); \
1758 (rect) = (firstrect).data() + (dest).numRects;\
1759 }\
1760 }
1761
1762
1763/*
1764 * number of points to buffer before sending them off
1765 * to scanlines(): Must be an even number
1766 */
1767#define NUMPTSTOBUFFER 200
1768
1769/*
1770 * used to allocate buffers for points and link
1771 * the buffers together
1772 */
1773typedef struct _POINTBLOCK {
1774 int data[NUMPTSTOBUFFER * sizeof(QPoint)];
1775 QPoint *pts;
1776 struct _POINTBLOCK *next;
1777} POINTBLOCK;
1778
1779#endif
1780// END OF region.h extract
1781
1782// START OF Region.c extract
1783/* $XConsortium: Region.c /main/30 1996/10/22 14:21:24 kaleb $ */
1784/************************************************************************
1785
1786Copyright (c) 1987, 1988 X Consortium
1787
1788Permission is hereby granted, free of charge, to any person obtaining a copy
1789of this software and associated documentation files (the "Software"), to deal
1790in the Software without restriction, including without limitation the rights
1791to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1792copies of the Software, and to permit persons to whom the Software is
1793furnished to do so, subject to the following conditions:
1794
1795The above copyright notice and this permission notice shall be included in
1796all copies or substantial portions of the Software.
1797
1798THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1799IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1800FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1801X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1802AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1803CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1804
1805Except as contained in this notice, the name of the X Consortium shall not be
1806used in advertising or otherwise to promote the sale, use or other dealings
1807in this Software without prior written authorization from the X Consortium.
1808
1809
1810Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
1811
1812 All Rights Reserved
1813
1814Permission to use, copy, modify, and distribute this software and its
1815documentation for any purpose and without fee is hereby granted,
1816provided that the above copyright notice appear in all copies and that
1817both that copyright notice and this permission notice appear in
1818supporting documentation, and that the name of Digital not be
1819used in advertising or publicity pertaining to distribution of the
1820software without specific, written prior permission.
1821
1822DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1823ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1824DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1825ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1826WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1827ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1828SOFTWARE.
1829
1830************************************************************************/
1831/*
1832 * The functions in this file implement the Region abstraction, similar to one
1833 * used in the X11 sample server. A Region is simply an area, as the name
1834 * implies, and is implemented as a "y-x-banded" array of rectangles. To
1835 * explain: Each Region is made up of a certain number of rectangles sorted
1836 * by y coordinate first, and then by x coordinate.
1837 *
1838 * Furthermore, the rectangles are banded such that every rectangle with a
1839 * given upper-left y coordinate (y1) will have the same lower-right y
1840 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
1841 * will span the entire vertical distance of the band. This means that some
1842 * areas that could be merged into a taller rectangle will be represented as
1843 * several shorter rectangles to account for shorter rectangles to its left
1844 * or right but within its "vertical scope".
1845 *
1846 * An added constraint on the rectangles is that they must cover as much
1847 * horizontal area as possible. E.g. no two rectangles in a band are allowed
1848 * to touch.
1849 *
1850 * Whenever possible, bands will be merged together to cover a greater vertical
1851 * distance (and thus reduce the number of rectangles). Two bands can be merged
1852 * only if the bottom of one touches the top of the other and they have
1853 * rectangles in the same places (of the same width, of course). This maintains
1854 * the y-x-banding that's so nice to have...
1855 */
1856/* $XFree86: xc/lib/X11/Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */
1857
1858static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source,
1859 QRegionPrivate &dest)
1860{
1861 if (rect->isEmpty())
1862 return;
1863
1864 Q_ASSERT(EqualRegion(source, &dest));
1865
1866 if (dest.numRects == 0) {
1867 dest = QRegionPrivate(*rect);
1868 } else if (dest.canAppend(rect)) {
1869 dest.append(rect);
1870 } else {
1871 QRegionPrivate p(*rect);
1872 UnionRegion(&p, source, dest);
1873 }
1874}
1875
1876/*-
1877 *-----------------------------------------------------------------------
1878 * miSetExtents --
1879 * Reset the extents and innerRect of a region to what they should be.
1880 * Called by miSubtract and miIntersect b/c they can't figure it out
1881 * along the way or do so easily, as miUnion can.
1882 *
1883 * Results:
1884 * None.
1885 *
1886 * Side Effects:
1887 * The region's 'extents' and 'innerRect' structure is overwritten.
1888 *
1889 *-----------------------------------------------------------------------
1890 */
1891static void miSetExtents(QRegionPrivate &dest)
1892{
1893 register const QRect *pBox,
1894 *pBoxEnd;
1895 register QRect *pExtents;
1896
1897 dest.innerRect.setCoords(0, 0, -1, -1);
1898 dest.innerArea = -1;
1899 if (dest.numRects == 0) {
1900 dest.extents.setCoords(0, 0, -1, -1);
1901 return;
1902 }
1903
1904 pExtents = &dest.extents;
1905 if (dest.rects.isEmpty())
1906 pBox = &dest.extents;
1907 else
1908 pBox = dest.rects.constData();
1909 pBoxEnd = pBox + dest.numRects - 1;
1910
1911 /*
1912 * Since pBox is the first rectangle in the region, it must have the
1913 * smallest y1 and since pBoxEnd is the last rectangle in the region,
1914 * it must have the largest y2, because of banding. Initialize x1 and
1915 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
1916 * to...
1917 */
1918 pExtents->setLeft(pBox->left());
1919 pExtents->setTop(pBox->top());
1920 pExtents->setRight(pBoxEnd->right());
1921 pExtents->setBottom(pBoxEnd->bottom());
1922
1923 Q_ASSERT(pExtents->top() <= pExtents->bottom());
1924 while (pBox <= pBoxEnd) {
1925 if (pBox->left() < pExtents->left())
1926 pExtents->setLeft(pBox->left());
1927 if (pBox->right() > pExtents->right())
1928 pExtents->setRight(pBox->right());
1929 dest.updateInnerRect(*pBox);
1930 ++pBox;
1931 }
1932 Q_ASSERT(pExtents->left() <= pExtents->right());
1933}
1934
1935/* TranslateRegion(pRegion, x, y)
1936 translates in place
1937 added by raymond
1938*/
1939
1940static void OffsetRegion(register QRegionPrivate &region, register int x, register int y)
1941{
1942 if (region.rects.size()) {
1943 register QRect *pbox = region.rects.data();
1944 register int nbox = region.numRects;
1945
1946 while (nbox--) {
1947 pbox->translate(x, y);
1948 ++pbox;
1949 }
1950 }
1951 region.extents.translate(x, y);
1952 region.innerRect.translate(x, y);
1953}
1954
1955/*======================================================================
1956 * Region Intersection
1957 *====================================================================*/
1958/*-
1959 *-----------------------------------------------------------------------
1960 * miIntersectO --
1961 * Handle an overlapping band for miIntersect.
1962 *
1963 * Results:
1964 * None.
1965 *
1966 * Side Effects:
1967 * Rectangles may be added to the region.
1968 *
1969 *-----------------------------------------------------------------------
1970 */
1971static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1972 register const QRect *r2, const QRect *r2End, int y1, int y2)
1973{
1974 register int x1;
1975 register int x2;
1976 register QRect *pNextRect;
1977
1978 pNextRect = dest.rects.data() + dest.numRects;
1979
1980 while (r1 != r1End && r2 != r2End) {
1981 x1 = qMax(r1->left(), r2->left());
1982 x2 = qMin(r1->right(), r2->right());
1983
1984 /*
1985 * If there's any overlap between the two rectangles, add that
1986 * overlap to the new region.
1987 * There's no need to check for subsumption because the only way
1988 * such a need could arise is if some region has two rectangles
1989 * right next to each other. Since that should never happen...
1990 */
1991 if (x1 <= x2) {
1992 Q_ASSERT(y1 <= y2);
1993 MEMCHECK(dest, pNextRect, dest.rects)
1994 pNextRect->setCoords(x1, y1, x2, y2);
1995 ++dest.numRects;
1996 ++pNextRect;
1997 }
1998
1999 /*
2000 * Need to advance the pointers. Shift the one that extends
2001 * to the right the least, since the other still has a chance to
2002 * overlap with that region's next rectangle, if you see what I mean.
2003 */
2004 if (r1->right() < r2->right()) {
2005 ++r1;
2006 } else if (r2->right() < r1->right()) {
2007 ++r2;
2008 } else {
2009 ++r1;
2010 ++r2;
2011 }
2012 }
2013}
2014
2015/*======================================================================
2016 * Generic Region Operator
2017 *====================================================================*/
2018
2019/*-
2020 *-----------------------------------------------------------------------
2021 * miCoalesce --
2022 * Attempt to merge the boxes in the current band with those in the
2023 * previous one. Used only by miRegionOp.
2024 *
2025 * Results:
2026 * The new index for the previous band.
2027 *
2028 * Side Effects:
2029 * If coalescing takes place:
2030 * - rectangles in the previous band will have their y2 fields
2031 * altered.
2032 * - dest.numRects will be decreased.
2033 *
2034 *-----------------------------------------------------------------------
2035 */
2036static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
2037{
2038 register QRect *pPrevBox; /* Current box in previous band */
2039 register QRect *pCurBox; /* Current box in current band */
2040 register QRect *pRegEnd; /* End of region */
2041 int curNumRects; /* Number of rectangles in current band */
2042 int prevNumRects; /* Number of rectangles in previous band */
2043 int bandY1; /* Y1 coordinate for current band */
2044 QRect *rData = dest.rects.data();
2045
2046 pRegEnd = rData + dest.numRects;
2047
2048 pPrevBox = rData + prevStart;
2049 prevNumRects = curStart - prevStart;
2050
2051 /*
2052 * Figure out how many rectangles are in the current band. Have to do
2053 * this because multiple bands could have been added in miRegionOp
2054 * at the end when one region has been exhausted.
2055 */
2056 pCurBox = rData + curStart;
2057 bandY1 = pCurBox->top();
2058 for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
2059 ++pCurBox;
2060 }
2061
2062 if (pCurBox != pRegEnd) {
2063 /*
2064 * If more than one band was added, we have to find the start
2065 * of the last band added so the next coalescing job can start
2066 * at the right place... (given when multiple bands are added,
2067 * this may be pointless -- see above).
2068 */
2069 --pRegEnd;
2070 while ((pRegEnd - 1)->top() == pRegEnd->top())
2071 --pRegEnd;
2072 curStart = pRegEnd - rData;
2073 pRegEnd = rData + dest.numRects;
2074 }
2075
2076 if (curNumRects == prevNumRects && curNumRects != 0) {
2077 pCurBox -= curNumRects;
2078 /*
2079 * The bands may only be coalesced if the bottom of the previous
2080 * matches the top scanline of the current.
2081 */
2082 if (pPrevBox->bottom() == pCurBox->top() - 1) {
2083 /*
2084 * Make sure the bands have boxes in the same places. This
2085 * assumes that boxes have been added in such a way that they
2086 * cover the most area possible. I.e. two boxes in a band must
2087 * have some horizontal space between them.
2088 */
2089 do {
2090 if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
2091 // The bands don't line up so they can't be coalesced.
2092 return curStart;
2093 }
2094 ++pPrevBox;
2095 ++pCurBox;
2096 --prevNumRects;
2097 } while (prevNumRects != 0);
2098
2099 dest.numRects -= curNumRects;
2100 pCurBox -= curNumRects;
2101 pPrevBox -= curNumRects;
2102
2103 /*
2104 * The bands may be merged, so set the bottom y of each box
2105 * in the previous band to that of the corresponding box in
2106 * the current band.
2107 */
2108 do {
2109 pPrevBox->setBottom(pCurBox->bottom());
2110 dest.updateInnerRect(*pPrevBox);
2111 ++pPrevBox;
2112 ++pCurBox;
2113 curNumRects -= 1;
2114 } while (curNumRects != 0);
2115
2116 /*
2117 * If only one band was added to the region, we have to backup
2118 * curStart to the start of the previous band.
2119 *
2120 * If more than one band was added to the region, copy the
2121 * other bands down. The assumption here is that the other bands
2122 * came from the same region as the current one and no further
2123 * coalescing can be done on them since it's all been done
2124 * already... curStart is already in the right place.
2125 */
2126 if (pCurBox == pRegEnd) {
2127 curStart = prevStart;
2128 } else {
2129 do {
2130 *pPrevBox++ = *pCurBox++;
2131 dest.updateInnerRect(*pPrevBox);
2132 } while (pCurBox != pRegEnd);
2133 }
2134 }
2135 }
2136 return curStart;
2137}
2138
2139/*-
2140 *-----------------------------------------------------------------------
2141 * miRegionOp --
2142 * Apply an operation to two regions. Called by miUnion, miInverse,
2143 * miSubtract, miIntersect...
2144 *
2145 * Results:
2146 * None.
2147 *
2148 * Side Effects:
2149 * The new region is overwritten.
2150 *
2151 * Notes:
2152 * The idea behind this function is to view the two regions as sets.
2153 * Together they cover a rectangle of area that this function divides
2154 * into horizontal bands where points are covered only by one region
2155 * or by both. For the first case, the nonOverlapFunc is called with
2156 * each the band and the band's upper and lower extents. For the
2157 * second, the overlapFunc is called to process the entire band. It
2158 * is responsible for clipping the rectangles in the band, though
2159 * this function provides the boundaries.
2160 * At the end of each band, the new region is coalesced, if possible,
2161 * to reduce the number of rectangles in the region.
2162 *
2163 *-----------------------------------------------------------------------
2164 */
2165static void miRegionOp(register QRegionPrivate &dest,
2166 const QRegionPrivate *reg1, const QRegionPrivate *reg2,
2167 OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
2168 NonOverlapFunc nonOverlap2Func)
2169{
2170 register const QRect *r1; // Pointer into first region
2171 register const QRect *r2; // Pointer into 2d region
2172 const QRect *r1End; // End of 1st region
2173 const QRect *r2End; // End of 2d region
2174 register int ybot; // Bottom of intersection
2175 register int ytop; // Top of intersection
2176 int prevBand; // Index of start of previous band in dest
2177 int curBand; // Index of start of current band in dest
2178 register const QRect *r1BandEnd; // End of current band in r1
2179 register const QRect *r2BandEnd; // End of current band in r2
2180 int top; // Top of non-overlapping band
2181 int bot; // Bottom of non-overlapping band
2182
2183 /*
2184 * Initialization:
2185 * set r1, r2, r1End and r2End appropriately, preserve the important
2186 * parts of the destination region until the end in case it's one of
2187 * the two source regions, then mark the "new" region empty, allocating
2188 * another array of rectangles for it to use.
2189 */
2190 if (reg1->numRects == 1)
2191 r1 = &reg1->extents;
2192 else
2193 r1 = reg1->rects.constData();
2194 if (reg2->numRects == 1)
2195 r2 = &reg2->extents;
2196 else
2197 r2 = reg2->rects.constData();
2198
2199 r1End = r1 + reg1->numRects;
2200 r2End = r2 + reg2->numRects;
2201
2202 dest.vectorize();
2203
2204 QVector<QRect> oldRects = dest.rects;
2205
2206 dest.numRects = 0;
2207
2208 /*
2209 * Allocate a reasonable number of rectangles for the new region. The idea
2210 * is to allocate enough so the individual functions don't need to
2211 * reallocate and copy the array, which is time consuming, yet we don't
2212 * have to worry about using too much memory. I hope to be able to
2213 * nuke the realloc() at the end of this function eventually.
2214 */
2215 dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);
2216
2217 /*
2218 * Initialize ybot and ytop.
2219 * In the upcoming loop, ybot and ytop serve different functions depending
2220 * on whether the band being handled is an overlapping or non-overlapping
2221 * band.
2222 * In the case of a non-overlapping band (only one of the regions
2223 * has points in the band), ybot is the bottom of the most recent
2224 * intersection and thus clips the top of the rectangles in that band.
2225 * ytop is the top of the next intersection between the two regions and
2226 * serves to clip the bottom of the rectangles in the current band.
2227 * For an overlapping band (where the two regions intersect), ytop clips
2228 * the top of the rectangles of both regions and ybot clips the bottoms.
2229 */
2230 if (reg1->extents.top() < reg2->extents.top())
2231 ybot = reg1->extents.top() - 1;
2232 else
2233 ybot = reg2->extents.top() - 1;
2234
2235 /*
2236 * prevBand serves to mark the start of the previous band so rectangles
2237 * can be coalesced into larger rectangles. qv. miCoalesce, above.
2238 * In the beginning, there is no previous band, so prevBand == curBand
2239 * (curBand is set later on, of course, but the first band will always
2240 * start at index 0). prevBand and curBand must be indices because of
2241 * the possible expansion, and resultant moving, of the new region's
2242 * array of rectangles.
2243 */
2244 prevBand = 0;
2245
2246 do {
2247 curBand = dest.numRects;
2248
2249 /*
2250 * This algorithm proceeds one source-band (as opposed to a
2251 * destination band, which is determined by where the two regions
2252 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
2253 * rectangle after the last one in the current band for their
2254 * respective regions.
2255 */
2256 r1BandEnd = r1;
2257 while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
2258 ++r1BandEnd;
2259
2260 r2BandEnd = r2;
2261 while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
2262 ++r2BandEnd;
2263
2264 /*
2265 * First handle the band that doesn't intersect, if any.
2266 *
2267 * Note that attention is restricted to one band in the
2268 * non-intersecting region at once, so if a region has n
2269 * bands between the current position and the next place it overlaps
2270 * the other, this entire loop will be passed through n times.
2271 */
2272 if (r1->top() < r2->top()) {
2273 top = qMax(r1->top(), ybot + 1);
2274 bot = qMin(r1->bottom(), r2->top() - 1);
2275
2276 if (nonOverlap1Func != 0 && bot >= top)
2277 (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
2278 ytop = r2->top();
2279 } else if (r2->top() < r1->top()) {
2280 top = qMax(r2->top(), ybot + 1);
2281 bot = qMin(r2->bottom(), r1->top() - 1);
2282
2283 if (nonOverlap2Func != 0 && bot >= top)
2284 (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
2285 ytop = r1->top();
2286 } else {
2287 ytop = r1->top();
2288 }
2289
2290 /*
2291 * If any rectangles got added to the region, try and coalesce them
2292 * with rectangles from the previous band. Note we could just do
2293 * this test in miCoalesce, but some machines incur a not
2294 * inconsiderable cost for function calls, so...
2295 */
2296 if (dest.numRects != curBand)
2297 prevBand = miCoalesce(dest, prevBand, curBand);
2298
2299 /*
2300 * Now see if we've hit an intersecting band. The two bands only
2301 * intersect if ybot >= ytop
2302 */
2303 ybot = qMin(r1->bottom(), r2->bottom());
2304 curBand = dest.numRects;
2305 if (ybot >= ytop)
2306 (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
2307
2308 if (dest.numRects != curBand)
2309 prevBand = miCoalesce(dest, prevBand, curBand);
2310
2311 /*
2312 * If we've finished with a band (y2 == ybot) we skip forward
2313 * in the region to the next band.
2314 */
2315 if (r1->bottom() == ybot)
2316 r1 = r1BandEnd;
2317 if (r2->bottom() == ybot)
2318 r2 = r2BandEnd;
2319 } while (r1 != r1End && r2 != r2End);
2320
2321 /*
2322 * Deal with whichever region still has rectangles left.
2323 */
2324 curBand = dest.numRects;
2325 if (r1 != r1End) {
2326 if (nonOverlap1Func != 0) {
2327 do {
2328 r1BandEnd = r1;
2329 while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
2330 ++r1BandEnd;
2331 (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
2332 r1 = r1BandEnd;
2333 } while (r1 != r1End);
2334 }
2335 } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
2336 do {
2337 r2BandEnd = r2;
2338 while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
2339 ++r2BandEnd;
2340 (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
2341 r2 = r2BandEnd;
2342 } while (r2 != r2End);
2343 }
2344
2345 if (dest.numRects != curBand)
2346 (void)miCoalesce(dest, prevBand, curBand);
2347
2348 /*
2349 * A bit of cleanup. To keep regions from growing without bound,
2350 * we shrink the array of rectangles to match the new number of
2351 * rectangles in the region.
2352 *
2353 * Only do this stuff if the number of rectangles allocated is more than
2354 * twice the number of rectangles in the region (a simple optimization).
2355 */
2356 if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
2357 dest.rects.resize(dest.numRects);
2358}
2359
2360/*======================================================================
2361 * Region Union
2362 *====================================================================*/
2363
2364/*-
2365 *-----------------------------------------------------------------------
2366 * miUnionNonO --
2367 * Handle a non-overlapping band for the union operation. Just
2368 * Adds the rectangles into the region. Doesn't have to check for
2369 * subsumption or anything.
2370 *
2371 * Results:
2372 * None.
2373 *
2374 * Side Effects:
2375 * dest.numRects is incremented and the final rectangles overwritten
2376 * with the rectangles we're passed.
2377 *
2378 *-----------------------------------------------------------------------
2379 */
2380
2381static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
2382 register int y1, register int y2)
2383{
2384 register QRect *pNextRect;
2385
2386 pNextRect = dest.rects.data() + dest.numRects;
2387
2388 Q_ASSERT(y1 <= y2);
2389
2390 while (r != rEnd) {
2391 Q_ASSERT(r->left() <= r->right());
2392 MEMCHECK(dest, pNextRect, dest.rects)
2393 pNextRect->setCoords(r->left(), y1, r->right(), y2);
2394 dest.numRects++;
2395 ++pNextRect;
2396 ++r;
2397 }
2398}
2399
2400
2401/*-
2402 *-----------------------------------------------------------------------
2403 * miUnionO --
2404 * Handle an overlapping band for the union operation. Picks the
2405 * left-most rectangle each time and merges it into the region.
2406 *
2407 * Results:
2408 * None.
2409 *
2410 * Side Effects:
2411 * Rectangles are overwritten in dest.rects and dest.numRects will
2412 * be changed.
2413 *
2414 *-----------------------------------------------------------------------
2415 */
2416
2417static void miUnionO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2418 register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2419{
2420 register QRect *pNextRect;
2421
2422 pNextRect = dest.rects.data() + dest.numRects;
2423
2424#define MERGERECT(r) \
2425 if ((dest.numRects != 0) && \
2426 (pNextRect[-1].top() == y1) && \
2427 (pNextRect[-1].bottom() == y2) && \
2428 (pNextRect[-1].right() >= r->left()-1)) { \
2429 if (pNextRect[-1].right() < r->right()) { \
2430 pNextRect[-1].setRight(r->right()); \
2431 dest.updateInnerRect(pNextRect[-1]); \
2432 Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
2433 } \
2434 } else { \
2435 MEMCHECK(dest, pNextRect, dest.rects) \
2436 pNextRect->setCoords(r->left(), y1, r->right(), y2); \
2437 dest.updateInnerRect(*pNextRect); \
2438 dest.numRects++; \
2439 pNextRect++; \
2440 } \
2441 r++;
2442
2443 Q_ASSERT(y1 <= y2);
2444 while (r1 != r1End && r2 != r2End) {
2445 if (r1->left() < r2->left()) {
2446 MERGERECT(r1)
2447 } else {
2448 MERGERECT(r2)
2449 }
2450 }
2451
2452 if (r1 != r1End) {
2453 do {
2454 MERGERECT(r1)
2455 } while (r1 != r1End);
2456 } else {
2457 while (r2 != r2End) {
2458 MERGERECT(r2)
2459 }
2460 }
2461}
2462
2463static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
2464{
2465 Q_ASSERT(!isEmptyHelper(reg1) && !isEmptyHelper(reg2));
2466 Q_ASSERT(!reg1->contains(*reg2));
2467 Q_ASSERT(!reg2->contains(*reg1));
2468 Q_ASSERT(!EqualRegion(reg1, reg2));
2469 Q_ASSERT(!reg1->canAppend(reg2));
2470 Q_ASSERT(!reg2->canAppend(reg1));
2471
2472 if (reg1->innerArea > reg2->innerArea) {
2473 dest.innerArea = reg1->innerArea;
2474 dest.innerRect = reg1->innerRect;
2475 } else {
2476 dest.innerArea = reg2->innerArea;
2477 dest.innerRect = reg2->innerRect;
2478 }
2479 miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
2480
2481 dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
2482 qMin(reg1->extents.top(), reg2->extents.top()),
2483 qMax(reg1->extents.right(), reg2->extents.right()),
2484 qMax(reg1->extents.bottom(), reg2->extents.bottom()));
2485}
2486
2487/*======================================================================
2488 * Region Subtraction
2489 *====================================================================*/
2490
2491/*-
2492 *-----------------------------------------------------------------------
2493 * miSubtractNonO --
2494 * Deal with non-overlapping band for subtraction. Any parts from
2495 * region 2 we discard. Anything from region 1 we add to the region.
2496 *
2497 * Results:
2498 * None.
2499 *
2500 * Side Effects:
2501 * dest may be affected.
2502 *
2503 *-----------------------------------------------------------------------
2504 */
2505
2506static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r,
2507 const QRect *rEnd, register int y1, register int y2)
2508{
2509 register QRect *pNextRect;
2510
2511 pNextRect = dest.rects.data() + dest.numRects;
2512
2513 Q_ASSERT(y1<=y2);
2514
2515 while (r != rEnd) {
2516 Q_ASSERT(r->left() <= r->right());
2517 MEMCHECK(dest, pNextRect, dest.rects)
2518 pNextRect->setCoords(r->left(), y1, r->right(), y2);
2519 ++dest.numRects;
2520 ++pNextRect;
2521 ++r;
2522 }
2523}
2524
2525/*-
2526 *-----------------------------------------------------------------------
2527 * miSubtractO --
2528 * Overlapping band subtraction. x1 is the left-most point not yet
2529 * checked.
2530 *
2531 * Results:
2532 * None.
2533 *
2534 * Side Effects:
2535 * dest may have rectangles added to it.
2536 *
2537 *-----------------------------------------------------------------------
2538 */
2539
2540static void miSubtractO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2541 register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2542{
2543 register QRect *pNextRect;
2544 register int x1;
2545
2546 x1 = r1->left();
2547
2548 Q_ASSERT(y1 <= y2);
2549 pNextRect = dest.rects.data() + dest.numRects;
2550
2551 while (r1 != r1End && r2 != r2End) {
2552 if (r2->right() < x1) {
2553 /*
2554 * Subtrahend missed the boat: go to next subtrahend.
2555 */
2556 ++r2;
2557 } else if (r2->left() <= x1) {
2558 /*
2559 * Subtrahend precedes minuend: nuke left edge of minuend.
2560 */
2561 x1 = r2->right() + 1;
2562 if (x1 > r1->right()) {
2563 /*
2564 * Minuend completely covered: advance to next minuend and
2565 * reset left fence to edge of new minuend.
2566 */
2567 ++r1;
2568 if (r1 != r1End)
2569 x1 = r1->left();
2570 } else {
2571 // Subtrahend now used up since it doesn't extend beyond minuend
2572 ++r2;
2573 }
2574 } else if (r2->left() <= r1->right()) {
2575 /*
2576 * Left part of subtrahend covers part of minuend: add uncovered
2577 * part of minuend to region and skip to next subtrahend.
2578 */
2579 Q_ASSERT(x1 < r2->left());
2580 MEMCHECK(dest, pNextRect, dest.rects)
2581 pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
2582 ++dest.numRects;
2583 ++pNextRect;
2584
2585 x1 = r2->right() + 1;
2586 if (x1 > r1->right()) {
2587 /*
2588 * Minuend used up: advance to new...
2589 */
2590 ++r1;
2591 if (r1 != r1End)
2592 x1 = r1->left();
2593 } else {
2594 // Subtrahend used up
2595 ++r2;
2596 }
2597 } else {
2598 /*
2599 * Minuend used up: add any remaining piece before advancing.
2600 */
2601 if (r1->right() >= x1) {
2602 MEMCHECK(dest, pNextRect, dest.rects)
2603 pNextRect->setCoords(x1, y1, r1->right(), y2);
2604 ++dest.numRects;
2605 ++pNextRect;
2606 }
2607 ++r1;
2608 if (r1 != r1End)
2609 x1 = r1->left();
2610 }
2611 }
2612
2613 /*
2614 * Add remaining minuend rectangles to region.
2615 */
2616 while (r1 != r1End) {
2617 Q_ASSERT(x1 <= r1->right());
2618 MEMCHECK(dest, pNextRect, dest.rects)
2619 pNextRect->setCoords(x1, y1, r1->right(), y2);
2620 ++dest.numRects;
2621 ++pNextRect;
2622
2623 ++r1;
2624 if (r1 != r1End)
2625 x1 = r1->left();
2626 }
2627}
2628
2629/*-
2630 *-----------------------------------------------------------------------
2631 * miSubtract --
2632 * Subtract regS from regM and leave the result in regD.
2633 * S stands for subtrahend, M for minuend and D for difference.
2634 *
2635 * Side Effects:
2636 * regD is overwritten.
2637 *
2638 *-----------------------------------------------------------------------
2639 */
2640
2641static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS,
2642 register QRegionPrivate &dest)
2643{
2644 Q_ASSERT(!isEmptyHelper(regM));
2645 Q_ASSERT(!isEmptyHelper(regS));
2646 Q_ASSERT(EXTENTCHECK(&regM->extents, &regS->extents));
2647 Q_ASSERT(!regS->contains(*regM));
2648 Q_ASSERT(!EqualRegion(regM, regS));
2649
2650 miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);
2651
2652 /*
2653 * Can't alter dest's extents before we call miRegionOp because
2654 * it might be one of the source regions and miRegionOp depends
2655 * on the extents of those regions being the unaltered. Besides, this
2656 * way there's no checking against rectangles that will be nuked
2657 * due to coalescing, so we have to examine fewer rectangles.
2658 */
2659 miSetExtents(dest);
2660}
2661
2662static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
2663{
2664 Q_ASSERT(!isEmptyHelper(sra) && !isEmptyHelper(srb));
2665 Q_ASSERT(EXTENTCHECK(&sra->extents, &srb->extents));
2666 Q_ASSERT(!EqualRegion(sra, srb));
2667
2668 QRegionPrivate tra, trb;
2669
2670 if (!srb->contains(*sra))
2671 SubtractRegion(sra, srb, tra);
2672 if (!sra->contains(*srb))
2673 SubtractRegion(srb, sra, trb);
2674
2675 Q_ASSERT(isEmptyHelper(&trb) || !tra.contains(trb));
2676 Q_ASSERT(isEmptyHelper(&tra) || !trb.contains(tra));
2677
2678 if (isEmptyHelper(&tra)) {
2679 dest = trb;
2680 } else if (isEmptyHelper(&trb)) {
2681 dest = tra;
2682 } else if (tra.canAppend(&trb)) {
2683 dest = tra;
2684 dest.append(&trb);
2685 } else if (trb.canAppend(&tra)) {
2686 dest = trb;
2687 dest.append(&tra);
2688 } else {
2689 UnionRegion(&tra, &trb, dest);
2690 }
2691}
2692
2693/*
2694 * Check to see if two regions are equal
2695 */
2696static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
2697{
2698 if (r1->numRects != r2->numRects) {
2699 return false;
2700 } else if (r1->numRects == 0) {
2701 return true;
2702 } else if (r1->extents != r2->extents) {
2703 return false;
2704 } else if (r1->numRects == 1 && r2->numRects == 1) {
2705 return true; // equality tested in previous if-statement
2706 } else {
2707 const QRect *rr1 = (r1->numRects == 1) ? &r1->extents : r1->rects.constData();
2708 const QRect *rr2 = (r2->numRects == 1) ? &r2->extents : r2->rects.constData();
2709 for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
2710 if (*rr1 != *rr2)
2711 return false;
2712 }
2713 }
2714
2715 return true;
2716}
2717
2718static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
2719{
2720 int i;
2721
2722 if (isEmptyHelper(pRegion))
2723 return false;
2724 if (!pRegion->extents.contains(x, y))
2725 return false;
2726 if (pRegion->numRects == 1)
2727 return pRegion->extents.contains(x, y);
2728 if (pRegion->innerRect.contains(x, y))
2729 return true;
2730 for (i = 0; i < pRegion->numRects; ++i) {
2731 if (pRegion->rects[i].contains(x, y))
2732 return true;
2733 }
2734 return false;
2735}
2736
2737static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
2738{
2739 register const QRect *pbox;
2740 register const QRect *pboxEnd;
2741 QRect rect(rx, ry, rwidth, rheight);
2742 register QRect *prect = &rect;
2743 int partIn, partOut;
2744
2745 if (!region || region->numRects == 0 || !EXTENTCHECK(&region->extents, prect))
2746 return RectangleOut;
2747
2748 partOut = false;
2749 partIn = false;
2750
2751 /* can stop when both partOut and partIn are true, or we reach prect->y2 */
2752 pbox = (region->numRects == 1) ? &region->extents : region->rects.constData();
2753 pboxEnd = pbox + region->numRects;
2754 for (; pbox < pboxEnd; ++pbox) {
2755 if (pbox->bottom() < ry)
2756 continue;
2757
2758 if (pbox->top() > ry) {
2759 partOut = true;
2760 if (partIn || pbox->top() > prect->bottom())
2761 break;
2762 ry = pbox->top();
2763 }
2764
2765 if (pbox->right() < rx)
2766 continue; /* not far enough over yet */
2767
2768 if (pbox->left() > rx) {
2769 partOut = true; /* missed part of rectangle to left */
2770 if (partIn)
2771 break;
2772 }
2773
2774 if (pbox->left() <= prect->right()) {
2775 partIn = true; /* definitely overlap */
2776 if (partOut)
2777 break;
2778 }
2779
2780 if (pbox->right() >= prect->right()) {
2781 ry = pbox->bottom() + 1; /* finished with this band */
2782 if (ry > prect->bottom())
2783 break;
2784 rx = prect->left(); /* reset x out to left again */
2785 } else {
2786 /*
2787 * Because boxes in a band are maximal width, if the first box
2788 * to overlap the rectangle doesn't completely cover it in that
2789 * band, the rectangle must be partially out, since some of it
2790 * will be uncovered in that band. partIn will have been set true
2791 * by now...
2792 */
2793 break;
2794 }
2795 }
2796 return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
2797}
2798// END OF Region.c extract
2799// START OF poly.h extract
2800/* $XConsortium: poly.h,v 1.4 94/04/17 20:22:19 rws Exp $ */
2801/************************************************************************
2802
2803Copyright (c) 1987 X Consortium
2804
2805Permission is hereby granted, free of charge, to any person obtaining a copy
2806of this software and associated documentation files (the "Software"), to deal
2807in the Software without restriction, including without limitation the rights
2808to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2809copies of the Software, and to permit persons to whom the Software is
2810furnished to do so, subject to the following conditions:
2811
2812The above copyright notice and this permission notice shall be included in
2813all copies or substantial portions of the Software.
2814
2815THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2816IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2817FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2818X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
2819AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
2820CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
2821
2822Except as contained in this notice, the name of the X Consortium shall not be
2823used in advertising or otherwise to promote the sale, use or other dealings
2824in this Software without prior written authorization from the X Consortium.
2825
2826
2827Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
2828
2829 All Rights Reserved
2830
2831Permission to use, copy, modify, and distribute this software and its
2832documentation for any purpose and without fee is hereby granted,
2833provided that the above copyright notice appear in all copies and that
2834both that copyright notice and this permission notice appear in
2835supporting documentation, and that the name of Digital not be
2836used in advertising or publicity pertaining to distribution of the
2837software without specific, written prior permission.
2838
2839DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
2840ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
2841DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
2842ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
2843WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
2844ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
2845SOFTWARE.
2846
2847************************************************************************/
2848
2849/*
2850 * This file contains a few macros to help track
2851 * the edge of a filled object. The object is assumed
2852 * to be filled in scanline order, and thus the
2853 * algorithm used is an extension of Bresenham's line
2854 * drawing algorithm which assumes that y is always the
2855 * major axis.
2856 * Since these pieces of code are the same for any filled shape,
2857 * it is more convenient to gather the library in one
2858 * place, but since these pieces of code are also in
2859 * the inner loops of output primitives, procedure call
2860 * overhead is out of the question.
2861 * See the author for a derivation if needed.
2862 */
2863
2864
2865/*
2866 * In scan converting polygons, we want to choose those pixels
2867 * which are inside the polygon. Thus, we add .5 to the starting
2868 * x coordinate for both left and right edges. Now we choose the
2869 * first pixel which is inside the pgon for the left edge and the
2870 * first pixel which is outside the pgon for the right edge.
2871 * Draw the left pixel, but not the right.
2872 *
2873 * How to add .5 to the starting x coordinate:
2874 * If the edge is moving to the right, then subtract dy from the
2875 * error term from the general form of the algorithm.
2876 * If the edge is moving to the left, then add dy to the error term.
2877 *
2878 * The reason for the difference between edges moving to the left
2879 * and edges moving to the right is simple: If an edge is moving
2880 * to the right, then we want the algorithm to flip immediately.
2881 * If it is moving to the left, then we don't want it to flip until
2882 * we traverse an entire pixel.
2883 */
2884#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
2885 int dx; /* local storage */ \
2886\
2887 /* \
2888 * if the edge is horizontal, then it is ignored \
2889 * and assumed not to be processed. Otherwise, do this stuff. \
2890 */ \
2891 if ((dy) != 0) { \
2892 xStart = (x1); \
2893 dx = (x2) - xStart; \
2894 if (dx < 0) { \
2895 m = dx / (dy); \
2896 m1 = m - 1; \
2897 incr1 = -2 * dx + 2 * (dy) * m1; \
2898 incr2 = -2 * dx + 2 * (dy) * m; \
2899 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
2900 } else { \
2901 m = dx / (dy); \
2902 m1 = m + 1; \
2903 incr1 = 2 * dx - 2 * (dy) * m1; \
2904 incr2 = 2 * dx - 2 * (dy) * m; \
2905 d = -2 * m * (dy) + 2 * dx; \
2906 } \
2907 } \
2908}
2909
2910#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
2911 if (m1 > 0) { \
2912 if (d > 0) { \
2913 minval += m1; \
2914 d += incr1; \
2915 } \
2916 else { \
2917 minval += m; \
2918 d += incr2; \
2919 } \
2920 } else {\
2921 if (d >= 0) { \
2922 minval += m1; \
2923 d += incr1; \
2924 } \
2925 else { \
2926 minval += m; \
2927 d += incr2; \
2928 } \
2929 } \
2930}
2931
2932
2933/*
2934 * This structure contains all of the information needed
2935 * to run the bresenham algorithm.
2936 * The variables may be hardcoded into the declarations
2937 * instead of using this structure to make use of
2938 * register declarations.
2939 */
2940typedef struct {
2941 int minor_axis; /* minor axis */
2942 int d; /* decision variable */
2943 int m, m1; /* slope and slope+1 */
2944 int incr1, incr2; /* error increments */
2945} BRESINFO;
2946
2947
2948#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
2949 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
2950 bres.m, bres.m1, bres.incr1, bres.incr2)
2951
2952#define BRESINCRPGONSTRUCT(bres) \
2953 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
2954
2955
2956
2957/*
2958 * These are the data structures needed to scan
2959 * convert regions. Two different scan conversion
2960 * methods are available -- the even-odd method, and
2961 * the winding number method.
2962 * The even-odd rule states that a point is inside
2963 * the polygon if a ray drawn from that point in any
2964 * direction will pass through an odd number of
2965 * path segments.
2966 * By the winding number rule, a point is decided
2967 * to be inside the polygon if a ray drawn from that
2968 * point in any direction passes through a different
2969 * number of clockwise and counter-clockwise path
2970 * segments.
2971 *
2972 * These data structures are adapted somewhat from
2973 * the algorithm in (Foley/Van Dam) for scan converting
2974 * polygons.
2975 * The basic algorithm is to start at the top (smallest y)
2976 * of the polygon, stepping down to the bottom of
2977 * the polygon by incrementing the y coordinate. We
2978 * keep a list of edges which the current scanline crosses,
2979 * sorted by x. This list is called the Active Edge Table (AET)
2980 * As we change the y-coordinate, we update each entry in
2981 * in the active edge table to reflect the edges new xcoord.
2982 * This list must be sorted at each scanline in case
2983 * two edges intersect.
2984 * We also keep a data structure known as the Edge Table (ET),
2985 * which keeps track of all the edges which the current
2986 * scanline has not yet reached. The ET is basically a
2987 * list of ScanLineList structures containing a list of
2988 * edges which are entered at a given scanline. There is one
2989 * ScanLineList per scanline at which an edge is entered.
2990 * When we enter a new edge, we move it from the ET to the AET.
2991 *
2992 * From the AET, we can implement the even-odd rule as in
2993 * (Foley/Van Dam).
2994 * The winding number rule is a little trickier. We also
2995 * keep the EdgeTableEntries in the AET linked by the
2996 * nextWETE (winding EdgeTableEntry) link. This allows
2997 * the edges to be linked just as before for updating
2998 * purposes, but only uses the edges linked by the nextWETE
2999 * link as edges representing spans of the polygon to
3000 * drawn (as with the even-odd rule).
3001 */
3002
3003/*
3004 * for the winding number rule
3005 */
3006#define CLOCKWISE 1
3007#define COUNTERCLOCKWISE -1
3008
3009typedef struct _EdgeTableEntry {
3010 int ymax; /* ycoord at which we exit this edge. */
3011 BRESINFO bres; /* Bresenham info to run the edge */
3012 struct _EdgeTableEntry *next; /* next in the list */
3013 struct _EdgeTableEntry *back; /* for insertion sort */
3014 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
3015 int ClockWise; /* flag for winding number rule */
3016} EdgeTableEntry;
3017
3018
3019typedef struct _ScanLineList{
3020 int scanline; /* the scanline represented */
3021 EdgeTableEntry *edgelist; /* header node */
3022 struct _ScanLineList *next; /* next in the list */
3023} ScanLineList;
3024
3025
3026typedef struct {
3027 int ymax; /* ymax for the polygon */
3028 int ymin; /* ymin for the polygon */
3029 ScanLineList scanlines; /* header node */
3030} EdgeTable;
3031
3032
3033/*
3034 * Here is a struct to help with storage allocation
3035 * so we can allocate a big chunk at a time, and then take
3036 * pieces from this heap when we need to.
3037 */
3038#define SLLSPERBLOCK 25
3039
3040typedef struct _ScanLineListBlock {
3041 ScanLineList SLLs[SLLSPERBLOCK];
3042 struct _ScanLineListBlock *next;
3043} ScanLineListBlock;
3044
3045
3046
3047/*
3048 *
3049 * a few macros for the inner loops of the fill code where
3050 * performance considerations don't allow a procedure call.
3051 *
3052 * Evaluate the given edge at the given scanline.
3053 * If the edge has expired, then we leave it and fix up
3054 * the active edge table; otherwise, we increment the
3055 * x value to be ready for the next scanline.
3056 * The winding number rule is in effect, so we must notify
3057 * the caller when the edge has been removed so he
3058 * can reorder the Winding Active Edge Table.
3059 */
3060#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
3061 if (pAET->ymax == y) { /* leaving this edge */ \
3062 pPrevAET->next = pAET->next; \
3063 pAET = pPrevAET->next; \
3064 fixWAET = 1; \
3065 if (pAET) \
3066 pAET->back = pPrevAET; \
3067 } \
3068 else { \
3069 BRESINCRPGONSTRUCT(pAET->bres) \
3070 pPrevAET = pAET; \
3071 pAET = pAET->next; \
3072 } \
3073}
3074
3075
3076/*
3077 * Evaluate the given edge at the given scanline.
3078 * If the edge has expired, then we leave it and fix up
3079 * the active edge table; otherwise, we increment the
3080 * x value to be ready for the next scanline.
3081 * The even-odd rule is in effect.
3082 */
3083#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
3084 if (pAET->ymax == y) { /* leaving this edge */ \
3085 pPrevAET->next = pAET->next; \
3086 pAET = pPrevAET->next; \
3087 if (pAET) \
3088 pAET->back = pPrevAET; \
3089 } \
3090 else { \
3091 BRESINCRPGONSTRUCT(pAET->bres) \
3092 pPrevAET = pAET; \
3093 pAET = pAET->next; \
3094 } \
3095}
3096// END OF poly.h extract
3097// START OF PolyReg.c extract
3098/* $XConsortium: PolyReg.c,v 11.23 94/11/17 21:59:37 converse Exp $ */
3099/************************************************************************
3100
3101Copyright (c) 1987 X Consortium
3102
3103Permission is hereby granted, free of charge, to any person obtaining a copy
3104of this software and associated documentation files (the "Software"), to deal
3105in the Software without restriction, including without limitation the rights
3106to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
3107copies of the Software, and to permit persons to whom the Software is
3108furnished to do so, subject to the following conditions:
3109
3110The above copyright notice and this permission notice shall be included in
3111all copies or substantial portions of the Software.
3112
3113THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
3114IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
3115FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
3116X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
3117AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
3118CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
3119
3120Except as contained in this notice, the name of the X Consortium shall not be
3121used in advertising or otherwise to promote the sale, use or other dealings
3122in this Software without prior written authorization from the X Consortium.
3123
3124
3125Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
3126
3127 All Rights Reserved
3128
3129Permission to use, copy, modify, and distribute this software and its
3130documentation for any purpose and without fee is hereby granted,
3131provided that the above copyright notice appear in all copies and that
3132both that copyright notice and this permission notice appear in
3133supporting documentation, and that the name of Digital not be
3134used in advertising or publicity pertaining to distribution of the
3135software without specific, written prior permission.
3136
3137DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
3138ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
3139DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
3140ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
3141WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
3142ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
3143SOFTWARE.
3144
3145************************************************************************/
3146/* $XFree86: xc/lib/X11/PolyReg.c,v 1.1.1.2.8.2 1998/10/04 15:22:49 hohndel Exp $ */
3147
3148#define LARGE_COORDINATE INT_MAX
3149#define SMALL_COORDINATE INT_MIN
3150
3151/*
3152 * InsertEdgeInET
3153 *
3154 * Insert the given edge into the edge table.
3155 * First we must find the correct bucket in the
3156 * Edge table, then find the right slot in the
3157 * bucket. Finally, we can insert it.
3158 *
3159 */
3160static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
3161 ScanLineListBlock **SLLBlock, int *iSLLBlock)
3162{
3163 register EdgeTableEntry *start, *prev;
3164 register ScanLineList *pSLL, *pPrevSLL;
3165 ScanLineListBlock *tmpSLLBlock;
3166
3167 /*
3168 * find the right bucket to put the edge into
3169 */
3170 pPrevSLL = &ET->scanlines;
3171 pSLL = pPrevSLL->next;
3172 while (pSLL && (pSLL->scanline < scanline)) {
3173 pPrevSLL = pSLL;
3174 pSLL = pSLL->next;
3175 }
3176
3177 /*
3178 * reassign pSLL (pointer to ScanLineList) if necessary
3179 */
3180 if ((!pSLL) || (pSLL->scanline > scanline)) {
3181 if (*iSLLBlock > SLLSPERBLOCK-1)
3182 {
3183 tmpSLLBlock =
3184 (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
3185 Q_CHECK_PTR(tmpSLLBlock);
3186 (*SLLBlock)->next = tmpSLLBlock;
3187 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
3188 *SLLBlock = tmpSLLBlock;
3189 *iSLLBlock = 0;
3190 }
3191 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
3192
3193 pSLL->next = pPrevSLL->next;
3194 pSLL->edgelist = (EdgeTableEntry *)NULL;
3195 pPrevSLL->next = pSLL;
3196 }
3197 pSLL->scanline = scanline;
3198
3199 /*
3200 * now insert the edge in the right bucket
3201 */
3202 prev = 0;
3203 start = pSLL->edgelist;
3204 while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
3205 prev = start;
3206 start = start->next;
3207 }
3208 ETE->next = start;
3209
3210 if (prev)
3211 prev->next = ETE;
3212 else
3213 pSLL->edgelist = ETE;
3214}
3215
3216/*
3217 * CreateEdgeTable
3218 *
3219 * This routine creates the edge table for
3220 * scan converting polygons.
3221 * The Edge Table (ET) looks like:
3222 *
3223 * EdgeTable
3224 * --------
3225 * | ymax | ScanLineLists
3226 * |scanline|-->------------>-------------->...
3227 * -------- |scanline| |scanline|
3228 * |edgelist| |edgelist|
3229 * --------- ---------
3230 * | |
3231 * | |
3232 * V V
3233 * list of ETEs list of ETEs
3234 *
3235 * where ETE is an EdgeTableEntry data structure,
3236 * and there is one ScanLineList per scanline at
3237 * which an edge is initially entered.
3238 *
3239 */
3240
3241static void CreateETandAET(register int count, register const QPoint *pts,
3242 EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs,
3243 ScanLineListBlock *pSLLBlock)
3244{
3245 register const QPoint *top,
3246 *bottom,
3247 *PrevPt,
3248 *CurrPt;
3249 int iSLLBlock = 0;
3250 int dy;
3251
3252 if (count < 2)
3253 return;
3254
3255 /*
3256 * initialize the Active Edge Table
3257 */
3258 AET->next = 0;
3259 AET->back = 0;
3260 AET->nextWETE = 0;
3261 AET->bres.minor_axis = SMALL_COORDINATE;
3262
3263 /*
3264 * initialize the Edge Table.
3265 */
3266 ET->scanlines.next = 0;
3267 ET->ymax = SMALL_COORDINATE;
3268 ET->ymin = LARGE_COORDINATE;
3269 pSLLBlock->next = 0;
3270
3271 PrevPt = &pts[count - 1];
3272
3273 /*
3274 * for each vertex in the array of points.
3275 * In this loop we are dealing with two vertices at
3276 * a time -- these make up one edge of the polygon.
3277 */
3278 while (count--) {
3279 CurrPt = pts++;
3280
3281 /*
3282 * find out which point is above and which is below.
3283 */
3284 if (PrevPt->y() > CurrPt->y()) {
3285 bottom = PrevPt;
3286 top = CurrPt;
3287 pETEs->ClockWise = 0;
3288 } else {
3289 bottom = CurrPt;
3290 top = PrevPt;
3291 pETEs->ClockWise = 1;
3292 }
3293
3294 /*
3295 * don't add horizontal edges to the Edge table.
3296 */
3297 if (bottom->y() != top->y()) {
3298 pETEs->ymax = bottom->y() - 1; /* -1 so we don't get last scanline */
3299
3300 /*
3301 * initialize integer edge algorithm
3302 */
3303 dy = bottom->y() - top->y();
3304 BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)
3305
3306 InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);
3307
3308 if (PrevPt->y() > ET->ymax)
3309 ET->ymax = PrevPt->y();
3310 if (PrevPt->y() < ET->ymin)
3311 ET->ymin = PrevPt->y();
3312 ++pETEs;
3313 }
3314
3315 PrevPt = CurrPt;
3316 }
3317}
3318
3319/*
3320 * loadAET
3321 *
3322 * This routine moves EdgeTableEntries from the
3323 * EdgeTable into the Active Edge Table,
3324 * leaving them sorted by smaller x coordinate.
3325 *
3326 */
3327
3328static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
3329{
3330 register EdgeTableEntry *pPrevAET;
3331 register EdgeTableEntry *tmp;
3332
3333 pPrevAET = AET;
3334 AET = AET->next;
3335 while (ETEs) {
3336 while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
3337 pPrevAET = AET;
3338 AET = AET->next;
3339 }
3340 tmp = ETEs->next;
3341 ETEs->next = AET;
3342 if (AET)
3343 AET->back = ETEs;
3344 ETEs->back = pPrevAET;
3345 pPrevAET->next = ETEs;
3346 pPrevAET = ETEs;
3347
3348 ETEs = tmp;
3349 }
3350}
3351
3352/*
3353 * computeWAET
3354 *
3355 * This routine links the AET by the
3356 * nextWETE (winding EdgeTableEntry) link for
3357 * use by the winding number rule. The final
3358 * Active Edge Table (AET) might look something
3359 * like:
3360 *
3361 * AET
3362 * ---------- --------- ---------
3363 * |ymax | |ymax | |ymax |
3364 * | ... | |... | |... |
3365 * |next |->|next |->|next |->...
3366 * |nextWETE| |nextWETE| |nextWETE|
3367 * --------- --------- ^--------
3368 * | | |
3369 * V-------------------> V---> ...
3370 *
3371 */
3372static void computeWAET(register EdgeTableEntry *AET)
3373{
3374 register EdgeTableEntry *pWETE;
3375 register int inside = 1;
3376 register int isInside = 0;
3377
3378 AET->nextWETE = 0;
3379 pWETE = AET;
3380 AET = AET->next;
3381 while (AET) {
3382 if (AET->ClockWise)
3383 ++isInside;
3384 else
3385 --isInside;
3386
3387 if ((!inside && !isInside) || (inside && isInside)) {
3388 pWETE->nextWETE = AET;
3389 pWETE = AET;
3390 inside = !inside;
3391 }
3392 AET = AET->next;
3393 }
3394 pWETE->nextWETE = 0;
3395}
3396
3397/*
3398 * InsertionSort
3399 *
3400 * Just a simple insertion sort using
3401 * pointers and back pointers to sort the Active
3402 * Edge Table.
3403 *
3404 */
3405
3406static int InsertionSort(register EdgeTableEntry *AET)
3407{
3408 register EdgeTableEntry *pETEchase;
3409 register EdgeTableEntry *pETEinsert;
3410 register EdgeTableEntry *pETEchaseBackTMP;
3411 register int changed = 0;
3412
3413 AET = AET->next;
3414 while (AET) {
3415 pETEinsert = AET;
3416 pETEchase = AET;
3417 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
3418 pETEchase = pETEchase->back;
3419
3420 AET = AET->next;
3421 if (pETEchase != pETEinsert) {
3422 pETEchaseBackTMP = pETEchase->back;
3423 pETEinsert->back->next = AET;
3424 if (AET)
3425 AET->back = pETEinsert->back;
3426 pETEinsert->next = pETEchase;
3427 pETEchase->back->next = pETEinsert;
3428 pETEchase->back = pETEinsert;
3429 pETEinsert->back = pETEchaseBackTMP;
3430 changed = 1;
3431 }
3432 }
3433 return changed;
3434}
3435
3436/*
3437 * Clean up our act.
3438 */
3439static void FreeStorage(register ScanLineListBlock *pSLLBlock)
3440{
3441 register ScanLineListBlock *tmpSLLBlock;
3442
3443 while (pSLLBlock) {
3444 tmpSLLBlock = pSLLBlock->next;
3445 free(pSLLBlock);
3446 pSLLBlock = tmpSLLBlock;
3447 }
3448}
3449
3450struct QRegionSpan {
3451 QRegionSpan() {}
3452 QRegionSpan(int x1_, int x2_) : x1(x1_), x2(x2_) {}
3453
3454 int x1;
3455 int x2;
3456 int width() const { return x2 - x1; }
3457};
3458
3459Q_DECLARE_TYPEINFO(QRegionSpan, Q_PRIMITIVE_TYPE);
3460
3461static inline void flushRow(const QRegionSpan *spans, int y, int numSpans, QRegionPrivate *reg, int *lastRow, int *extendTo, bool *needsExtend)
3462{
3463 QRect *regRects = reg->rects.data() + *lastRow;
3464 bool canExtend = reg->rects.size() - *lastRow == numSpans
3465 && !(*needsExtend && *extendTo + 1 != y)
3466 && (*needsExtend || regRects[0].y() + regRects[0].height() == y);
3467
3468 for (int i = 0; i < numSpans && canExtend; ++i) {
3469 if (regRects[i].x() != spans[i].x1 || regRects[i].right() != spans[i].x2 - 1)
3470 canExtend = false;
3471 }
3472
3473 if (canExtend) {
3474 *extendTo = y;
3475 *needsExtend = true;
3476 } else {
3477 if (*needsExtend) {
3478 for (int i = 0; i < reg->rects.size() - *lastRow; ++i)
3479 regRects[i].setBottom(*extendTo);
3480 }
3481
3482 *lastRow = reg->rects.size();
3483 reg->rects.reserve(*lastRow + numSpans);
3484 for (int i = 0; i < numSpans; ++i)
3485 reg->rects << QRect(spans[i].x1, y, spans[i].width(), 1);
3486
3487 if (spans[0].x1 < reg->extents.left())
3488 reg->extents.setLeft(spans[0].x1);
3489
3490 if (spans[numSpans-1].x2 - 1 > reg->extents.right())
3491 reg->extents.setRight(spans[numSpans-1].x2 - 1);
3492
3493 *needsExtend = false;
3494 }
3495}
3496
3497/*
3498 * Create an array of rectangles from a list of points.
3499 * If indeed these things (POINTS, RECTS) are the same,
3500 * then this proc is still needed, because it allocates
3501 * storage for the array, which was allocated on the
3502 * stack by the calling procedure.
3503 *
3504 */
3505static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock,
3506 POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
3507{
3508 int lastRow = 0;
3509 int extendTo = 0;
3510 bool needsExtend = false;
3511 QVarLengthArray<QRegionSpan> row;
3512 int rowSize = 0;
3513
3514 reg->extents.setLeft(INT_MAX);
3515 reg->extents.setRight(INT_MIN);
3516 reg->innerArea = -1;
3517
3518 POINTBLOCK *CurPtBlock = FirstPtBlock;
3519 for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
3520 /* the loop uses 2 points per iteration */
3521 int i = NUMPTSTOBUFFER >> 1;
3522 if (!numFullPtBlocks)
3523 i = iCurPtBlock >> 1;
3524 if(i) {
3525 row.resize(qMax(row.size(), rowSize + i));
3526 for (QPoint *pts = CurPtBlock->pts; i--; pts += 2) {
3527 const int width = pts[1].x() - pts[0].x();
3528 if (width) {
3529 if (rowSize && row[rowSize-1].x2 == pts[0].x())
3530 row[rowSize-1].x2 = pts[1].x();
3531 else
3532 row[rowSize++] = QRegionSpan(pts[0].x(), pts[1].x());
3533 }
3534
3535 if (rowSize) {
3536 QPoint *next = i ? &pts[2] : (numFullPtBlocks ? CurPtBlock->next->pts : 0);
3537
3538 if (!next || next->y() != pts[0].y()) {
3539 flushRow(row.data(), pts[0].y(), rowSize, reg, &lastRow, &extendTo, &needsExtend);
3540 rowSize = 0;
3541 }
3542 }
3543 }
3544 }
3545 CurPtBlock = CurPtBlock->next;
3546 }
3547
3548 if (needsExtend) {
3549 for (int i = lastRow; i < reg->rects.size(); ++i)
3550 reg->rects[i].setBottom(extendTo);
3551 }
3552
3553 reg->numRects = reg->rects.size();
3554
3555 if (reg->numRects) {
3556 reg->extents.setTop(reg->rects[0].top());
3557 reg->extents.setBottom(reg->rects[lastRow].bottom());
3558
3559 for (int i = 0; i < reg->rects.size(); ++i)
3560 reg->updateInnerRect(reg->rects[i]);
3561 } else {
3562 reg->extents.setCoords(0, 0, 0, 0);
3563 }
3564}
3565
3566/*
3567 * polytoregion
3568 *
3569 * Scan converts a polygon by returning a run-length
3570 * encoding of the resultant bitmap -- the run-length
3571 * encoding is in the form of an array of rectangles.
3572 *
3573 * Can return 0 in case of errors.
3574 */
3575static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule)
3576 //Point *Pts; /* the pts */
3577 //int Count; /* number of pts */
3578 //int rule; /* winding rule */
3579{
3580 QRegionPrivate *region;
3581 register EdgeTableEntry *pAET; /* Active Edge Table */
3582 register int y; /* current scanline */
3583 register int iPts = 0; /* number of pts in buffer */
3584 register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
3585 register ScanLineList *pSLL; /* current scanLineList */
3586 register QPoint *pts; /* output buffer */
3587 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
3588 EdgeTable ET; /* header node for ET */
3589 EdgeTableEntry AET; /* header node for AET */
3590 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
3591 ScanLineListBlock SLLBlock; /* header for scanlinelist */
3592 int fixWAET = false;
3593 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
3594 FirstPtBlock.pts = reinterpret_cast<QPoint *>(FirstPtBlock.data);
3595 POINTBLOCK *tmpPtBlock;
3596 int numFullPtBlocks = 0;
3597
3598 if (!(region = new QRegionPrivate))
3599 return 0;
3600
3601 /* special case a rectangle */
3602 if (((Count == 4) ||
3603 ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
3604 && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
3605 && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
3606 && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
3607 && (Pts[3].y() == Pts[0].y())))) {
3608 int x = qMin(Pts[0].x(), Pts[2].x());
3609 region->extents.setLeft(x);
3610 int y = qMin(Pts[0].y(), Pts[2].y());
3611 region->extents.setTop(y);
3612 region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
3613 region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
3614 if ((region->extents.left() <= region->extents.right()) &&
3615 (region->extents.top() <= region->extents.bottom())) {
3616 region->numRects = 1;
3617 region->innerRect = region->extents;
3618 region->innerArea = region->innerRect.width() * region->innerRect.height();
3619 }
3620 return region;
3621 }
3622
3623 if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
3624 return 0;
3625
3626 region->vectorize();
3627
3628 pts = FirstPtBlock.pts;
3629 CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
3630
3631 pSLL = ET.scanlines.next;
3632 curPtBlock = &FirstPtBlock;
3633
3634 // sanity check that the region won't become too big...
3635 if (ET.ymax - ET.ymin > 100000) {
3636 // clean up region ptr
3637#ifndef QT_NO_DEBUG
3638 qWarning("QRegion: creating region from big polygon failed...!");
3639#endif
3640 delete region;
3641 return 0;
3642 }
3643
3644
3645 QT_TRY {
3646 if (rule == EvenOddRule) {
3647 /*
3648 * for each scanline
3649 */
3650 for (y = ET.ymin; y < ET.ymax; ++y) {
3651
3652 /*
3653 * Add a new edge to the active edge table when we
3654 * get to the next edge.
3655 */
3656 if (pSLL && y == pSLL->scanline) {
3657 loadAET(&AET, pSLL->edgelist);
3658 pSLL = pSLL->next;
3659 }
3660 pPrevAET = &AET;
3661 pAET = AET.next;
3662
3663 /*
3664 * for each active edge
3665 */
3666 while (pAET) {
3667 pts->setX(pAET->bres.minor_axis);
3668 pts->setY(y);
3669 ++pts;
3670 ++iPts;
3671
3672 /*
3673 * send out the buffer
3674 */
3675 if (iPts == NUMPTSTOBUFFER) {
3676 tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
3677 Q_CHECK_PTR(tmpPtBlock);
3678 tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3679 curPtBlock->next = tmpPtBlock;
3680 curPtBlock = tmpPtBlock;
3681 pts = curPtBlock->pts;
3682 ++numFullPtBlocks;
3683 iPts = 0;
3684 }
3685 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
3686 }
3687 InsertionSort(&AET);
3688 }
3689 } else {
3690 /*
3691 * for each scanline
3692 */
3693 for (y = ET.ymin; y < ET.ymax; ++y) {
3694 /*
3695 * Add a new edge to the active edge table when we
3696 * get to the next edge.
3697 */
3698 if (pSLL && y == pSLL->scanline) {
3699 loadAET(&AET, pSLL->edgelist);
3700 computeWAET(&AET);
3701 pSLL = pSLL->next;
3702 }
3703 pPrevAET = &AET;
3704 pAET = AET.next;
3705 pWETE = pAET;
3706
3707 /*
3708 * for each active edge
3709 */
3710 while (pAET) {
3711 /*
3712 * add to the buffer only those edges that
3713 * are in the Winding active edge table.
3714 */
3715 if (pWETE == pAET) {
3716 pts->setX(pAET->bres.minor_axis);
3717 pts->setY(y);
3718 ++pts;
3719 ++iPts;
3720
3721 /*
3722 * send out the buffer
3723 */
3724 if (iPts == NUMPTSTOBUFFER) {
3725 tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
3726 tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3727 curPtBlock->next = tmpPtBlock;
3728 curPtBlock = tmpPtBlock;
3729 pts = curPtBlock->pts;
3730 ++numFullPtBlocks;
3731 iPts = 0;
3732 }
3733 pWETE = pWETE->nextWETE;
3734 }
3735 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
3736 }
3737
3738 /*
3739 * recompute the winding active edge table if
3740 * we just resorted or have exited an edge.
3741 */
3742 if (InsertionSort(&AET) || fixWAET) {
3743 computeWAET(&AET);
3744 fixWAET = false;
3745 }
3746 }
3747 }
3748 } QT_CATCH(...) {
3749 FreeStorage(SLLBlock.next);
3750 PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3751 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3752 tmpPtBlock = curPtBlock->next;
3753 free(curPtBlock);
3754 curPtBlock = tmpPtBlock;
3755 }
3756 free(pETEs);
3757 return 0; // this function returns 0 in case of an error
3758 }
3759
3760 FreeStorage(SLLBlock.next);
3761 PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3762 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3763 tmpPtBlock = curPtBlock->next;
3764 free(curPtBlock);
3765 curPtBlock = tmpPtBlock;
3766 }
3767 free(pETEs);
3768 return region;
3769}
3770// END OF PolyReg.c extract
3771
3772QRegionPrivate *qt_bitmapToRegion(const QBitmap& bitmap)
3773{
3774 QImage image = bitmap.toImage();
3775
3776 QRegionPrivate *region = new QRegionPrivate;
3777
3778 QRect xr;
3779
3780#define AddSpan \
3781 { \
3782 xr.setCoords(prev1, y, x-1, y); \
3783 UnionRectWithRegion(&xr, region, *region); \
3784 }
3785
3786 const uchar zero = 0;
3787 bool little = image.format() == QImage::Format_MonoLSB;
3788
3789 int x,
3790 y;
3791 for (y = 0; y < image.height(); ++y) {
3792 uchar *line = image.scanLine(y);
3793 int w = image.width();
3794 uchar all = zero;
3795 int prev1 = -1;
3796 for (x = 0; x < w;) {
3797 uchar byte = line[x / 8];
3798 if (x > w - 8 || byte!=all) {
3799 if (little) {
3800 for (int b = 8; b > 0 && x < w; --b) {
3801 if (!(byte & 0x01) == !all) {
3802 // More of the same
3803 } else {
3804 // A change.
3805 if (all!=zero) {
3806 AddSpan
3807 all = zero;
3808 } else {
3809 prev1 = x;
3810 all = ~zero;
3811 }
3812 }
3813 byte >>= 1;
3814 ++x;
3815 }
3816 } else {
3817 for (int b = 8; b > 0 && x < w; --b) {
3818 if (!(byte & 0x80) == !all) {
3819 // More of the same
3820 } else {
3821 // A change.
3822 if (all != zero) {
3823 AddSpan
3824 all = zero;
3825 } else {
3826 prev1 = x;
3827 all = ~zero;
3828 }
3829 }
3830 byte <<= 1;
3831 ++x;
3832 }
3833 }
3834 } else {
3835 x += 8;
3836 }
3837 }
3838 if (all != zero) {
3839 AddSpan
3840 }
3841 }
3842#undef AddSpan
3843
3844 return region;
3845}
3846
3847QRegion::QRegion()
3848 : d(&shared_empty)
3849{
3850 d->ref.ref();
3851}
3852
3853QRegion::QRegion(const QRect &r, RegionType t)
3854{
3855 if (r.isEmpty()) {
3856 d = &shared_empty;
3857 d->ref.ref();
3858 } else {
3859 d = new QRegionData;
3860 d->ref = 1;
3861#if defined(Q_WS_X11)
3862 d->rgn = 0;
3863 d->xrectangles = 0;
3864#elif defined(Q_WS_WIN)
3865 d->rgn = 0;
3866#elif defined(Q_WS_PM)
3867 d->rgn = 0;
3868 d->height = 0;
3869#endif
3870 if (t == Rectangle) {
3871 d->qt_rgn = new QRegionPrivate(r);
3872 } else if (t == Ellipse) {
3873 QPainterPath path;
3874 path.addEllipse(r.x(), r.y(), r.width(), r.height());
3875 QPolygon a = path.toSubpathPolygons().at(0).toPolygon();
3876 d->qt_rgn = PolygonRegion(a.constData(), a.size(), EvenOddRule);
3877 }
3878 }
3879}
3880
3881QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
3882{
3883 if (a.count() > 2) {
3884 QRegionPrivate *qt_rgn = PolygonRegion(a.constData(), a.size(),
3885 fillRule == Qt::WindingFill ? WindingRule : EvenOddRule);
3886 if (qt_rgn) {
3887 d = new QRegionData;
3888 d->ref = 1;
3889#if defined(Q_WS_X11)
3890 d->rgn = 0;
3891 d->xrectangles = 0;
3892#elif defined(Q_WS_WIN)
3893 d->rgn = 0;
3894#elif defined(Q_WS_PM)
3895 d->rgn = 0;
3896 d->height = 0;
3897#endif
3898 d->qt_rgn = qt_rgn;
3899 } else {
3900 d = &shared_empty;
3901 d->ref.ref();
3902 }
3903 } else {
3904 d = &shared_empty;
3905 d->ref.ref();
3906 }
3907}
3908
3909QRegion::QRegion(const QRegion &r)
3910{
3911 d = r.d;
3912 d->ref.ref();
3913}
3914
3915
3916QRegion::QRegion(const QBitmap &bm)
3917{
3918 if (bm.isNull()) {
3919 d = &shared_empty;
3920 d->ref.ref();
3921 } else {
3922 d = new QRegionData;
3923 d->ref = 1;
3924#if defined(Q_WS_X11)
3925 d->rgn = 0;
3926 d->xrectangles = 0;
3927#elif defined(Q_WS_WIN)
3928 d->rgn = 0;
3929#elif defined(Q_WS_PM)
3930 d->rgn = 0;
3931 d->height = 0;
3932#endif
3933 d->qt_rgn = qt_bitmapToRegion(bm);
3934 }
3935}
3936
3937void QRegion::cleanUp(QRegion::QRegionData *x)
3938{
3939 delete x->qt_rgn;
3940#if defined(Q_WS_X11)
3941 if (x->rgn)
3942 XDestroyRegion(x->rgn);
3943 if (x->xrectangles)
3944 free(x->xrectangles);
3945#elif defined(Q_WS_WIN)
3946 if (x->rgn)
3947 qt_win_dispose_rgn(x->rgn);
3948#elif defined(Q_WS_PM)
3949 if (x->rgn)
3950 disposeHandle(x->rgn);
3951#endif
3952 delete x;
3953}
3954
3955QRegion::~QRegion()
3956{
3957 if (!d->ref.deref())
3958 cleanUp(d);
3959}
3960
3961
3962QRegion &QRegion::operator=(const QRegion &r)
3963{
3964 r.d->ref.ref();
3965 if (!d->ref.deref())
3966 cleanUp(d);
3967 d = r.d;
3968 return *this;
3969}
3970
3971
3972/*!
3973 \internal
3974*/
3975QRegion QRegion::copy() const
3976{
3977 QRegion r;
3978 QScopedPointer<QRegionData> x(new QRegionData);
3979 x->ref = 1;
3980#if defined(Q_WS_X11)
3981 x->rgn = 0;
3982 x->xrectangles = 0;
3983#elif defined(Q_WS_WIN)
3984 x->rgn = 0;
3985#elif defined(Q_WS_PM)
3986 x->rgn = 0;
3987 x->height = 0;
3988#endif
3989 if (d->qt_rgn)
3990 x->qt_rgn = new QRegionPrivate(*d->qt_rgn);
3991 else
3992 x->qt_rgn = new QRegionPrivate;
3993 if (!r.d->ref.deref())
3994 cleanUp(r.d);
3995 r.d = x.take();
3996 return r;
3997}
3998
3999bool QRegion::isEmpty() const
4000{
4001 return d == &shared_empty || d->qt_rgn->numRects == 0;
4002}
4003
4004
4005bool QRegion::contains(const QPoint &p) const
4006{
4007 return PointInRegion(d->qt_rgn, p.x(), p.y());
4008}
4009
4010bool QRegion::contains(const QRect &r) const
4011{
4012 return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut;
4013}
4014
4015
4016
4017void QRegion::translate(int dx, int dy)
4018{
4019 if ((dx == 0 && dy == 0) || isEmptyHelper(d->qt_rgn))
4020 return;
4021
4022 detach();
4023 OffsetRegion(*d->qt_rgn, dx, dy);
4024}
4025
4026QRegion QRegion::unite(const QRegion &r) const
4027{
4028 if (isEmptyHelper(d->qt_rgn))
4029 return r;
4030 if (isEmptyHelper(r.d->qt_rgn))
4031 return *this;
4032 if (d == r.d)
4033 return *this;
4034
4035 if (d->qt_rgn->contains(*r.d->qt_rgn)) {
4036 return *this;
4037 } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
4038 return r;
4039 } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
4040 QRegion result(*this);
4041 result.detach();
4042 result.d->qt_rgn->append(r.d->qt_rgn);
4043 return result;
4044 } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
4045 QRegion result(*this);
4046 result.detach();
4047 result.d->qt_rgn->prepend(r.d->qt_rgn);
4048 return result;
4049 } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4050 return *this;
4051 } else {
4052 QRegion result;
4053 result.detach();
4054 UnionRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4055 return result;
4056 }
4057}
4058
4059QRegion& QRegion::operator+=(const QRegion &r)
4060{
4061 if (isEmptyHelper(d->qt_rgn))
4062 return *this = r;
4063 if (isEmptyHelper(r.d->qt_rgn))
4064 return *this;
4065 if (d == r.d)
4066 return *this;
4067
4068 if (d->qt_rgn->contains(*r.d->qt_rgn)) {
4069 return *this;
4070 } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
4071 return *this = r;
4072 } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
4073 detach();
4074 d->qt_rgn->append(r.d->qt_rgn);
4075 return *this;
4076 } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
4077 detach();
4078 d->qt_rgn->prepend(r.d->qt_rgn);
4079 return *this;
4080 } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4081 return *this;
4082 } else {
4083 detach();
4084 UnionRegion(d->qt_rgn, r.d->qt_rgn, *d->qt_rgn);
4085 return *this;
4086 }
4087}
4088
4089QRegion QRegion::unite(const QRect &r) const
4090{
4091 if (isEmptyHelper(d->qt_rgn))
4092 return r;
4093 if (r.isEmpty())
4094 return *this;
4095
4096 if (d->qt_rgn->contains(r)) {
4097 return *this;
4098 } else if (d->qt_rgn->within(r)) {
4099 return r;
4100 } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4101 return *this;
4102 } else if (d->qt_rgn->canAppend(&r)) {
4103 QRegion result(*this);
4104 result.detach();
4105 result.d->qt_rgn->append(&r);
4106 return result;
4107 } else if (d->qt_rgn->canPrepend(&r)) {
4108 QRegion result(*this);
4109 result.detach();
4110 result.d->qt_rgn->prepend(&r);
4111 return result;
4112 } else {
4113 QRegion result;
4114 result.detach();
4115 QRegionPrivate rp(r);
4116 UnionRegion(d->qt_rgn, &rp, *result.d->qt_rgn);
4117 return result;
4118 }
4119}
4120
4121QRegion& QRegion::operator+=(const QRect &r)
4122{
4123 if (isEmptyHelper(d->qt_rgn))
4124 return *this = r;
4125 if (r.isEmpty())
4126 return *this;
4127
4128 if (d->qt_rgn->contains(r)) {
4129 return *this;
4130 } else if (d->qt_rgn->within(r)) {
4131 return *this = r;
4132 } else if (d->qt_rgn->canAppend(&r)) {
4133 detach();
4134 d->qt_rgn->append(&r);
4135 return *this;
4136 } else if (d->qt_rgn->canPrepend(&r)) {
4137 detach();
4138 d->qt_rgn->prepend(&r);
4139 return *this;
4140 } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4141 return *this;
4142 } else {
4143 detach();
4144 QRegionPrivate p(r);
4145 UnionRegion(d->qt_rgn, &p, *d->qt_rgn);
4146 return *this;
4147 }
4148}
4149
4150QRegion QRegion::intersect(const QRegion &r) const
4151{
4152 if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn)
4153 || !EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4154 return QRegion();
4155
4156 /* this is fully contained in r */
4157 if (r.d->qt_rgn->contains(*d->qt_rgn))
4158 return *this;
4159
4160 /* r is fully contained in this */
4161 if (d->qt_rgn->contains(*r.d->qt_rgn))
4162 return r;
4163
4164 if (r.d->qt_rgn->numRects == 1 && d->qt_rgn->numRects == 1) {
4165 const QRect rect = qt_rect_intersect_normalized(r.d->qt_rgn->extents,
4166 d->qt_rgn->extents);
4167 return QRegion(rect);
4168 } else if (r.d->qt_rgn->numRects == 1) {
4169 QRegion result(*this);
4170 result.detach();
4171 result.d->qt_rgn->intersect(r.d->qt_rgn->extents);
4172 return result;
4173 } else if (d->qt_rgn->numRects == 1) {
4174 QRegion result(r);
4175 result.detach();
4176 result.d->qt_rgn->intersect(d->qt_rgn->extents);
4177 return result;
4178 }
4179
4180 QRegion result;
4181 result.detach();
4182 miRegionOp(*result.d->qt_rgn, d->qt_rgn, r.d->qt_rgn, miIntersectO, 0, 0);
4183
4184 /*
4185 * Can't alter dest's extents before we call miRegionOp because
4186 * it might be one of the source regions and miRegionOp depends
4187 * on the extents of those regions being the same. Besides, this
4188 * way there's no checking against rectangles that will be nuked
4189 * due to coalescing, so we have to examine fewer rectangles.
4190 */
4191 miSetExtents(*result.d->qt_rgn);
4192 return result;
4193}
4194
4195QRegion QRegion::intersect(const QRect &r) const
4196{
4197 if (isEmptyHelper(d->qt_rgn) || r.isEmpty()
4198 || !EXTENTCHECK(&d->qt_rgn->extents, &r))
4199 return QRegion();
4200
4201 /* this is fully contained in r */
4202 if (d->qt_rgn->within(r))
4203 return *this;
4204
4205 /* r is fully contained in this */
4206 if (d->qt_rgn->contains(r))
4207 return r;
4208
4209 if (d->qt_rgn->numRects == 1) {
4210 const QRect rect = qt_rect_intersect_normalized(d->qt_rgn->extents,
4211 r.normalized());
4212 return QRegion(rect);
4213 }
4214
4215 QRegion result(*this);
4216 result.detach();
4217 result.d->qt_rgn->intersect(r);
4218 return result;
4219}
4220
4221QRegion QRegion::subtract(const QRegion &r) const
4222{
4223 if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn))
4224 return *this;
4225 if (r.d->qt_rgn->contains(*d->qt_rgn))
4226 return QRegion();
4227 if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4228 return *this;
4229 if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn))
4230 return QRegion();
4231
4232#ifdef QT_REGION_DEBUG
4233 d->qt_rgn->selfTest();
4234 r.d->qt_rgn->selfTest();
4235#endif
4236
4237 QRegion result;
4238 result.detach();
4239 SubtractRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4240#ifdef QT_REGION_DEBUG
4241 result.d->qt_rgn->selfTest();
4242#endif
4243 return result;
4244}
4245
4246QRegion QRegion::eor(const QRegion &r) const
4247{
4248 if (isEmptyHelper(d->qt_rgn)) {
4249 return r;
4250 } else if (isEmptyHelper(r.d->qt_rgn)) {
4251 return *this;
4252 } else if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents)) {
4253 return (*this + r);
4254 } else if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4255 return QRegion();
4256 } else {
4257 QRegion result;
4258 result.detach();
4259 XorRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4260 return result;
4261 }
4262}
4263
4264QRect QRegion::boundingRect() const
4265{
4266 if (isEmpty())
4267 return QRect();
4268 return d->qt_rgn->extents;
4269}
4270
4271/*! \internal
4272 Returns true if \a rect is guaranteed to be fully contained in \a region.
4273 A false return value does not guarantee the opposite.
4274*/
4275#ifdef Q_WS_QWS
4276Q_GUI_EXPORT
4277#endif
4278bool qt_region_strictContains(const QRegion &region, const QRect &rect)
4279{
4280 if (isEmptyHelper(region.d->qt_rgn) || !rect.isValid())
4281 return false;
4282
4283#if 0 // TEST_INNERRECT
4284 static bool guard = false;
4285 if (guard)
4286 return false;
4287 guard = true;
4288 QRegion inner = region.d->qt_rgn->innerRect;
4289 Q_ASSERT((inner - region).isEmpty());
4290 guard = false;
4291
4292 int maxArea = 0;
4293 for (int i = 0; i < region.d->qt_rgn->numRects; ++i) {
4294 const QRect r = region.d->qt_rgn->rects.at(i);
4295 if (r.width() * r.height() > maxArea)
4296 maxArea = r.width() * r.height();
4297 }
4298
4299 if (maxArea > region.d->qt_rgn->innerArea) {
4300 qDebug() << "not largest rectangle" << region << region.d->qt_rgn->innerRect;
4301 }
4302 Q_ASSERT(maxArea <= region.d->qt_rgn->innerArea);
4303#endif
4304
4305 const QRect r1 = region.d->qt_rgn->innerRect;
4306 return (rect.left() >= r1.left() && rect.right() <= r1.right()
4307 && rect.top() >= r1.top() && rect.bottom() <= r1.bottom());
4308}
4309
4310QVector<QRect> QRegion::rects() const
4311{
4312 if (d->qt_rgn) {
4313 d->qt_rgn->vectorize();
4314 // hw: modify the vector size directly to avoid reallocation
4315 d->qt_rgn->rects.d->size = d->qt_rgn->numRects;
4316 return d->qt_rgn->rects;
4317 } else {
4318 return QVector<QRect>();
4319 }
4320}
4321
4322void QRegion::setRects(const QRect *rects, int num)
4323{
4324 *this = QRegion();
4325 if (!rects || num == 0 || (num == 1 && rects->isEmpty()))
4326 return;
4327
4328 detach();
4329
4330 d->qt_rgn->numRects = num;
4331 if (num == 1) {
4332 d->qt_rgn->extents = *rects;
4333 d->qt_rgn->innerRect = *rects;
4334 } else {
4335 d->qt_rgn->rects.resize(num);
4336
4337 int left = INT_MAX,
4338 right = INT_MIN,
4339 top = INT_MAX,
4340 bottom = INT_MIN;
4341 for (int i = 0; i < num; ++i) {
4342 const QRect &rect = rects[i];
4343 d->qt_rgn->rects[i] = rect;
4344 left = qMin(rect.left(), left);
4345 right = qMax(rect.right(), right);
4346 top = qMin(rect.top(), top);
4347 bottom = qMax(rect.bottom(), bottom);
4348 d->qt_rgn->updateInnerRect(rect);
4349 }
4350 d->qt_rgn->extents = QRect(QPoint(left, top), QPoint(right, bottom));
4351 }
4352}
4353
4354int QRegion::numRects() const
4355{
4356 return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4357}
4358
4359int QRegion::rectCount() const
4360{
4361 return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4362}
4363
4364
4365bool QRegion::operator==(const QRegion &r) const
4366{
4367 if (!d->qt_rgn)
4368 return r.isEmpty();
4369 if (!r.d->qt_rgn)
4370 return isEmpty();
4371
4372 if (d == r.d)
4373 return true;
4374 else
4375 return EqualRegion(d->qt_rgn, r.d->qt_rgn);
4376}
4377
4378#endif
4379QT_END_NAMESPACE
Note: See TracBrowser for help on using the repository browser.