1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef QBEZIER_P_H

    43 #define QBEZIER_P_H

    44 

    45 //

    46 //  W A R N I N G

    47 //  -------------

    48 //

    49 // This file is not part of the Qt API.  It exists for the convenience

    50 // of other Qt classes.  This header file may change from version to

    51 // version without notice, or even be removed.

    52 //

    53 // We mean it.

    54 //

    55 

    56 #include "QtCore/qpoint.h"

    57 #include "QtCore/qline.h"

    58 #include "QtCore/qrect.h"

    59 #include "QtCore/qvector.h"

    60 #include "QtCore/qlist.h"

    61 #include "QtCore/qpair.h"

    62 

    63 QT_BEGIN_NAMESPACE

    64 

    65 class QPolygonF;

    66 

    67 class Q_GUI_EXPORT QBezier

    68 {

    69 public:

    70     static QBezier fromPoints(const QPointF &p1, const QPointF &p2,

    71                               const QPointF &p3, const QPointF &p4);

    72 

    73     static void coefficients(qreal t, qreal &a, qreal &b, qreal &c, qreal &d);

    74 

    75     inline QPointF pointAt(qreal t) const;

    76     inline QPointF normalVector(qreal t) const;

    77 

    78     inline QPointF derivedAt(qreal t) const;

    79     inline QPointF secondDerivedAt(qreal t) const;

    80 

    81     QPolygonF toPolygon() const;

    82     void addToPolygon(QPolygonF *p) const;

    83     void addToPolygonIterative(QPolygonF *p) const;

    84     void addToPolygonMixed(QPolygonF *p) const;

    85     QRectF bounds() const;

    86     qreal length(qreal error = 0.01) const;

    87     void addIfClose(qreal *length, qreal error) const;

    88 

    89     qreal tAtLength(qreal len) const;

    90 

    91     int stationaryYPoints(qreal &t0, qreal &t1) const;

    92     qreal tForY(qreal t0, qreal t1, qreal y) const;

    93 

    94     QPointF pt1() const { return QPointF(x1, y1); }

    95     QPointF pt2() const { return QPointF(x2, y2); }

    96     QPointF pt3() const { return QPointF(x3, y3); }

    97     QPointF pt4() const { return QPointF(x4, y4); }

    98 

    99     inline QPointF midPoint() const;

   100     inline QLineF midTangent() const;

   101 

   102     inline QLineF startTangent() const;

   103     inline QLineF endTangent() const;

   104 

   105     inline void parameterSplitLeft(qreal t, QBezier *left);

   106     inline void split(QBezier *firstHalf, QBezier *secondHalf) const;

   107     int shifted(QBezier *curveSegments, int maxSegmets,

   108                 qreal offset, float threshold) const;

   109 

   110     QVector< QList<QBezier> > splitAtIntersections(QBezier &a);

   111 

   112     QBezier bezierOnInterval(qreal t0, qreal t1) const;

   113 

   114     static QVector< QPair<qreal, qreal> > findIntersections(const QBezier &a,

   115                                                      const QBezier &b);

   116 

   117     static bool findIntersections(const QBezier &a, const QBezier &b,

   118                                   QVector<QPair<qreal, qreal> > *t);

   119 

   120     qreal x1, y1, x2, y2, x3, y3, x4, y4;

   121 };

   122 

   123 inline QPointF QBezier::midPoint() const

   124 {

   125     return QPointF((x1 + x4 + 3*(x2 + x3))/8., (y1 + y4 + 3*(y2 + y3))/8.);

   126 }

   127 

   128 inline QLineF QBezier::midTangent() const

   129 {

   130     QPointF mid = midPoint();

   131     QLineF dir(QLineF(x1, y1, x2, y2).pointAt(0.5), QLineF(x3, y3, x4, y4).pointAt(0.5));

   132     return QLineF(mid.x() - dir.dx(), mid.y() - dir.dy(),

   133                   mid.x() + dir.dx(), mid.y() + dir.dy());

   134 }

   135 

   136 inline QLineF QBezier::startTangent() const

   137 {

   138     QLineF tangent(pt1(), pt2());

   139     if (tangent.isNull())

   140         tangent = QLineF(pt1(), pt3());

   141     if (tangent.isNull())

   142         tangent = QLineF(pt1(), pt4());

   143     return tangent;

   144 }

   145 

   146 inline QLineF QBezier::endTangent() const

   147 {

   148     QLineF tangent(pt4(), pt3());

   149     if (tangent.isNull())

   150         tangent = QLineF(pt4(), pt2());

   151     if (tangent.isNull())

   152         tangent = QLineF(pt4(), pt1());

   153     return tangent;

   154 }

   155 

   156 inline void QBezier::coefficients(qreal t, qreal &a, qreal &b, qreal &c, qreal &d)

   157 {

   158     qreal m_t = 1. - t;

   159     b = m_t * m_t;

   160     c = t * t;

   161     d = c * t;

   162     a = b * m_t;

   163     b *= 3. * t;

   164     c *= 3. * m_t;

   165 }

   166 

   167 inline QPointF QBezier::pointAt(qreal t) const

   168 {

   169     Q_ASSERT(t >= 0);

   170     Q_ASSERT(t <= 1);

   171 #if 1

   172     qreal a, b, c, d;

   173     coefficients(t, a, b, c, d);

   174     return QPointF(a*x1 + b*x2 + c*x3 + d*x4, a*y1 + b*y2 + c*y3 + d*y4);

   175 #else

   176     // numerically more stable:

   177     qreal m_t = 1. - t;

   178     qreal a = x1*m_t + x2*t;

   179     qreal b = x2*m_t + x3*t;

   180     qreal c = x3*m_t + x4*t;

   181     a = a*m_t + b*t;

   182     b = b*m_t + c*t;

   183     qreal x = a*m_t + b*t;

   184     qreal a = y1*m_t + y2*t;

   185     qreal b = y2*m_t + y3*t;

   186     qreal c = y3*m_t + y4*t;

   187     a = a*m_t + b*t;

   188     b = b*m_t + c*t;

   189     qreal y = a*m_t + b*t;

   190     return QPointF(x, y);

   191 #endif

   192 }

   193 

   194 inline QPointF QBezier::normalVector(qreal t) const

   195 {

   196     qreal m_t = 1. - t;

   197     qreal a = m_t * m_t;

   198     qreal b = t * m_t;

   199     qreal c = t * t;

   200 

   201     return QPointF((y2-y1) * a + (y3-y2) * b + (y4-y3) * c,  -(x2-x1) * a - (x3-x2) * b - (x4-x3) * c);

   202 }

   203 

   204 inline QPointF QBezier::derivedAt(qreal t) const

   205 {

   206     // p'(t) = 3 * (-(1-2t+t^2) * p0 + (1 - 4 * t + 3 * t^2) * p1 + (2 * t - 3 * t^2) * p2 + t^2 * p3)

   207 

   208     qreal m_t = 1. - t;

   209 

   210     qreal d = t * t;

   211     qreal a = -m_t * m_t;

   212     qreal b = 1 - 4 * t + 3 * d;

   213     qreal c = 2 * t - 3 * d;

   214 

   215     return 3 * QPointF(a * x1 + b * x2 + c * x3 + d * x4,

   216                        a * y1 + b * y2 + c * y3 + d * y4);

   217 }

   218 

   219 inline QPointF QBezier::secondDerivedAt(qreal t) const

   220 {

   221     qreal a = 2. - 2. * t;

   222     qreal b = -4 + 6 * t;

   223     qreal c = 2 - 6 * t;

   224     qreal d = 2 * t;

   225 

   226     return 3 * QPointF(a * x1 + b * x2 + c * x3 + d * x4,

   227                        a * y1 + b * y2 + c * y3 + d * y4);

   228 }

   229 

   230 inline void QBezier::split(QBezier *firstHalf, QBezier *secondHalf) const

   231 {

   232     Q_ASSERT(firstHalf);

   233     Q_ASSERT(secondHalf);

   234 

   235     qreal c = (x2 + x3)*.5;

   236     firstHalf->x2 = (x1 + x2)*.5;

   237     secondHalf->x3 = (x3 + x4)*.5;

   238     firstHalf->x1 = x1;

   239     secondHalf->x4 = x4;

   240     firstHalf->x3 = (firstHalf->x2 + c)*.5;

   241     secondHalf->x2 = (secondHalf->x3 + c)*.5;

   242     firstHalf->x4 = secondHalf->x1 = (firstHalf->x3 + secondHalf->x2)*.5;

   243 

   244     c = (y2 + y3)/2;

   245     firstHalf->y2 = (y1 + y2)*.5;

   246     secondHalf->y3 = (y3 + y4)*.5;

   247     firstHalf->y1 = y1;

   248     secondHalf->y4 = y4;

   249     firstHalf->y3 = (firstHalf->y2 + c)*.5;

   250     secondHalf->y2 = (secondHalf->y3 + c)*.5;

   251     firstHalf->y4 = secondHalf->y1 = (firstHalf->y3 + secondHalf->y2)*.5;

   252 }

   253 

   254 inline void QBezier::parameterSplitLeft(qreal t, QBezier *left)

   255 {

   256     left->x1 = x1;

   257     left->y1 = y1;

   258 

   259     left->x2 = x1 + t * ( x2 - x1 );

   260     left->y2 = y1 + t * ( y2 - y1 );

   261 

   262     left->x3 = x2 + t * ( x3 - x2 ); // temporary holding spot

   263     left->y3 = y2 + t * ( y3 - y2 ); // temporary holding spot

   264 

   265     x3 = x3 + t * ( x4 - x3 );

   266     y3 = y3 + t * ( y4 - y3 );

   267 

   268     x2 = left->x3 + t * ( x3 - left->x3);

   269     y2 = left->y3 + t * ( y3 - left->y3);

   270 

   271     left->x3 = left->x2 + t * ( left->x3 - left->x2 );

   272     left->y3 = left->y2 + t * ( left->y3 - left->y2 );

   273 

   274     left->x4 = x1 = left->x3 + t * (x2 - left->x3);

   275     left->y4 = y1 = left->y3 + t * (y2 - left->y3);

   276 }

   277 

   278 QT_END_NAMESPACE

   279 

   280 #endif // QBEZIER_P_H