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
22QT_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*/
160QRegion::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
174void 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*/
204void 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
311QDataStream &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
345QDataStream &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
355QDebug 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*/
399QRegion 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*/
408QRegion QRegion::operator+(const QRegion &r) const
409 { return united(r); }
410
411/*!
412 \overload
413 \since 4.4
414 */
415QRegion 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*/
424QRegion QRegion::operator&(const QRegion &r) const
425 { return intersected(r); }
426
427/*!
428 \overload
429 \since 4.4
430 */
431QRegion 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*/
442QRegion 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*/
451QRegion 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*/
461QRegion& 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)
481QRegion& 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*/
496QRegion& 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)
504QRegion& QRegion::operator&=(const QRect &r)
505{
506 return *this = *this & r;
507}
508#else
509QRegion& 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*/
524QRegion& 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*/
534QRegion& 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*/
547QRegion::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
590QRegion
591QRegion::translated(int dx, int dy) const
592{
593 QRegion ret(*this);
594 ret.translate(dx, dy);
595 return ret;
596}
597
598
599inline 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*/
611bool 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*/
642QRegion 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
906namespace {
907
908struct 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
971void 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
988void 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:
1014Q_DECLARE_TYPEINFO(Segment, Q_PRIMITIVE_TYPE);
1015
1016Q_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
1079struct 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
1165static inline bool isEmptyHelper(const QRegionPrivate *preg)
1166{
1167 return !preg || preg->numRects == 0;
1168}
1169
1170static 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
1177static inline bool canMergeFromLeft(const QRect *right, const QRect *left)
1178{
1179 return canMergeFromRight(left, right);
1180}
1181
1182bool 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
1192bool 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
1202static 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
1216bool 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
1228bool 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
1240static 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
1251void 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
1304void 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
1335void 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
1408void 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
1481void 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
1513bool 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
1530bool QRegionPrivate::canAppend(const QRegionPrivate *r) const
1531{
1532 return canAppend(r: r->numRects == 1 ? &r->extents : r->rects.constData());
1533}
1534
1535bool 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
1552bool 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
1558void 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
1595static QRegionPrivate qrp;
1596const QRegion::QRegionData QRegion::shared_empty = {Q_REFCOUNT_INITIALIZE_STATIC, .qt_rgn: &qrp};
1597
1598typedef void (*OverlapFunc)(QRegionPrivate &dest, const QRect *r1, const QRect *r1End,
1599 const QRect *r2, const QRect *r2End, int y1, int y2);
1600typedef void (*NonOverlapFunc)(QRegionPrivate &dest, const QRect *r, const QRect *rEnd,
1601 int y1, int y2);
1602
1603static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2);
1604static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest);
1605static 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
1619Copyright (c) 1987 X Consortium
1620
1621Permission is hereby granted, free of charge, to any person obtaining a copy
1622of this software and associated documentation files (the "Software"), to deal
1623in the Software without restriction, including without limitation the rights
1624to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1625copies of the Software, and to permit persons to whom the Software is
1626furnished to do so, subject to the following conditions:
1627
1628The above copyright notice and this permission notice shall be included in
1629all copies or substantial portions of the Software.
1630
1631THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1632IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1633FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1634X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1635AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1636CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1637
1638Except as contained in this notice, the name of the X Consortium shall not be
1639used in advertising or otherwise to promote the sale, use or other dealings
1640in this Software without prior written authorization from the X Consortium.
1641
1642
1643Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1644
1645 All Rights Reserved
1646
1647Permission to use, copy, modify, and distribute this software and its
1648documentation for any purpose and without fee is hereby granted,
1649provided that the above copyright notice appear in all copies and that
1650both that copyright notice and this permission notice appear in
1651supporting documentation, and that the name of Digital not be
1652used in advertising or publicity pertaining to distribution of the
1653software without specific, written prior permission.
1654
1655DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1656ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1657DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1658ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1659WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1660ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1661SOFTWARE.
1662
1663************************************************************************/
1664
1665#ifndef _XREGION_H
1666#define _XREGION_H
1667
1668QT_BEGIN_INCLUDE_NAMESPACE
1669#include <limits.h>
1670QT_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 */
1717typedef 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
1730Copyright (c) 1987, 1988 X Consortium
1731
1732Permission is hereby granted, free of charge, to any person obtaining a copy
1733of this software and associated documentation files (the "Software"), to deal
1734in the Software without restriction, including without limitation the rights
1735to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1736copies of the Software, and to permit persons to whom the Software is
1737furnished to do so, subject to the following conditions:
1738
1739The above copyright notice and this permission notice shall be included in
1740all copies or substantial portions of the Software.
1741
1742THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1743IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1744FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1745X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1746AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1747CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1748
1749Except as contained in this notice, the name of the X Consortium shall not be
1750used in advertising or otherwise to promote the sale, use or other dealings
1751in this Software without prior written authorization from the X Consortium.
1752
1753
1754Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
1755
1756 All Rights Reserved
1757
1758Permission to use, copy, modify, and distribute this software and its
1759documentation for any purpose and without fee is hereby granted,
1760provided that the above copyright notice appear in all copies and that
1761both that copyright notice and this permission notice appear in
1762supporting documentation, and that the name of Digital not be
1763used in advertising or publicity pertaining to distribution of the
1764software without specific, written prior permission.
1765
1766DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1767ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1768DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1769ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1770WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1771ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1772SOFTWARE.
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
1802static 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 */
1835static 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
1884static 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 */
1915static 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 */
1980static 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 */
2109static 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
2332static 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
2368static 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
2414static 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
2457static 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
2491static 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
2592static 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
2613static 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 */
2647static 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
2669static 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
2688static 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
2754Copyright (c) 1987 X Consortium
2755
2756Permission is hereby granted, free of charge, to any person obtaining a copy
2757of this software and associated documentation files (the "Software"), to deal
2758in the Software without restriction, including without limitation the rights
2759to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2760copies of the Software, and to permit persons to whom the Software is
2761furnished to do so, subject to the following conditions:
2762
2763The above copyright notice and this permission notice shall be included in
2764all copies or substantial portions of the Software.
2765
2766THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2767IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2768FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2769X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
2770AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
2771CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
2772
2773Except as contained in this notice, the name of the X Consortium shall not be
2774used in advertising or otherwise to promote the sale, use or other dealings
2775in this Software without prior written authorization from the X Consortium.
2776
2777
2778Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
2779
2780 All Rights Reserved
2781
2782Permission to use, copy, modify, and distribute this software and its
2783documentation for any purpose and without fee is hereby granted,
2784provided that the above copyright notice appear in all copies and that
2785both that copyright notice and this permission notice appear in
2786supporting documentation, and that the name of Digital not be
2787used in advertising or publicity pertaining to distribution of the
2788software without specific, written prior permission.
2789
2790DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
2791ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
2792DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
2793ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
2794WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
2795ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
2796SOFTWARE.
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 */
2891typedef 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
2960typedef 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
2970typedef 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
2977typedef 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
2991typedef 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
3052Copyright (c) 1987 X Consortium
3053
3054Permission is hereby granted, free of charge, to any person obtaining a copy
3055of this software and associated documentation files (the "Software"), to deal
3056in the Software without restriction, including without limitation the rights
3057to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
3058copies of the Software, and to permit persons to whom the Software is
3059furnished to do so, subject to the following conditions:
3060
3061The above copyright notice and this permission notice shall be included in
3062all copies or substantial portions of the Software.
3063
3064THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
3065IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
3066FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
3067X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
3068AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
3069CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
3070
3071Except as contained in this notice, the name of the X Consortium shall not be
3072used in advertising or otherwise to promote the sale, use or other dealings
3073in this Software without prior written authorization from the X Consortium.
3074
3075
3076Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
3077
3078 All Rights Reserved
3079
3080Permission to use, copy, modify, and distribute this software and its
3081documentation for any purpose and without fee is hereby granted,
3082provided that the above copyright notice appear in all copies and that
3083both that copyright notice and this permission notice appear in
3084supporting documentation, and that the name of Digital not be
3085used in advertising or publicity pertaining to distribution of the
3086software without specific, written prior permission.
3087
3088DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
3089ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
3090DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
3091ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
3092WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
3093ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
3094SOFTWARE.
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 */
3111static 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
3192static 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
3278static 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 */
3322static 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
3356static 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 */
3389static 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
3400struct 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
3409Q_DECLARE_TYPEINFO(QRegionSpan, Q_PRIMITIVE_TYPE);
3410
3411static 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 */
3455static 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 */
3525static 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
3729QRegionPrivate *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
3804QRegion::QRegion()
3805 : d(const_cast<QRegionData*>(&shared_empty))
3806{
3807}
3808
3809QRegion::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
3827QRegion::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
3844QRegion::QRegion(const QRegion &r)
3845{
3846 d = r.d;
3847 d->ref.ref();
3848}
3849
3850
3851QRegion::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
3862void QRegion::cleanUp(QRegion::QRegionData *x)
3863{
3864 delete x->qt_rgn;
3865 delete x;
3866}
3867
3868QRegion::~QRegion()
3869{
3870 if (!d->ref.deref())
3871 cleanUp(x: d);
3872}
3873
3874
3875QRegion &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*/
3888QRegion 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
3903bool QRegion::isEmpty() const
3904{
3905 return d == &shared_empty || d->qt_rgn->numRects == 0;
3906}
3907
3908bool QRegion::isNull() const
3909{
3910 return d == &shared_empty || d->qt_rgn->numRects == 0;
3911}
3912
3913bool QRegion::contains(const QPoint &p) const
3914{
3915 return PointInRegion(pRegion: d->qt_rgn, x: p.x(), y: p.y());
3916}
3917
3918bool 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
3925void 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
3934QRegion 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
3967QRegion& 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
3997QRegion 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
4029QRegion& 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
4058QRegion 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
4103QRegion 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
4129QRegion 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
4154QRegion 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
4172QRect 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*/
4183Q_GUI_EXPORT
4184bool 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
4216QRegion::const_iterator QRegion::begin() const noexcept
4217{
4218 return d->qt_rgn ? d->qt_rgn->begin() : nullptr;
4219}
4220
4221QRegion::const_iterator QRegion::end() const noexcept
4222{
4223 return d->qt_rgn ? d->qt_rgn->end() : nullptr;
4224}
4225
4226static Q_DECL_COLD_FUNCTION
4227void set_rects_warn(const char *what)
4228{
4229 qWarning(msg: "QRegion::setRects(): %s", what);
4230}
4231
4232void 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
4241void 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*/
4293QSpan<const QRect> QRegion::rects() const noexcept
4294{
4295 return {begin(), end()};
4296};
4297
4298int QRegion::rectCount() const noexcept
4299{
4300 return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4301}
4302
4303bool 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
4316bool 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
4339static 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*/
4349HRGN 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 */
4373QRegion 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
4397QT_END_NAMESPACE
4398

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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