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