1 /****************************************************************************
3 ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
7 ** This file is part of the QtGui module of the Qt Toolkit.
9 ** $QT_BEGIN_LICENSE:LGPL$
10 ** GNU Lesser General Public License Usage
11 ** This file may be used under the terms of the GNU Lesser General Public
12 ** License version 2.1 as published by the Free Software Foundation and
13 ** appearing in the file LICENSE.LGPL included in the packaging of this
14 ** file. Please review the following information to ensure the GNU Lesser
15 ** General Public License version 2.1 requirements will be met:
16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
18 ** In addition, as a special exception, Nokia gives you certain additional
19 ** rights. These rights are described in the Nokia Qt LGPL Exception
20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
22 ** GNU General Public License Usage
23 ** Alternatively, this file may be used under the terms of the GNU General
24 ** Public License version 3.0 as published by the Free Software Foundation
25 ** and appearing in the file LICENSE.GPL included in the packaging of this
26 ** file. Please review the following information to ensure the GNU General
27 ** Public License version 3.0 requirements will be met:
28 ** http://www.gnu.org/copyleft/gpl.html.
31 ** Alternatively, this file may be used in accordance with the terms and
32 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
43 #include "qpainterpath.h"
46 #include "qdatastream.h"
48 #include "qvarlengtharray.h"
52 #if defined(Q_OS_UNIX) || defined(Q_WS_WIN)
62 \brief The QRegion class specifies a clip region for a painter.
67 QRegion is used with QPainter::setClipRegion() to limit the paint
68 area to what needs to be painted. There is also a QWidget::repaint()
69 function that takes a QRegion parameter. QRegion is the best tool for
70 minimizing the amount of screen area to be updated by a repaint.
72 This class is not suitable for constructing shapes for rendering, especially
73 as outlines. Use QPainterPath to create paths and shapes for use with
76 QRegion is an \l{implicitly shared} class.
78 \section1 Creating and Using Regions
80 A region can be created from a rectangle, an ellipse, a polygon or
81 a bitmap. Complex regions may be created by combining simple
82 regions using united(), intersected(), subtracted(), or xored() (exclusive
83 or). You can move a region using translate().
85 You can test whether a region isEmpty() or if it
86 contains() a QPoint or QRect. The bounding rectangle can be found
89 The function rects() gives a decomposition of the region into
92 Example of using complex regions:
93 \snippet doc/src/snippets/code/src_gui_painting_qregion.cpp 0
95 \section1 Additional License Information
97 On Embedded Linux, Windows CE and X11 platforms, parts of this class rely on
98 code obtained under the following licenses:
101 Copyright (c) 1987 X Consortium
103 Permission is hereby granted, free of charge, to any person obtaining a copy
104 of this software and associated documentation files (the "Software"), to deal
105 in the Software without restriction, including without limitation the rights
106 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
107 copies of the Software, and to permit persons to whom the Software is
108 furnished to do so, subject to the following conditions:
110 The above copyright notice and this permission notice shall be included in
111 all copies or substantial portions of the Software.
113 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
114 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
115 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
116 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
117 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
118 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
120 Except as contained in this notice, the name of the X Consortium shall not be
121 used in advertising or otherwise to promote the sale, use or other dealings
122 in this Software without prior written authorization from the X Consortium.
128 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
132 Permission to use, copy, modify, and distribute this software and its
133 documentation for any purpose and without fee is hereby granted,
134 provided that the above copyright notice appear in all copies and that
135 both that copyright notice and this permission notice appear in
136 supporting documentation, and that the name of Digital not be
137 used in advertising or publicity pertaining to distribution of the
138 software without specific, written prior permission.
140 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
141 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
142 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
143 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
144 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
145 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
149 \sa QPainter::setClipRegion(), QPainter::setClipRect(), QPainterPath
154 \enum QRegion::RegionType
156 Specifies the shape of the region to be created.
158 \value Rectangle the region covers the entire rectangle.
159 \value Ellipse the region is an ellipse inside the rectangle.
163 \fn void QRegion::translate(const QPoint &point)
167 Translates the region \a{point}\e{.x()} along the x axis and
168 \a{point}\e{.y()} along the y axis, relative to the current
169 position. Positive values move the region to the right and down.
171 Translates to the given \a point.
175 \fn Handle QRegion::handle() const
177 Returns a platform-specific region handle. The \c Handle type is
178 \c HRGN on Windows, \c Region on X11, and \c RgnHandle on Mac OS
179 X. On \l{Qt for Embedded Linux} it is \c {void *}.
181 \warning This function is not portable.
184 /*****************************************************************************
185 QRegion member functions
186 *****************************************************************************/
189 \fn QRegion::QRegion()
191 Constructs an empty region.
197 \fn QRegion::QRegion(const QRect &r, RegionType t)
200 Create a region based on the rectange \a r with region type \a t.
202 If the rectangle is invalid a null region will be created.
204 \sa QRegion::RegionType
208 \fn QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
210 Constructs a polygon region from the point array \a a with the fill rule
211 specified by \a fillRule.
213 If \a fillRule is \l{Qt::WindingFill}, the polygon region is defined
214 using the winding algorithm; if it is \l{Qt::OddEvenFill}, the odd-even fill
217 \warning This constructor can be used to create complex regions that will
218 slow down painting when used.
222 \fn QRegion::QRegion(const QRegion &r)
224 Constructs a new region which is equal to region \a r.
228 \fn QRegion::QRegion(const QBitmap &bm)
230 Constructs a region from the bitmap \a bm.
232 The resulting region consists of the pixels in bitmap \a bm that
233 are Qt::color1, as if each pixel was a 1 by 1 rectangle.
235 This constructor may create complex regions that will slow down
236 painting when used. Note that drawing masked pixmaps can be done
237 much faster using QPixmap::setMask().
241 Constructs a rectangular or elliptic region.
243 If \a t is \c Rectangle, the region is the filled rectangle (\a x,
244 \a y, \a w, \a h). If \a t is \c Ellipse, the region is the filled
245 ellipse with center at (\a x + \a w / 2, \a y + \a h / 2) and size
248 QRegion::QRegion(int x, int y, int w, int h, RegionType t)
250 QRegion tmp(QRect(x, y, w, h), t);
257 Use the constructor tha takes a Qt::FillRule as the second
260 QRegion::QRegion(const QPolygon &pa, bool winding)
262 new (this) QRegion(pa, winding ? Qt::WindingFill : Qt::OddEvenFill);
267 \fn QRegion::~QRegion()
273 void QRegion::detach()
277 #if defined(Q_WS_X11)
278 else if (d->xrectangles) {
279 free(d->xrectangles);
285 // duplicates in qregion_win.cpp and qregion_wce.cpp
286 #define QRGN_SETRECT 1 // region stream commands
287 #define QRGN_SETELLIPSE 2 // (these are internal)
288 #define QRGN_SETPTARRAY_ALT 3
289 #define QRGN_SETPTARRAY_WIND 4
290 #define QRGN_TRANSLATE 5
295 #define QRGN_RECTS 10
298 #ifndef QT_NO_DATASTREAM
301 Executes region commands in the internal buffer and rebuilds the
304 We do this when we read a region from the data stream.
306 If \a ver is non-0, uses the format version \a ver on reading the
309 void QRegion::exec(const QByteArray &buffer, int ver, QDataStream::ByteOrder byteOrder)
311 QByteArray copy = buffer;
312 QDataStream s(©, QIODevice::ReadOnly);
315 s.setByteOrder(byteOrder);
322 if (s.version() == 1) {
330 if (test_cnt > 0 && id != QRGN_TRANSLATE)
331 qWarning("QRegion::exec: Internal error");
334 if (id == QRGN_SETRECT || id == QRGN_SETELLIPSE) {
337 rgn = QRegion(r, id == QRGN_SETRECT ? Rectangle : Ellipse);
338 } else if (id == QRGN_SETPTARRAY_ALT || id == QRGN_SETPTARRAY_WIND) {
341 rgn = QRegion(a, id == QRGN_SETPTARRAY_WIND ? Qt::WindingFill : Qt::OddEvenFill);
342 } else if (id == QRGN_TRANSLATE) {
345 rgn.translate(p.x(), p.y());
346 } else if (id >= QRGN_OR && id <= QRGN_XOR) {
347 QByteArray bop1, bop2;
359 rgn = r1.intersected(r2);
362 rgn = r1.subtracted(r2);
368 } else if (id == QRGN_RECTS) {
369 // (This is the only form used in Qt 2.0)
373 for (int i=0; i<(int)n; i++) {
375 rgn = rgn.united(QRegion(r));
383 /*****************************************************************************
384 QRegion stream functions
385 *****************************************************************************/
388 \fn QRegion &QRegion::operator=(const QRegion &r)
390 Assigns \a r to this region and returns a reference to the region.
394 \fn void QRegion::swap(QRegion &other)
397 Swaps region \a other with this region. This operation is very
398 fast and never fails.
404 Writes the region \a r to the stream \a s and returns a reference
407 \sa \link datastreamformat.html Format of the QDataStream operators \endlink
410 QDataStream &operator<<(QDataStream &s, const QRegion &r)
412 QVector<QRect> a = r.rects();
416 if (s.version() == 1) {
418 for (i = a.size() - 1; i > 0; --i) {
419 s << (quint32)(12 + i * 24);
422 for (i = 0; i < a.size(); ++i) {
423 s << (quint32)(4+8) << (int)QRGN_SETRECT << a[i];
426 s << (quint32)(4 + 4 + 16 * a.size()); // 16: storage size of QRect
427 s << (qint32)QRGN_RECTS;
437 Reads a region from the stream \a s into \a r and returns a
438 reference to the stream.
440 \sa \link datastreamformat.html Format of the QDataStream operators \endlink
443 QDataStream &operator>>(QDataStream &s, QRegion &r)
447 r.exec(b, s.version(), s.byteOrder());
450 #endif //QT_NO_DATASTREAM
452 #ifndef QT_NO_DEBUG_STREAM
453 QDebug operator<<(QDebug s, const QRegion &r)
455 QVector<QRect> rects = r.rects();
456 s.nospace() << "QRegion(size=" << rects.size() << "), "
457 << "bounds = " << r.boundingRect() << '\n';
458 for (int i=0; i<rects.size(); ++i)
459 s << "- " << i << rects.at(i) << '\n';
465 // These are not inline - they can be implemented better on some platforms
466 // (eg. Windows at least provides 3-variable operations). For now, simple.
470 Applies the united() function to this region and \a r. \c r1|r2 is
471 equivalent to \c r1.united(r2).
473 \sa united(), operator+()
475 const QRegion QRegion::operator|(const QRegion &r) const
476 { return united(r); }
479 Applies the united() function to this region and \a r. \c r1+r2 is
480 equivalent to \c r1.united(r2).
482 \sa united(), operator|()
484 const QRegion QRegion::operator+(const QRegion &r) const
485 { return united(r); }
491 const QRegion QRegion::operator+(const QRect &r) const
492 { return united(r); }
495 Applies the intersected() function to this region and \a r. \c r1&r2
496 is equivalent to \c r1.intersected(r2).
500 const QRegion QRegion::operator&(const QRegion &r) const
501 { return intersected(r); }
507 const QRegion QRegion::operator&(const QRect &r) const
509 return intersected(r);
513 Applies the subtracted() function to this region and \a r. \c r1-r2
514 is equivalent to \c r1.subtracted(r2).
518 const QRegion QRegion::operator-(const QRegion &r) const
519 { return subtracted(r); }
522 Applies the xored() function to this region and \a r. \c r1^r2 is
523 equivalent to \c r1.xored(r2).
527 const QRegion QRegion::operator^(const QRegion &r) const
531 Applies the united() function to this region and \a r and assigns
532 the result to this region. \c r1|=r2 is equivalent to \c
533 {r1 = r1.united(r2)}.
537 QRegion& QRegion::operator|=(const QRegion &r)
538 { return *this = *this | r; }
541 \fn QRegion& QRegion::operator+=(const QRect &rect)
543 Returns a region that is the union of this region with the specified \a rect.
548 \fn QRegion& QRegion::operator+=(const QRegion &r)
550 Applies the united() function to this region and \a r and assigns
551 the result to this region. \c r1+=r2 is equivalent to \c
552 {r1 = r1.united(r2)}.
556 #if !defined (Q_OS_UNIX) && !defined (Q_WS_WIN)
557 QRegion& QRegion::operator+=(const QRect &r)
559 return operator+=(QRegion(r));
564 \fn QRegion& QRegion::operator&=(const QRegion &r)
566 Applies the intersected() function to this region and \a r and
567 assigns the result to this region. \c r1&=r2 is equivalent to \c
568 r1 = r1.intersected(r2).
572 QRegion& QRegion::operator&=(const QRegion &r)
573 { return *this = *this & r; }
579 #if defined (Q_OS_UNIX) || defined (Q_WS_WIN)
580 QRegion& QRegion::operator&=(const QRect &r)
582 return *this = *this & r;
585 QRegion& QRegion::operator&=(const QRect &r)
587 return *this &= (QRegion(r));
592 \fn QRegion& QRegion::operator-=(const QRegion &r)
594 Applies the subtracted() function to this region and \a r and
595 assigns the result to this region. \c r1-=r2 is equivalent to \c
596 {r1 = r1.subtracted(r2)}.
600 QRegion& QRegion::operator-=(const QRegion &r)
601 { return *this = *this - r; }
604 Applies the xored() function to this region and \a r and
605 assigns the result to this region. \c r1^=r2 is equivalent to \c
610 QRegion& QRegion::operator^=(const QRegion &r)
611 { return *this = *this ^ r; }
614 \fn bool QRegion::operator!=(const QRegion &other) const
616 Returns true if this region is different from the \a other region;
617 otherwise returns false.
621 Returns the region as a QVariant
623 QRegion::operator QVariant() const
625 return QVariant(QVariant::Region, this);
629 \fn bool QRegion::operator==(const QRegion &r) const
631 Returns true if the region is equal to \a r; otherwise returns
636 \fn bool QRegion::isNull() const
638 Use isEmpty() instead.
643 \fn void QRegion::translate(int dx, int dy)
645 Translates (moves) the region \a dx along the X axis and \a dy
650 \fn QRegion QRegion::translated(const QPoint &p) const
654 Returns a copy of the regtion that is translated \a{p}\e{.x()}
655 along the x axis and \a{p}\e{.y()} along the y axis, relative to
656 the current position. Positive values move the rectangle to the
665 Returns a copy of the region that is translated \a dx along the
666 x axis and \a dy along the y axis, relative to the current
667 position. Positive values move the region to the right and
674 QRegion::translated(int dx, int dy) const
677 ret.translate(dx, dy);
682 inline bool rect_intersects(const QRect &r1, const QRect &r2)
684 return (r1.right() >= r2.left() && r1.left() <= r2.right() &&
685 r1.bottom() >= r2.top() && r1.top() <= r2.bottom());
691 Returns true if this region intersects with \a region, otherwise
694 bool QRegion::intersects(const QRegion ®ion) const
696 if (isEmpty() || region.isEmpty())
699 if (!rect_intersects(boundingRect(), region.boundingRect()))
701 if (rectCount() == 1 && region.rectCount() == 1)
704 const QVector<QRect> myRects = rects();
705 const QVector<QRect> otherRects = region.rects();
707 for (QVector<QRect>::const_iterator i1 = myRects.constBegin(); i1 < myRects.constEnd(); ++i1)
708 for (QVector<QRect>::const_iterator i2 = otherRects.constBegin(); i2 < otherRects.constEnd(); ++i2)
709 if (rect_intersects(*i1, *i2))
715 \fn bool QRegion::intersects(const QRect &rect) const
718 Returns true if this region intersects with \a rect, otherwise
723 #if !defined (Q_OS_UNIX) && !defined (Q_WS_WIN)
728 QRegion QRegion::intersect(const QRect &r) const
730 return intersect(QRegion(r));
736 \fn int QRegion::numRects() const
739 Returns the number of rectangles that will be returned in rects().
743 \fn int QRegion::rectCount() const
746 Returns the number of rectangles that will be returned in rects().
750 \fn bool QRegion::isEmpty() const
752 Returns true if the region is empty; otherwise returns false. An
753 empty region is a region that contains no points.
756 \snippet doc/src/snippets/code/src_gui_painting_qregion_unix.cpp 0
760 \fn bool QRegion::contains(const QPoint &p) const
762 Returns true if the region contains the point \a p; otherwise
767 \fn bool QRegion::contains(const QRect &r) const
770 Returns true if the region overlaps the rectangle \a r; otherwise
775 \fn QRegion QRegion::unite(const QRegion &r) const
778 Use united(\a r) instead.
782 \fn QRegion QRegion::unite(const QRect &rect) const
786 Use united(\a rect) instead.
790 \fn QRegion QRegion::united(const QRect &rect) const
793 Returns a region which is the union of this region and the given \a rect.
795 \sa intersected(), subtracted(), xored()
799 \fn QRegion QRegion::united(const QRegion &r) const
802 Returns a region which is the union of this region and \a r.
804 \img runion.png Region Union
806 The figure shows the union of two elliptical regions.
808 \sa intersected(), subtracted(), xored()
812 \fn QRegion QRegion::intersect(const QRegion &r) const
815 Use intersected(\a r) instead.
819 \fn QRegion QRegion::intersect(const QRect &rect) const
823 Use intersected(\a rect) instead.
827 \fn QRegion QRegion::intersected(const QRect &rect) const
830 Returns a region which is the intersection of this region and the given \a rect.
832 \sa subtracted(), united(), xored()
836 \fn QRegion QRegion::intersected(const QRegion &r) const
839 Returns a region which is the intersection of this region and \a r.
841 \img rintersect.png Region Intersection
843 The figure shows the intersection of two elliptical regions.
845 \sa subtracted(), united(), xored()
849 \fn QRegion QRegion::subtract(const QRegion &r) const
852 Use subtracted(\a r) instead.
856 \fn QRegion QRegion::subtracted(const QRegion &r) const
859 Returns a region which is \a r subtracted from this region.
861 \img rsubtract.png Region Subtraction
863 The figure shows the result when the ellipse on the right is
864 subtracted from the ellipse on the left (\c {left - right}).
866 \sa intersected(), united(), xored()
870 \fn QRegion QRegion::eor(const QRegion &r) const
873 Use xored(\a r) instead.
877 \fn QRegion QRegion::xored(const QRegion &r) const
880 Returns a region which is the exclusive or (XOR) of this region
883 \img rxor.png Region XORed
885 The figure shows the exclusive or of two elliptical regions.
887 \sa intersected(), united(), subtracted()
891 \fn QRect QRegion::boundingRect() const
893 Returns the bounding rectangle of this region. An empty region
894 gives a rectangle that is QRect::isNull().
898 \fn QVector<QRect> QRegion::rects() const
900 Returns an array of non-overlapping rectangles that make up the
903 The union of all the rectangles is equal to the original region.
907 \fn void QRegion::setRects(const QRect *rects, int number)
909 Sets the region using the array of rectangles specified by \a rects and
911 The rectangles \e must be optimally Y-X sorted and follow these restrictions:
914 \o The rectangles must not intersect.
915 \o All rectangles with a given top coordinate must have the same height.
916 \o No two rectangles may abut horizontally (they should be combined
917 into a single wider rectangle in that case).
918 \o The rectangles must be sorted in ascending order, with Y as the major
919 sort key and X as the minor sort key.
922 Only some platforms have these restrictions (Qt for Embedded Linux, X11 and Mac OS X).
931 Segment(const QPoint &p)
939 return qMin(point.x(), next->point.x());
944 return qMax(point.x(), next->point.x());
947 bool overlaps(const Segment &other) const
949 return left() < other.right() && other.left() < right();
952 void connect(Segment &other)
957 horizontal = (point.y() == other.point.y());
960 void merge(Segment &other)
962 if (right() <= other.right()) {
963 QPoint p = other.point;
964 Segment *oprev = other.prev;
974 Segment *onext = other.next;
991 void mergeSegments(Segment *a, int na, Segment *b, int nb)
996 while (i != na && j != nb) {
999 const int ra = sa.right();
1000 const int rb = sb.right();
1001 if (sa.overlaps(sb))
1008 void addSegmentsToPath(Segment *segment, QPainterPath &path)
1010 Segment *current = segment;
1011 path.moveTo(current->point);
1013 current->added = true;
1015 Segment *last = current;
1016 current = current->next;
1017 while (current != segment) {
1018 if (current->horizontal != last->horizontal)
1019 path.lineTo(current->point);
1020 current->added = true;
1022 current = current->next;
1028 Q_AUTOTEST_EXPORT QPainterPath qt_regionToPath(const QRegion ®ion)
1030 QPainterPath result;
1031 if (region.rectCount() == 1) {
1032 result.addRect(region.boundingRect());
1036 const QVector<QRect> rects = region.rects();
1038 QVarLengthArray<Segment> segments;
1039 segments.resize(4 * rects.size());
1041 const QRect *rect = rects.constData();
1042 const QRect *end = rect + rects.size();
1044 int lastRowSegmentCount = 0;
1045 Segment *lastRowSegments = 0;
1047 int lastSegment = 0;
1049 while (rect != end) {
1050 const int y = rect[0].y();
1052 while (&rect[count] != end && rect[count].y() == y)
1055 for (int i = 0; i < count; ++i) {
1056 int offset = lastSegment + i;
1057 segments[offset] = Segment(rect[i].topLeft());
1058 segments[offset += count] = Segment(rect[i].topRight() + QPoint(1, 0));
1059 segments[offset += count] = Segment(rect[i].bottomRight() + QPoint(1, 1));
1060 segments[offset += count] = Segment(rect[i].bottomLeft() + QPoint(0, 1));
1062 offset = lastSegment + i;
1063 for (int j = 0; j < 4; ++j)
1064 segments[offset + j * count].connect(segments[offset + ((j + 1) % 4) * count]);
1067 if (lastRowSegments && lastY == y)
1068 mergeSegments(lastRowSegments, lastRowSegmentCount, &segments[lastSegment], count);
1070 lastRowSegments = &segments[lastSegment + 2 * count];
1071 lastRowSegmentCount = count;
1072 lastSegment += 4 * count;
1073 lastY = y + rect[0].height();
1077 for (int i = 0; i < lastSegment; ++i) {
1078 Segment *segment = &segments[i];
1079 if (!segment->added)
1080 addSegmentsToPath(segment, result);
1086 #if defined(Q_OS_UNIX) || defined(Q_WS_WIN)
1088 //#define QT_REGION_DEBUG
1093 struct QRegionPrivate {
1095 QVector<QRect> rects;
1100 inline QRegionPrivate() : numRects(0), innerArea(-1) {}
1101 inline QRegionPrivate(const QRect &r) {
1105 innerArea = r.width() * r.height();
1108 inline QRegionPrivate(const QRegionPrivate &r) {
1110 numRects = r.numRects;
1111 extents = r.extents;
1112 innerRect = r.innerRect;
1113 innerArea = r.innerArea;
1116 inline QRegionPrivate &operator=(const QRegionPrivate &r) {
1118 numRects = r.numRects;
1119 extents = r.extents;
1120 innerRect = r.innerRect;
1121 innerArea = r.innerArea;
1125 void intersect(const QRect &r);
1128 * Returns true if r is guaranteed to be fully contained in this region.
1129 * A false return value does not guarantee the opposite.
1131 inline bool contains(const QRegionPrivate &r) const {
1132 return contains(r.extents);
1135 inline bool contains(const QRect &r2) const {
1136 const QRect &r1 = innerRect;
1137 return r2.left() >= r1.left() && r2.right() <= r1.right()
1138 && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1142 * Returns true if this region is guaranteed to be fully contained in r.
1144 inline bool within(const QRect &r1) const {
1145 const QRect &r2 = extents;
1146 return r2.left() >= r1.left() && r2.right() <= r1.right()
1147 && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1150 inline void updateInnerRect(const QRect &rect) {
1151 const int area = rect.width() * rect.height();
1152 if (area > innerArea) {
1158 inline void vectorize() {
1159 if (numRects == 1) {
1166 inline void append(const QRect *r);
1167 void append(const QRegionPrivate *r);
1168 void prepend(const QRect *r);
1169 void prepend(const QRegionPrivate *r);
1170 inline bool canAppend(const QRect *r) const;
1171 inline bool canAppend(const QRegionPrivate *r) const;
1172 inline bool canPrepend(const QRect *r) const;
1173 inline bool canPrepend(const QRegionPrivate *r) const;
1175 inline bool mergeFromRight(QRect *left, const QRect *right);
1176 inline bool mergeFromLeft(QRect *left, const QRect *right);
1177 inline bool mergeFromBelow(QRect *top, const QRect *bottom,
1178 const QRect *nextToTop,
1179 const QRect *nextToBottom);
1180 inline bool mergeFromAbove(QRect *bottom, const QRect *top,
1181 const QRect *nextToBottom,
1182 const QRect *nextToTop);
1184 #ifdef QT_REGION_DEBUG
1185 void selfTest() const;
1189 static inline bool isEmptyHelper(const QRegionPrivate *preg)
1191 return !preg || preg->numRects == 0;
1194 static inline bool canMergeFromRight(const QRect *left, const QRect *right)
1196 return (right->top() == left->top()
1197 && right->bottom() == left->bottom()
1198 && right->left() <= (left->right() + 1));
1201 static inline bool canMergeFromLeft(const QRect *right, const QRect *left)
1203 return canMergeFromRight(left, right);
1206 bool QRegionPrivate::mergeFromRight(QRect *left, const QRect *right)
1208 if (canMergeFromRight(left, right)) {
1209 left->setRight(right->right());
1210 updateInnerRect(*left);
1216 bool QRegionPrivate::mergeFromLeft(QRect *right, const QRect *left)
1218 if (canMergeFromLeft(right, left)) {
1219 right->setLeft(left->left());
1220 updateInnerRect(*right);
1226 static inline bool canMergeFromBelow(const QRect *top, const QRect *bottom,
1227 const QRect *nextToTop,
1228 const QRect *nextToBottom)
1230 if (nextToTop && nextToTop->y() == top->y())
1232 if (nextToBottom && nextToBottom->y() == bottom->y())
1235 return ((top->bottom() >= (bottom->top() - 1))
1236 && top->left() == bottom->left()
1237 && top->right() == bottom->right());
1240 bool QRegionPrivate::mergeFromBelow(QRect *top, const QRect *bottom,
1241 const QRect *nextToTop,
1242 const QRect *nextToBottom)
1244 if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1245 top->setBottom(bottom->bottom());
1246 updateInnerRect(*top);
1252 bool QRegionPrivate::mergeFromAbove(QRect *bottom, const QRect *top,
1253 const QRect *nextToBottom,
1254 const QRect *nextToTop)
1256 if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1257 bottom->setTop(top->top());
1258 updateInnerRect(*bottom);
1264 static inline QRect qt_rect_intersect_normalized(const QRect &r1,
1268 r.setLeft(qMax(r1.left(), r2.left()));
1269 r.setRight(qMin(r1.right(), r2.right()));
1270 r.setTop(qMax(r1.top(), r2.top()));
1271 r.setBottom(qMin(r1.bottom(), r2.bottom()));
1275 void QRegionPrivate::intersect(const QRect &rect)
1277 Q_ASSERT(extents.intersects(rect));
1278 Q_ASSERT(numRects > 1);
1280 #ifdef QT_REGION_DEBUG
1284 const QRect r = rect.normalized();
1286 innerRect = QRect();
1289 QRect *dest = rects.data();
1290 const QRect *src = dest;
1294 *dest = qt_rect_intersect_normalized(*src++, r);
1295 if (dest->isEmpty())
1298 if (numRects == 0) {
1301 extents.setLeft(qMin(extents.left(), dest->left()));
1302 // hw: extents.top() will never change after initialization
1303 //extents.setTop(qMin(extents.top(), dest->top()));
1304 extents.setRight(qMax(extents.right(), dest->right()));
1305 extents.setBottom(qMax(extents.bottom(), dest->bottom()));
1307 const QRect *nextToLast = (numRects > 1 ? dest - 2 : 0);
1309 // mergeFromBelow inlined and optimized
1310 if (canMergeFromBelow(dest - 1, dest, nextToLast, 0)) {
1311 if (!n || src->y() != dest->y() || src->left() > r.right()) {
1312 QRect *prev = dest - 1;
1313 prev->setBottom(dest->bottom());
1314 updateInnerRect(*prev);
1319 updateInnerRect(*dest);
1323 #ifdef QT_REGION_DEBUG
1328 void QRegionPrivate::append(const QRect *r)
1330 Q_ASSERT(!r->isEmpty());
1332 QRect *myLast = (numRects == 1 ? &extents : rects.data() + (numRects - 1));
1333 if (mergeFromRight(myLast, r)) {
1335 const QRect *nextToTop = (numRects > 2 ? myLast - 2 : 0);
1336 if (mergeFromBelow(myLast - 1, myLast, nextToTop, 0))
1339 } else if (mergeFromBelow(myLast, r, (numRects > 1 ? myLast - 1 : 0), 0)) {
1344 updateInnerRect(*r);
1345 if (rects.size() < numRects)
1346 rects.resize(numRects);
1347 rects[numRects - 1] = *r;
1349 extents.setCoords(qMin(extents.left(), r->left()),
1350 qMin(extents.top(), r->top()),
1351 qMax(extents.right(), r->right()),
1352 qMax(extents.bottom(), r->bottom()));
1354 #ifdef QT_REGION_DEBUG
1359 void QRegionPrivate::append(const QRegionPrivate *r)
1361 Q_ASSERT(!isEmptyHelper(r));
1363 if (r->numRects == 1) {
1364 append(&r->extents);
1370 QRect *destRect = rects.data() + numRects;
1371 const QRect *srcRect = r->rects.constData();
1372 int numAppend = r->numRects;
1376 const QRect *rFirst = srcRect;
1377 QRect *myLast = destRect - 1;
1378 const QRect *nextToLast = (numRects > 1 ? myLast - 1 : 0);
1379 if (mergeFromRight(myLast, rFirst)) {
1382 const QRect *rNextToFirst = (numAppend > 1 ? rFirst + 2 : 0);
1383 if (mergeFromBelow(myLast, rFirst + 1, nextToLast, rNextToFirst)) {
1388 nextToLast = (numRects > 2 ? myLast - 2 : 0);
1389 rNextToFirst = (numAppend > 0 ? srcRect : 0);
1390 if (mergeFromBelow(myLast - 1, myLast, nextToLast, rNextToFirst)) {
1395 } else if (mergeFromBelow(myLast, rFirst, nextToLast, rFirst + 1)) {
1401 // append rectangles
1402 if (numAppend > 0) {
1403 const int newNumRects = numRects + numAppend;
1404 if (newNumRects > rects.size()) {
1405 rects.resize(newNumRects);
1406 destRect = rects.data() + numRects;
1408 memcpy(destRect, srcRect, numAppend * sizeof(QRect));
1410 numRects = newNumRects;
1413 // update inner rectangle
1414 if (innerArea < r->innerArea) {
1415 innerArea = r->innerArea;
1416 innerRect = r->innerRect;
1420 destRect = &extents;
1421 srcRect = &r->extents;
1422 extents.setCoords(qMin(destRect->left(), srcRect->left()),
1423 qMin(destRect->top(), srcRect->top()),
1424 qMax(destRect->right(), srcRect->right()),
1425 qMax(destRect->bottom(), srcRect->bottom()));
1427 #ifdef QT_REGION_DEBUG
1432 void QRegionPrivate::prepend(const QRegionPrivate *r)
1434 Q_ASSERT(!isEmptyHelper(r));
1436 if (r->numRects == 1) {
1437 prepend(&r->extents);
1443 int numPrepend = r->numRects;
1448 QRect *myFirst = rects.data();
1449 const QRect *nextToFirst = (numRects > 1 ? myFirst + 1 : 0);
1450 const QRect *rLast = r->rects.constData() + r->numRects - 1;
1451 const QRect *rNextToLast = (r->numRects > 1 ? rLast - 1 : 0);
1452 if (mergeFromLeft(myFirst, rLast)) {
1455 rNextToLast = (numPrepend > 1 ? rLast - 1 : 0);
1456 if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1461 nextToFirst = (numRects > 2? myFirst + 2 : 0);
1462 rNextToLast = (numPrepend > 0 ? rLast : 0);
1463 if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, rNextToLast)) {
1468 } else if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1473 if (numPrepend > 0) {
1474 const int newNumRects = numRects + numPrepend;
1475 if (newNumRects > rects.size())
1476 rects.resize(newNumRects);
1478 // move existing rectangles
1479 memmove(rects.data() + numPrepend, rects.constData() + numSkip,
1480 numRects * sizeof(QRect));
1482 // prepend new rectangles
1483 memcpy(rects.data(), r->rects.constData(), numPrepend * sizeof(QRect));
1485 numRects = newNumRects;
1488 // update inner rectangle
1489 if (innerArea < r->innerArea) {
1490 innerArea = r->innerArea;
1491 innerRect = r->innerRect;
1495 extents.setCoords(qMin(extents.left(), r->extents.left()),
1496 qMin(extents.top(), r->extents.top()),
1497 qMax(extents.right(), r->extents.right()),
1498 qMax(extents.bottom(), r->extents.bottom()));
1500 #ifdef QT_REGION_DEBUG
1505 void QRegionPrivate::prepend(const QRect *r)
1507 Q_ASSERT(!r->isEmpty());
1509 QRect *myFirst = (numRects == 1 ? &extents : rects.data());
1510 if (mergeFromLeft(myFirst, r)) {
1512 const QRect *nextToFirst = (numRects > 2 ? myFirst + 2 : 0);
1513 if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, 0)) {
1515 memmove(rects.data(), rects.constData() + 1,
1516 numRects * sizeof(QRect));
1519 } else if (mergeFromAbove(myFirst, r, (numRects > 1 ? myFirst + 1 : 0), 0)) {
1524 updateInnerRect(*r);
1527 extents.setCoords(qMin(extents.left(), r->left()),
1528 qMin(extents.top(), r->top()),
1529 qMax(extents.right(), r->right()),
1530 qMax(extents.bottom(), r->bottom()));
1532 #ifdef QT_REGION_DEBUG
1537 bool QRegionPrivate::canAppend(const QRect *r) const
1539 Q_ASSERT(!r->isEmpty());
1541 const QRect *myLast = (numRects == 1) ? &extents : (rects.constData() + (numRects - 1));
1542 if (r->top() > myLast->bottom())
1544 if (r->top() == myLast->top()
1545 && r->height() == myLast->height()
1546 && r->left() > myLast->right())
1554 bool QRegionPrivate::canAppend(const QRegionPrivate *r) const
1556 return canAppend(r->numRects == 1 ? &r->extents : r->rects.constData());
1559 bool QRegionPrivate::canPrepend(const QRect *r) const
1561 Q_ASSERT(!r->isEmpty());
1563 const QRect *myFirst = (numRects == 1) ? &extents : rects.constData();
1564 if (r->bottom() < myFirst->top()) // not overlapping
1566 if (r->top() == myFirst->top()
1567 && r->height() == myFirst->height()
1568 && r->right() < myFirst->left())
1576 bool QRegionPrivate::canPrepend(const QRegionPrivate *r) const
1578 return canPrepend(r->numRects == 1 ? &r->extents : r->rects.constData() + r->numRects - 1);
1581 #ifdef QT_REGION_DEBUG
1582 void QRegionPrivate::selfTest() const
1584 if (numRects == 0) {
1585 Q_ASSERT(extents.isEmpty());
1586 Q_ASSERT(innerRect.isEmpty());
1590 Q_ASSERT(innerArea == (innerRect.width() * innerRect.height()));
1592 if (numRects == 1) {
1593 Q_ASSERT(innerRect == extents);
1594 Q_ASSERT(!innerRect.isEmpty());
1598 for (int i = 0; i < numRects; ++i) {
1599 const QRect r = rects.at(i);
1600 if ((r.width() * r.height()) > innerArea)
1601 qDebug() << "selfTest(): innerRect" << innerRect << '<' << r;
1604 QRect r = rects.first();
1605 for (int i = 1; i < numRects; ++i) {
1606 const QRect r2 = rects.at(i);
1607 Q_ASSERT(!r2.isEmpty());
1608 if (r2.y() == r.y()) {
1609 Q_ASSERT(r.bottom() == r2.bottom());
1610 Q_ASSERT(r.right() < (r2.left() + 1));
1612 Q_ASSERT(r2.y() >= r.bottom());
1617 #endif // QT_REGION_DEBUG
1619 #if defined(Q_WS_X11)
1620 QT_BEGIN_INCLUDE_NAMESPACE
1621 # include "qregion_x11.cpp"
1622 QT_END_INCLUDE_NAMESPACE
1623 #elif defined(Q_WS_MAC)
1624 QT_BEGIN_INCLUDE_NAMESPACE
1625 # include "qregion_mac.cpp"
1626 QT_END_INCLUDE_NAMESPACE
1627 #elif defined(Q_WS_WIN)
1628 QT_BEGIN_INCLUDE_NAMESPACE
1629 # include "qregion_win.cpp"
1630 QT_END_INCLUDE_NAMESPACE
1631 #elif defined(Q_WS_QWS) || defined(Q_WS_QPA)
1632 static QRegionPrivate qrp;
1633 QRegion::QRegionData QRegion::shared_empty = {Q_BASIC_ATOMIC_INITIALIZER(1), &qrp};
1636 typedef void (*OverlapFunc)(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1637 register const QRect *r2, const QRect *r2End, register int y1, register int y2);
1638 typedef void (*NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
1639 register int y1, register int y2);
1641 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2);
1642 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest);
1643 static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
1644 OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
1645 NonOverlapFunc nonOverlap2Func);
1647 #define RectangleOut 0
1648 #define RectangleIn 1
1649 #define RectanglePart 2
1650 #define EvenOddRule 0
1651 #define WindingRule 1
1653 // START OF region.h extract
1654 /* $XConsortium: region.h,v 11.14 94/04/17 20:22:20 rws Exp $ */
1655 /************************************************************************
1657 Copyright (c) 1987 X Consortium
1659 Permission is hereby granted, free of charge, to any person obtaining a copy
1660 of this software and associated documentation files (the "Software"), to deal
1661 in the Software without restriction, including without limitation the rights
1662 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1663 copies of the Software, and to permit persons to whom the Software is
1664 furnished to do so, subject to the following conditions:
1666 The above copyright notice and this permission notice shall be included in
1667 all copies or substantial portions of the Software.
1669 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1670 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1671 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1672 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1673 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1674 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1676 Except as contained in this notice, the name of the X Consortium shall not be
1677 used in advertising or otherwise to promote the sale, use or other dealings
1678 in this Software without prior written authorization from the X Consortium.
1681 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1685 Permission to use, copy, modify, and distribute this software and its
1686 documentation for any purpose and without fee is hereby granted,
1687 provided that the above copyright notice appear in all copies and that
1688 both that copyright notice and this permission notice appear in
1689 supporting documentation, and that the name of Digital not be
1690 used in advertising or publicity pertaining to distribution of the
1691 software without specific, written prior permission.
1693 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1694 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1695 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1696 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1697 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1698 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1701 ************************************************************************/
1706 QT_BEGIN_INCLUDE_NAMESPACE
1708 QT_END_INCLUDE_NAMESPACE
1710 /* 1 if two BOXes overlap.
1711 * 0 if two BOXes do not overlap.
1712 * Remember, x2 and y2 are not in the region
1714 #define EXTENTCHECK(r1, r2) \
1715 ((r1)->right() >= (r2)->left() && \
1716 (r1)->left() <= (r2)->right() && \
1717 (r1)->bottom() >= (r2)->top() && \
1718 (r1)->top() <= (r2)->bottom())
1721 * update region extents
1723 #define EXTENTS(r,idRect){\
1724 if((r)->left() < (idRect)->extents.left())\
1725 (idRect)->extents.setLeft((r)->left());\
1726 if((r)->top() < (idRect)->extents.top())\
1727 (idRect)->extents.setTop((r)->top());\
1728 if((r)->right() > (idRect)->extents.right())\
1729 (idRect)->extents.setRight((r)->right());\
1730 if((r)->bottom() > (idRect)->extents.bottom())\
1731 (idRect)->extents.setBottom((r)->bottom());\
1735 * Check to see if there is enough memory in the present region.
1737 #define MEMCHECK(dest, rect, firstrect){\
1738 if ((dest).numRects >= ((dest).rects.size()-1)){\
1739 firstrect.resize(firstrect.size() * 2); \
1740 (rect) = (firstrect).data() + (dest).numRects;\
1746 * number of points to buffer before sending them off
1747 * to scanlines(): Must be an even number
1749 #define NUMPTSTOBUFFER 200
1752 * used to allocate buffers for points and link
1753 * the buffers together
1755 typedef struct _POINTBLOCK {
1756 int data[NUMPTSTOBUFFER * sizeof(QPoint)];
1758 struct _POINTBLOCK *next;
1762 // END OF region.h extract
1764 // START OF Region.c extract
1765 /* $XConsortium: Region.c /main/30 1996/10/22 14:21:24 kaleb $ */
1766 /************************************************************************
1768 Copyright (c) 1987, 1988 X Consortium
1770 Permission is hereby granted, free of charge, to any person obtaining a copy
1771 of this software and associated documentation files (the "Software"), to deal
1772 in the Software without restriction, including without limitation the rights
1773 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1774 copies of the Software, and to permit persons to whom the Software is
1775 furnished to do so, subject to the following conditions:
1777 The above copyright notice and this permission notice shall be included in
1778 all copies or substantial portions of the Software.
1780 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1781 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1782 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1783 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1784 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1785 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1787 Except as contained in this notice, the name of the X Consortium shall not be
1788 used in advertising or otherwise to promote the sale, use or other dealings
1789 in this Software without prior written authorization from the X Consortium.
1792 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
1796 Permission to use, copy, modify, and distribute this software and its
1797 documentation for any purpose and without fee is hereby granted,
1798 provided that the above copyright notice appear in all copies and that
1799 both that copyright notice and this permission notice appear in
1800 supporting documentation, and that the name of Digital not be
1801 used in advertising or publicity pertaining to distribution of the
1802 software without specific, written prior permission.
1804 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1805 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1806 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1807 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1808 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1809 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1812 ************************************************************************/
1814 * The functions in this file implement the Region abstraction, similar to one
1815 * used in the X11 sample server. A Region is simply an area, as the name
1816 * implies, and is implemented as a "y-x-banded" array of rectangles. To
1817 * explain: Each Region is made up of a certain number of rectangles sorted
1818 * by y coordinate first, and then by x coordinate.
1820 * Furthermore, the rectangles are banded such that every rectangle with a
1821 * given upper-left y coordinate (y1) will have the same lower-right y
1822 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
1823 * will span the entire vertical distance of the band. This means that some
1824 * areas that could be merged into a taller rectangle will be represented as
1825 * several shorter rectangles to account for shorter rectangles to its left
1826 * or right but within its "vertical scope".
1828 * An added constraint on the rectangles is that they must cover as much
1829 * horizontal area as possible. E.g. no two rectangles in a band are allowed
1832 * Whenever possible, bands will be merged together to cover a greater vertical
1833 * distance (and thus reduce the number of rectangles). Two bands can be merged
1834 * only if the bottom of one touches the top of the other and they have
1835 * rectangles in the same places (of the same width, of course). This maintains
1836 * the y-x-banding that's so nice to have...
1838 /* $XFree86: xc/lib/X11/Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */
1840 static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source,
1841 QRegionPrivate &dest)
1843 if (rect->isEmpty())
1846 Q_ASSERT(EqualRegion(source, &dest));
1848 if (dest.numRects == 0) {
1849 dest = QRegionPrivate(*rect);
1850 } else if (dest.canAppend(rect)) {
1853 QRegionPrivate p(*rect);
1854 UnionRegion(&p, source, dest);
1859 *-----------------------------------------------------------------------
1861 * Reset the extents and innerRect of a region to what they should be.
1862 * Called by miSubtract and miIntersect b/c they can't figure it out
1863 * along the way or do so easily, as miUnion can.
1869 * The region's 'extents' and 'innerRect' structure is overwritten.
1871 *-----------------------------------------------------------------------
1873 static void miSetExtents(QRegionPrivate &dest)
1875 register const QRect *pBox,
1877 register QRect *pExtents;
1879 dest.innerRect.setCoords(0, 0, -1, -1);
1880 dest.innerArea = -1;
1881 if (dest.numRects == 0) {
1882 dest.extents.setCoords(0, 0, -1, -1);
1886 pExtents = &dest.extents;
1887 if (dest.rects.isEmpty())
1888 pBox = &dest.extents;
1890 pBox = dest.rects.constData();
1891 pBoxEnd = pBox + dest.numRects - 1;
1894 * Since pBox is the first rectangle in the region, it must have the
1895 * smallest y1 and since pBoxEnd is the last rectangle in the region,
1896 * it must have the largest y2, because of banding. Initialize x1 and
1897 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
1900 pExtents->setLeft(pBox->left());
1901 pExtents->setTop(pBox->top());
1902 pExtents->setRight(pBoxEnd->right());
1903 pExtents->setBottom(pBoxEnd->bottom());
1905 Q_ASSERT(pExtents->top() <= pExtents->bottom());
1906 while (pBox <= pBoxEnd) {
1907 if (pBox->left() < pExtents->left())
1908 pExtents->setLeft(pBox->left());
1909 if (pBox->right() > pExtents->right())
1910 pExtents->setRight(pBox->right());
1911 dest.updateInnerRect(*pBox);
1914 Q_ASSERT(pExtents->left() <= pExtents->right());
1917 /* TranslateRegion(pRegion, x, y)
1922 static void OffsetRegion(register QRegionPrivate ®ion, register int x, register int y)
1924 if (region.rects.size()) {
1925 register QRect *pbox = region.rects.data();
1926 register int nbox = region.numRects;
1929 pbox->translate(x, y);
1933 region.extents.translate(x, y);
1934 region.innerRect.translate(x, y);
1937 /*======================================================================
1938 * Region Intersection
1939 *====================================================================*/
1941 *-----------------------------------------------------------------------
1943 * Handle an overlapping band for miIntersect.
1949 * Rectangles may be added to the region.
1951 *-----------------------------------------------------------------------
1953 static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1954 register const QRect *r2, const QRect *r2End, int y1, int y2)
1958 register QRect *pNextRect;
1960 pNextRect = dest.rects.data() + dest.numRects;
1962 while (r1 != r1End && r2 != r2End) {
1963 x1 = qMax(r1->left(), r2->left());
1964 x2 = qMin(r1->right(), r2->right());
1967 * If there's any overlap between the two rectangles, add that
1968 * overlap to the new region.
1969 * There's no need to check for subsumption because the only way
1970 * such a need could arise is if some region has two rectangles
1971 * right next to each other. Since that should never happen...
1975 MEMCHECK(dest, pNextRect, dest.rects)
1976 pNextRect->setCoords(x1, y1, x2, y2);
1982 * Need to advance the pointers. Shift the one that extends
1983 * to the right the least, since the other still has a chance to
1984 * overlap with that region's next rectangle, if you see what I mean.
1986 if (r1->right() < r2->right()) {
1988 } else if (r2->right() < r1->right()) {
1997 /*======================================================================
1998 * Generic Region Operator
1999 *====================================================================*/
2002 *-----------------------------------------------------------------------
2004 * Attempt to merge the boxes in the current band with those in the
2005 * previous one. Used only by miRegionOp.
2008 * The new index for the previous band.
2011 * If coalescing takes place:
2012 * - rectangles in the previous band will have their y2 fields
2014 * - dest.numRects will be decreased.
2016 *-----------------------------------------------------------------------
2018 static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
2020 register QRect *pPrevBox; /* Current box in previous band */
2021 register QRect *pCurBox; /* Current box in current band */
2022 register QRect *pRegEnd; /* End of region */
2023 int curNumRects; /* Number of rectangles in current band */
2024 int prevNumRects; /* Number of rectangles in previous band */
2025 int bandY1; /* Y1 coordinate for current band */
2026 QRect *rData = dest.rects.data();
2028 pRegEnd = rData + dest.numRects;
2030 pPrevBox = rData + prevStart;
2031 prevNumRects = curStart - prevStart;
2034 * Figure out how many rectangles are in the current band. Have to do
2035 * this because multiple bands could have been added in miRegionOp
2036 * at the end when one region has been exhausted.
2038 pCurBox = rData + curStart;
2039 bandY1 = pCurBox->top();
2040 for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
2044 if (pCurBox != pRegEnd) {
2046 * If more than one band was added, we have to find the start
2047 * of the last band added so the next coalescing job can start
2048 * at the right place... (given when multiple bands are added,
2049 * this may be pointless -- see above).
2052 while ((pRegEnd - 1)->top() == pRegEnd->top())
2054 curStart = pRegEnd - rData;
2055 pRegEnd = rData + dest.numRects;
2058 if (curNumRects == prevNumRects && curNumRects != 0) {
2059 pCurBox -= curNumRects;
2061 * The bands may only be coalesced if the bottom of the previous
2062 * matches the top scanline of the current.
2064 if (pPrevBox->bottom() == pCurBox->top() - 1) {
2066 * Make sure the bands have boxes in the same places. This
2067 * assumes that boxes have been added in such a way that they
2068 * cover the most area possible. I.e. two boxes in a band must
2069 * have some horizontal space between them.
2072 if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
2073 // The bands don't line up so they can't be coalesced.
2079 } while (prevNumRects != 0);
2081 dest.numRects -= curNumRects;
2082 pCurBox -= curNumRects;
2083 pPrevBox -= curNumRects;
2086 * The bands may be merged, so set the bottom y of each box
2087 * in the previous band to that of the corresponding box in
2091 pPrevBox->setBottom(pCurBox->bottom());
2092 dest.updateInnerRect(*pPrevBox);
2096 } while (curNumRects != 0);
2099 * If only one band was added to the region, we have to backup
2100 * curStart to the start of the previous band.
2102 * If more than one band was added to the region, copy the
2103 * other bands down. The assumption here is that the other bands
2104 * came from the same region as the current one and no further
2105 * coalescing can be done on them since it's all been done
2106 * already... curStart is already in the right place.
2108 if (pCurBox == pRegEnd) {
2109 curStart = prevStart;
2112 *pPrevBox++ = *pCurBox++;
2113 dest.updateInnerRect(*pPrevBox);
2114 } while (pCurBox != pRegEnd);
2122 *-----------------------------------------------------------------------
2124 * Apply an operation to two regions. Called by miUnion, miInverse,
2125 * miSubtract, miIntersect...
2131 * The new region is overwritten.
2134 * The idea behind this function is to view the two regions as sets.
2135 * Together they cover a rectangle of area that this function divides
2136 * into horizontal bands where points are covered only by one region
2137 * or by both. For the first case, the nonOverlapFunc is called with
2138 * each the band and the band's upper and lower extents. For the
2139 * second, the overlapFunc is called to process the entire band. It
2140 * is responsible for clipping the rectangles in the band, though
2141 * this function provides the boundaries.
2142 * At the end of each band, the new region is coalesced, if possible,
2143 * to reduce the number of rectangles in the region.
2145 *-----------------------------------------------------------------------
2147 static void miRegionOp(register QRegionPrivate &dest,
2148 const QRegionPrivate *reg1, const QRegionPrivate *reg2,
2149 OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
2150 NonOverlapFunc nonOverlap2Func)
2152 register const QRect *r1; // Pointer into first region
2153 register const QRect *r2; // Pointer into 2d region
2154 const QRect *r1End; // End of 1st region
2155 const QRect *r2End; // End of 2d region
2156 register int ybot; // Bottom of intersection
2157 register int ytop; // Top of intersection
2158 int prevBand; // Index of start of previous band in dest
2159 int curBand; // Index of start of current band in dest
2160 register const QRect *r1BandEnd; // End of current band in r1
2161 register const QRect *r2BandEnd; // End of current band in r2
2162 int top; // Top of non-overlapping band
2163 int bot; // Bottom of non-overlapping band
2167 * set r1, r2, r1End and r2End appropriately, preserve the important
2168 * parts of the destination region until the end in case it's one of
2169 * the two source regions, then mark the "new" region empty, allocating
2170 * another array of rectangles for it to use.
2172 if (reg1->numRects == 1)
2173 r1 = ®1->extents;
2175 r1 = reg1->rects.constData();
2176 if (reg2->numRects == 1)
2177 r2 = ®2->extents;
2179 r2 = reg2->rects.constData();
2181 r1End = r1 + reg1->numRects;
2182 r2End = r2 + reg2->numRects;
2186 QVector<QRect> oldRects = dest.rects;
2191 * Allocate a reasonable number of rectangles for the new region. The idea
2192 * is to allocate enough so the individual functions don't need to
2193 * reallocate and copy the array, which is time consuming, yet we don't
2194 * have to worry about using too much memory. I hope to be able to
2195 * nuke the realloc() at the end of this function eventually.
2197 dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);
2200 * Initialize ybot and ytop.
2201 * In the upcoming loop, ybot and ytop serve different functions depending
2202 * on whether the band being handled is an overlapping or non-overlapping
2204 * In the case of a non-overlapping band (only one of the regions
2205 * has points in the band), ybot is the bottom of the most recent
2206 * intersection and thus clips the top of the rectangles in that band.
2207 * ytop is the top of the next intersection between the two regions and
2208 * serves to clip the bottom of the rectangles in the current band.
2209 * For an overlapping band (where the two regions intersect), ytop clips
2210 * the top of the rectangles of both regions and ybot clips the bottoms.
2212 if (reg1->extents.top() < reg2->extents.top())
2213 ybot = reg1->extents.top() - 1;
2215 ybot = reg2->extents.top() - 1;
2218 * prevBand serves to mark the start of the previous band so rectangles
2219 * can be coalesced into larger rectangles. qv. miCoalesce, above.
2220 * In the beginning, there is no previous band, so prevBand == curBand
2221 * (curBand is set later on, of course, but the first band will always
2222 * start at index 0). prevBand and curBand must be indices because of
2223 * the possible expansion, and resultant moving, of the new region's
2224 * array of rectangles.
2229 curBand = dest.numRects;
2232 * This algorithm proceeds one source-band (as opposed to a
2233 * destination band, which is determined by where the two regions
2234 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
2235 * rectangle after the last one in the current band for their
2236 * respective regions.
2239 while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
2243 while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
2247 * First handle the band that doesn't intersect, if any.
2249 * Note that attention is restricted to one band in the
2250 * non-intersecting region at once, so if a region has n
2251 * bands between the current position and the next place it overlaps
2252 * the other, this entire loop will be passed through n times.
2254 if (r1->top() < r2->top()) {
2255 top = qMax(r1->top(), ybot + 1);
2256 bot = qMin(r1->bottom(), r2->top() - 1);
2258 if (nonOverlap1Func != 0 && bot >= top)
2259 (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
2261 } else if (r2->top() < r1->top()) {
2262 top = qMax(r2->top(), ybot + 1);
2263 bot = qMin(r2->bottom(), r1->top() - 1);
2265 if (nonOverlap2Func != 0 && bot >= top)
2266 (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
2273 * If any rectangles got added to the region, try and coalesce them
2274 * with rectangles from the previous band. Note we could just do
2275 * this test in miCoalesce, but some machines incur a not
2276 * inconsiderable cost for function calls, so...
2278 if (dest.numRects != curBand)
2279 prevBand = miCoalesce(dest, prevBand, curBand);
2282 * Now see if we've hit an intersecting band. The two bands only
2283 * intersect if ybot >= ytop
2285 ybot = qMin(r1->bottom(), r2->bottom());
2286 curBand = dest.numRects;
2288 (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
2290 if (dest.numRects != curBand)
2291 prevBand = miCoalesce(dest, prevBand, curBand);
2294 * If we've finished with a band (y2 == ybot) we skip forward
2295 * in the region to the next band.
2297 if (r1->bottom() == ybot)
2299 if (r2->bottom() == ybot)
2301 } while (r1 != r1End && r2 != r2End);
2304 * Deal with whichever region still has rectangles left.
2306 curBand = dest.numRects;
2308 if (nonOverlap1Func != 0) {
2311 while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
2313 (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
2315 } while (r1 != r1End);
2317 } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
2320 while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
2322 (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
2324 } while (r2 != r2End);
2327 if (dest.numRects != curBand)
2328 (void)miCoalesce(dest, prevBand, curBand);
2331 * A bit of cleanup. To keep regions from growing without bound,
2332 * we shrink the array of rectangles to match the new number of
2333 * rectangles in the region.
2335 * Only do this stuff if the number of rectangles allocated is more than
2336 * twice the number of rectangles in the region (a simple optimization).
2338 if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
2339 dest.rects.resize(dest.numRects);
2342 /*======================================================================
2344 *====================================================================*/
2347 *-----------------------------------------------------------------------
2349 * Handle a non-overlapping band for the union operation. Just
2350 * Adds the rectangles into the region. Doesn't have to check for
2351 * subsumption or anything.
2357 * dest.numRects is incremented and the final rectangles overwritten
2358 * with the rectangles we're passed.
2360 *-----------------------------------------------------------------------
2363 static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
2364 register int y1, register int y2)
2366 register QRect *pNextRect;
2368 pNextRect = dest.rects.data() + dest.numRects;
2373 Q_ASSERT(r->left() <= r->right());
2374 MEMCHECK(dest, pNextRect, dest.rects)
2375 pNextRect->setCoords(r->left(), y1, r->right(), y2);
2384 *-----------------------------------------------------------------------
2386 * Handle an overlapping band for the union operation. Picks the
2387 * left-most rectangle each time and merges it into the region.
2393 * Rectangles are overwritten in dest.rects and dest.numRects will
2396 *-----------------------------------------------------------------------
2399 static void miUnionO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2400 register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2402 register QRect *pNextRect;
2404 pNextRect = dest.rects.data() + dest.numRects;
2406 #define MERGERECT(r) \
2407 if ((dest.numRects != 0) && \
2408 (pNextRect[-1].top() == y1) && \
2409 (pNextRect[-1].bottom() == y2) && \
2410 (pNextRect[-1].right() >= r->left()-1)) { \
2411 if (pNextRect[-1].right() < r->right()) { \
2412 pNextRect[-1].setRight(r->right()); \
2413 dest.updateInnerRect(pNextRect[-1]); \
2414 Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
2417 MEMCHECK(dest, pNextRect, dest.rects) \
2418 pNextRect->setCoords(r->left(), y1, r->right(), y2); \
2419 dest.updateInnerRect(*pNextRect); \
2426 while (r1 != r1End && r2 != r2End) {
2427 if (r1->left() < r2->left()) {
2437 } while (r1 != r1End);
2439 while (r2 != r2End) {
2445 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
2447 Q_ASSERT(!isEmptyHelper(reg1) && !isEmptyHelper(reg2));
2448 Q_ASSERT(!reg1->contains(*reg2));
2449 Q_ASSERT(!reg2->contains(*reg1));
2450 Q_ASSERT(!EqualRegion(reg1, reg2));
2451 Q_ASSERT(!reg1->canAppend(reg2));
2452 Q_ASSERT(!reg2->canAppend(reg1));
2454 if (reg1->innerArea > reg2->innerArea) {
2455 dest.innerArea = reg1->innerArea;
2456 dest.innerRect = reg1->innerRect;
2458 dest.innerArea = reg2->innerArea;
2459 dest.innerRect = reg2->innerRect;
2461 miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
2463 dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
2464 qMin(reg1->extents.top(), reg2->extents.top()),
2465 qMax(reg1->extents.right(), reg2->extents.right()),
2466 qMax(reg1->extents.bottom(), reg2->extents.bottom()));
2469 /*======================================================================
2470 * Region Subtraction
2471 *====================================================================*/
2474 *-----------------------------------------------------------------------
2476 * Deal with non-overlapping band for subtraction. Any parts from
2477 * region 2 we discard. Anything from region 1 we add to the region.
2483 * dest may be affected.
2485 *-----------------------------------------------------------------------
2488 static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r,
2489 const QRect *rEnd, register int y1, register int y2)
2491 register QRect *pNextRect;
2493 pNextRect = dest.rects.data() + dest.numRects;
2498 Q_ASSERT(r->left() <= r->right());
2499 MEMCHECK(dest, pNextRect, dest.rects)
2500 pNextRect->setCoords(r->left(), y1, r->right(), y2);
2508 *-----------------------------------------------------------------------
2510 * Overlapping band subtraction. x1 is the left-most point not yet
2517 * dest may have rectangles added to it.
2519 *-----------------------------------------------------------------------
2522 static void miSubtractO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2523 register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2525 register QRect *pNextRect;
2531 pNextRect = dest.rects.data() + dest.numRects;
2533 while (r1 != r1End && r2 != r2End) {
2534 if (r2->right() < x1) {
2536 * Subtrahend missed the boat: go to next subtrahend.
2539 } else if (r2->left() <= x1) {
2541 * Subtrahend precedes minuend: nuke left edge of minuend.
2543 x1 = r2->right() + 1;
2544 if (x1 > r1->right()) {
2546 * Minuend completely covered: advance to next minuend and
2547 * reset left fence to edge of new minuend.
2553 // Subtrahend now used up since it doesn't extend beyond minuend
2556 } else if (r2->left() <= r1->right()) {
2558 * Left part of subtrahend covers part of minuend: add uncovered
2559 * part of minuend to region and skip to next subtrahend.
2561 Q_ASSERT(x1 < r2->left());
2562 MEMCHECK(dest, pNextRect, dest.rects)
2563 pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
2567 x1 = r2->right() + 1;
2568 if (x1 > r1->right()) {
2570 * Minuend used up: advance to new...
2576 // Subtrahend used up
2581 * Minuend used up: add any remaining piece before advancing.
2583 if (r1->right() >= x1) {
2584 MEMCHECK(dest, pNextRect, dest.rects)
2585 pNextRect->setCoords(x1, y1, r1->right(), y2);
2596 * Add remaining minuend rectangles to region.
2598 while (r1 != r1End) {
2599 Q_ASSERT(x1 <= r1->right());
2600 MEMCHECK(dest, pNextRect, dest.rects)
2601 pNextRect->setCoords(x1, y1, r1->right(), y2);
2612 *-----------------------------------------------------------------------
2614 * Subtract regS from regM and leave the result in regD.
2615 * S stands for subtrahend, M for minuend and D for difference.
2618 * regD is overwritten.
2620 *-----------------------------------------------------------------------
2623 static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS,
2624 register QRegionPrivate &dest)
2626 Q_ASSERT(!isEmptyHelper(regM));
2627 Q_ASSERT(!isEmptyHelper(regS));
2628 Q_ASSERT(EXTENTCHECK(®M->extents, ®S->extents));
2629 Q_ASSERT(!regS->contains(*regM));
2630 Q_ASSERT(!EqualRegion(regM, regS));
2632 miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);
2635 * Can't alter dest's extents before we call miRegionOp because
2636 * it might be one of the source regions and miRegionOp depends
2637 * on the extents of those regions being the unaltered. Besides, this
2638 * way there's no checking against rectangles that will be nuked
2639 * due to coalescing, so we have to examine fewer rectangles.
2644 static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
2646 Q_ASSERT(!isEmptyHelper(sra) && !isEmptyHelper(srb));
2647 Q_ASSERT(EXTENTCHECK(&sra->extents, &srb->extents));
2648 Q_ASSERT(!EqualRegion(sra, srb));
2650 QRegionPrivate tra, trb;
2652 if (!srb->contains(*sra))
2653 SubtractRegion(sra, srb, tra);
2654 if (!sra->contains(*srb))
2655 SubtractRegion(srb, sra, trb);
2657 Q_ASSERT(isEmptyHelper(&trb) || !tra.contains(trb));
2658 Q_ASSERT(isEmptyHelper(&tra) || !trb.contains(tra));
2660 if (isEmptyHelper(&tra)) {
2662 } else if (isEmptyHelper(&trb)) {
2664 } else if (tra.canAppend(&trb)) {
2667 } else if (trb.canAppend(&tra)) {
2671 UnionRegion(&tra, &trb, dest);
2676 * Check to see if two regions are equal
2678 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
2680 if (r1->numRects != r2->numRects) {
2682 } else if (r1->numRects == 0) {
2684 } else if (r1->extents != r2->extents) {
2686 } else if (r1->numRects == 1 && r2->numRects == 1) {
2687 return true; // equality tested in previous if-statement
2689 const QRect *rr1 = (r1->numRects == 1) ? &r1->extents : r1->rects.constData();
2690 const QRect *rr2 = (r2->numRects == 1) ? &r2->extents : r2->rects.constData();
2691 for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
2700 static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
2704 if (isEmptyHelper(pRegion))
2706 if (!pRegion->extents.contains(x, y))
2708 if (pRegion->numRects == 1)
2709 return pRegion->extents.contains(x, y);
2710 if (pRegion->innerRect.contains(x, y))
2712 for (i = 0; i < pRegion->numRects; ++i) {
2713 if (pRegion->rects[i].contains(x, y))
2719 static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
2721 register const QRect *pbox;
2722 register const QRect *pboxEnd;
2723 QRect rect(rx, ry, rwidth, rheight);
2724 register QRect *prect = ▭
2725 int partIn, partOut;
2727 if (!region || region->numRects == 0 || !EXTENTCHECK(®ion->extents, prect))
2728 return RectangleOut;
2733 /* can stop when both partOut and partIn are true, or we reach prect->y2 */
2734 pbox = (region->numRects == 1) ? ®ion->extents : region->rects.constData();
2735 pboxEnd = pbox + region->numRects;
2736 for (; pbox < pboxEnd; ++pbox) {
2737 if (pbox->bottom() < ry)
2740 if (pbox->top() > ry) {
2742 if (partIn || pbox->top() > prect->bottom())
2747 if (pbox->right() < rx)
2748 continue; /* not far enough over yet */
2750 if (pbox->left() > rx) {
2751 partOut = true; /* missed part of rectangle to left */
2756 if (pbox->left() <= prect->right()) {
2757 partIn = true; /* definitely overlap */
2762 if (pbox->right() >= prect->right()) {
2763 ry = pbox->bottom() + 1; /* finished with this band */
2764 if (ry > prect->bottom())
2766 rx = prect->left(); /* reset x out to left again */
2769 * Because boxes in a band are maximal width, if the first box
2770 * to overlap the rectangle doesn't completely cover it in that
2771 * band, the rectangle must be partially out, since some of it
2772 * will be uncovered in that band. partIn will have been set true
2778 return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
2780 // END OF Region.c extract
2781 // START OF poly.h extract
2782 /* $XConsortium: poly.h,v 1.4 94/04/17 20:22:19 rws Exp $ */
2783 /************************************************************************
2785 Copyright (c) 1987 X Consortium
2787 Permission is hereby granted, free of charge, to any person obtaining a copy
2788 of this software and associated documentation files (the "Software"), to deal
2789 in the Software without restriction, including without limitation the rights
2790 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2791 copies of the Software, and to permit persons to whom the Software is
2792 furnished to do so, subject to the following conditions:
2794 The above copyright notice and this permission notice shall be included in
2795 all copies or substantial portions of the Software.
2797 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2798 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2799 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
2800 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
2801 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
2802 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
2804 Except as contained in this notice, the name of the X Consortium shall not be
2805 used in advertising or otherwise to promote the sale, use or other dealings
2806 in this Software without prior written authorization from the X Consortium.
2809 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
2813 Permission to use, copy, modify, and distribute this software and its
2814 documentation for any purpose and without fee is hereby granted,
2815 provided that the above copyright notice appear in all copies and that
2816 both that copyright notice and this permission notice appear in
2817 supporting documentation, and that the name of Digital not be
2818 used in advertising or publicity pertaining to distribution of the
2819 software without specific, written prior permission.
2821 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
2822 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
2823 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
2824 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
2825 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
2826 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
2829 ************************************************************************/
2832 * This file contains a few macros to help track
2833 * the edge of a filled object. The object is assumed
2834 * to be filled in scanline order, and thus the
2835 * algorithm used is an extension of Bresenham's line
2836 * drawing algorithm which assumes that y is always the
2838 * Since these pieces of code are the same for any filled shape,
2839 * it is more convenient to gather the library in one
2840 * place, but since these pieces of code are also in
2841 * the inner loops of output primitives, procedure call
2842 * overhead is out of the question.
2843 * See the author for a derivation if needed.
2848 * In scan converting polygons, we want to choose those pixels
2849 * which are inside the polygon. Thus, we add .5 to the starting
2850 * x coordinate for both left and right edges. Now we choose the
2851 * first pixel which is inside the pgon for the left edge and the
2852 * first pixel which is outside the pgon for the right edge.
2853 * Draw the left pixel, but not the right.
2855 * How to add .5 to the starting x coordinate:
2856 * If the edge is moving to the right, then subtract dy from the
2857 * error term from the general form of the algorithm.
2858 * If the edge is moving to the left, then add dy to the error term.
2860 * The reason for the difference between edges moving to the left
2861 * and edges moving to the right is simple: If an edge is moving
2862 * to the right, then we want the algorithm to flip immediately.
2863 * If it is moving to the left, then we don't want it to flip until
2864 * we traverse an entire pixel.
2866 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
2867 int dx; /* local storage */ \
2870 * if the edge is horizontal, then it is ignored \
2871 * and assumed not to be processed. Otherwise, do this stuff. \
2875 dx = (x2) - xStart; \
2879 incr1 = -2 * dx + 2 * (dy) * m1; \
2880 incr2 = -2 * dx + 2 * (dy) * m; \
2881 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
2885 incr1 = 2 * dx - 2 * (dy) * m1; \
2886 incr2 = 2 * dx - 2 * (dy) * m; \
2887 d = -2 * m * (dy) + 2 * dx; \
2892 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
2916 * This structure contains all of the information needed
2917 * to run the bresenham algorithm.
2918 * The variables may be hardcoded into the declarations
2919 * instead of using this structure to make use of
2920 * register declarations.
2923 int minor_axis; /* minor axis */
2924 int d; /* decision variable */
2925 int m, m1; /* slope and slope+1 */
2926 int incr1, incr2; /* error increments */
2930 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
2931 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
2932 bres.m, bres.m1, bres.incr1, bres.incr2)
2934 #define BRESINCRPGONSTRUCT(bres) \
2935 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
2940 * These are the data structures needed to scan
2941 * convert regions. Two different scan conversion
2942 * methods are available -- the even-odd method, and
2943 * the winding number method.
2944 * The even-odd rule states that a point is inside
2945 * the polygon if a ray drawn from that point in any
2946 * direction will pass through an odd number of
2948 * By the winding number rule, a point is decided
2949 * to be inside the polygon if a ray drawn from that
2950 * point in any direction passes through a different
2951 * number of clockwise and counter-clockwise path
2954 * These data structures are adapted somewhat from
2955 * the algorithm in (Foley/Van Dam) for scan converting
2957 * The basic algorithm is to start at the top (smallest y)
2958 * of the polygon, stepping down to the bottom of
2959 * the polygon by incrementing the y coordinate. We
2960 * keep a list of edges which the current scanline crosses,
2961 * sorted by x. This list is called the Active Edge Table (AET)
2962 * As we change the y-coordinate, we update each entry in
2963 * in the active edge table to reflect the edges new xcoord.
2964 * This list must be sorted at each scanline in case
2965 * two edges intersect.
2966 * We also keep a data structure known as the Edge Table (ET),
2967 * which keeps track of all the edges which the current
2968 * scanline has not yet reached. The ET is basically a
2969 * list of ScanLineList structures containing a list of
2970 * edges which are entered at a given scanline. There is one
2971 * ScanLineList per scanline at which an edge is entered.
2972 * When we enter a new edge, we move it from the ET to the AET.
2974 * From the AET, we can implement the even-odd rule as in
2976 * The winding number rule is a little trickier. We also
2977 * keep the EdgeTableEntries in the AET linked by the
2978 * nextWETE (winding EdgeTableEntry) link. This allows
2979 * the edges to be linked just as before for updating
2980 * purposes, but only uses the edges linked by the nextWETE
2981 * link as edges representing spans of the polygon to
2982 * drawn (as with the even-odd rule).
2986 * for the winding number rule
2989 #define COUNTERCLOCKWISE -1
2991 typedef struct _EdgeTableEntry {
2992 int ymax; /* ycoord at which we exit this edge. */
2993 BRESINFO bres; /* Bresenham info to run the edge */
2994 struct _EdgeTableEntry *next; /* next in the list */
2995 struct _EdgeTableEntry *back; /* for insertion sort */
2996 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
2997 int ClockWise; /* flag for winding number rule */
3001 typedef struct _ScanLineList{
3002 int scanline; /* the scanline represented */
3003 EdgeTableEntry *edgelist; /* header node */
3004 struct _ScanLineList *next; /* next in the list */
3009 int ymax; /* ymax for the polygon */
3010 int ymin; /* ymin for the polygon */
3011 ScanLineList scanlines; /* header node */
3016 * Here is a struct to help with storage allocation
3017 * so we can allocate a big chunk at a time, and then take
3018 * pieces from this heap when we need to.
3020 #define SLLSPERBLOCK 25
3022 typedef struct _ScanLineListBlock {
3023 ScanLineList SLLs[SLLSPERBLOCK];
3024 struct _ScanLineListBlock *next;
3025 } ScanLineListBlock;
3031 * a few macros for the inner loops of the fill code where
3032 * performance considerations don't allow a procedure call.
3034 * Evaluate the given edge at the given scanline.
3035 * If the edge has expired, then we leave it and fix up
3036 * the active edge table; otherwise, we increment the
3037 * x value to be ready for the next scanline.
3038 * The winding number rule is in effect, so we must notify
3039 * the caller when the edge has been removed so he
3040 * can reorder the Winding Active Edge Table.
3042 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
3043 if (pAET->ymax == y) { /* leaving this edge */ \
3044 pPrevAET->next = pAET->next; \
3045 pAET = pPrevAET->next; \
3048 pAET->back = pPrevAET; \
3051 BRESINCRPGONSTRUCT(pAET->bres) \
3053 pAET = pAET->next; \
3059 * Evaluate the given edge at the given scanline.
3060 * If the edge has expired, then we leave it and fix up
3061 * the active edge table; otherwise, we increment the
3062 * x value to be ready for the next scanline.
3063 * The even-odd rule is in effect.
3065 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
3066 if (pAET->ymax == y) { /* leaving this edge */ \
3067 pPrevAET->next = pAET->next; \
3068 pAET = pPrevAET->next; \
3070 pAET->back = pPrevAET; \
3073 BRESINCRPGONSTRUCT(pAET->bres) \
3075 pAET = pAET->next; \
3078 // END OF poly.h extract
3079 // START OF PolyReg.c extract
3080 /* $XConsortium: PolyReg.c,v 11.23 94/11/17 21:59:37 converse Exp $ */
3081 /************************************************************************
3083 Copyright (c) 1987 X Consortium
3085 Permission is hereby granted, free of charge, to any person obtaining a copy
3086 of this software and associated documentation files (the "Software"), to deal
3087 in the Software without restriction, including without limitation the rights
3088 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
3089 copies of the Software, and to permit persons to whom the Software is
3090 furnished to do so, subject to the following conditions:
3092 The above copyright notice and this permission notice shall be included in
3093 all copies or substantial portions of the Software.
3095 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
3096 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
3097 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
3098 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
3099 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
3100 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
3102 Except as contained in this notice, the name of the X Consortium shall not be
3103 used in advertising or otherwise to promote the sale, use or other dealings
3104 in this Software without prior written authorization from the X Consortium.
3107 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
3111 Permission to use, copy, modify, and distribute this software and its
3112 documentation for any purpose and without fee is hereby granted,
3113 provided that the above copyright notice appear in all copies and that
3114 both that copyright notice and this permission notice appear in
3115 supporting documentation, and that the name of Digital not be
3116 used in advertising or publicity pertaining to distribution of the
3117 software without specific, written prior permission.
3119 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
3120 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
3121 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
3122 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
3123 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
3124 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
3127 ************************************************************************/
3128 /* $XFree86: xc/lib/X11/PolyReg.c,v 1.1.1.2.8.2 1998/10/04 15:22:49 hohndel Exp $ */
3130 #define LARGE_COORDINATE INT_MAX
3131 #define SMALL_COORDINATE INT_MIN
3136 * Insert the given edge into the edge table.
3137 * First we must find the correct bucket in the
3138 * Edge table, then find the right slot in the
3139 * bucket. Finally, we can insert it.
3142 static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
3143 ScanLineListBlock **SLLBlock, int *iSLLBlock)
3145 register EdgeTableEntry *start, *prev;
3146 register ScanLineList *pSLL, *pPrevSLL;
3147 ScanLineListBlock *tmpSLLBlock;
3150 * find the right bucket to put the edge into
3152 pPrevSLL = &ET->scanlines;
3153 pSLL = pPrevSLL->next;
3154 while (pSLL && (pSLL->scanline < scanline)) {
3160 * reassign pSLL (pointer to ScanLineList) if necessary
3162 if ((!pSLL) || (pSLL->scanline > scanline)) {
3163 if (*iSLLBlock > SLLSPERBLOCK-1)
3166 (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
3167 Q_CHECK_PTR(tmpSLLBlock);
3168 (*SLLBlock)->next = tmpSLLBlock;
3169 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
3170 *SLLBlock = tmpSLLBlock;
3173 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
3175 pSLL->next = pPrevSLL->next;
3176 pSLL->edgelist = (EdgeTableEntry *)NULL;
3177 pPrevSLL->next = pSLL;
3179 pSLL->scanline = scanline;
3182 * now insert the edge in the right bucket
3185 start = pSLL->edgelist;
3186 while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
3188 start = start->next;
3195 pSLL->edgelist = ETE;
3201 * This routine creates the edge table for
3202 * scan converting polygons.
3203 * The Edge Table (ET) looks like:
3207 * | ymax | ScanLineLists
3208 * |scanline|-->------------>-------------->...
3209 * -------- |scanline| |scanline|
3210 * |edgelist| |edgelist|
3211 * --------- ---------
3215 * list of ETEs list of ETEs
3217 * where ETE is an EdgeTableEntry data structure,
3218 * and there is one ScanLineList per scanline at
3219 * which an edge is initially entered.
3223 static void CreateETandAET(register int count, register const QPoint *pts,
3224 EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs,
3225 ScanLineListBlock *pSLLBlock)
3227 register const QPoint *top,
3238 * initialize the Active Edge Table
3243 AET->bres.minor_axis = SMALL_COORDINATE;
3246 * initialize the Edge Table.
3248 ET->scanlines.next = 0;
3249 ET->ymax = SMALL_COORDINATE;
3250 ET->ymin = LARGE_COORDINATE;
3251 pSLLBlock->next = 0;
3253 PrevPt = &pts[count - 1];
3256 * for each vertex in the array of points.
3257 * In this loop we are dealing with two vertices at
3258 * a time -- these make up one edge of the polygon.
3264 * find out which point is above and which is below.
3266 if (PrevPt->y() > CurrPt->y()) {
3269 pETEs->ClockWise = 0;
3273 pETEs->ClockWise = 1;
3277 * don't add horizontal edges to the Edge table.
3279 if (bottom->y() != top->y()) {
3280 pETEs->ymax = bottom->y() - 1; /* -1 so we don't get last scanline */
3283 * initialize integer edge algorithm
3285 dy = bottom->y() - top->y();
3286 BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)
3288 InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);
3290 if (PrevPt->y() > ET->ymax)
3291 ET->ymax = PrevPt->y();
3292 if (PrevPt->y() < ET->ymin)
3293 ET->ymin = PrevPt->y();
3304 * This routine moves EdgeTableEntries from the
3305 * EdgeTable into the Active Edge Table,
3306 * leaving them sorted by smaller x coordinate.
3310 static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
3312 register EdgeTableEntry *pPrevAET;
3313 register EdgeTableEntry *tmp;
3318 while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
3326 ETEs->back = pPrevAET;
3327 pPrevAET->next = ETEs;
3337 * This routine links the AET by the
3338 * nextWETE (winding EdgeTableEntry) link for
3339 * use by the winding number rule. The final
3340 * Active Edge Table (AET) might look something
3344 * ---------- --------- ---------
3345 * |ymax | |ymax | |ymax |
3346 * | ... | |... | |... |
3347 * |next |->|next |->|next |->...
3348 * |nextWETE| |nextWETE| |nextWETE|
3349 * --------- --------- ^--------
3351 * V-------------------> V---> ...
3354 static void computeWAET(register EdgeTableEntry *AET)
3356 register EdgeTableEntry *pWETE;
3357 register int inside = 1;
3358 register int isInside = 0;
3369 if ((!inside && !isInside) || (inside && isInside)) {
3370 pWETE->nextWETE = AET;
3376 pWETE->nextWETE = 0;
3382 * Just a simple insertion sort using
3383 * pointers and back pointers to sort the Active
3388 static int InsertionSort(register EdgeTableEntry *AET)
3390 register EdgeTableEntry *pETEchase;
3391 register EdgeTableEntry *pETEinsert;
3392 register EdgeTableEntry *pETEchaseBackTMP;
3393 register int changed = 0;
3399 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
3400 pETEchase = pETEchase->back;
3403 if (pETEchase != pETEinsert) {
3404 pETEchaseBackTMP = pETEchase->back;
3405 pETEinsert->back->next = AET;
3407 AET->back = pETEinsert->back;
3408 pETEinsert->next = pETEchase;
3409 pETEchase->back->next = pETEinsert;
3410 pETEchase->back = pETEinsert;
3411 pETEinsert->back = pETEchaseBackTMP;
3421 static void FreeStorage(register ScanLineListBlock *pSLLBlock)
3423 register ScanLineListBlock *tmpSLLBlock;
3426 tmpSLLBlock = pSLLBlock->next;
3428 pSLLBlock = tmpSLLBlock;
3432 struct QRegionSpan {
3434 QRegionSpan(int x1_, int x2_) : x1(x1_), x2(x2_) {}
3438 int width() const { return x2 - x1; }
3441 Q_DECLARE_TYPEINFO(QRegionSpan, Q_PRIMITIVE_TYPE);
3443 static inline void flushRow(const QRegionSpan *spans, int y, int numSpans, QRegionPrivate *reg, int *lastRow, int *extendTo, bool *needsExtend)
3445 QRect *regRects = reg->rects.data() + *lastRow;
3446 bool canExtend = reg->rects.size() - *lastRow == numSpans
3447 && !(*needsExtend && *extendTo + 1 != y)
3448 && (*needsExtend || regRects[0].y() + regRects[0].height() == y);
3450 for (int i = 0; i < numSpans && canExtend; ++i) {
3451 if (regRects[i].x() != spans[i].x1 || regRects[i].right() != spans[i].x2 - 1)
3457 *needsExtend = true;
3460 for (int i = 0; i < reg->rects.size() - *lastRow; ++i)
3461 regRects[i].setBottom(*extendTo);
3464 *lastRow = reg->rects.size();
3465 reg->rects.reserve(*lastRow + numSpans);
3466 for (int i = 0; i < numSpans; ++i)
3467 reg->rects << QRect(spans[i].x1, y, spans[i].width(), 1);
3469 if (spans[0].x1 < reg->extents.left())
3470 reg->extents.setLeft(spans[0].x1);
3472 if (spans[numSpans-1].x2 - 1 > reg->extents.right())
3473 reg->extents.setRight(spans[numSpans-1].x2 - 1);
3475 *needsExtend = false;
3480 * Create an array of rectangles from a list of points.
3481 * If indeed these things (POINTS, RECTS) are the same,
3482 * then this proc is still needed, because it allocates
3483 * storage for the array, which was allocated on the
3484 * stack by the calling procedure.
3487 static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock,
3488 POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
3492 bool needsExtend = false;
3493 QVarLengthArray<QRegionSpan> row;
3496 reg->extents.setLeft(INT_MAX);
3497 reg->extents.setRight(INT_MIN);
3498 reg->innerArea = -1;
3500 POINTBLOCK *CurPtBlock = FirstPtBlock;
3501 for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
3502 /* the loop uses 2 points per iteration */
3503 int i = NUMPTSTOBUFFER >> 1;
3504 if (!numFullPtBlocks)
3505 i = iCurPtBlock >> 1;
3507 row.resize(qMax(row.size(), rowSize + i));
3508 for (QPoint *pts = CurPtBlock->pts; i--; pts += 2) {
3509 const int width = pts[1].x() - pts[0].x();
3511 if (rowSize && row[rowSize-1].x2 == pts[0].x())
3512 row[rowSize-1].x2 = pts[1].x();
3514 row[rowSize++] = QRegionSpan(pts[0].x(), pts[1].x());
3518 QPoint *next = i ? &pts[2] : (numFullPtBlocks ? CurPtBlock->next->pts : 0);
3520 if (!next || next->y() != pts[0].y()) {
3521 flushRow(row.data(), pts[0].y(), rowSize, reg, &lastRow, &extendTo, &needsExtend);
3527 CurPtBlock = CurPtBlock->next;
3531 for (int i = lastRow; i < reg->rects.size(); ++i)
3532 reg->rects[i].setBottom(extendTo);
3535 reg->numRects = reg->rects.size();
3537 if (reg->numRects) {
3538 reg->extents.setTop(reg->rects[0].top());
3539 reg->extents.setBottom(reg->rects[lastRow].bottom());
3541 for (int i = 0; i < reg->rects.size(); ++i)
3542 reg->updateInnerRect(reg->rects[i]);
3544 reg->extents.setCoords(0, 0, 0, 0);
3551 * Scan converts a polygon by returning a run-length
3552 * encoding of the resultant bitmap -- the run-length
3553 * encoding is in the form of an array of rectangles.
3555 * Can return 0 in case of errors.
3557 static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule)
3558 //Point *Pts; /* the pts */
3559 //int Count; /* number of pts */
3560 //int rule; /* winding rule */
3562 QRegionPrivate *region;
3563 register EdgeTableEntry *pAET; /* Active Edge Table */
3564 register int y; /* current scanline */
3565 register int iPts = 0; /* number of pts in buffer */
3566 register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
3567 register ScanLineList *pSLL; /* current scanLineList */
3568 register QPoint *pts; /* output buffer */
3569 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
3570 EdgeTable ET; /* header node for ET */
3571 EdgeTableEntry AET; /* header node for AET */
3572 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
3573 ScanLineListBlock SLLBlock; /* header for scanlinelist */
3574 int fixWAET = false;
3575 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
3576 FirstPtBlock.pts = reinterpret_cast<QPoint *>(FirstPtBlock.data);
3577 POINTBLOCK *tmpPtBlock;
3578 int numFullPtBlocks = 0;
3580 if (!(region = new QRegionPrivate))
3583 /* special case a rectangle */
3584 if (((Count == 4) ||
3585 ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
3586 && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
3587 && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
3588 && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
3589 && (Pts[3].y() == Pts[0].y())))) {
3590 int x = qMin(Pts[0].x(), Pts[2].x());
3591 region->extents.setLeft(x);
3592 int y = qMin(Pts[0].y(), Pts[2].y());
3593 region->extents.setTop(y);
3594 region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
3595 region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
3596 if ((region->extents.left() <= region->extents.right()) &&
3597 (region->extents.top() <= region->extents.bottom())) {
3598 region->numRects = 1;
3599 region->innerRect = region->extents;
3600 region->innerArea = region->innerRect.width() * region->innerRect.height();
3605 if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
3608 region->vectorize();
3610 pts = FirstPtBlock.pts;
3611 CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
3613 pSLL = ET.scanlines.next;
3614 curPtBlock = &FirstPtBlock;
3616 // sanity check that the region won't become too big...
3617 if (ET.ymax - ET.ymin > 100000) {
3618 // clean up region ptr
3620 qWarning("QRegion: creating region from big polygon failed...!");
3628 if (rule == EvenOddRule) {
3632 for (y = ET.ymin; y < ET.ymax; ++y) {
3635 * Add a new edge to the active edge table when we
3636 * get to the next edge.
3638 if (pSLL && y == pSLL->scanline) {
3639 loadAET(&AET, pSLL->edgelist);
3646 * for each active edge
3649 pts->setX(pAET->bres.minor_axis);
3655 * send out the buffer
3657 if (iPts == NUMPTSTOBUFFER) {
3658 tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
3659 Q_CHECK_PTR(tmpPtBlock);
3660 tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3661 curPtBlock->next = tmpPtBlock;
3662 curPtBlock = tmpPtBlock;
3663 pts = curPtBlock->pts;
3667 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
3669 InsertionSort(&AET);
3675 for (y = ET.ymin; y < ET.ymax; ++y) {
3677 * Add a new edge to the active edge table when we
3678 * get to the next edge.
3680 if (pSLL && y == pSLL->scanline) {
3681 loadAET(&AET, pSLL->edgelist);
3690 * for each active edge
3694 * add to the buffer only those edges that
3695 * are in the Winding active edge table.
3697 if (pWETE == pAET) {
3698 pts->setX(pAET->bres.minor_axis);
3704 * send out the buffer
3706 if (iPts == NUMPTSTOBUFFER) {
3707 tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
3708 tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3709 curPtBlock->next = tmpPtBlock;
3710 curPtBlock = tmpPtBlock;
3711 pts = curPtBlock->pts;
3715 pWETE = pWETE->nextWETE;
3717 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
3721 * recompute the winding active edge table if
3722 * we just resorted or have exited an edge.
3724 if (InsertionSort(&AET) || fixWAET) {
3731 FreeStorage(SLLBlock.next);
3732 PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3733 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3734 tmpPtBlock = curPtBlock->next;
3736 curPtBlock = tmpPtBlock;
3739 return 0; // this function returns 0 in case of an error
3742 FreeStorage(SLLBlock.next);
3743 PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3744 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3745 tmpPtBlock = curPtBlock->next;
3747 curPtBlock = tmpPtBlock;
3752 // END OF PolyReg.c extract
3754 QRegionPrivate *qt_bitmapToRegion(const QBitmap& bitmap)
3756 QImage image = bitmap.toImage();
3758 QRegionPrivate *region = new QRegionPrivate;
3764 xr.setCoords(prev1, y, x-1, y); \
3765 UnionRectWithRegion(&xr, region, *region); \
3768 const uchar zero = 0;
3769 bool little = image.format() == QImage::Format_MonoLSB;
3773 for (y = 0; y < image.height(); ++y) {
3774 uchar *line = image.scanLine(y);
3775 int w = image.width();
3778 for (x = 0; x < w;) {
3779 uchar byte = line[x / 8];
3780 if (x > w - 8 || byte!=all) {
3782 for (int b = 8; b > 0 && x < w; --b) {
3783 if (!(byte & 0x01) == !all) {
3799 for (int b = 8; b > 0 && x < w; --b) {
3800 if (!(byte & 0x80) == !all) {
3835 QRegion::QRegion(const QRect &r, RegionType t)
3841 d = new QRegionData;
3843 #if defined(Q_WS_X11)
3846 #elif defined(Q_WS_WIN)
3849 if (t == Rectangle) {
3850 d->qt_rgn = new QRegionPrivate(r);
3851 } else if (t == Ellipse) {
3853 path.addEllipse(r.x(), r.y(), r.width(), r.height());
3854 QPolygon a = path.toSubpathPolygons().at(0).toPolygon();
3855 d->qt_rgn = PolygonRegion(a.constData(), a.size(), EvenOddRule);
3860 QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
3862 if (a.count() > 2) {
3863 QRegionPrivate *qt_rgn = PolygonRegion(a.constData(), a.size(),
3864 fillRule == Qt::WindingFill ? WindingRule : EvenOddRule);
3866 d = new QRegionData;
3868 #if defined(Q_WS_X11)
3871 #elif defined(Q_WS_WIN)
3885 QRegion::QRegion(const QRegion &r)
3892 QRegion::QRegion(const QBitmap &bm)
3898 d = new QRegionData;
3900 #if defined(Q_WS_X11)
3903 #elif defined(Q_WS_WIN)
3906 d->qt_rgn = qt_bitmapToRegion(bm);
3910 void QRegion::cleanUp(QRegion::QRegionData *x)
3913 #if defined(Q_WS_X11)
3915 XDestroyRegion(x->rgn);
3917 free(x->xrectangles);
3918 #elif defined(Q_WS_WIN)
3920 qt_win_dispose_rgn(x->rgn);
3927 if (!d->ref.deref())
3932 QRegion &QRegion::operator=(const QRegion &r)
3935 if (!d->ref.deref())
3945 QRegion QRegion::copy() const
3948 QScopedPointer<QRegionData> x(new QRegionData);
3950 #if defined(Q_WS_X11)
3953 #elif defined(Q_WS_WIN)
3957 x->qt_rgn = new QRegionPrivate(*d->qt_rgn);
3959 x->qt_rgn = new QRegionPrivate;
3960 if (!r.d->ref.deref())
3966 bool QRegion::isEmpty() const
3968 return d == &shared_empty || d->qt_rgn->numRects == 0;
3972 bool QRegion::contains(const QPoint &p) const
3974 return PointInRegion(d->qt_rgn, p.x(), p.y());
3977 bool QRegion::contains(const QRect &r) const
3979 return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut;
3984 void QRegion::translate(int dx, int dy)
3986 if ((dx == 0 && dy == 0) || isEmptyHelper(d->qt_rgn))
3990 OffsetRegion(*d->qt_rgn, dx, dy);
3993 QRegion QRegion::unite(const QRegion &r) const
3995 if (isEmptyHelper(d->qt_rgn))
3997 if (isEmptyHelper(r.d->qt_rgn))
4002 if (d->qt_rgn->contains(*r.d->qt_rgn)) {
4004 } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
4006 } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
4007 QRegion result(*this);
4009 result.d->qt_rgn->append(r.d->qt_rgn);
4011 } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
4012 QRegion result(*this);
4014 result.d->qt_rgn->prepend(r.d->qt_rgn);
4016 } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4021 UnionRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4026 QRegion& QRegion::operator+=(const QRegion &r)
4028 if (isEmptyHelper(d->qt_rgn))
4030 if (isEmptyHelper(r.d->qt_rgn))
4035 if (d->qt_rgn->contains(*r.d->qt_rgn)) {
4037 } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
4039 } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
4041 d->qt_rgn->append(r.d->qt_rgn);
4043 } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
4045 d->qt_rgn->prepend(r.d->qt_rgn);
4047 } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4051 UnionRegion(d->qt_rgn, r.d->qt_rgn, *d->qt_rgn);
4056 QRegion QRegion::unite(const QRect &r) const
4058 if (isEmptyHelper(d->qt_rgn))
4063 if (d->qt_rgn->contains(r)) {
4065 } else if (d->qt_rgn->within(r)) {
4067 } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4069 } else if (d->qt_rgn->canAppend(&r)) {
4070 QRegion result(*this);
4072 result.d->qt_rgn->append(&r);
4074 } else if (d->qt_rgn->canPrepend(&r)) {
4075 QRegion result(*this);
4077 result.d->qt_rgn->prepend(&r);
4082 QRegionPrivate rp(r);
4083 UnionRegion(d->qt_rgn, &rp, *result.d->qt_rgn);
4088 QRegion& QRegion::operator+=(const QRect &r)
4090 if (isEmptyHelper(d->qt_rgn))
4095 if (d->qt_rgn->contains(r)) {
4097 } else if (d->qt_rgn->within(r)) {
4099 } else if (d->qt_rgn->canAppend(&r)) {
4101 d->qt_rgn->append(&r);
4103 } else if (d->qt_rgn->canPrepend(&r)) {
4105 d->qt_rgn->prepend(&r);
4107 } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4111 QRegionPrivate p(r);
4112 UnionRegion(d->qt_rgn, &p, *d->qt_rgn);
4117 QRegion QRegion::intersect(const QRegion &r) const
4119 if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn)
4120 || !EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4123 /* this is fully contained in r */
4124 if (r.d->qt_rgn->contains(*d->qt_rgn))
4127 /* r is fully contained in this */
4128 if (d->qt_rgn->contains(*r.d->qt_rgn))
4131 if (r.d->qt_rgn->numRects == 1 && d->qt_rgn->numRects == 1) {
4132 const QRect rect = qt_rect_intersect_normalized(r.d->qt_rgn->extents,
4133 d->qt_rgn->extents);
4134 return QRegion(rect);
4135 } else if (r.d->qt_rgn->numRects == 1) {
4136 QRegion result(*this);
4138 result.d->qt_rgn->intersect(r.d->qt_rgn->extents);
4140 } else if (d->qt_rgn->numRects == 1) {
4143 result.d->qt_rgn->intersect(d->qt_rgn->extents);
4149 miRegionOp(*result.d->qt_rgn, d->qt_rgn, r.d->qt_rgn, miIntersectO, 0, 0);
4152 * Can't alter dest's extents before we call miRegionOp because
4153 * it might be one of the source regions and miRegionOp depends
4154 * on the extents of those regions being the same. Besides, this
4155 * way there's no checking against rectangles that will be nuked
4156 * due to coalescing, so we have to examine fewer rectangles.
4158 miSetExtents(*result.d->qt_rgn);
4162 QRegion QRegion::intersect(const QRect &r) const
4164 if (isEmptyHelper(d->qt_rgn) || r.isEmpty()
4165 || !EXTENTCHECK(&d->qt_rgn->extents, &r))
4168 /* this is fully contained in r */
4169 if (d->qt_rgn->within(r))
4172 /* r is fully contained in this */
4173 if (d->qt_rgn->contains(r))
4176 if (d->qt_rgn->numRects == 1) {
4177 const QRect rect = qt_rect_intersect_normalized(d->qt_rgn->extents,
4179 return QRegion(rect);
4182 QRegion result(*this);
4184 result.d->qt_rgn->intersect(r);
4188 QRegion QRegion::subtract(const QRegion &r) const
4190 if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn))
4192 if (r.d->qt_rgn->contains(*d->qt_rgn))
4194 if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4196 if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn))
4199 #ifdef QT_REGION_DEBUG
4200 d->qt_rgn->selfTest();
4201 r.d->qt_rgn->selfTest();
4206 SubtractRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4207 #ifdef QT_REGION_DEBUG
4208 result.d->qt_rgn->selfTest();
4213 QRegion QRegion::eor(const QRegion &r) const
4215 if (isEmptyHelper(d->qt_rgn)) {
4217 } else if (isEmptyHelper(r.d->qt_rgn)) {
4219 } else if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents)) {
4221 } else if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4226 XorRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4231 QRect QRegion::boundingRect() const
4235 return d->qt_rgn->extents;
4239 Returns true if \a rect is guaranteed to be fully contained in \a region.
4240 A false return value does not guarantee the opposite.
4242 #if defined(Q_WS_QWS) || defined(Q_WS_QPA)
4245 bool qt_region_strictContains(const QRegion ®ion, const QRect &rect)
4247 if (isEmptyHelper(region.d->qt_rgn) || !rect.isValid())
4250 #if 0 // TEST_INNERRECT
4251 static bool guard = false;
4255 QRegion inner = region.d->qt_rgn->innerRect;
4256 Q_ASSERT((inner - region).isEmpty());
4260 for (int i = 0; i < region.d->qt_rgn->numRects; ++i) {
4261 const QRect r = region.d->qt_rgn->rects.at(i);
4262 if (r.width() * r.height() > maxArea)
4263 maxArea = r.width() * r.height();
4266 if (maxArea > region.d->qt_rgn->innerArea) {
4267 qDebug() << "not largest rectangle" << region << region.d->qt_rgn->innerRect;
4269 Q_ASSERT(maxArea <= region.d->qt_rgn->innerArea);
4272 const QRect r1 = region.d->qt_rgn->innerRect;
4273 return (rect.left() >= r1.left() && rect.right() <= r1.right()
4274 && rect.top() >= r1.top() && rect.bottom() <= r1.bottom());
4277 QVector<QRect> QRegion::rects() const
4280 d->qt_rgn->vectorize();
4281 // hw: modify the vector size directly to avoid reallocation
4282 d->qt_rgn->rects.d->size = d->qt_rgn->numRects;
4283 return d->qt_rgn->rects;
4285 return QVector<QRect>();
4289 void QRegion::setRects(const QRect *rects, int num)
4292 if (!rects || num == 0 || (num == 1 && rects->isEmpty()))
4297 d->qt_rgn->numRects = num;
4299 d->qt_rgn->extents = *rects;
4300 d->qt_rgn->innerRect = *rects;
4302 d->qt_rgn->rects.resize(num);
4308 for (int i = 0; i < num; ++i) {
4309 const QRect &rect = rects[i];
4310 d->qt_rgn->rects[i] = rect;
4311 left = qMin(rect.left(), left);
4312 right = qMax(rect.right(), right);
4313 top = qMin(rect.top(), top);
4314 bottom = qMax(rect.bottom(), bottom);
4315 d->qt_rgn->updateInnerRect(rect);
4317 d->qt_rgn->extents = QRect(QPoint(left, top), QPoint(right, bottom));
4321 int QRegion::numRects() const
4323 return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4326 int QRegion::rectCount() const
4328 return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4332 bool QRegion::operator==(const QRegion &r) const
4342 return EqualRegion(d->qt_rgn, r.d->qt_rgn);
4345 bool QRegion::intersects(const QRect &rect) const
4347 if (isEmptyHelper(d->qt_rgn) || rect.isNull())
4350 const QRect r = rect.normalized();
4351 if (!rect_intersects(d->qt_rgn->extents, r))
4353 if (d->qt_rgn->numRects == 1)
4356 const QVector<QRect> myRects = rects();
4357 for (QVector<QRect>::const_iterator it = myRects.constBegin(); it < myRects.constEnd(); ++it)
4358 if (rect_intersects(r, *it))