src/gui/painting/qpainterpath.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 "qpainterpath.h"
  43 #include "qpainterpath_p.h"
  44
  45 #include <qbitmap.h>
  46 #include <qdebug.h>
  47 #include <qiodevice.h>
  48 #include <qlist.h>
  49 #include <qmatrix.h>
  50 #include <qpen.h>
  51 #include <qpolygon.h>
  52 #include <qtextlayout.h>
  53 #include <qvarlengtharray.h>
  54 #include <qmath.h>
  55
  56 #include <private/qbezier_p.h>
  57 #include <private/qfontengine_p.h>
  58 #include <private/qnumeric_p.h>
  59 #include <private/qobject_p.h>
  60 #include <private/qpathclipper_p.h>
  61 #include <private/qstroker_p.h>
  62 #include <private/qtextengine_p.h>
  63
  64 #include <limits.h>
  65
  66 #if 0
  67 #include <performance.h>
  68 #else
  69 #define PM_INIT
  70 #define PM_MEASURE(x)
  71 #define PM_DISPLAY
  72 #endif
  73
  74 QT_BEGIN_NAMESPACE
  75
  76 struct QPainterPathPrivateDeleter
  77 {
  78     static inline void cleanup(QPainterPathPrivate *d)
  79     {
  80         // note - we must up-cast to QPainterPathData since QPainterPathPrivate
  81         // has a non-virtual destructor!
  82         if (d && !d->ref.deref())
  83             delete static_cast<QPainterPathData *>(d);
  84     }
  85 };
  86
  87 // This value is used to determine the length of control point vectors
  88 // when approximating arc segments as curves. The factor is multiplied
  89 // with the radius of the circle.
  90
  91 // #define QPP_DEBUG
  92 // #define QPP_STROKE_DEBUG
  93 //#define QPP_FILLPOLYGONS_DEBUG
  94
  95 QPainterPath qt_stroke_dash(const QPainterPath &path, qreal *dashes, int dashCount);
  96
  97 void qt_find_ellipse_coords(const QRectF &r, qreal angle, qreal length,
  98                             QPointF* startPoint, QPointF *endPoint)
  99 {
 100     if (r.isNull()) {
 101         if (startPoint)
 102             *startPoint = QPointF();
 103         if (endPoint)
 104             *endPoint = QPointF();
 105         return;
 106     }
 107
 108     qreal w2 = r.width() / 2;
 109     qreal h2 = r.height() / 2;
 110
 111     qreal angles[2] = { angle, angle + length };
 112     QPointF *points[2] = { startPoint, endPoint };
 113
 114     for (int i = 0; i < 2; ++i) {
 115         if (!points[i])
 116             continue;
 117
 118         qreal theta = angles[i] - 360 * qFloor(angles[i] / 360);
 119         qreal t = theta / 90;
 120         // truncate
 121         int quadrant = int(t);
 122         t -= quadrant;
 123
 124         t = qt_t_for_arc_angle(90 * t);
 125
 126         // swap x and y?
 127         if (quadrant & 1)
 128             t = 1 - t;
 129
 130         qreal a, b, c, d;
 131         QBezier::coefficients(t, a, b, c, d);
 132         QPointF p(a + b + c*QT_PATH_KAPPA, d + c + b*QT_PATH_KAPPA);
 133
 134         // left quadrants
 135         if (quadrant == 1 || quadrant == 2)
 136             p.rx() = -p.x();
 137
 138         // top quadrants
 139         if (quadrant == 0 || quadrant == 1)
 140             p.ry() = -p.y();
 141
 142         *points[i] = r.center() + QPointF(w2 * p.x(), h2 * p.y());
 143     }
 144 }
 145
 146 #ifdef QPP_DEBUG
 147 static void qt_debug_path(const QPainterPath &path)
 148 {
 149     const char *names[] = {
 150         "MoveTo     ",
 151         "LineTo     ",
 152         "CurveTo    ",
 153         "CurveToData"
 154     };
 155
 156     printf("\nQPainterPath: elementCount=%d\n", path.elementCount());
 157     for (int i=0; i<path.elementCount(); ++i) {
 158         const QPainterPath::Element &e = path.elementAt(i);
 159         Q_ASSERT(e.type >= 0 && e.type <= QPainterPath::CurveToDataElement);
 160         printf(" - %3d:: %s, (%.2f, %.2f)\n", i, names[e.type], e.x, e.y);
 161     }
 162 }
 163 #endif
 164
 165 /*!
 166     \class QPainterPath
 167     \ingroup painting
 168     \ingroup shared
 169     \inmodule QtGui
 170
 171     \brief The QPainterPath class provides a container for painting operations,
 172     enabling graphical shapes to be constructed and reused.
 173
 174     A painter path is an object composed of a number of graphical
 175     building blocks, such as rectangles, ellipses, lines, and curves.
 176     Building blocks can be joined in closed subpaths, for example as a
 177     rectangle or an ellipse. A closed path has coinciding start and
 178     end points. Or they can exist independently as unclosed subpaths,
 179     such as lines and curves.
 180
 181     A QPainterPath object can be used for filling, outlining, and
 182     clipping. To generate fillable outlines for a given painter path,
 183     use the QPainterPathStroker class.  The main advantage of painter
 184     paths over normal drawing operations is that complex shapes only
 185     need to be created once; then they can be drawn many times using
 186     only calls to the QPainter::drawPath() function.
 187
 188     QPainterPath provides a collection of functions that can be used
 189     to obtain information about the path and its elements. In addition
 190     it is possible to reverse the order of the elements using the
 191     toReversed() function. There are also several functions to convert
 192     this painter path object into a polygon representation.
 193
 194     \tableofcontents
 195
 196     \section1 Composing a QPainterPath
 197
 198     A QPainterPath object can be constructed as an empty path, with a
 199     given start point, or as a copy of another QPainterPath object.
 200     Once created, lines and curves can be added to the path using the
 201     lineTo(), arcTo(), cubicTo() and quadTo() functions. The lines and
 202     curves stretch from the currentPosition() to the position passed
 203     as argument.
 204
 205     The currentPosition() of the QPainterPath object is always the end
 206     position of the last subpath that was added (or the initial start
 207     point). Use the moveTo() function to move the currentPosition()
 208     without adding a component. The moveTo() function implicitly
 209     starts a new subpath, and closes the previous one.  Another way of
 210     starting a new subpath is to call the closeSubpath() function
 211     which closes the current path by adding a line from the
 212     currentPosition() back to the path's start position. Note that the
 213     new path will have (0, 0) as its initial currentPosition().
 214
 215     QPainterPath class also provides several convenience functions to
 216     add closed subpaths to a painter path: addEllipse(), addPath(),
 217     addRect(), addRegion() and addText(). The addPolygon() function
 218     adds an \e unclosed subpath. In fact, these functions are all
 219     collections of moveTo(), lineTo() and cubicTo() operations.
 220
 221     In addition, a path can be added to the current path using the
 222     connectPath() function. But note that this function will connect
 223     the last element of the current path to the first element of given
 224     one by adding a line.
 225
 226     Below is a code snippet that shows how a QPainterPath object can
 227     be used:
 228
 229     \table 100%
 230     \row
 231     \li \inlineimage qpainterpath-construction.png
 232     \li
 233     \snippet code/src_gui_painting_qpainterpath.cpp 0
 234     \endtable
 235
 236     The painter path is initially empty when constructed. We first add
 237     a rectangle, which is a closed subpath. Then we add two bezier
 238     curves which together form a closed subpath even though they are
 239     not closed individually. Finally we draw the entire path. The path
 240     is filled using the default fill rule, Qt::OddEvenFill. Qt
 241     provides two methods for filling paths:
 242
 243     \table
 244     \header
 245     \li Qt::OddEvenFill
 246     \li Qt::WindingFill
 247     \row
 248     \li \inlineimage qt-fillrule-oddeven.png
 249     \li \inlineimage qt-fillrule-winding.png
 250     \endtable
 251
 252     See the Qt::FillRule documentation for the definition of the
 253     rules. A painter path's currently set fill rule can be retrieved
 254     using the fillRule() function, and altered using the setFillRule()
 255     function.
 256
 257     \section1 QPainterPath Information
 258
 259     The QPainterPath class provides a collection of functions that
 260     returns information about the path and its elements.
 261
 262     The currentPosition() function returns the end point of the last
 263     subpath that was added (or the initial start point). The
 264     elementAt() function can be used to retrieve the various subpath
 265     elements, the \e number of elements can be retrieved using the
 266     elementCount() function, and the isEmpty() function tells whether
 267     this QPainterPath object contains any elements at all.
 268
 269     The controlPointRect() function returns the rectangle containing
 270     all the points and control points in this path. This function is
 271     significantly faster to compute than the exact boundingRect()
 272     which returns the bounding rectangle of this painter path with
 273     floating point precision.
 274
 275     Finally, QPainterPath provides the contains() function which can
 276     be used to determine whether a given point or rectangle is inside
 277     the path, and the intersects() function which determines if any of
 278     the points inside a given rectangle also are inside this path.
 279
 280     \section1 QPainterPath Conversion
 281
 282     For compatibility reasons, it might be required to simplify the
 283     representation of a painter path: QPainterPath provides the
 284     toFillPolygon(), toFillPolygons() and toSubpathPolygons()
 285     functions which convert the painter path into a polygon. The
 286     toFillPolygon() returns the painter path as one single polygon,
 287     while the two latter functions return a list of polygons.
 288
 289     The toFillPolygons() and toSubpathPolygons() functions are
 290     provided because it is usually faster to draw several small
 291     polygons than to draw one large polygon, even though the total
 292     number of points drawn is the same. The difference between the two
 293     is the \e number of polygons they return: The toSubpathPolygons()
 294     creates one polygon for each subpath regardless of intersecting
 295     subpaths (i.e. overlapping bounding rectangles), while the
 296     toFillPolygons() functions creates only one polygon for
 297     overlapping subpaths.
 298
 299     The toFillPolygon() and toFillPolygons() functions first convert
 300     all the subpaths to polygons, then uses a rewinding technique to
 301     make sure that overlapping subpaths can be filled using the
 302     correct fill rule. Note that rewinding inserts additional lines in
 303     the polygon so the outline of the fill polygon does not match the
 304     outline of the path.
 305
 306     \section1 Examples
 307
 308     Qt provides the \l {painting/painterpaths}{Painter Paths Example}
 309     and the \l {painting/deform}{Vector Deformation example} which are
 310     located in Qt's example directory.
 311
 312     The \l {painting/painterpaths}{Painter Paths Example} shows how
 313     painter paths can be used to build complex shapes for rendering
 314     and lets the user experiment with the filling and stroking.  The
 315     \l {painting/deform}{Vector Deformation Example} shows how to use
 316     QPainterPath to draw text.
 317
 318     \table
 319     \header
 320     \li \l {painting/painterpaths}{Painter Paths Example}
 321     \li \l {painting/deform}{Vector Deformation Example}
 322     \row
 323     \li \inlineimage qpainterpath-example.png
 324     \li \inlineimage qpainterpath-demo.png
 325     \endtable
 326
 327     \sa QPainterPathStroker, QPainter, QRegion, {Painter Paths Example}
 328 */
 329
 330 /*!
 331     \enum QPainterPath::ElementType
 332
 333     This enum describes the types of elements used to connect vertices
 334     in subpaths.
 335
 336     Note that elements added as closed subpaths using the
 337     addEllipse(), addPath(), addPolygon(), addRect(), addRegion() and
 338     addText() convenience functions, is actually added to the path as
 339     a collection of separate elements using the moveTo(), lineTo() and
 340     cubicTo() functions.
 341
 342     \value MoveToElement          A new subpath. See also moveTo().
 343     \value LineToElement            A line. See also lineTo().
 344     \value CurveToElement         A curve. See also cubicTo() and quadTo().
 345     \value CurveToDataElement  The extra data required to describe a curve in
 346                                                a CurveToElement element.
 347
 348     \sa elementAt(), elementCount()
 349 */
 350
 351 /*!
 352     \class QPainterPath::Element
 353     \inmodule QtGui
 354
 355     \brief The QPainterPath::Element class specifies the position and
 356     type of a subpath.
 357
 358     Once a QPainterPath object is constructed, subpaths like lines and
 359     curves can be added to the path (creating
 360     QPainterPath::LineToElement and QPainterPath::CurveToElement
 361     components).
 362
 363     The lines and curves stretch from the currentPosition() to the
 364     position passed as argument. The currentPosition() of the
 365     QPainterPath object is always the end position of the last subpath
 366     that was added (or the initial start point). The moveTo() function
 367     can be used to move the currentPosition() without adding a line or
 368     curve, creating a QPainterPath::MoveToElement component.
 369
 370     \sa QPainterPath
 371 */
 372
 373 /*!
 374     \variable QPainterPath::Element::x
 375     \brief the x coordinate of the element's position.
 376
 377     \sa {operator QPointF()}
 378 */
 379
 380 /*!
 381     \variable QPainterPath::Element::y
 382     \brief the y coordinate of the element's position.
 383
 384     \sa {operator QPointF()}
 385 */
 386
 387 /*!
 388     \variable QPainterPath::Element::type
 389     \brief the type of element
 390
 391     \sa isCurveTo(), isLineTo(), isMoveTo()
 392 */
 393
 394 /*!
 395     \fn bool QPainterPath::Element::operator==(const Element &other) const
 396     \since 4.2
 397
 398     Returns true if this element is equal to \a other;
 399     otherwise returns false.
 400
 401     \sa operator!=()
 402 */
 403
 404 /*!
 405     \fn bool QPainterPath::Element::operator!=(const Element &other) const
 406     \since 4.2
 407
 408     Returns true if this element is not equal to \a other;
 409     otherwise returns false.
 410
 411     \sa operator==()
 412 */
 413
 414 /*!
 415     \fn bool QPainterPath::Element::isCurveTo () const
 416
 417     Returns true if the element is a curve, otherwise returns false.
 418
 419     \sa type, QPainterPath::CurveToElement
 420 */
 421
 422 /*!
 423     \fn bool QPainterPath::Element::isLineTo () const
 424
 425     Returns true if the element is a line, otherwise returns false.
 426
 427     \sa type, QPainterPath::LineToElement
 428 */
 429
 430 /*!
 431     \fn bool QPainterPath::Element::isMoveTo () const
 432
 433     Returns true if the element is moving the current position,
 434     otherwise returns false.
 435
 436     \sa type, QPainterPath::MoveToElement
 437 */
 438
 439 /*!
 440     \fn QPainterPath::Element::operator QPointF () const
 441
 442     Returns the element's position.
 443
 444     \sa x, y
 445 */
 446
 447 /*!
 448     \fn void QPainterPath::addEllipse(qreal x, qreal y, qreal width, qreal height)
 449     \overload
 450
 451     Creates an ellipse within the bounding rectangle defined by its top-left
 452     corner at (\a x, \a y), \a width and \a height, and adds it to the
 453     painter path as a closed subpath.
 454 */
 455
 456 /*!
 457     \since 4.4
 458
 459     \fn void QPainterPath::addEllipse(const QPointF &center, qreal rx, qreal ry)
 460     \overload
 461
 462     Creates an ellipse positioned at \a{center} with radii \a{rx} and \a{ry},
 463     and adds it to the painter path as a closed subpath.
 464 */
 465
 466 /*!
 467     \fn void QPainterPath::addText(qreal x, qreal y, const QFont &font, const QString &text)
 468     \overload
 469
 470     Adds the given \a text to this path as a set of closed subpaths created
 471     from the \a font supplied. The subpaths are positioned so that the left
 472     end of the text's baseline lies at the point specified by (\a x, \a y).
 473 */
 474
 475 /*!
 476     \fn int QPainterPath::elementCount() const
 477
 478     Returns the number of path elements in the painter path.
 479
 480     \sa ElementType, elementAt(), isEmpty()
 481 */
 482
 483 int QPainterPath::elementCount() const
 484 {
 485     return d_ptr ? d_ptr->elements.size() : 0;
 486 }
 487
 488 /*!
 489     \fn QPainterPath::Element QPainterPath::elementAt(int index) const
 490
 491     Returns the element at the given \a index in the painter path.
 492
 493     \sa ElementType, elementCount(), isEmpty()
 494 */
 495
 496 QPainterPath::Element QPainterPath::elementAt(int i) const
 497 {
 498     Q_ASSERT(d_ptr);
 499     Q_ASSERT(i >= 0 && i < elementCount());
 500     return d_ptr->elements.at(i);
 501 }
 502
 503 /*!
 504     \fn void QPainterPath::setElementPositionAt(int index, qreal x, qreal y)
 505     \since 4.2
 506
 507     Sets the x and y coordinate of the element at index \a index to \a
 508     x and \a y.
 509 */
 510
 511 void QPainterPath::setElementPositionAt(int i, qreal x, qreal y)
 512 {
 513     Q_ASSERT(d_ptr);
 514     Q_ASSERT(i >= 0 && i < elementCount());
 515     detach();
 516     QPainterPath::Element &e = d_ptr->elements[i];
 517     e.x = x;
 518     e.y = y;
 519 }
 520
 521
 522 /*###
 523     \fn QPainterPath &QPainterPath::operator +=(const QPainterPath &other)
 524
 525     Appends the \a other painter path to this painter path and returns a
 526     reference to the result.
 527 */
 528
 529 /*!
 530     Constructs an empty QPainterPath object.
 531 */
 532 QPainterPath::QPainterPath()
 533     : d_ptr(0)
 534 {
 535 }
 536
 537 /*!
 538     \fn QPainterPath::QPainterPath(const QPainterPath &path)
 539
 540     Creates a QPainterPath object that is a copy of the given \a path.
 541
 542     \sa operator=()
 543 */
 544 QPainterPath::QPainterPath(const QPainterPath &other)
 545     : d_ptr(other.d_ptr.data())
 546 {
 547     if (d_ptr)
 548         d_ptr->ref.ref();
 549 }
 550
 551 /*!
 552     Creates a QPainterPath object with the given \a startPoint as its
 553     current position.
 554 */
 555
 556 QPainterPath::QPainterPath(const QPointF &startPoint)
 557     : d_ptr(new QPainterPathData)
 558 {
 559     Element e = { startPoint.x(), startPoint.y(), MoveToElement };
 560     d_func()->elements << e;
 561 }
 562
 563 void QPainterPath::detach()
 564 {
 565     if (d_ptr->ref.load() != 1)
 566         detach_helper();
 567     setDirty(true);
 568 }
 569
 570 /*!
 571     \internal
 572 */
 573 void QPainterPath::detach_helper()
 574 {
 575     QPainterPathPrivate *data = new QPainterPathData(*d_func());
 576     d_ptr.reset(data);
 577 }
 578
 579 /*!
 580     \internal
 581 */
 582 void QPainterPath::ensureData_helper()
 583 {
 584     QPainterPathPrivate *data = new QPainterPathData;
 585     data->elements.reserve(16);
 586     QPainterPath::Element e = { 0, 0, QPainterPath::MoveToElement };
 587     data->elements << e;
 588     d_ptr.reset(data);
 589     Q_ASSERT(d_ptr != 0);
 590 }
 591
 592 /*!
 593     \fn QPainterPath &QPainterPath::operator=(const QPainterPath &path)
 594
 595     Assigns the given \a path to this painter path.
 596
 597     \sa QPainterPath()
 598 */
 599 QPainterPath &QPainterPath::operator=(const QPainterPath &other)
 600 {
 601     if (other.d_func() != d_func()) {
 602         QPainterPathPrivate *data = other.d_func();
 603         if (data)
 604             data->ref.ref();
 605         d_ptr.reset(data);
 606     }
 607     return *this;
 608 }
 609
 610 /*!
 611     \fn void QPainterPath::swap(QPainterPath &other)
 612     \since 4.8
 613
 614     Swaps painter path \a other with this painter path. This operation is very
 615     fast and never fails.
 616 */
 617
 618 /*!
 619     Destroys this QPainterPath object.
 620 */
 621 QPainterPath::~QPainterPath()
 622 {
 623 }
 624
 625 /*!
 626     Closes the current subpath by drawing a line to the beginning of
 627     the subpath, automatically starting a new path. The current point
 628     of the new path is (0, 0).
 629
 630     If the subpath does not contain any elements, this function does
 631     nothing.
 632
 633     \sa moveTo(), {QPainterPath#Composing a QPainterPath}{Composing
 634     a QPainterPath}
 635  */
 636 void QPainterPath::closeSubpath()
 637 {
 638 #ifdef QPP_DEBUG
 639     printf("QPainterPath::closeSubpath()\n");
 640 #endif
 641     if (isEmpty())
 642         return;
 643     detach();
 644
 645     d_func()->close();
 646 }
 647
 648 /*!
 649     \fn void QPainterPath::moveTo(qreal x, qreal y)
 650
 651     \overload
 652
 653     Moves the current position to (\a{x}, \a{y}) and starts a new
 654     subpath, implicitly closing the previous path.
 655 */
 656
 657 /*!
 658     \fn void QPainterPath::moveTo(const QPointF &point)
 659
 660     Moves the current point to the given \a point, implicitly starting
 661     a new subpath and closing the previous one.
 662
 663     \sa closeSubpath(), {QPainterPath#Composing a
 664     QPainterPath}{Composing a QPainterPath}
 665 */
 666 void QPainterPath::moveTo(const QPointF &p)
 667 {
 668 #ifdef QPP_DEBUG
 669     printf("QPainterPath::moveTo() (%.2f,%.2f)\n", p.x(), p.y());
 670 #endif
 671
 672     if (!qt_is_finite(p.x()) || !qt_is_finite(p.y())) {
 673 #ifndef QT_NO_DEBUG
 674         qWarning("QPainterPath::moveTo: Adding point where x or y is NaN or Inf, ignoring call");
 675 #endif
 676         return;
 677     }
 678
 679     ensureData();
 680     detach();
 681
 682     QPainterPathData *d = d_func();
 683     Q_ASSERT(!d->elements.isEmpty());
 684
 685     d->require_moveTo = false;
 686
 687     if (d->elements.last().type == MoveToElement) {
 688         d->elements.last().x = p.x();
 689         d->elements.last().y = p.y();
 690     } else {
 691         Element elm = { p.x(), p.y(), MoveToElement };
 692         d->elements.append(elm);
 693     }
 694     d->cStart = d->elements.size() - 1;
 695 }
 696
 697 /*!
 698     \fn void QPainterPath::lineTo(qreal x, qreal y)
 699
 700     \overload
 701
 702     Draws a line from the current position to the point (\a{x},
 703     \a{y}).
 704 */
 705
 706 /*!
 707     \fn void QPainterPath::lineTo(const QPointF &endPoint)
 708
 709     Adds a straight line from the current position to the given \a
 710     endPoint.  After the line is drawn, the current position is updated
 711     to be at the end point of the line.
 712
 713     \sa addPolygon(), addRect(), {QPainterPath#Composing a
 714     QPainterPath}{Composing a QPainterPath}
 715  */
 716 void QPainterPath::lineTo(const QPointF &p)
 717 {
 718 #ifdef QPP_DEBUG
 719     printf("QPainterPath::lineTo() (%.2f,%.2f)\n", p.x(), p.y());
 720 #endif
 721
 722     if (!qt_is_finite(p.x()) || !qt_is_finite(p.y())) {
 723 #ifndef QT_NO_DEBUG
 724         qWarning("QPainterPath::lineTo: Adding point where x or y is NaN or Inf, ignoring call");
 725 #endif
 726         return;
 727     }
 728
 729     ensureData();
 730     detach();
 731
 732     QPainterPathData *d = d_func();
 733     Q_ASSERT(!d->elements.isEmpty());
 734     d->maybeMoveTo();
 735     if (p == QPointF(d->elements.last()))
 736         return;
 737     Element elm = { p.x(), p.y(), LineToElement };
 738     d->elements.append(elm);
 739
 740     d->convex = d->elements.size() == 3 || (d->elements.size() == 4 && d->isClosed());
 741 }
 742
 743 /*!
 744     \fn void QPainterPath::cubicTo(qreal c1X, qreal c1Y, qreal c2X,
 745     qreal c2Y, qreal endPointX, qreal endPointY);
 746
 747     \overload
 748
 749     Adds a cubic Bezier curve between the current position and the end
 750     point (\a{endPointX}, \a{endPointY}) with control points specified
 751     by (\a{c1X}, \a{c1Y}) and (\a{c2X}, \a{c2Y}).
 752 */
 753
 754 /*!
 755     \fn void QPainterPath::cubicTo(const QPointF &c1, const QPointF &c2, const QPointF &endPoint)
 756
 757     Adds a cubic Bezier curve between the current position and the
 758     given \a endPoint using the control points specified by \a c1, and
 759     \a c2.
 760
 761     After the curve is added, the current position is updated to be at
 762     the end point of the curve.
 763
 764     \table 100%
 765     \row
 766     \li \inlineimage qpainterpath-cubicto.png
 767     \li
 768     \snippet code/src_gui_painting_qpainterpath.cpp 1
 769     \endtable
 770
 771     \sa quadTo(), {QPainterPath#Composing a QPainterPath}{Composing
 772     a QPainterPath}
 773 */
 774 void QPainterPath::cubicTo(const QPointF &c1, const QPointF &c2, const QPointF &e)
 775 {
 776 #ifdef QPP_DEBUG
 777     printf("QPainterPath::cubicTo() (%.2f,%.2f), (%.2f,%.2f), (%.2f,%.2f)\n",
 778            c1.x(), c1.y(), c2.x(), c2.y(), e.x(), e.y());
 779 #endif
 780
 781     if (!qt_is_finite(c1.x()) || !qt_is_finite(c1.y()) || !qt_is_finite(c2.x()) || !qt_is_finite(c2.y())
 782         || !qt_is_finite(e.x()) || !qt_is_finite(e.y())) {
 783 #ifndef QT_NO_DEBUG
 784         qWarning("QPainterPath::cubicTo: Adding point where x or y is NaN or Inf, ignoring call");
 785 #endif
 786         return;
 787     }
 788
 789     ensureData();
 790     detach();
 791
 792     QPainterPathData *d = d_func();
 793     Q_ASSERT(!d->elements.isEmpty());
 794
 795
 796     // Abort on empty curve as a stroker cannot handle this and the
 797     // curve is irrelevant anyway.
 798     if (d->elements.last() == c1 && c1 == c2 && c2 == e)
 799         return;
 800
 801     d->maybeMoveTo();
 802
 803     Element ce1 = { c1.x(), c1.y(), CurveToElement };
 804     Element ce2 = { c2.x(), c2.y(), CurveToDataElement };
 805     Element ee = { e.x(), e.y(), CurveToDataElement };
 806     d->elements << ce1 << ce2 << ee;
 807 }
 808
 809 /*!
 810     \fn void QPainterPath::quadTo(qreal cx, qreal cy, qreal endPointX, qreal endPointY);
 811
 812     \overload
 813
 814     Adds a quadratic Bezier curve between the current point and the endpoint
 815     (\a{endPointX}, \a{endPointY}) with the control point specified by
 816     (\a{cx}, \a{cy}).
 817 */
 818
 819 /*!
 820     \fn void QPainterPath::quadTo(const QPointF &c, const QPointF &endPoint)
 821
 822     Adds a quadratic Bezier curve between the current position and the
 823     given \a endPoint with the control point specified by \a c.
 824
 825     After the curve is added, the current point is updated to be at
 826     the end point of the curve.
 827
 828     \sa cubicTo(), {QPainterPath#Composing a QPainterPath}{Composing a
 829     QPainterPath}
 830 */
 831 void QPainterPath::quadTo(const QPointF &c, const QPointF &e)
 832 {
 833 #ifdef QPP_DEBUG
 834     printf("QPainterPath::quadTo() (%.2f,%.2f), (%.2f,%.2f)\n",
 835            c.x(), c.y(), e.x(), e.y());
 836 #endif
 837
 838     if (!qt_is_finite(c.x()) || !qt_is_finite(c.y()) || !qt_is_finite(e.x()) || !qt_is_finite(e.y())) {
 839 #ifndef QT_NO_DEBUG
 840         qWarning("QPainterPath::quadTo: Adding point where x or y is NaN or Inf, ignoring call");
 841 #endif
 842         return;
 843     }
 844
 845     ensureData();
 846     detach();
 847
 848     Q_D(QPainterPath);
 849     Q_ASSERT(!d->elements.isEmpty());
 850     const QPainterPath::Element &elm = d->elements.at(elementCount()-1);
 851     QPointF prev(elm.x, elm.y);
 852
 853     // Abort on empty curve as a stroker cannot handle this and the
 854     // curve is irrelevant anyway.
 855     if (prev == c && c == e)
 856         return;
 857
 858     QPointF c1((prev.x() + 2*c.x()) / 3, (prev.y() + 2*c.y()) / 3);
 859     QPointF c2((e.x() + 2*c.x()) / 3, (e.y() + 2*c.y()) / 3);
 860     cubicTo(c1, c2, e);
 861 }
 862
 863 /*!
 864     \fn void QPainterPath::arcTo(qreal x, qreal y, qreal width, qreal
 865     height, qreal startAngle, qreal sweepLength)
 866
 867     \overload
 868
 869     Creates an arc that occupies the rectangle QRectF(\a x, \a y, \a
 870     width, \a height), beginning at the specified \a startAngle and
 871     extending \a sweepLength degrees counter-clockwise.
 872
 873 */
 874
 875 /*!
 876     \fn void QPainterPath::arcTo(const QRectF &rectangle, qreal startAngle, qreal sweepLength)
 877
 878     Creates an arc that occupies the given \a rectangle, beginning at
 879     the specified \a startAngle and extending \a sweepLength degrees
 880     counter-clockwise.
 881
 882     Angles are specified in degrees. Clockwise arcs can be specified
 883     using negative angles.
 884
 885     Note that this function connects the starting point of the arc to
 886     the current position if they are not already connected. After the
 887     arc has been added, the current position is the last point in
 888     arc. To draw a line back to the first point, use the
 889     closeSubpath() function.
 890
 891     \table 100%
 892     \row
 893     \li \inlineimage qpainterpath-arcto.png
 894     \li
 895     \snippet code/src_gui_painting_qpainterpath.cpp 2
 896     \endtable
 897
 898     \sa arcMoveTo(), addEllipse(), QPainter::drawArc(), QPainter::drawPie(),
 899     {QPainterPath#Composing a QPainterPath}{Composing a
 900     QPainterPath}
 901 */
 902 void QPainterPath::arcTo(const QRectF &rect, qreal startAngle, qreal sweepLength)
 903 {
 904 #ifdef QPP_DEBUG
 905     printf("QPainterPath::arcTo() (%.2f, %.2f, %.2f, %.2f, angle=%.2f, sweep=%.2f\n",
 906            rect.x(), rect.y(), rect.width(), rect.height(), startAngle, sweepLength);
 907 #endif
 908
 909     if ((!qt_is_finite(rect.x()) && !qt_is_finite(rect.y())) || !qt_is_finite(rect.width()) || !qt_is_finite(rect.height())
 910         || !qt_is_finite(startAngle) || !qt_is_finite(sweepLength)) {
 911 #ifndef QT_NO_DEBUG
 912         qWarning("QPainterPath::arcTo: Adding arc where a parameter is NaN or Inf, ignoring call");
 913 #endif
 914         return;
 915     }
 916
 917     if (rect.isNull())
 918         return;
 919
 920     ensureData();
 921     detach();
 922
 923     int point_count;
 924     QPointF pts[15];
 925     QPointF curve_start = qt_curves_for_arc(rect, startAngle, sweepLength, pts, &point_count);
 926
 927     lineTo(curve_start);
 928     for (int i=0; i<point_count; i+=3) {
 929         cubicTo(pts[i].x(), pts[i].y(),
 930                 pts[i+1].x(), pts[i+1].y(),
 931                 pts[i+2].x(), pts[i+2].y());
 932     }
 933
 934 }
 935
 936
 937 /*!
 938     \fn void QPainterPath::arcMoveTo(qreal x, qreal y, qreal width, qreal height, qreal angle)
 939     \overload
 940     \since 4.2
 941
 942     Creates a move to that lies on the arc that occupies the
 943     QRectF(\a x, \a y, \a width, \a height) at \a angle.
 944 */
 945
 946
 947 /*!
 948     \fn void QPainterPath::arcMoveTo(const QRectF &rectangle, qreal angle)
 949     \since 4.2
 950
 951     Creates a move to that lies on the arc that occupies the given \a
 952     rectangle at \a angle.
 953
 954     Angles are specified in degrees. Clockwise arcs can be specified
 955     using negative angles.
 956
 957     \sa moveTo(), arcTo()
 958 */
 959
 960 void QPainterPath::arcMoveTo(const QRectF &rect, qreal angle)
 961 {
 962     if (rect.isNull())
 963         return;
 964
 965     QPointF pt;
 966     qt_find_ellipse_coords(rect, angle, 0, &pt, 0);
 967     moveTo(pt);
 968 }
 969
 970
 971
 972 /*!
 973     \fn QPointF QPainterPath::currentPosition() const
 974
 975     Returns the current position of the path.
 976 */
 977 QPointF QPainterPath::currentPosition() const
 978 {
 979     return !d_ptr || d_func()->elements.isEmpty()
 980         ? QPointF()
 981         : QPointF(d_func()->elements.last().x, d_func()->elements.last().y);
 982 }
 983
 984
 985 /*!
 986     \fn void QPainterPath::addRect(qreal x, qreal y, qreal width, qreal height)
 987
 988     \overload
 989
 990     Adds a rectangle at position (\a{x}, \a{y}), with the given \a
 991     width and \a height, as a closed subpath.
 992 */
 993
 994 /*!
 995     \fn void QPainterPath::addRect(const QRectF &rectangle)
 996
 997     Adds the given \a rectangle to this path as a closed subpath.
 998
 999     The \a rectangle is added as a clockwise set of lines. The painter
1000     path's current position after the \a rectangle has been added is
1001     at the top-left corner of the rectangle.
1002
1003     \table 100%
1004     \row
1005     \li \inlineimage qpainterpath-addrectangle.png
1006     \li
1007     \snippet code/src_gui_painting_qpainterpath.cpp 3
1008     \endtable
1009
1010     \sa addRegion(), lineTo(), {QPainterPath#Composing a
1011     QPainterPath}{Composing a QPainterPath}
1012 */
1013 void QPainterPath::addRect(const QRectF &r)
1014 {
1015     if (!qt_is_finite(r.x()) || !qt_is_finite(r.y()) || !qt_is_finite(r.width()) || !qt_is_finite(r.height())) {
1016 #ifndef QT_NO_DEBUG
1017         qWarning("QPainterPath::addRect: Adding rect where a parameter is NaN or Inf, ignoring call");
1018 #endif
1019         return;
1020     }
1021
1022     if (r.isNull())
1023         return;
1024
1025     ensureData();
1026     detach();
1027
1028     bool first = d_func()->elements.size() < 2;
1029
1030     d_func()->elements.reserve(d_func()->elements.size() + 5);
1031     moveTo(r.x(), r.y());
1032
1033     Element l1 = { r.x() + r.width(), r.y(), LineToElement };
1034     Element l2 = { r.x() + r.width(), r.y() + r.height(), LineToElement };
1035     Element l3 = { r.x(), r.y() + r.height(), LineToElement };
1036     Element l4 = { r.x(), r.y(), LineToElement };
1037
1038     d_func()->elements << l1 << l2 << l3 << l4;
1039     d_func()->require_moveTo = true;
1040     d_func()->convex = first;
1041 }
1042
1043 /*!
1044     Adds the given \a polygon to the path as an (unclosed) subpath.
1045
1046     Note that the current position after the polygon has been added,
1047     is the last point in \a polygon. To draw a line back to the first
1048     point, use the closeSubpath() function.
1049
1050     \table 100%
1051     \row
1052     \li \inlineimage qpainterpath-addpolygon.png
1053     \li
1054     \snippet code/src_gui_painting_qpainterpath.cpp 4
1055     \endtable
1056
1057     \sa lineTo(), {QPainterPath#Composing a QPainterPath}{Composing
1058     a QPainterPath}
1059 */
1060 void QPainterPath::addPolygon(const QPolygonF &polygon)
1061 {
1062     if (polygon.isEmpty())
1063         return;
1064
1065     ensureData();
1066     detach();
1067
1068     d_func()->elements.reserve(d_func()->elements.size() + polygon.size());
1069
1070     moveTo(polygon.first());
1071     for (int i=1; i<polygon.size(); ++i) {
1072         Element elm = { polygon.at(i).x(), polygon.at(i).y(), LineToElement };
1073         d_func()->elements << elm;
1074     }
1075 }
1076
1077 /*!
1078     \fn void QPainterPath::addEllipse(const QRectF &boundingRectangle)
1079
1080     Creates an ellipse within the specified \a boundingRectangle
1081     and adds it to the painter path as a closed subpath.
1082
1083     The ellipse is composed of a clockwise curve, starting and
1084     finishing at zero degrees (the 3 o'clock position).
1085
1086     \table 100%
1087     \row
1088     \li \inlineimage qpainterpath-addellipse.png
1089     \li
1090     \snippet code/src_gui_painting_qpainterpath.cpp 5
1091     \endtable
1092
1093     \sa arcTo(), QPainter::drawEllipse(), {QPainterPath#Composing a
1094     QPainterPath}{Composing a QPainterPath}
1095 */
1096 void QPainterPath::addEllipse(const QRectF &boundingRect)
1097 {
1098     if (!qt_is_finite(boundingRect.x()) || !qt_is_finite(boundingRect.y())
1099         || !qt_is_finite(boundingRect.width()) || !qt_is_finite(boundingRect.height())) {
1100 #ifndef QT_NO_DEBUG
1101         qWarning("QPainterPath::addEllipse: Adding ellipse where a parameter is NaN or Inf, ignoring call");
1102 #endif
1103         return;
1104     }
1105
1106     if (boundingRect.isNull())
1107         return;
1108
1109     ensureData();
1110     detach();
1111
1112     Q_D(QPainterPath);
1113     bool first = d_func()->elements.size() < 2;
1114     d->elements.reserve(d->elements.size() + 13);
1115
1116     QPointF pts[12];
1117     int point_count;
1118     QPointF start = qt_curves_for_arc(boundingRect, 0, -360, pts, &point_count);
1119
1120     moveTo(start);
1121     cubicTo(pts[0], pts[1], pts[2]);           // 0 -> 270
1122     cubicTo(pts[3], pts[4], pts[5]);           // 270 -> 180
1123     cubicTo(pts[6], pts[7], pts[8]);           // 180 -> 90
1124     cubicTo(pts[9], pts[10], pts[11]);         // 90 - >0
1125     d_func()->require_moveTo = true;
1126
1127     d_func()->convex = first;
1128 }
1129
1130 /*!
1131     \fn void QPainterPath::addText(const QPointF &point, const QFont &font, const QString &text)
1132
1133     Adds the given \a text to this path as a set of closed subpaths
1134     created from the \a font supplied. The subpaths are positioned so
1135     that the left end of the text's baseline lies at the specified \a
1136     point.
1137
1138     \table 100%
1139     \row
1140     \li \inlineimage qpainterpath-addtext.png
1141     \li
1142     \snippet code/src_gui_painting_qpainterpath.cpp 6
1143     \endtable
1144
1145     \sa QPainter::drawText(), {QPainterPath#Composing a
1146     QPainterPath}{Composing a QPainterPath}
1147 */
1148 void QPainterPath::addText(const QPointF &point, const QFont &f, const QString &text)
1149 {
1150     if (text.isEmpty())
1151         return;
1152
1153     ensureData();
1154     detach();
1155
1156     QTextLayout layout(text, f);
1157     layout.setCacheEnabled(true);
1158     QTextEngine *eng = layout.engine();
1159     layout.beginLayout();
1160     QTextLine line = layout.createLine();
1161     Q_UNUSED(line);
1162     layout.endLayout();
1163     const QScriptLine &sl = eng->lines[0];
1164     if (!sl.length || !eng->layoutData)
1165         return;
1166
1167     int nItems = eng->layoutData->items.size();
1168
1169     qreal x(point.x());
1170     qreal y(point.y());
1171
1172     QVarLengthArray<int> visualOrder(nItems);
1173     QVarLengthArray<uchar> levels(nItems);
1174     for (int i = 0; i < nItems; ++i)
1175         levels[i] = eng->layoutData->items[i].analysis.bidiLevel;
1176     QTextEngine::bidiReorder(nItems, levels.data(), visualOrder.data());
1177
1178     for (int i = 0; i < nItems; ++i) {
1179         int item = visualOrder[i];
1180         QScriptItem &si = eng->layoutData->items[item];
1181
1182         if (si.analysis.flags < QScriptAnalysis::TabOrObject) {
1183             QGlyphLayout glyphs = eng->shapedGlyphs(&si);
1184             QFontEngine *fe = f.d->engineForScript(si.analysis.script);
1185             Q_ASSERT(fe);
1186             fe->addOutlineToPath(x, y, glyphs, this,
1187                                  si.analysis.bidiLevel % 2
1188                                  ? QTextItem::RenderFlags(QTextItem::RightToLeft)
1189                                  : QTextItem::RenderFlags(0));
1190
1191             const qreal lw = fe->lineThickness().toReal();
1192             if (f.d->underline) {
1193                 qreal pos = fe->underlinePosition().toReal();
1194                 addRect(x, y + pos, si.width.toReal(), lw);
1195             }
1196             if (f.d->overline) {
1197                 qreal pos = fe->ascent().toReal() + 1;
1198                 addRect(x, y - pos, si.width.toReal(), lw);
1199             }
1200             if (f.d->strikeOut) {
1201                 qreal pos = fe->ascent().toReal() / 3;
1202                 addRect(x, y - pos, si.width.toReal(), lw);
1203             }
1204         }
1205         x += si.width.toReal();
1206     }
1207 }
1208
1209 /*!
1210     \fn void QPainterPath::addPath(const QPainterPath &path)
1211
1212     Adds the given \a path to \e this path as a closed subpath.
1213
1214     \sa connectPath(), {QPainterPath#Composing a
1215     QPainterPath}{Composing a QPainterPath}
1216 */
1217 void QPainterPath::addPath(const QPainterPath &other)
1218 {
1219     if (other.isEmpty())
1220         return;
1221
1222     ensureData();
1223     detach();
1224
1225     QPainterPathData *d = reinterpret_cast<QPainterPathData *>(d_func());
1226     // Remove last moveto so we don't get multiple moveto's
1227     if (d->elements.last().type == MoveToElement)
1228         d->elements.remove(d->elements.size()-1);
1229
1230     // Locate where our own current subpath will start after the other path is added.
1231     int cStart = d->elements.size() + other.d_func()->cStart;
1232     d->elements += other.d_func()->elements;
1233     d->cStart = cStart;
1234
1235     d->require_moveTo = other.d_func()->isClosed();
1236 }
1237
1238
1239 /*!
1240     \fn void QPainterPath::connectPath(const QPainterPath &path)
1241
1242     Connects the given \a path to \e this path by adding a line from the
1243     last element of this path to the first element of the given path.
1244
1245     \sa addPath(), {QPainterPath#Composing a QPainterPath}{Composing
1246     a QPainterPath}
1247 */
1248 void QPainterPath::connectPath(const QPainterPath &other)
1249 {
1250     if (other.isEmpty())
1251         return;
1252
1253     ensureData();
1254     detach();
1255
1256     QPainterPathData *d = reinterpret_cast<QPainterPathData *>(d_func());
1257     // Remove last moveto so we don't get multiple moveto's
1258     if (d->elements.last().type == MoveToElement)
1259         d->elements.remove(d->elements.size()-1);
1260
1261     // Locate where our own current subpath will start after the other path is added.
1262     int cStart = d->elements.size() + other.d_func()->cStart;
1263     int first = d->elements.size();
1264     d->elements += other.d_func()->elements;
1265
1266     if (first != 0)
1267         d->elements[first].type = LineToElement;
1268
1269     // avoid duplicate points
1270     if (first > 0 && QPointF(d->elements[first]) == QPointF(d->elements[first - 1])) {
1271         d->elements.remove(first--);
1272         --cStart;
1273     }
1274
1275     if (cStart != first)
1276         d->cStart = cStart;
1277 }
1278
1279 /*!
1280     Adds the given \a region to the path by adding each rectangle in
1281     the region as a separate closed subpath.
1282
1283     \sa addRect(), {QPainterPath#Composing a QPainterPath}{Composing
1284     a QPainterPath}
1285 */
1286 void QPainterPath::addRegion(const QRegion &region)
1287 {
1288     ensureData();
1289     detach();
1290
1291     QVector<QRect> rects = region.rects();
1292     d_func()->elements.reserve(rects.size() * 5);
1293     for (int i=0; i<rects.size(); ++i)
1294         addRect(rects.at(i));
1295 }
1296
1297
1298 /*!
1299     Returns the painter path's currently set fill rule.
1300
1301     \sa setFillRule()
1302 */
1303 Qt::FillRule QPainterPath::fillRule() const
1304 {
1305     return isEmpty() ? Qt::OddEvenFill : d_func()->fillRule;
1306 }
1307
1308 /*!
1309     \fn void QPainterPath::setFillRule(Qt::FillRule fillRule)
1310
1311     Sets the fill rule of the painter path to the given \a
1312     fillRule. Qt provides two methods for filling paths:
1313
1314     \table
1315     \header
1316     \li Qt::OddEvenFill (default)
1317     \li Qt::WindingFill
1318     \row
1319     \li \inlineimage qt-fillrule-oddeven.png
1320     \li \inlineimage qt-fillrule-winding.png
1321     \endtable
1322
1323     \sa fillRule()
1324 */
1325 void QPainterPath::setFillRule(Qt::FillRule fillRule)
1326 {
1327     ensureData();
1328     if (d_func()->fillRule == fillRule)
1329         return;
1330     detach();
1331
1332     d_func()->fillRule = fillRule;
1333 }
1334
1335 #define QT_BEZIER_A(bezier, coord) 3 * (-bezier.coord##1 \
1336                                         + 3*bezier.coord##2 \
1337                                         - 3*bezier.coord##3 \
1338                                         +bezier.coord##4)
1339
1340 #define QT_BEZIER_B(bezier, coord) 6 * (bezier.coord##1 \
1341                                         - 2*bezier.coord##2 \
1342                                         + bezier.coord##3)
1343
1344 #define QT_BEZIER_C(bezier, coord) 3 * (- bezier.coord##1 \
1345                                         + bezier.coord##2)
1346
1347 #define QT_BEZIER_CHECK_T(bezier, t) \
1348     if (t >= 0 && t <= 1) { \
1349         QPointF p(b.pointAt(t)); \
1350         if (p.x() < minx) minx = p.x(); \
1351         else if (p.x() > maxx) maxx = p.x(); \
1352         if (p.y() < miny) miny = p.y(); \
1353         else if (p.y() > maxy) maxy = p.y(); \
1354     }
1355
1356
1357 static QRectF qt_painterpath_bezier_extrema(const QBezier &b)
1358 {
1359     qreal minx, miny, maxx, maxy;
1360
1361     // initialize with end points
1362     if (b.x1 < b.x4) {
1363         minx = b.x1;
1364         maxx = b.x4;
1365     } else {
1366         minx = b.x4;
1367         maxx = b.x1;
1368     }
1369     if (b.y1 < b.y4) {
1370         miny = b.y1;
1371         maxy = b.y4;
1372     } else {
1373         miny = b.y4;
1374         maxy = b.y1;
1375     }
1376
1377     // Update for the X extrema
1378     {
1379         qreal ax = QT_BEZIER_A(b, x);
1380         qreal bx = QT_BEZIER_B(b, x);
1381         qreal cx = QT_BEZIER_C(b, x);
1382         // specialcase quadratic curves to avoid div by zero
1383         if (qFuzzyIsNull(ax)) {
1384
1385             // linear curves are covered by initialization.
1386             if (!qFuzzyIsNull(bx)) {
1387                 qreal t = -cx / bx;
1388                 QT_BEZIER_CHECK_T(b, t);
1389             }
1390
1391         } else {
1392             const qreal tx = bx * bx - 4 * ax * cx;
1393
1394             if (tx >= 0) {
1395                 qreal temp = qSqrt(tx);
1396                 qreal rcp = 1 / (2 * ax);
1397                 qreal t1 = (-bx + temp) * rcp;
1398                 QT_BEZIER_CHECK_T(b, t1);
1399
1400                 qreal t2 = (-bx - temp) * rcp;
1401                 QT_BEZIER_CHECK_T(b, t2);
1402             }
1403         }
1404     }
1405
1406     // Update for the Y extrema
1407     {
1408         qreal ay = QT_BEZIER_A(b, y);
1409         qreal by = QT_BEZIER_B(b, y);
1410         qreal cy = QT_BEZIER_C(b, y);
1411
1412         // specialcase quadratic curves to avoid div by zero
1413         if (qFuzzyIsNull(ay)) {
1414
1415             // linear curves are covered by initialization.
1416             if (!qFuzzyIsNull(by)) {
1417                 qreal t = -cy / by;
1418                 QT_BEZIER_CHECK_T(b, t);
1419             }
1420
1421         } else {
1422             const qreal ty = by * by - 4 * ay * cy;
1423
1424             if (ty > 0) {
1425                 qreal temp = qSqrt(ty);
1426                 qreal rcp = 1 / (2 * ay);
1427                 qreal t1 = (-by + temp) * rcp;
1428                 QT_BEZIER_CHECK_T(b, t1);
1429
1430                 qreal t2 = (-by - temp) * rcp;
1431                 QT_BEZIER_CHECK_T(b, t2);
1432             }
1433         }
1434     }
1435     return QRectF(minx, miny, maxx - minx, maxy - miny);
1436 }
1437
1438 /*!
1439     Returns the bounding rectangle of this painter path as a rectangle with
1440     floating point precision.
1441
1442     \sa controlPointRect()
1443 */
1444 QRectF QPainterPath::boundingRect() const
1445 {
1446     if (!d_ptr)
1447         return QRectF();
1448     QPainterPathData *d = d_func();
1449
1450     if (d->dirtyBounds)
1451         computeBoundingRect();
1452     return d->bounds;
1453 }
1454
1455 /*!
1456     Returns the rectangle containing all the points and control points
1457     in this path.
1458
1459     This function is significantly faster to compute than the exact
1460     boundingRect(), and the returned rectangle is always a superset of
1461     the rectangle returned by boundingRect().
1462
1463     \sa boundingRect()
1464 */
1465 QRectF QPainterPath::controlPointRect() const
1466 {
1467     if (!d_ptr)
1468         return QRectF();
1469     QPainterPathData *d = d_func();
1470
1471     if (d->dirtyControlBounds)
1472         computeControlPointRect();
1473     return d->controlBounds;
1474 }
1475
1476
1477 /*!
1478     \fn bool QPainterPath::isEmpty() const
1479
1480     Returns true if either there are no elements in this path, or if the only
1481     element is a MoveToElement; otherwise returns false.
1482
1483     \sa elementCount()
1484 */
1485
1486 bool QPainterPath::isEmpty() const
1487 {
1488     return !d_ptr || (d_ptr->elements.size() == 1 && d_ptr->elements.first().type == MoveToElement);
1489 }
1490
1491 /*!
1492     Creates and returns a reversed copy of the path.
1493
1494     It is the order of the elements that is reversed: If a
1495     QPainterPath is composed by calling the moveTo(), lineTo() and
1496     cubicTo() functions in the specified order, the reversed copy is
1497     composed by calling cubicTo(), lineTo() and moveTo().
1498 */
1499 QPainterPath QPainterPath::toReversed() const
1500 {
1501     Q_D(const QPainterPath);
1502     QPainterPath rev;
1503
1504     if (isEmpty()) {
1505         rev = *this;
1506         return rev;
1507     }
1508
1509     rev.moveTo(d->elements.at(d->elements.size()-1).x, d->elements.at(d->elements.size()-1).y);
1510
1511     for (int i=d->elements.size()-1; i>=1; --i) {
1512         const QPainterPath::Element &elm = d->elements.at(i);
1513         const QPainterPath::Element &prev = d->elements.at(i-1);
1514         switch (elm.type) {
1515         case LineToElement:
1516             rev.lineTo(prev.x, prev.y);
1517             break;
1518         case MoveToElement:
1519             rev.moveTo(prev.x, prev.y);
1520             break;
1521         case CurveToDataElement:
1522             {
1523                 Q_ASSERT(i>=3);
1524                 const QPainterPath::Element &cp1 = d->elements.at(i-2);
1525                 const QPainterPath::Element &sp = d->elements.at(i-3);
1526                 Q_ASSERT(prev.type == CurveToDataElement);
1527                 Q_ASSERT(cp1.type == CurveToElement);
1528                 rev.cubicTo(prev.x, prev.y, cp1.x, cp1.y, sp.x, sp.y);
1529                 i -= 2;
1530                 break;
1531             }
1532         default:
1533             Q_ASSERT(!"qt_reversed_path");
1534             break;
1535         }
1536     }
1537     //qt_debug_path(rev);
1538     return rev;
1539 }
1540
1541 /*!
1542     Converts the path into a list of polygons using the QTransform
1543     \a matrix, and returns the list.
1544
1545     This function creates one polygon for each subpath regardless of
1546     intersecting subpaths (i.e. overlapping bounding rectangles). To
1547     make sure that such overlapping subpaths are filled correctly, use
1548     the toFillPolygons() function instead.
1549
1550     \sa toFillPolygons(), toFillPolygon(), {QPainterPath#QPainterPath
1551     Conversion}{QPainterPath Conversion}
1552 */
1553 QList<QPolygonF> QPainterPath::toSubpathPolygons(const QTransform &matrix) const
1554 {
1555
1556     Q_D(const QPainterPath);
1557     QList<QPolygonF> flatCurves;
1558     if (isEmpty())
1559         return flatCurves;
1560
1561     QPolygonF current;
1562     for (int i=0; i<elementCount(); ++i) {
1563         const QPainterPath::Element &e = d->elements.at(i);
1564         switch (e.type) {
1565         case QPainterPath::MoveToElement:
1566             if (current.size() > 1)
1567                 flatCurves += current;
1568             current.clear();
1569             current.reserve(16);
1570             current += QPointF(e.x, e.y) * matrix;
1571             break;
1572         case QPainterPath::LineToElement:
1573             current += QPointF(e.x, e.y) * matrix;
1574             break;
1575         case QPainterPath::CurveToElement: {
1576             Q_ASSERT(d->elements.at(i+1).type == QPainterPath::CurveToDataElement);
1577             Q_ASSERT(d->elements.at(i+2).type == QPainterPath::CurveToDataElement);
1578             QBezier bezier = QBezier::fromPoints(QPointF(d->elements.at(i-1).x, d->elements.at(i-1).y) * matrix,
1579                                        QPointF(e.x, e.y) * matrix,
1580                                        QPointF(d->elements.at(i+1).x, d->elements.at(i+1).y) * matrix,
1581                                                  QPointF(d->elements.at(i+2).x, d->elements.at(i+2).y) * matrix);
1582             bezier.addToPolygon(&current);
1583             i+=2;
1584             break;
1585         }
1586         case QPainterPath::CurveToDataElement:
1587             Q_ASSERT(!"QPainterPath::toSubpathPolygons(), bad element type");
1588             break;
1589         }
1590     }
1591
1592     if (current.size()>1)
1593         flatCurves += current;
1594
1595     return flatCurves;
1596 }
1597
1598 /*!
1599   \overload
1600  */
1601 QList<QPolygonF> QPainterPath::toSubpathPolygons(const QMatrix &matrix) const
1602 {
1603     return toSubpathPolygons(QTransform(matrix));
1604 }
1605
1606 /*!
1607     Converts the path into a list of polygons using the
1608     QTransform \a matrix, and returns the list.
1609
1610     The function differs from the toFillPolygon() function in that it
1611     creates several polygons. It is provided because it is usually
1612     faster to draw several small polygons than to draw one large
1613     polygon, even though the total number of points drawn is the same.
1614
1615     The toFillPolygons() function differs from the toSubpathPolygons()
1616     function in that it create only polygon for subpaths that have
1617     overlapping bounding rectangles.
1618
1619     Like the toFillPolygon() function, this function uses a rewinding
1620     technique to make sure that overlapping subpaths can be filled
1621     using the correct fill rule. Note that rewinding inserts addition
1622     lines in the polygons so the outline of the fill polygon does not
1623     match the outline of the path.
1624
1625     \sa toSubpathPolygons(), toFillPolygon(),
1626     {QPainterPath#QPainterPath Conversion}{QPainterPath Conversion}
1627 */
1628 QList<QPolygonF> QPainterPath::toFillPolygons(const QTransform &matrix) const
1629 {
1630
1631     QList<QPolygonF> polys;
1632
1633     QList<QPolygonF> subpaths = toSubpathPolygons(matrix);
1634     int count = subpaths.size();
1635
1636     if (count == 0)
1637         return polys;
1638
1639     QList<QRectF> bounds;
1640     for (int i=0; i<count; ++i)
1641         bounds += subpaths.at(i).boundingRect();
1642
1643 #ifdef QPP_FILLPOLYGONS_DEBUG
1644     printf("QPainterPath::toFillPolygons, subpathCount=%d\n", count);
1645     for (int i=0; i<bounds.size(); ++i)
1646         qDebug() << " bounds" << i << bounds.at(i);
1647 #endif
1648
1649     QVector< QList<int> > isects;
1650     isects.resize(count);
1651
1652     // find all intersections
1653     for (int j=0; j<count; ++j) {
1654         if (subpaths.at(j).size() <= 2)
1655             continue;
1656         QRectF cbounds = bounds.at(j);
1657         for (int i=0; i<count; ++i) {
1658             if (cbounds.intersects(bounds.at(i))) {
1659                 isects[j] << i;
1660             }
1661         }
1662     }
1663
1664 #ifdef QPP_FILLPOLYGONS_DEBUG
1665     printf("Intersections before flattening:\n");
1666     for (int i = 0; i < count; ++i) {
1667         printf("%d: ", i);
1668         for (int j = 0; j < isects[i].size(); ++j) {
1669             printf("%d ", isects[i][j]);
1670         }
1671         printf("\n");
1672     }
1673 #endif
1674
1675     // flatten the sets of intersections
1676     for (int i=0; i<count; ++i) {
1677         const QList<int> &current_isects = isects.at(i);
1678         for (int j=0; j<current_isects.size(); ++j) {
1679             int isect_j = current_isects.at(j);
1680             if (isect_j == i)
1681                 continue;
1682             for (int k=0; k<isects[isect_j].size(); ++k) {
1683                 int isect_k = isects[isect_j][k];
1684                 if (isect_k != i && !isects.at(i).contains(isect_k)) {
1685                     isects[i] += isect_k;
1686                 }
1687             }
1688             isects[isect_j].clear();
1689         }
1690     }
1691
1692 #ifdef QPP_FILLPOLYGONS_DEBUG
1693     printf("Intersections after flattening:\n");
1694     for (int i = 0; i < count; ++i) {
1695         printf("%d: ", i);
1696         for (int j = 0; j < isects[i].size(); ++j) {
1697             printf("%d ", isects[i][j]);
1698         }
1699         printf("\n");
1700     }
1701 #endif
1702
1703     // Join the intersected subpaths as rewinded polygons
1704     for (int i=0; i<count; ++i) {
1705         const QList<int> &subpath_list = isects[i];
1706         if (!subpath_list.isEmpty()) {
1707             QPolygonF buildUp;
1708             for (int j=0; j<subpath_list.size(); ++j) {
1709                 const QPolygonF &subpath = subpaths.at(subpath_list.at(j));
1710                 buildUp += subpath;
1711                 if (!subpath.isClosed())
1712                     buildUp += subpath.first();
1713                 if (!buildUp.isClosed())
1714                     buildUp += buildUp.first();
1715             }
1716             polys += buildUp;
1717         }
1718     }
1719
1720     return polys;
1721 }
1722
1723 /*!
1724   \overload
1725  */
1726 QList<QPolygonF> QPainterPath::toFillPolygons(const QMatrix &matrix) const
1727 {
1728     return toFillPolygons(QTransform(matrix));
1729 }
1730
1731 //same as qt_polygon_isect_line in qpolygon.cpp
1732 static void qt_painterpath_isect_line(const QPointF &p1,
1733                                       const QPointF &p2,
1734                                       const QPointF &pos,
1735                                       int *winding)
1736 {
1737     qreal x1 = p1.x();
1738     qreal y1 = p1.y();
1739     qreal x2 = p2.x();
1740     qreal y2 = p2.y();
1741     qreal y = pos.y();
1742
1743     int dir = 1;
1744
1745     if (qFuzzyCompare(y1, y2)) {
1746         // ignore horizontal lines according to scan conversion rule
1747         return;
1748     } else if (y2 < y1) {
1749         qreal x_tmp = x2; x2 = x1; x1 = x_tmp;
1750         qreal y_tmp = y2; y2 = y1; y1 = y_tmp;
1751         dir = -1;
1752     }
1753
1754     if (y >= y1 && y < y2) {
1755         qreal x = x1 + ((x2 - x1) / (y2 - y1)) * (y - y1);
1756
1757         // count up the winding number if we're
1758         if (x<=pos.x()) {
1759             (*winding) += dir;
1760         }
1761     }
1762 }
1763
1764 static void qt_painterpath_isect_curve(const QBezier &bezier, const QPointF &pt,
1765                                        int *winding, int depth = 0)
1766 {
1767     qreal y = pt.y();
1768     qreal x = pt.x();
1769     QRectF bounds = bezier.bounds();
1770
1771     // potential intersection, divide and try again...
1772     // Please note that a sideeffect of the bottom exclusion is that
1773     // horizontal lines are dropped, but this is correct according to
1774     // scan conversion rules.
1775     if (y >= bounds.y() && y < bounds.y() + bounds.height()) {
1776
1777         // hit lower limit... This is a rough threshold, but its a
1778         // tradeoff between speed and precision.
1779         const qreal lower_bound = qreal(.001);
1780         if (depth == 32 || (bounds.width() < lower_bound && bounds.height() < lower_bound)) {
1781             // We make the assumption here that the curve starts to
1782             // approximate a line after while (i.e. that it doesn't
1783             // change direction drastically during its slope)
1784             if (bezier.pt1().x() <= x) {
1785                 (*winding) += (bezier.pt4().y() > bezier.pt1().y() ? 1 : -1);
1786             }
1787             return;
1788         }
1789
1790         // split curve and try again...
1791         QBezier first_half, second_half;
1792         bezier.split(&first_half, &second_half);
1793         qt_painterpath_isect_curve(first_half, pt, winding, depth + 1);
1794         qt_painterpath_isect_curve(second_half, pt, winding, depth + 1);
1795     }
1796 }
1797
1798 /*!
1799     \fn bool QPainterPath::contains(const QPointF &point) const
1800
1801     Returns true if the given \a point is inside the path, otherwise
1802     returns false.
1803
1804     \sa intersects()
1805 */
1806 bool QPainterPath::contains(const QPointF &pt) const
1807 {
1808     if (isEmpty() || !controlPointRect().contains(pt))
1809         return false;
1810
1811     QPainterPathData *d = d_func();
1812
1813     int winding_number = 0;
1814
1815     QPointF last_pt;
1816     QPointF last_start;
1817     for (int i=0; i<d->elements.size(); ++i) {
1818         const Element &e = d->elements.at(i);
1819
1820         switch (e.type) {
1821
1822         case MoveToElement:
1823             if (i > 0) // implicitly close all paths.
1824                 qt_painterpath_isect_line(last_pt, last_start, pt, &winding_number);
1825             last_start = last_pt = e;
1826             break;
1827
1828         case LineToElement:
1829             qt_painterpath_isect_line(last_pt, e, pt, &winding_number);
1830             last_pt = e;
1831             break;
1832
1833         case CurveToElement:
1834             {
1835                 const QPainterPath::Element &cp2 = d->elements.at(++i);
1836                 const QPainterPath::Element &ep = d->elements.at(++i);
1837                 qt_painterpath_isect_curve(QBezier::fromPoints(last_pt, e, cp2, ep),
1838                                            pt, &winding_number);
1839                 last_pt = ep;
1840
1841             }
1842             break;
1843
1844         default:
1845             break;
1846         }
1847     }
1848
1849     // implicitly close last subpath
1850     if (last_pt != last_start)
1851         qt_painterpath_isect_line(last_pt, last_start, pt, &winding_number);
1852
1853     return (d->fillRule == Qt::WindingFill
1854             ? (winding_number != 0)
1855             : ((winding_number % 2) != 0));
1856 }
1857
1858 static bool qt_painterpath_isect_line_rect(qreal x1, qreal y1, qreal x2, qreal y2,
1859                                            const QRectF &rect)
1860 {
1861     qreal left = rect.left();
1862     qreal right = rect.right();
1863     qreal top = rect.top();
1864     qreal bottom = rect.bottom();
1865
1866     enum { Left, Right, Top, Bottom };
1867     // clip the lines, after cohen-sutherland, see e.g. http://www.nondot.org/~sabre/graphpro/line6.html
1868     int p1 = ((x1 < left) << Left)
1869              | ((x1 > right) << Right)
1870              | ((y1 < top) << Top)
1871              | ((y1 > bottom) << Bottom);
1872     int p2 = ((x2 < left) << Left)
1873              | ((x2 > right) << Right)
1874              | ((y2 < top) << Top)
1875              | ((y2 > bottom) << Bottom);
1876
1877     if (p1 & p2)
1878         // completely inside
1879         return false;
1880
1881     if (p1 | p2) {
1882         qreal dx = x2 - x1;
1883         qreal dy = y2 - y1;
1884
1885         // clip x coordinates
1886         if (x1 < left) {
1887             y1 += dy/dx * (left - x1);
1888             x1 = left;
1889         } else if (x1 > right) {
1890             y1 -= dy/dx * (x1 - right);
1891             x1 = right;
1892         }
1893         if (x2 < left) {
1894             y2 += dy/dx * (left - x2);
1895             x2 = left;
1896         } else if (x2 > right) {
1897             y2 -= dy/dx * (x2 - right);
1898             x2 = right;
1899         }
1900
1901         p1 = ((y1 < top) << Top)
1902              | ((y1 > bottom) << Bottom);
1903         p2 = ((y2 < top) << Top)
1904              | ((y2 > bottom) << Bottom);
1905
1906         if (p1 & p2)
1907             return false;
1908
1909         // clip y coordinates
1910         if (y1 < top) {
1911             x1 += dx/dy * (top - y1);
1912             y1 = top;
1913         } else if (y1 > bottom) {
1914             x1 -= dx/dy * (y1 - bottom);
1915             y1 = bottom;
1916         }
1917         if (y2 < top) {
1918             x2 += dx/dy * (top - y2);
1919             y2 = top;
1920         } else if (y2 > bottom) {
1921             x2 -= dx/dy * (y2 - bottom);
1922             y2 = bottom;
1923         }
1924
1925         p1 = ((x1 < left) << Left)
1926              | ((x1 > right) << Right);
1927         p2 = ((x2 < left) << Left)
1928              | ((x2 > right) << Right);
1929
1930         if (p1 & p2)
1931             return false;
1932
1933         return true;
1934     }
1935     return false;
1936 }
1937
1938 static bool qt_isect_curve_horizontal(const QBezier &bezier, qreal y, qreal x1, qreal x2, int depth = 0)
1939 {
1940     QRectF bounds = bezier.bounds();
1941
1942     if (y >= bounds.top() && y < bounds.bottom()
1943         && bounds.right() >= x1 && bounds.left() < x2) {
1944         const qreal lower_bound = qreal(.01);
1945         if (depth == 32 || (bounds.width() < lower_bound && bounds.height() < lower_bound))
1946             return true;
1947
1948         QBezier first_half, second_half;
1949         bezier.split(&first_half, &second_half);
1950         if (qt_isect_curve_horizontal(first_half, y, x1, x2, depth + 1)
1951             || qt_isect_curve_horizontal(second_half, y, x1, x2, depth + 1))
1952             return true;
1953     }
1954     return false;
1955 }
1956
1957 static bool qt_isect_curve_vertical(const QBezier &bezier, qreal x, qreal y1, qreal y2, int depth = 0)
1958 {
1959     QRectF bounds = bezier.bounds();
1960
1961     if (x >= bounds.left() && x < bounds.right()
1962         && bounds.bottom() >= y1 && bounds.top() < y2) {
1963         const qreal lower_bound = qreal(.01);
1964         if (depth == 32 || (bounds.width() < lower_bound && bounds.height() < lower_bound))
1965             return true;
1966
1967         QBezier first_half, second_half;
1968         bezier.split(&first_half, &second_half);
1969         if (qt_isect_curve_vertical(first_half, x, y1, y2, depth + 1)
1970             || qt_isect_curve_vertical(second_half, x, y1, y2, depth + 1))
1971             return true;
1972     }
1973      return false;
1974 }
1975
1976 /*
1977     Returns true if any lines or curves cross the four edges in of rect
1978 */
1979 static bool qt_painterpath_check_crossing(const QPainterPath *path, const QRectF &rect)
1980 {
1981     QPointF last_pt;
1982     QPointF last_start;
1983     for (int i=0; i<path->elementCount(); ++i) {
1984         const QPainterPath::Element &e = path->elementAt(i);
1985
1986         switch (e.type) {
1987
1988         case QPainterPath::MoveToElement:
1989             if (i > 0
1990                 && qFuzzyCompare(last_pt.x(), last_start.x())
1991                 && qFuzzyCompare(last_pt.y(), last_start.y())
1992                 && qt_painterpath_isect_line_rect(last_pt.x(), last_pt.y(),
1993                                                   last_start.x(), last_start.y(), rect))
1994                 return true;
1995             last_start = last_pt = e;
1996             break;
1997
1998         case QPainterPath::LineToElement:
1999             if (qt_painterpath_isect_line_rect(last_pt.x(), last_pt.y(), e.x, e.y, rect))
2000                 return true;
2001             last_pt = e;
2002             break;
2003
2004         case QPainterPath::CurveToElement:
2005             {
2006                 QPointF cp2 = path->elementAt(++i);
2007                 QPointF ep = path->elementAt(++i);
2008                 QBezier bezier = QBezier::fromPoints(last_pt, e, cp2, ep);
2009                 if (qt_isect_curve_horizontal(bezier, rect.top(), rect.left(), rect.right())
2010                     || qt_isect_curve_horizontal(bezier, rect.bottom(), rect.left(), rect.right())
2011                     || qt_isect_curve_vertical(bezier, rect.left(), rect.top(), rect.bottom())
2012                     || qt_isect_curve_vertical(bezier, rect.right(), rect.top(), rect.bottom()))
2013                     return true;
2014                 last_pt = ep;
2015             }
2016             break;
2017
2018         default:
2019             break;
2020         }
2021     }
2022
2023     // implicitly close last subpath
2024     if (last_pt != last_start
2025         && qt_painterpath_isect_line_rect(last_pt.x(), last_pt.y(),
2026                                           last_start.x(), last_start.y(), rect))
2027         return true;
2028
2029     return false;
2030 }
2031
2032 /*!
2033     \fn bool QPainterPath::intersects(const QRectF &rectangle) const
2034
2035     Returns true if any point in the given \a rectangle intersects the
2036     path; otherwise returns false.
2037
2038     There is an intersection if any of the lines making up the
2039     rectangle crosses a part of the path or if any part of the
2040     rectangle overlaps with any area enclosed by the path. This
2041     function respects the current fillRule to determine what is
2042     considered inside the path.
2043
2044     \sa contains()
2045 */
2046 bool QPainterPath::intersects(const QRectF &rect) const
2047 {
2048     if (elementCount() == 1 && rect.contains(elementAt(0)))
2049         return true;
2050
2051     if (isEmpty())
2052         return false;
2053
2054     QRectF cp = controlPointRect();
2055     QRectF rn = rect.normalized();
2056
2057     // QRectF::intersects returns false if one of the rects is a null rect
2058     // which would happen for a painter path consisting of a vertical or
2059     // horizontal line
2060     if (qMax(rn.left(), cp.left()) > qMin(rn.right(), cp.right())
2061         || qMax(rn.top(), cp.top()) > qMin(rn.bottom(), cp.bottom()))
2062         return false;
2063
2064     // If any path element cross the rect its bound to be an intersection
2065     if (qt_painterpath_check_crossing(this, rect))
2066         return true;
2067
2068     if (contains(rect.center()))
2069         return true;
2070
2071     Q_D(QPainterPath);
2072
2073     // Check if the rectangle surounds any subpath...
2074     for (int i=0; i<d->elements.size(); ++i) {
2075         const Element &e = d->elements.at(i);
2076         if (e.type == QPainterPath::MoveToElement && rect.contains(e))
2077             return true;
2078     }
2079
2080     return false;
2081 }
2082
2083 /*!
2084     Translates all elements in the path by (\a{dx}, \a{dy}).
2085
2086     \since 4.6
2087     \sa translated()
2088 */
2089 void QPainterPath::translate(qreal dx, qreal dy)
2090 {
2091     if (!d_ptr || (dx == 0 && dy == 0))
2092         return;
2093
2094     int elementsLeft = d_ptr->elements.size();
2095     if (elementsLeft <= 0)
2096         return;
2097
2098     detach();
2099     QPainterPath::Element *element = d_func()->elements.data();
2100     Q_ASSERT(element);
2101     while (elementsLeft--) {
2102         element->x += dx;
2103         element->y += dy;
2104         ++element;
2105     }
2106 }
2107
2108 /*!
2109     \fn void QPainterPath::translate(const QPointF &offset)
2110     \overload
2111     \since 4.6
2112
2113     Translates all elements in the path by the given \a offset.
2114
2115     \sa translated()
2116 */
2117
2118 /*!
2119     Returns a copy of the path that is translated by (\a{dx}, \a{dy}).
2120
2121     \since 4.6
2122     \sa translate()
2123 */
2124 QPainterPath QPainterPath::translated(qreal dx, qreal dy) const
2125 {
2126     QPainterPath copy(*this);
2127     copy.translate(dx, dy);
2128     return copy;
2129 }
2130
2131 /*!
2132     \fn QPainterPath QPainterPath::translated(const QPointF &offset) const;
2133     \overload
2134     \since 4.6
2135
2136     Returns a copy of the path that is translated by the given \a offset.
2137
2138     \sa translate()
2139 */
2140
2141 /*!
2142     \fn bool QPainterPath::contains(const QRectF &rectangle) const
2143
2144     Returns true if the given \a rectangle is inside the path,
2145     otherwise returns false.
2146 */
2147 bool QPainterPath::contains(const QRectF &rect) const
2148 {
2149     Q_D(QPainterPath);
2150
2151     // the path is empty or the control point rect doesn't completely
2152     // cover the rectangle we abort stratight away.
2153     if (isEmpty() || !controlPointRect().contains(rect))
2154         return false;
2155
2156     // if there are intersections, chances are that the rect is not
2157     // contained, except if we have winding rule, in which case it
2158     // still might.
2159     if (qt_painterpath_check_crossing(this, rect)) {
2160         if (fillRule() == Qt::OddEvenFill) {
2161             return false;
2162         } else {
2163             // Do some wague sampling in the winding case. This is not
2164             // precise but it should mostly be good enough.
2165             if (!contains(rect.topLeft()) ||
2166                 !contains(rect.topRight()) ||
2167                 !contains(rect.bottomRight()) ||
2168                 !contains(rect.bottomLeft()))
2169                 return false;
2170         }
2171     }
2172
2173     // If there exists a point inside that is not part of the path its
2174     // because: rectangle lies completely outside path or a subpath
2175     // excludes parts of the rectangle. Both cases mean that the rect
2176     // is not contained
2177     if (!contains(rect.center()))
2178         return false;
2179
2180     // If there are any subpaths inside this rectangle we need to
2181     // check if they are still contained as a result of the fill
2182     // rule. This can only be the case for WindingFill though. For
2183     // OddEvenFill the rect will never be contained if it surrounds a
2184     // subpath. (the case where two subpaths are completely identical
2185     // can be argued but we choose to neglect it).
2186     for (int i=0; i<d->elements.size(); ++i) {
2187         const Element &e = d->elements.at(i);
2188         if (e.type == QPainterPath::MoveToElement && rect.contains(e)) {
2189             if (fillRule() == Qt::OddEvenFill)
2190                 return false;
2191
2192             bool stop = false;
2193             for (; !stop && i<d->elements.size(); ++i) {
2194                 const Element &el = d->elements.at(i);
2195                 switch (el.type) {
2196                 case MoveToElement:
2197                     stop = true;
2198                     break;
2199                 case LineToElement:
2200                     if (!contains(el))
2201                         return false;
2202                     break;
2203                 case CurveToElement:
2204                     if (!contains(d->elements.at(i+2)))
2205                         return false;
2206                     i += 2;
2207                     break;
2208                 default:
2209                     break;
2210                 }
2211             }
2212
2213             // compensate for the last ++i in the inner for
2214             --i;
2215         }
2216     }
2217
2218     return true;
2219 }
2220
2221 static inline bool epsilonCompare(const QPointF &a, const QPointF &b, const QSizeF &epsilon)
2222 {
2223     return qAbs(a.x() - b.x()) <= epsilon.width()
2224         && qAbs(a.y() - b.y()) <= epsilon.height();
2225 }
2226
2227 /*!
2228     Returns true if this painterpath is equal to the given \a path.
2229
2230     Note that comparing paths may involve a per element comparison
2231     which can be slow for complex paths.
2232
2233     \sa operator!=()
2234 */
2235
2236 bool QPainterPath::operator==(const QPainterPath &path) const
2237 {
2238     QPainterPathData *d = reinterpret_cast<QPainterPathData *>(d_func());
2239     if (path.d_func() == d)
2240         return true;
2241     else if (!d || !path.d_func())
2242         return false;
2243     else if (d->fillRule != path.d_func()->fillRule)
2244         return false;
2245     else if (d->elements.size() != path.d_func()->elements.size())
2246         return false;
2247
2248     const qreal qt_epsilon = sizeof(qreal) == sizeof(double) ? 1e-12 : qreal(1e-5);
2249
2250     QSizeF epsilon = boundingRect().size();
2251     epsilon.rwidth() *= qt_epsilon;
2252     epsilon.rheight() *= qt_epsilon;
2253
2254     for (int i = 0; i < d->elements.size(); ++i)
2255         if (d->elements.at(i).type != path.d_func()->elements.at(i).type
2256             || !epsilonCompare(d->elements.at(i), path.d_func()->elements.at(i), epsilon))
2257             return false;
2258
2259     return true;
2260 }
2261
2262 /*!
2263     Returns true if this painter path differs from the given \a path.
2264
2265     Note that comparing paths may involve a per element comparison
2266     which can be slow for complex paths.
2267
2268     \sa operator==()
2269 */
2270
2271 bool QPainterPath::operator!=(const QPainterPath &path) const
2272 {
2273     return !(*this==path);
2274 }
2275
2276 /*!
2277     \since 4.5
2278
2279     Returns the intersection of this path and the \a other path.
2280
2281     \sa intersected(), operator&=(), united(), operator|()
2282 */
2283 QPainterPath QPainterPath::operator&(const QPainterPath &other) const
2284 {
2285     return intersected(other);
2286 }
2287
2288 /*!
2289     \since 4.5
2290
2291     Returns the union of this path and the \a other path.
2292
2293     \sa united(), operator|=(), intersected(), operator&()
2294 */
2295 QPainterPath QPainterPath::operator|(const QPainterPath &other) const
2296 {
2297     return united(other);
2298 }
2299
2300 /*!
2301     \since 4.5
2302
2303     Returns the union of this path and the \a other path. This function is equivalent
2304     to operator|().
2305
2306     \sa united(), operator+=(), operator-()
2307 */
2308 QPainterPath QPainterPath::operator+(const QPainterPath &other) const
2309 {
2310     return united(other);
2311 }
2312
2313 /*!
2314     \since 4.5
2315
2316     Subtracts the \a other path from a copy of this path, and returns the copy.
2317
2318     \sa subtracted(), operator-=(), operator+()
2319 */
2320 QPainterPath QPainterPath::operator-(const QPainterPath &other) const
2321 {
2322     return subtracted(other);
2323 }
2324
2325 /*!
2326     \since 4.5
2327
2328     Intersects this path with \a other and returns a reference to this path.
2329
2330     \sa intersected(), operator&(), operator|=()
2331 */
2332 QPainterPath &QPainterPath::operator&=(const QPainterPath &other)
2333 {
2334     return *this = (*this & other);
2335 }
2336
2337 /*!
2338     \since 4.5
2339
2340     Unites this path with \a other and returns a reference to this path.
2341
2342     \sa united(), operator|(), operator&=()
2343 */
2344 QPainterPath &QPainterPath::operator|=(const QPainterPath &other)
2345 {
2346     return *this = (*this | other);
2347 }
2348
2349 /*!
2350     \since 4.5
2351
2352     Unites this path with \a other, and returns a reference to this path. This
2353     is equivalent to operator|=().
2354
2355     \sa united(), operator+(), operator-=()
2356 */
2357 QPainterPath &QPainterPath::operator+=(const QPainterPath &other)
2358 {
2359     return *this = (*this + other);
2360 }
2361
2362 /*!
2363     \since 4.5
2364
2365     Subtracts \a other from this path, and returns a reference to this
2366     path.
2367
2368     \sa subtracted(), operator-(), operator+=()
2369 */
2370 QPainterPath &QPainterPath::operator-=(const QPainterPath &other)
2371 {
2372     return *this = (*this - other);
2373 }
2374
2375 #ifndef QT_NO_DATASTREAM
2376 /*!
2377     \fn QDataStream &operator<<(QDataStream &stream, const QPainterPath &path)
2378     \relates QPainterPath
2379
2380     Writes the given painter \a path to the given \a stream, and
2381     returns a reference to the \a stream.
2382
2383     \sa {Serializing Qt Data Types}
2384 */
2385 QDataStream &operator<<(QDataStream &s, const QPainterPath &p)
2386 {
2387     if (p.isEmpty()) {
2388         s << 0;
2389         return s;
2390     }
2391
2392     s << p.elementCount();
2393     for (int i=0; i < p.d_func()->elements.size(); ++i) {
2394         const QPainterPath::Element &e = p.d_func()->elements.at(i);
2395         s << int(e.type);
2396         s << double(e.x) << double(e.y);
2397     }
2398     s << p.d_func()->cStart;
2399     s << int(p.d_func()->fillRule);
2400     return s;
2401 }
2402
2403 /*!
2404     \fn QDataStream &operator>>(QDataStream &stream, QPainterPath &path)
2405     \relates QPainterPath
2406
2407     Reads a painter path from the given \a stream into the specified \a path,
2408     and returns a reference to the \a stream.
2409
2410     \sa {Serializing Qt Data Types}
2411 */
2412 QDataStream &operator>>(QDataStream &s, QPainterPath &p)
2413 {
2414     int size;
2415     s >> size;
2416
2417     if (size == 0)
2418         return s;
2419
2420     p.ensureData(); // in case if p.d_func() == 0
2421     if (p.d_func()->elements.size() == 1) {
2422         Q_ASSERT(p.d_func()->elements.at(0).type == QPainterPath::MoveToElement);
2423         p.d_func()->elements.clear();
2424     }
2425     p.d_func()->elements.reserve(p.d_func()->elements.size() + size);
2426     for (int i=0; i<size; ++i) {
2427         int type;
2428         double x, y;
2429         s >> type;
2430         s >> x;
2431         s >> y;
2432         Q_ASSERT(type >= 0 && type <= 3);
2433         if (!qt_is_finite(x) || !qt_is_finite(y)) {
2434 #ifndef QT_NO_DEBUG
2435             qWarning("QDataStream::operator>>: NaN or Inf element found in path, skipping it");
2436 #endif
2437             continue;
2438         }
2439         QPainterPath::Element elm = { qreal(x), qreal(y), QPainterPath::ElementType(type) };
2440         p.d_func()->elements.append(elm);
2441     }
2442     s >> p.d_func()->cStart;
2443     int fillRule;
2444     s >> fillRule;
2445     Q_ASSERT(fillRule == Qt::OddEvenFill || Qt::WindingFill);
2446     p.d_func()->fillRule = Qt::FillRule(fillRule);
2447     p.d_func()->dirtyBounds = true;
2448     p.d_func()->dirtyControlBounds = true;
2449     return s;
2450 }
2451 #endif // QT_NO_DATASTREAM
2452
2453
2454 /*******************************************************************************
2455  * class QPainterPathStroker
2456  */
2457
2458 void qt_path_stroke_move_to(qfixed x, qfixed y, void *data)
2459 {
2460     ((QPainterPath *) data)->moveTo(qt_fixed_to_real(x), qt_fixed_to_real(y));
2461 }
2462
2463 void qt_path_stroke_line_to(qfixed x, qfixed y, void *data)
2464 {
2465     ((QPainterPath *) data)->lineTo(qt_fixed_to_real(x), qt_fixed_to_real(y));
2466 }
2467
2468 void qt_path_stroke_cubic_to(qfixed c1x, qfixed c1y,
2469                              qfixed c2x, qfixed c2y,
2470                              qfixed ex, qfixed ey,
2471                              void *data)
2472 {
2473     ((QPainterPath *) data)->cubicTo(qt_fixed_to_real(c1x), qt_fixed_to_real(c1y),
2474                                      qt_fixed_to_real(c2x), qt_fixed_to_real(c2y),
2475                                      qt_fixed_to_real(ex), qt_fixed_to_real(ey));
2476 }
2477
2478 /*!
2479     \since 4.1
2480     \class QPainterPathStroker
2481     \ingroup painting
2482     \inmodule QtGui
2483
2484     \brief The QPainterPathStroker class is used to generate fillable
2485     outlines for a given painter path.
2486
2487     By calling the createStroke() function, passing a given
2488     QPainterPath as argument, a new painter path representing the
2489     outline of the given path is created. The newly created painter
2490     path can then be filled to draw the original painter path's
2491     outline.
2492
2493     You can control the various design aspects (width, cap styles,
2494     join styles and dash pattern) of the outlining using the following
2495     functions:
2496
2497     \list
2498     \li setWidth()
2499     \li setCapStyle()
2500     \li setJoinStyle()
2501     \li setDashPattern()
2502     \endlist
2503
2504     The setDashPattern() function accepts both a Qt::PenStyle object
2505     and a vector representation of the pattern as argument.
2506
2507     In addition you can specify a curve's threshold, controlling the
2508     granularity with which a curve is drawn, using the
2509     setCurveThreshold() function. The default threshold is a well
2510     adjusted value (0.25), and normally you should not need to modify
2511     it. However, you can make the curve's appearance smoother by
2512     decreasing its value.
2513
2514     You can also control the miter limit for the generated outline
2515     using the setMiterLimit() function. The miter limit describes how
2516     far from each join the miter join can extend. The limit is
2517     specified in the units of width so the pixelwise miter limit will
2518     be \c {miterlimit * width}. This value is only used if the join
2519     style is Qt::MiterJoin.
2520
2521     The painter path generated by the createStroke() function should
2522     only be used for outlining the given painter path. Otherwise it
2523     may cause unexpected behavior. Generated outlines also require the
2524     Qt::WindingFill rule which is set by default.
2525
2526     \sa QPen, QBrush
2527 */
2528
2529 QPainterPathStrokerPrivate::QPainterPathStrokerPrivate()
2530     : dashOffset(0)
2531 {
2532     stroker.setMoveToHook(qt_path_stroke_move_to);
2533     stroker.setLineToHook(qt_path_stroke_line_to);
2534     stroker.setCubicToHook(qt_path_stroke_cubic_to);
2535 }
2536
2537 /*!
2538    Creates a new stroker.
2539  */
2540 QPainterPathStroker::QPainterPathStroker()
2541     : d_ptr(new QPainterPathStrokerPrivate)
2542 {
2543 }
2544
2545 /*!
2546     Destroys the stroker.
2547 */
2548 QPainterPathStroker::~QPainterPathStroker()
2549 {
2550 }
2551
2552
2553 /*!
2554     Generates a new path that is a fillable area representing the
2555     outline of the given \a path.
2556
2557     The various design aspects of the outline are based on the
2558     stroker's properties: width(), capStyle(), joinStyle(),
2559     dashPattern(), curveThreshold() and miterLimit().
2560
2561     The generated path should only be used for outlining the given
2562     painter path. Otherwise it may cause unexpected
2563     behavior. Generated outlines also require the Qt::WindingFill rule
2564     which is set by default.
2565 */
2566 QPainterPath QPainterPathStroker::createStroke(const QPainterPath &path) const
2567 {
2568     QPainterPathStrokerPrivate *d = const_cast<QPainterPathStrokerPrivate *>(d_func());
2569     QPainterPath stroke;
2570     if (path.isEmpty())
2571         return path;
2572     if (d->dashPattern.isEmpty()) {
2573         d->stroker.strokePath(path, &stroke, QTransform());
2574     } else {
2575         QDashStroker dashStroker(&d->stroker);
2576         dashStroker.setDashPattern(d->dashPattern);
2577         dashStroker.setDashOffset(d->dashOffset);
2578         dashStroker.setClipRect(d->stroker.clipRect());
2579         dashStroker.strokePath(path, &stroke, QTransform());
2580     }
2581     stroke.setFillRule(Qt::WindingFill);
2582     return stroke;
2583 }
2584
2585 /*!
2586     Sets the width of the generated outline painter path to \a width.
2587
2588     The generated outlines will extend approximately 50% of \a width
2589     to each side of the given input path's original outline.
2590 */
2591 void QPainterPathStroker::setWidth(qreal width)
2592 {
2593     Q_D(QPainterPathStroker);
2594     if (width <= 0)
2595         width = 1;
2596     d->stroker.setStrokeWidth(qt_real_to_fixed(width));
2597 }
2598
2599 /*!
2600     Returns the width of the generated outlines.
2601 */
2602 qreal QPainterPathStroker::width() const
2603 {
2604     return qt_fixed_to_real(d_func()->stroker.strokeWidth());
2605 }
2606
2607
2608 /*!
2609     Sets the cap style of the generated outlines to \a style.  If a
2610     dash pattern is set, each segment of the pattern is subject to the
2611     cap \a style.
2612 */
2613 void QPainterPathStroker::setCapStyle(Qt::PenCapStyle style)
2614 {
2615     d_func()->stroker.setCapStyle(style);
2616 }
2617
2618
2619 /*!
2620     Returns the cap style of the generated outlines.
2621 */
2622 Qt::PenCapStyle QPainterPathStroker::capStyle() const
2623 {
2624     return d_func()->stroker.capStyle();
2625 }
2626
2627 /*!
2628     Sets the join style of the generated outlines to \a style.
2629 */
2630 void QPainterPathStroker::setJoinStyle(Qt::PenJoinStyle style)
2631 {
2632     d_func()->stroker.setJoinStyle(style);
2633 }
2634
2635 /*!
2636     Returns the join style of the generated outlines.
2637 */
2638 Qt::PenJoinStyle QPainterPathStroker::joinStyle() const
2639 {
2640     return d_func()->stroker.joinStyle();
2641 }
2642
2643 /*!
2644     Sets the miter limit of the generated outlines to \a limit.
2645
2646     The miter limit describes how far from each join the miter join
2647     can extend. The limit is specified in units of the currently set
2648     width. So the pixelwise miter limit will be \c { miterlimit *
2649     width}.
2650
2651     This value is only used if the join style is Qt::MiterJoin.
2652 */
2653 void QPainterPathStroker::setMiterLimit(qreal limit)
2654 {
2655     d_func()->stroker.setMiterLimit(qt_real_to_fixed(limit));
2656 }
2657
2658 /*!
2659     Returns the miter limit for the generated outlines.
2660 */
2661 qreal QPainterPathStroker::miterLimit() const
2662 {
2663     return qt_fixed_to_real(d_func()->stroker.miterLimit());
2664 }
2665
2666
2667 /*!
2668     Specifies the curve flattening \a threshold, controlling the
2669     granularity with which the generated outlines' curve is drawn.
2670
2671     The default threshold is a well adjusted value (0.25), and
2672     normally you should not need to modify it. However, you can make
2673     the curve's appearance smoother by decreasing its value.
2674 */
2675 void QPainterPathStroker::setCurveThreshold(qreal threshold)
2676 {
2677     d_func()->stroker.setCurveThreshold(qt_real_to_fixed(threshold));
2678 }
2679
2680 /*!
2681     Returns the curve flattening threshold for the generated
2682     outlines.
2683 */
2684 qreal QPainterPathStroker::curveThreshold() const
2685 {
2686     return qt_fixed_to_real(d_func()->stroker.curveThreshold());
2687 }
2688
2689 /*!
2690     Sets the dash pattern for the generated outlines to \a style.
2691 */
2692 void QPainterPathStroker::setDashPattern(Qt::PenStyle style)
2693 {
2694     d_func()->dashPattern = QDashStroker::patternForStyle(style);
2695 }
2696
2697 /*!
2698     \overload
2699
2700     Sets the dash pattern for the generated outlines to \a
2701     dashPattern.  This function makes it possible to specify custom
2702     dash patterns.
2703
2704     Each element in the vector contains the lengths of the dashes and spaces
2705     in the stroke, beginning with the first dash in the first element, the
2706     first space in the second element, and alternating between dashes and
2707     spaces for each following pair of elements.
2708
2709     The vector can contain an odd number of elements, in which case the last
2710     element will be extended by the length of the first element when the
2711     pattern repeats.
2712 */
2713 void QPainterPathStroker::setDashPattern(const QVector<qreal> &dashPattern)
2714 {
2715     d_func()->dashPattern.clear();
2716     for (int i=0; i<dashPattern.size(); ++i)
2717         d_func()->dashPattern << qt_real_to_fixed(dashPattern.at(i));
2718 }
2719
2720 /*!
2721     Returns the dash pattern for the generated outlines.
2722 */
2723 QVector<qreal> QPainterPathStroker::dashPattern() const
2724 {
2725     return d_func()->dashPattern;
2726 }
2727
2728 /*!
2729     Returns the dash offset for the generated outlines.
2730  */
2731 qreal QPainterPathStroker::dashOffset() const
2732 {
2733     return d_func()->dashOffset;
2734 }
2735
2736 /*!
2737   Sets the dash offset for the generated outlines to \a offset.
2738
2739   See the documentation for QPen::setDashOffset() for a description of the
2740   dash offset.
2741  */
2742 void QPainterPathStroker::setDashOffset(qreal offset)
2743 {
2744     d_func()->dashOffset = offset;
2745 }
2746
2747 /*!
2748   Converts the path into a polygon using the QTransform
2749   \a matrix, and returns the polygon.
2750
2751   The polygon is created by first converting all subpaths to
2752   polygons, then using a rewinding technique to make sure that
2753   overlapping subpaths can be filled using the correct fill rule.
2754
2755   Note that rewinding inserts addition lines in the polygon so
2756   the outline of the fill polygon does not match the outline of
2757   the path.
2758
2759   \sa toSubpathPolygons(), toFillPolygons(),
2760   {QPainterPath#QPainterPath Conversion}{QPainterPath Conversion}
2761 */
2762 QPolygonF QPainterPath::toFillPolygon(const QTransform &matrix) const
2763 {
2764
2765     QList<QPolygonF> flats = toSubpathPolygons(matrix);
2766     QPolygonF polygon;
2767     if (flats.isEmpty())
2768         return polygon;
2769     QPointF first = flats.first().first();
2770     for (int i=0; i<flats.size(); ++i) {
2771         polygon += flats.at(i);
2772         if (!flats.at(i).isClosed())
2773             polygon += flats.at(i).first();
2774         if (i > 0)
2775             polygon += first;
2776     }
2777     return polygon;
2778 }
2779
2780 /*!
2781   \overload
2782 */
2783 QPolygonF QPainterPath::toFillPolygon(const QMatrix &matrix) const
2784 {
2785     return toFillPolygon(QTransform(matrix));
2786 }
2787
2788
2789 //derivative of the equation
2790 static inline qreal slopeAt(qreal t, qreal a, qreal b, qreal c, qreal d)
2791 {
2792     return 3*t*t*(d - 3*c + 3*b - a) + 6*t*(c - 2*b + a) + 3*(b - a);
2793 }
2794
2795 /*!
2796     Returns the length of the current path.
2797 */
2798 qreal QPainterPath::length() const
2799 {
2800     Q_D(QPainterPath);
2801     if (isEmpty())
2802         return 0;
2803
2804     qreal len = 0;
2805     for (int i=1; i<d->elements.size(); ++i) {
2806         const Element &e = d->elements.at(i);
2807
2808         switch (e.type) {
2809         case MoveToElement:
2810             break;
2811         case LineToElement:
2812         {
2813             len += QLineF(d->elements.at(i-1), e).length();
2814             break;
2815         }
2816         case CurveToElement:
2817         {
2818             QBezier b = QBezier::fromPoints(d->elements.at(i-1),
2819                                             e,
2820                                             d->elements.at(i+1),
2821                                             d->elements.at(i+2));
2822             len += b.length();
2823             i += 2;
2824             break;
2825         }
2826         default:
2827             break;
2828         }
2829     }
2830     return len;
2831 }
2832
2833 /*!
2834     Returns percentage of the whole path at the specified length \a len.
2835
2836     Note that similarly to other percent methods, the percentage measurement
2837     is not linear with regards to the length, if curves are present
2838     in the path. When curves are present the percentage argument is mapped
2839     to the t parameter of the Bezier equations.
2840 */
2841 qreal QPainterPath::percentAtLength(qreal len) const
2842 {
2843     Q_D(QPainterPath);
2844     if (isEmpty() || len <= 0)
2845         return 0;
2846
2847     qreal totalLength = length();
2848     if (len > totalLength)
2849         return 1;
2850
2851     qreal curLen = 0;
2852     for (int i=1; i<d->elements.size(); ++i) {
2853         const Element &e = d->elements.at(i);
2854
2855         switch (e.type) {
2856         case MoveToElement:
2857             break;
2858         case LineToElement:
2859         {
2860             QLineF line(d->elements.at(i-1), e);
2861             qreal llen = line.length();
2862             curLen += llen;
2863             if (curLen >= len) {
2864                 return len/totalLength ;
2865             }
2866
2867             break;
2868         }
2869         case CurveToElement:
2870         {
2871             QBezier b = QBezier::fromPoints(d->elements.at(i-1),
2872                                             e,
2873                                             d->elements.at(i+1),
2874                                             d->elements.at(i+2));
2875             qreal blen = b.length();
2876             qreal prevLen = curLen;
2877             curLen += blen;
2878
2879             if (curLen >= len) {
2880                 qreal res = b.tAtLength(len - prevLen);
2881                 return (res * blen + prevLen)/totalLength;
2882             }
2883
2884             i += 2;
2885             break;
2886         }
2887         default:
2888             break;
2889         }
2890     }
2891
2892     return 0;
2893 }
2894
2895 static inline QBezier bezierAtT(const QPainterPath &path, qreal t, qreal *startingLength, qreal *bezierLength)
2896 {
2897     *startingLength = 0;
2898     if (t > 1)
2899         return QBezier();
2900
2901     qreal curLen = 0;
2902     qreal totalLength = path.length();
2903
2904     const int lastElement = path.elementCount() - 1;
2905     for (int i=0; i <= lastElement; ++i) {
2906         const QPainterPath::Element &e = path.elementAt(i);
2907
2908         switch (e.type) {
2909         case QPainterPath::MoveToElement:
2910             break;
2911         case QPainterPath::LineToElement:
2912         {
2913             QLineF line(path.elementAt(i-1), e);
2914             qreal llen = line.length();
2915             curLen += llen;
2916             if (i == lastElement || curLen/totalLength >= t) {
2917                 *bezierLength = llen;
2918                 QPointF a = path.elementAt(i-1);
2919                 QPointF delta = e - a;
2920                 return QBezier::fromPoints(a, a + delta / 3, a + 2 * delta / 3, e);
2921             }
2922             break;
2923         }
2924         case QPainterPath::CurveToElement:
2925         {
2926             QBezier b = QBezier::fromPoints(path.elementAt(i-1),
2927                                             e,
2928                                             path.elementAt(i+1),
2929                                             path.elementAt(i+2));
2930             qreal blen = b.length();
2931             curLen += blen;
2932
2933             if (i + 2 == lastElement || curLen/totalLength >= t) {
2934                 *bezierLength = blen;
2935                 return b;
2936             }
2937
2938             i += 2;
2939             break;
2940         }
2941         default:
2942             break;
2943         }
2944         *startingLength = curLen;
2945     }
2946     return QBezier();
2947 }
2948
2949 /*!
2950     Returns the point at at the percentage \a t of the current path.
2951     The argument \a t has to be between 0 and 1.
2952
2953     Note that similarly to other percent methods, the percentage measurement
2954     is not linear with regards to the length, if curves are present
2955     in the path. When curves are present the percentage argument is mapped
2956     to the t parameter of the Bezier equations.
2957 */
2958 QPointF QPainterPath::pointAtPercent(qreal t) const
2959 {
2960     if (t < 0 || t > 1) {
2961         qWarning("QPainterPath::pointAtPercent accepts only values between 0 and 1");
2962         return QPointF();
2963     }
2964
2965     if (!d_ptr || d_ptr->elements.size() == 0)
2966         return QPointF();
2967
2968     if (d_ptr->elements.size() == 1)
2969         return d_ptr->elements.at(0);
2970
2971     qreal totalLength = length();
2972     qreal curLen = 0;
2973     qreal bezierLen = 0;
2974     QBezier b = bezierAtT(*this, t, &curLen, &bezierLen);
2975     qreal realT = (totalLength * t - curLen) / bezierLen;
2976
2977     return b.pointAt(qBound(qreal(0), realT, qreal(1)));
2978 }
2979
2980 /*!
2981     Returns the angle of the path tangent at the percentage \a t.
2982     The argument \a t has to be between 0 and 1.
2983
2984     Positive values for the angles mean counter-clockwise while negative values
2985     mean the clockwise direction. Zero degrees is at the 3 o'clock position.
2986
2987     Note that similarly to the other percent methods, the percentage measurement
2988     is not linear with regards to the length if curves are present
2989     in the path. When curves are present the percentage argument is mapped
2990     to the t parameter of the Bezier equations.
2991 */
2992 qreal QPainterPath::angleAtPercent(qreal t) const
2993 {
2994     if (t < 0 || t > 1) {
2995         qWarning("QPainterPath::angleAtPercent accepts only values between 0 and 1");
2996         return 0;
2997     }
2998
2999     qreal totalLength = length();
3000     qreal curLen = 0;
3001     qreal bezierLen = 0;
3002     QBezier bez = bezierAtT(*this, t, &curLen, &bezierLen);
3003     qreal realT = (totalLength * t - curLen) / bezierLen;
3004
3005     qreal m1 = slopeAt(realT, bez.x1, bez.x2, bez.x3, bez.x4);
3006     qreal m2 = slopeAt(realT, bez.y1, bez.y2, bez.y3, bez.y4);
3007
3008     return QLineF(0, 0, m1, m2).angle();
3009 }
3010
3011
3012 /*!
3013     Returns the slope of the path at the percentage \a t. The
3014     argument \a t has to be between 0 and 1.
3015
3016     Note that similarly to other percent methods, the percentage measurement
3017     is not linear with regards to the length, if curves are present
3018     in the path. When curves are present the percentage argument is mapped
3019     to the t parameter of the Bezier equations.
3020 */
3021 qreal QPainterPath::slopeAtPercent(qreal t) const
3022 {
3023     if (t < 0 || t > 1) {
3024         qWarning("QPainterPath::slopeAtPercent accepts only values between 0 and 1");
3025         return 0;
3026     }
3027
3028     qreal totalLength = length();
3029     qreal curLen = 0;
3030     qreal bezierLen = 0;
3031     QBezier bez = bezierAtT(*this, t, &curLen, &bezierLen);
3032     qreal realT = (totalLength * t - curLen) / bezierLen;
3033
3034     qreal m1 = slopeAt(realT, bez.x1, bez.x2, bez.x3, bez.x4);
3035     qreal m2 = slopeAt(realT, bez.y1, bez.y2, bez.y3, bez.y4);
3036     //tangent line
3037     qreal slope = 0;
3038
3039 #define SIGN(x) ((x < 0)?-1:1)
3040     if (m1)
3041         slope = m2/m1;
3042     else {
3043         //windows doesn't define INFINITY :(
3044 #ifdef INFINITY
3045         slope = INFINITY*SIGN(m2);
3046 #else
3047         if (sizeof(qreal) == sizeof(double)) {
3048             return 1.79769313486231570e+308;
3049         } else {
3050             return ((qreal)3.40282346638528860e+38);
3051         }
3052 #endif
3053     }
3054
3055     return slope;
3056 }
3057
3058 /*!
3059   \since 4.4
3060
3061   Adds the given rectangle \a rect with rounded corners to the path.
3062
3063   The \a xRadius and \a yRadius arguments specify the radii of
3064   the ellipses defining the corners of the rounded rectangle.
3065   When \a mode is Qt::RelativeSize, \a xRadius and
3066   \a yRadius are specified in percentage of half the rectangle's
3067   width and height respectively, and should be in the range 0.0 to 100.0.
3068
3069   \sa addRect()
3070 */
3071 void QPainterPath::addRoundedRect(const QRectF &rect, qreal xRadius, qreal yRadius,
3072                                   Qt::SizeMode mode)
3073 {
3074     QRectF r = rect.normalized();
3075
3076     if (r.isNull())
3077         return;
3078
3079     if (mode == Qt::AbsoluteSize) {
3080         qreal w = r.width() / 2;
3081         qreal h = r.height() / 2;
3082
3083         if (w == 0) {
3084             xRadius = 0;
3085         } else {
3086             xRadius = 100 * qMin(xRadius, w) / w;
3087         }
3088         if (h == 0) {
3089             yRadius = 0;
3090         } else {
3091             yRadius = 100 * qMin(yRadius, h) / h;
3092         }
3093     } else {
3094         if (xRadius > 100)                          // fix ranges
3095             xRadius = 100;
3096
3097         if (yRadius > 100)
3098             yRadius = 100;
3099     }
3100
3101     if (xRadius <= 0 || yRadius <= 0) {             // add normal rectangle
3102         addRect(r);
3103         return;
3104     }
3105
3106     qreal x = r.x();
3107     qreal y = r.y();
3108     qreal w = r.width();
3109     qreal h = r.height();
3110     qreal rxx2 = w*xRadius/100;
3111     qreal ryy2 = h*yRadius/100;
3112
3113     ensureData();
3114     detach();
3115
3116     bool first = d_func()->elements.size() < 2;
3117
3118     arcMoveTo(x, y, rxx2, ryy2, 180);
3119     arcTo(x, y, rxx2, ryy2, 180, -90);
3120     arcTo(x+w-rxx2, y, rxx2, ryy2, 90, -90);
3121     arcTo(x+w-rxx2, y+h-ryy2, rxx2, ryy2, 0, -90);
3122     arcTo(x, y+h-ryy2, rxx2, ryy2, 270, -90);
3123     closeSubpath();
3124
3125     d_func()->require_moveTo = true;
3126     d_func()->convex = first;
3127 }
3128
3129 /*!
3130   \fn void QPainterPath::addRoundedRect(qreal x, qreal y, qreal w, qreal h, qreal xRadius, qreal yRadius, Qt::SizeMode mode = Qt::AbsoluteSize);
3131   \since 4.4
3132   \overload
3133
3134   Adds the given rectangle \a x, \a y, \a w, \a h  with rounded corners to the path.
3135  */
3136
3137 /*!
3138   \obsolete
3139
3140   Adds a rectangle \a r with rounded corners to the path.
3141
3142   The \a xRnd and \a yRnd arguments specify how rounded the corners
3143   should be. 0 is angled corners, 99 is maximum roundedness.
3144
3145   \sa addRoundedRect()
3146 */
3147 void QPainterPath::addRoundRect(const QRectF &r, int xRnd, int yRnd)
3148 {
3149     if(xRnd >= 100)                          // fix ranges
3150         xRnd = 99;
3151     if(yRnd >= 100)
3152         yRnd = 99;
3153     if(xRnd <= 0 || yRnd <= 0) {             // add normal rectangle
3154         addRect(r);
3155         return;
3156     }
3157
3158     QRectF rect = r.normalized();
3159
3160     if (rect.isNull())
3161         return;
3162
3163     qreal x = rect.x();
3164     qreal y = rect.y();
3165     qreal w = rect.width();
3166     qreal h = rect.height();
3167     qreal rxx2 = w*xRnd/100;
3168     qreal ryy2 = h*yRnd/100;
3169
3170     ensureData();
3171     detach();
3172
3173     bool first = d_func()->elements.size() < 2;
3174
3175     arcMoveTo(x, y, rxx2, ryy2, 180);
3176     arcTo(x, y, rxx2, ryy2, 180, -90);
3177     arcTo(x+w-rxx2, y, rxx2, ryy2, 90, -90);
3178     arcTo(x+w-rxx2, y+h-ryy2, rxx2, ryy2, 0, -90);
3179     arcTo(x, y+h-ryy2, rxx2, ryy2, 270, -90);
3180     closeSubpath();
3181
3182     d_func()->require_moveTo = true;
3183     d_func()->convex = first;
3184 }
3185
3186 /*!
3187   \obsolete
3188
3189   \fn bool QPainterPath::addRoundRect(const QRectF &rect, int roundness);
3190   \since 4.3
3191   \overload
3192
3193   Adds a rounded rectangle, \a rect, to the path.
3194
3195   The \a roundness argument specifies uniform roundness for the
3196   rectangle.  Vertical and horizontal roundness factors will be
3197   adjusted accordingly to act uniformly around both axes. Use this
3198   method if you want a rectangle equally rounded across both the X and
3199   Y axis.
3200
3201   \sa addRoundedRect()
3202 */
3203
3204 /*!
3205   \obsolete
3206
3207   \fn void QPainterPath::addRoundRect(qreal x, qreal y, qreal w, qreal h, int xRnd, int yRnd);
3208   \overload
3209
3210   Adds a rectangle with rounded corners to the path. The rectangle
3211   is constructed from \a x, \a y, and the width and height \a w
3212   and \a h.
3213
3214   The \a xRnd and \a yRnd arguments specify how rounded the corners
3215   should be. 0 is angled corners, 99 is maximum roundedness.
3216
3217   \sa addRoundedRect()
3218  */
3219
3220 /*!
3221   \obsolete
3222
3223   \fn bool QPainterPath::addRoundRect(qreal x, qreal y, qreal width, qreal height, int roundness);
3224   \since 4.3
3225   \overload
3226
3227   Adds a rounded rectangle to the path, defined by the coordinates \a
3228   x and \a y with the specified \a width and \a height.
3229
3230   The \a roundness argument specifies uniform roundness for the
3231   rectangle. Vertical and horizontal roundness factors will be
3232   adjusted accordingly to act uniformly around both axes. Use this
3233   method if you want a rectangle equally rounded across both the X and
3234   Y axis.
3235
3236   \sa addRoundedRect()
3237 */
3238
3239 /*!
3240     \since 4.3
3241
3242     Returns a path which is the union of this path's fill area and \a p's fill area.
3243
3244     Set operations on paths will treat the paths as areas. Non-closed
3245     paths will be treated as implicitly closed.
3246     Bezier curves may be flattened to line segments due to numerical instability of
3247     doing bezier curve intersections.
3248
3249     \sa intersected(), subtracted()
3250 */
3251 QPainterPath QPainterPath::united(const QPainterPath &p) const
3252 {
3253     if (isEmpty() || p.isEmpty())
3254         return isEmpty() ? p : *this;
3255     QPathClipper clipper(*this, p);
3256     return clipper.clip(QPathClipper::BoolOr);
3257 }
3258
3259 /*!
3260     \since 4.3
3261
3262     Returns a path which is the intersection of this path's fill area and \a p's fill area.
3263     Bezier curves may be flattened to line segments due to numerical instability of
3264     doing bezier curve intersections.
3265 */
3266 QPainterPath QPainterPath::intersected(const QPainterPath &p) const
3267 {
3268     if (isEmpty() || p.isEmpty())
3269         return QPainterPath();
3270     QPathClipper clipper(*this, p);
3271     return clipper.clip(QPathClipper::BoolAnd);
3272 }
3273
3274 /*!
3275     \since 4.3
3276
3277     Returns a path which is \a p's fill area subtracted from this path's fill area.
3278
3279     Set operations on paths will treat the paths as areas. Non-closed
3280     paths will be treated as implicitly closed.
3281     Bezier curves may be flattened to line segments due to numerical instability of
3282     doing bezier curve intersections.
3283 */
3284 QPainterPath QPainterPath::subtracted(const QPainterPath &p) const
3285 {
3286     if (isEmpty() || p.isEmpty())
3287         return *this;
3288     QPathClipper clipper(*this, p);
3289     return clipper.clip(QPathClipper::BoolSub);
3290 }
3291
3292 /*!
3293     \since 4.3
3294     \obsolete
3295
3296     Use subtracted() instead.
3297
3298     \sa subtracted()
3299 */
3300 QPainterPath QPainterPath::subtractedInverted(const QPainterPath &p) const
3301 {
3302     return p.subtracted(*this);
3303 }
3304
3305 /*!
3306     \since 4.4
3307
3308     Returns a simplified version of this path. This implies merging all subpaths that intersect,
3309     and returning a path containing no intersecting edges. Consecutive parallel lines will also
3310     be merged. The simplified path will always use the default fill rule, Qt::OddEvenFill.
3311     Bezier curves may be flattened to line segments due to numerical instability of
3312     doing bezier curve intersections.
3313 */
3314 QPainterPath QPainterPath::simplified() const
3315 {
3316     if(isEmpty())
3317         return *this;
3318     QPathClipper clipper(*this, QPainterPath());
3319     return clipper.clip(QPathClipper::Simplify);
3320 }
3321
3322 /*!
3323   \since 4.3
3324
3325   Returns true if the current path intersects at any point the given path \a p.
3326   Also returns true if the current path contains or is contained by any part of \a p.
3327
3328   Set operations on paths will treat the paths as areas. Non-closed
3329   paths will be treated as implicitly closed.
3330
3331   \sa contains()
3332  */
3333 bool QPainterPath::intersects(const QPainterPath &p) const
3334 {
3335     if (p.elementCount() == 1)
3336         return contains(p.elementAt(0));
3337     if (isEmpty() || p.isEmpty())
3338         return false;
3339     QPathClipper clipper(*this, p);
3340     return clipper.intersect();
3341 }
3342
3343 /*!
3344   \since 4.3
3345
3346   Returns true if the given path \a p is contained within
3347   the current path. Returns false if any edges of the current path and
3348   \a p intersect.
3349
3350   Set operations on paths will treat the paths as areas. Non-closed
3351   paths will be treated as implicitly closed.
3352
3353   \sa intersects()
3354  */
3355 bool QPainterPath::contains(const QPainterPath &p) const
3356 {
3357     if (p.elementCount() == 1)
3358         return contains(p.elementAt(0));
3359     if (isEmpty() || p.isEmpty())
3360         return false;
3361     QPathClipper clipper(*this, p);
3362     return clipper.contains();
3363 }
3364
3365 void QPainterPath::setDirty(bool dirty)
3366 {
3367     d_func()->dirtyBounds        = dirty;
3368     d_func()->dirtyControlBounds = dirty;
3369     delete d_func()->pathConverter;
3370     d_func()->pathConverter = 0;
3371     d_func()->convex = false;
3372 }
3373
3374 void QPainterPath::computeBoundingRect() const
3375 {
3376     QPainterPathData *d = d_func();
3377     d->dirtyBounds = false;
3378     if (!d_ptr) {
3379         d->bounds = QRect();
3380         return;
3381     }
3382
3383     qreal minx, maxx, miny, maxy;
3384     minx = maxx = d->elements.at(0).x;
3385     miny = maxy = d->elements.at(0).y;
3386     for (int i=1; i<d->elements.size(); ++i) {
3387         const Element &e = d->elements.at(i);
3388
3389         switch (e.type) {
3390         case MoveToElement:
3391         case LineToElement:
3392             if (e.x > maxx) maxx = e.x;
3393             else if (e.x < minx) minx = e.x;
3394             if (e.y > maxy) maxy = e.y;
3395             else if (e.y < miny) miny = e.y;
3396             break;
3397         case CurveToElement:
3398             {
3399                 QBezier b = QBezier::fromPoints(d->elements.at(i-1),
3400                                                 e,
3401                                                 d->elements.at(i+1),
3402                                                 d->elements.at(i+2));
3403                 QRectF r = qt_painterpath_bezier_extrema(b);
3404                 qreal right = r.right();
3405                 qreal bottom = r.bottom();
3406                 if (r.x() < minx) minx = r.x();
3407                 if (right > maxx) maxx = right;
3408                 if (r.y() < miny) miny = r.y();
3409                 if (bottom > maxy) maxy = bottom;
3410                 i += 2;
3411             }
3412             break;
3413         default:
3414             break;
3415         }
3416     }
3417     d->bounds = QRectF(minx, miny, maxx - minx, maxy - miny);
3418 }
3419
3420
3421 void QPainterPath::computeControlPointRect() const
3422 {
3423     QPainterPathData *d = d_func();
3424     d->dirtyControlBounds = false;
3425     if (!d_ptr) {
3426         d->controlBounds = QRect();
3427         return;
3428     }
3429
3430     qreal minx, maxx, miny, maxy;
3431     minx = maxx = d->elements.at(0).x;
3432     miny = maxy = d->elements.at(0).y;
3433     for (int i=1; i<d->elements.size(); ++i) {
3434         const Element &e = d->elements.at(i);
3435         if (e.x > maxx) maxx = e.x;
3436         else if (e.x < minx) minx = e.x;
3437         if (e.y > maxy) maxy = e.y;
3438         else if (e.y < miny) miny = e.y;
3439     }
3440     d->controlBounds = QRectF(minx, miny, maxx - minx, maxy - miny);
3441 }
3442
3443 #ifndef QT_NO_DEBUG_STREAM
3444 QDebug operator<<(QDebug s, const QPainterPath &p)
3445 {
3446     s.nospace() << "QPainterPath: Element count=" << p.elementCount() << endl;
3447     const char *types[] = {"MoveTo", "LineTo", "CurveTo", "CurveToData"};
3448     for (int i=0; i<p.elementCount(); ++i) {
3449         s.nospace() << " -> " << types[p.elementAt(i).type] << "(x=" << p.elementAt(i).x << ", y=" << p.elementAt(i).y << ')' << endl;
3450
3451     }
3452     return s;
3453 }
3454 #endif
3455
3456 QT_END_NAMESPACE