qregion.cpp

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