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