src/gui/painting/qregion.cpp

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