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

source code of qtbase/src/gui/painting/qregion.cpp