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