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