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