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 test suite 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 #include "private/qpathclipper_p.h"

    42 #include "paths.h"

    43 

    44 #include <QtTest/QtTest>

    45 

    46 #include <qpainterpath.h>

    47 #include <qpolygon.h>

    48 #include <qdebug.h>

    49 #include <qpainter.h>

    50 

    51 #include <math.h>

    52 

    53 class tst_QPathClipper : public QObject

    54 {

    55     Q_OBJECT

    56 

    57 public:

    58     tst_QPathClipper();

    59     virtual ~tst_QPathClipper();

    60 

    61 private:

    62     void clipTest(int subjectIndex, int clipIndex, QPathClipper::Operation op);

    63 

    64     QList<QPainterPath> paths;

    65 

    66 public slots:

    67     void initTestCase();

    68 

    69 private slots:

    70     void testWingedEdge();

    71 

    72     void testComparePaths();

    73 

    74     void clip_data();

    75     void clip();

    76 

    77     void clip2();

    78     void clip3();

    79 

    80     void testIntersections();

    81     void testIntersections2();

    82     void testIntersections3();

    83     void testIntersections4();

    84     void testIntersections5();

    85     void testIntersections6();

    86     void testIntersections7();

    87     void testIntersections8();

    88     void testIntersections9();

    89 

    90     void zeroDerivativeCurves();

    91 

    92     void task204301_data();

    93     void task204301();

    94 

    95     void task209056();

    96     void task251909();

    97 };

    98 

    99 Q_DECLARE_METATYPE(QPainterPath)

   100 Q_DECLARE_METATYPE(QPathClipper::Operation)

   101 

   102 tst_QPathClipper::tst_QPathClipper()

   103 {

   104 }

   105 

   106 tst_QPathClipper::~tst_QPathClipper()

   107 {

   108 }

   109 

   110 void tst_QPathClipper::initTestCase()

   111 {

   112     paths << Paths::rect();

   113     paths << Paths::heart();

   114     paths << Paths::body();

   115     paths << Paths::mailbox();

   116     paths << Paths::deer();

   117     paths << Paths::fire();

   118 

   119     paths << Paths::random1();

   120     paths << Paths::random2();

   121 

   122     paths << Paths::heart2();

   123     paths << Paths::rect2();

   124     paths << Paths::rect3();

   125     paths << Paths::rect4();

   126     paths << Paths::rect5();

   127     paths << Paths::rect6();

   128 

   129     paths << Paths::frame1();

   130     paths << Paths::frame2();

   131     paths << Paths::frame3();

   132     paths << Paths::frame4();

   133 

   134     paths << Paths::triangle1();

   135     paths << Paths::triangle2();

   136 

   137     paths << Paths::node();

   138     paths << Paths::interRect();

   139 

   140     paths << Paths::simpleCurve();

   141     paths << Paths::simpleCurve2();

   142     paths << Paths::simpleCurve3();

   143 

   144     paths << Paths::bezier1();

   145     paths << Paths::bezier2();

   146     paths << Paths::bezier3();

   147     paths << Paths::bezier4();

   148 

   149     paths << Paths::bezierFlower();

   150     paths << Paths::lips();

   151     paths << Paths::clover();

   152     paths << Paths::ellipses();

   153     paths << Paths::windingFill();

   154     paths << Paths::oddEvenFill();

   155     paths << Paths::squareWithHole();

   156     paths << Paths::circleWithHole();

   157     paths << Paths::bezierQuadrant();

   158 

   159     // make sure all the bounding rects are centered at the origin

   160     for (int i = 0; i < paths.size(); ++i) {

   161         QRectF bounds = paths[i].boundingRect();

   162 

   163         QMatrix m(1, 0,

   164                   0, 1,

   165                   -bounds.center().x(), -bounds.center().y());

   166 

   167         paths[i] = m.map(paths[i]);

   168     }

   169 }

   170 

   171 static QPainterPath samplePath1()

   172 {

   173     QPainterPath path;

   174     path.moveTo(QPointF(200, 246.64789));

   175     path.lineTo(QPointF(200, 206.64789));

   176     path.lineTo(QPointF(231.42858, 206.64789));

   177     path.lineTo(QPointF(231.42858, 246.64789));

   178     path.lineTo(QPointF(200, 246.64789));

   179     return path;

   180 }

   181 

   182 static QPainterPath samplePath2()

   183 {

   184     QPainterPath path;

   185     path.moveTo(QPointF(200, 146.64789));

   186     path.lineTo(QPointF(200, 106.64789));

   187     path.lineTo(QPointF(231.42858, 106.64789));

   188     path.lineTo(QPointF(231.42858, 146.64789));

   189     path.lineTo(QPointF(200, 146.64789));

   190     return path;

   191 }

   192 

   193 static QPainterPath samplePath3()

   194 {

   195     QPainterPath path;

   196     path.moveTo(QPointF(231.42858, 80.933609));

   197     path.lineTo(QPointF(200, 80.933609));

   198     path.lineTo(QPointF(200, 96.64788999999999));

   199     path.lineTo(QPointF(231.42858, 96.64788999999999));

   200     path.lineTo(QPointF(231.42858, 80.933609));

   201     return path;

   202 }

   203 

   204 static QPainterPath samplePath4()

   205 {

   206     QPainterPath path;

   207     path.moveTo(QPointF(288.571434, 80.933609));

   208     path.lineTo(QPointF(431.42858, 80.933609));

   209     path.lineTo(QPointF(431.42858, 96.64788999999999));

   210     path.lineTo(QPointF(288.571434, 96.64788999999999));

   211     path.lineTo(QPointF(288.571434, 80.933609));

   212     return path;

   213 }

   214 

   215 static QPainterPath samplePath5()

   216 {

   217     QPainterPath path;

   218     path.moveTo(QPointF(588.571434, 80.933609));

   219     path.lineTo(QPointF(682.85715, 80.933609));

   220     path.lineTo(QPointF(682.85715, 96.64788999999999));

   221     path.lineTo(QPointF(588.571434, 96.64788999999999));

   222     path.lineTo(QPointF(588.571434, 80.933609));

   223     return path;

   224 }

   225 

   226 static QPainterPath samplePath6()

   227 {

   228     QPainterPath path;

   229     path.moveTo(QPointF(588.571434, 80.933609));

   230     path.lineTo(QPointF(200, 80.933609));

   231     path.lineTo(QPointF(200, 446.6479));

   232     path.lineTo(QPointF(682.85715, 446.6479));

   233     path.lineTo(QPointF(682.85715, 96.64788999999999));

   234     path.lineTo(QPointF(731.42858, 96.64788999999999));

   235     path.lineTo(QPointF(731.42858, 56.64788999999999));

   236     path.lineTo(QPointF(588.571434, 56.64788999999999));

   237     path.lineTo(QPointF(588.571434, 80.933609));

   238     return path;

   239 }

   240 

   241 static QPainterPath samplePath7()

   242 {

   243     QPainterPath path;

   244     path.moveTo(QPointF(682.85715, 206.64789));

   245     path.lineTo(QPointF(682.85715, 246.64789));

   246     path.lineTo(QPointF(588.571434, 246.64789));

   247     path.lineTo(QPointF(588.571434, 206.64789));

   248     path.lineTo(QPointF(682.85715, 206.64789));

   249     return path;

   250 }

   251 

   252 static QPainterPath samplePath8()

   253 {

   254     QPainterPath path;

   255     path.moveTo(QPointF(682.85715, 406.64789));

   256     path.lineTo(QPointF(682.85715, 446.64789));

   257     path.lineTo(QPointF(588.571434, 446.64789));

   258     path.lineTo(QPointF(588.571434, 406.64789));

   259     path.lineTo(QPointF(682.85715, 406.64789));

   260     return path;

   261 }

   262 

   263 static QPainterPath samplePath9()

   264 {

   265     QPainterPath path;

   266     path.moveTo(QPointF(682.85715, 426.64789));

   267     path.lineTo(QPointF(682.85715, 446.6479));

   268     path.lineTo(QPointF(568.571434, 446.6479));

   269     path.lineTo(QPointF(568.571434, 426.64789));

   270     path.lineTo(QPointF(682.85715, 426.64789));

   271     return path;

   272 }

   273 

   274 static QPainterPath samplePath10()

   275 {

   276     QPainterPath path;

   277     path.moveTo(QPointF(511.42858, 446.6479));

   278     path.lineTo(QPointF(368.571434, 446.6479));

   279     path.lineTo(QPointF(368.571434, 426.64789));

   280     path.lineTo(QPointF(511.42858, 426.64789));

   281     path.lineTo(QPointF(511.42858, 446.6479));

   282     return path;

   283 }

   284 

   285 static QPainterPath samplePath11()

   286 {

   287     QPainterPath path;

   288     path.moveTo(QPointF(165.71429, 338.79076));

   289     path.lineTo(QPointF(227.74288, 338.79076));

   290     path.cubicTo(QPointF(232.95048, 338.79076),

   291                  QPointF(237.14288, 342.88102),

   292                  QPointF(237.14288, 347.96176));

   293     path.lineTo(QPointF(237.14288, 366.76261));

   294     path.cubicTo(QPointF(237.14288, 371.84335),

   295                  QPointF(232.95048, 375.93361),

   296                  QPointF(227.74288, 375.93361));

   297     path.lineTo(QPointF(165.7142905131896, 375.93361));

   298     path.lineTo(QPointF(165.71429, 338.79076));

   299     return path;

   300 }

   301 static QPainterPath samplePath12()

   302 {

   303     QPainterPath path;

   304     path.moveTo(QPointF(333.297085225735, 61.53486494396167));

   305     path.cubicTo(QPointF(339.851755668807, 65.26555884471786),

   306                  QPointF(346.7164458828328, 69.04482864715078),

   307                  QPointF(353.4159970843586, 72.56059416636147));

   308     path.cubicTo(QPointF(353.4166971116034, 72.56155590850551),

   309                  QPointF(353.4173961086004, 72.56251809989483),

   310                  QPointF(353.4180950127331, 72.56348028832946));

   311     path.cubicTo(QPointF(342.4340366381152, 76.42344228577481),

   312                  QPointF(317.0596805768079, 94.67086588954379),

   313                  QPointF(309.78055, 101.00195));

   314     path.cubicTo(QPointF(286.0370715501102, 121.6530659984711),

   315                  QPointF(272.7748256344584, 134.1525788344904),

   316                  QPointF(250.7436468364447, 150.4434491585085));

   317     path.lineTo(QPointF(247.03629, 146.56585));

   318     path.lineTo(QPointF(240.71086, 91.501867));

   319     path.cubicTo(QPointF(240.71086, 91.501867),

   320                  QPointF(305.6382515924416, 62.21715375368672),

   321                  QPointF(333.297085225735, 61.53486494396167));

   322     return path;

   323 }

   324 

   325 static QPainterPath samplePath13()

   326 {

   327     QPainterPath path;

   328     path.moveTo(QPointF(160, 200));

   329     path.lineTo(QPointF(100, 200));

   330     path.lineTo(QPointF(100, 130));

   331     path.lineTo(QPointF(160, 130));

   332     path.lineTo(QPointF(160, 200));

   333     return path;

   334 }

   335 

   336 static QPainterPath samplePath14()

   337 {

   338     QPainterPath path;

   339     path.moveTo(QPointF(100, 180));

   340     path.lineTo(QPointF(100, 80));

   341     path.lineTo(QPointF(120, 80));

   342     path.lineTo(QPointF(120, 100));

   343     path.lineTo(QPointF(160, 100));

   344     path.lineTo(QPointF(160, 180));

   345     path.lineTo(QPointF(100, 180));

   346     return path;

   347 }

   348 

   349 void tst_QPathClipper::clip_data()

   350 {

   351     //create the testtable instance and define the elements

   352     QTest::addColumn<QPainterPath>("subject");

   353     QTest::addColumn<QPainterPath>("clip");

   354     QTest::addColumn<QPathClipper::Operation>("op");

   355     QTest::addColumn<QPainterPath>("result");

   356 

   357     //next we fill it with data

   358     QTest::newRow( "simple1" )  << Paths::frame3()

   359                                 << Paths::frame4()

   360                                 << QPathClipper::BoolAnd

   361                                 << samplePath1();

   362 

   363     QTest::newRow( "simple2" )  << Paths::frame3()

   364                                 << Paths::frame4() * QTransform().translate(0, -100)

   365                                 << QPathClipper::BoolAnd

   366                                 << samplePath2();

   367 

   368     QTest::newRow( "simple3" )  << Paths::frame3()

   369                                 << Paths::frame4() * QTransform().translate(0, -150)

   370                                 << QPathClipper::BoolAnd

   371                                 << samplePath3();

   372 

   373     QTest::newRow( "simple4" )  << Paths::frame3()

   374                                 << Paths::frame4() * QTransform().translate(200, -150)

   375                                 << QPathClipper::BoolAnd

   376                                 << samplePath4();

   377 

   378     QTest::newRow( "simple5" )  << Paths::frame3()

   379                                 << Paths::frame4() * QTransform().translate(500, -150)

   380                                 << QPathClipper::BoolAnd

   381                                 << samplePath5();

   382 

   383     QTest::newRow( "simple6" )  << Paths::frame3()

   384                                 << Paths::frame4() * QTransform().translate(500, -150)

   385                                 << QPathClipper::BoolOr

   386                                 << samplePath6();

   387 

   388     QTest::newRow( "simple7" )  << Paths::frame3()

   389                                 << Paths::frame4() * QTransform().translate(500, 0)

   390                                 << QPathClipper::BoolAnd

   391                                 << samplePath7();

   392 

   393     QTest::newRow( "simple8" )  << Paths::frame3()

   394                                 << Paths::frame4() * QTransform().translate(500, 200)

   395                                 << QPathClipper::BoolAnd

   396                                 << samplePath8();

   397 

   398     QTest::newRow( "simple9" )  << Paths::frame3()

   399                                 << Paths::frame4() * QTransform().translate(480, 220)

   400                                 << QPathClipper::BoolAnd

   401                                 << samplePath9();

   402 

   403     QTest::newRow( "simple10" )  << Paths::frame3()

   404                                  << Paths::frame4() * QTransform().translate(280, 220)

   405                                  << QPathClipper::BoolAnd

   406                                  << samplePath10();

   407 

   408     QTest::newRow( "simple11" )  << Paths::frame2()*QTransform().translate(40, 235)

   409                                  << Paths::frame1()

   410                                  << QPathClipper::BoolAnd

   411                                  << samplePath11();

   412 

   413     QTest::newRow( "intersection_at_edge" )  << Paths::lips()

   414                                              << Paths::mailbox()*QTransform().translate(-85, 34)

   415                                              << QPathClipper::BoolAnd

   416                                              << samplePath12();

   417 

   418     QTest::newRow( "simple_move_to1" )  << Paths::rect4()

   419                                        << Paths::rect2() * QTransform().translate(-20, 50)

   420                                        << QPathClipper::BoolAnd

   421                                        << samplePath13();

   422 

   423     QTest::newRow( "simple_move_to2" )  << Paths::rect4()

   424                                         << Paths::rect2() * QTransform().translate(-20, 0)

   425                                         << QPathClipper::BoolAnd

   426                                         << samplePath14();

   427 }

   428 

   429 static const int precision = 8;

   430 static const qreal epsilon = pow(0.1, precision);

   431 

   432 static inline bool fuzzyIsZero(qreal x, qreal relative)

   433 {

   434     if (qAbs(relative) < epsilon)

   435         return qAbs(x) < epsilon;

   436     else

   437         return qAbs(x / relative) < epsilon;

   438 }

   439 

   440 static bool fuzzyCompare(const QPointF &a, const QPointF &b)

   441 {

   442     const QPointF delta = a - b;

   443 

   444     const qreal x = qMax(qAbs(a.x()), qAbs(b.x()));

   445     const qreal y = qMax(qAbs(a.y()), qAbs(b.y()));

   446 

   447     return fuzzyIsZero(delta.x(), x) && fuzzyIsZero(delta.y(), y);

   448 }

   449 

   450 static bool isClosed(const QPainterPath &path)

   451 {

   452     if (path.elementCount() == 0)

   453         return false;

   454 

   455     QPointF first = path.elementAt(0);

   456     QPointF last = path.elementAt(path.elementCount() - 1);

   457 

   458     return fuzzyCompare(first, last);

   459 }

   460 

   461 // rotation and direction independent path comparison

   462 // allows paths to be shifted or reversed relative to each other

   463 static bool comparePaths(const QPainterPath &actual, const QPainterPath &expected)

   464 {

   465     const int endActual = isClosed(actual) ? actual.elementCount() - 1 : actual.elementCount();

   466     const int endExpected = isClosed(expected) ? expected.elementCount() - 1 : expected.elementCount();

   467 

   468     if (endActual != endExpected)

   469         return false;

   470 

   471     for (int i = 0; i < endActual; ++i) {

   472         int k = 0;

   473         for (k = 0; k < endActual; ++k) {

   474             int i1 = k;

   475             int i2 = (i + k) % endActual;

   476 

   477             QPointF a = actual.elementAt(i1);

   478             QPointF b = expected.elementAt(i2);

   479 

   480             if (!fuzzyCompare(a, b))

   481                 break;

   482         }

   483 

   484         if (k == endActual)

   485             return true;

   486 

   487         for (k = 0; k < endActual; ++k) {

   488             int i1 = k;

   489             int i2 = (i + endActual - k) % endActual;

   490 

   491             QPointF a = actual.elementAt(i1);

   492             QPointF b = expected.elementAt(i2);

   493 

   494             if (!fuzzyCompare(a, b))

   495                 break;

   496         }

   497 

   498         if (k == endActual)

   499             return true;

   500     }

   501 

   502     return false;

   503 }

   504 

   505 // sanity check to make sure comparePaths declared above works

   506 void tst_QPathClipper::testComparePaths()

   507 {

   508     QPainterPath a;

   509     QPainterPath b;

   510 

   511     a.addRect(0, 0, 10, 10);

   512     b.addRect(0, 0, 10.00001, 10.00001);

   513 

   514     QVERIFY(!comparePaths(a, b));

   515 

   516     b = QPainterPath();

   517     b.addRect(0, 0, 10.00000000001, 10.00000000001);

   518 

   519     QVERIFY(comparePaths(a, b));

   520 

   521     b = QPainterPath();

   522     b.moveTo(10, 0);

   523     b.lineTo(0, 0);

   524     b.lineTo(0, 10);

   525     b.lineTo(10, 10);

   526 

   527     QVERIFY(comparePaths(a, b));

   528     b.lineTo(10, 0);

   529     QVERIFY(comparePaths(a, b));

   530 

   531     b = QPainterPath();

   532     b.moveTo(10, 0);

   533     b.lineTo(0, 10);

   534     b.lineTo(0, 0);

   535     b.lineTo(10, 10);

   536 

   537     QVERIFY(!comparePaths(a, b));

   538 }

   539 

   540 void tst_QPathClipper::clip()

   541 {

   542     if (sizeof(double) != sizeof(qreal)) {

   543         QSKIP("This test only works for qreal=double, otherwise ends in rounding errors", SkipAll);

   544     }

   545     QFETCH( QPainterPath, subject );

   546     QFETCH( QPainterPath, clip );

   547     QFETCH( QPathClipper::Operation, op );

   548     QFETCH( QPainterPath,  result);

   549     QPathClipper clipper(subject, clip);

   550     QPainterPath x = clipper.clip(op);

   551 

   552     QVERIFY(comparePaths(x, result));

   553 }

   554 

   555 static inline QPointF randomPointInRect(const QRectF &rect)

   556 {

   557     qreal rx = qrand() / (RAND_MAX + 1.);

   558     qreal ry = qrand() / (RAND_MAX + 1.);

   559 

   560     return QPointF(rect.left() + rx * rect.width(),

   561                    rect.top() + ry * rect.height());

   562 }

   563 

   564 void tst_QPathClipper::clipTest(int subjectIndex, int clipIndex, QPathClipper::Operation op)

   565 {

   566     const QPainterPath &subject = paths[subjectIndex];

   567     const QPainterPath &clip = paths[clipIndex];

   568     const int count = 40;

   569 

   570     QRectF bounds = subject.boundingRect().united(clip.boundingRect());

   571 

   572     const qreal adjustX = bounds.width() * 0.01;

   573     const qreal adjustY = bounds.height() * 0.01;

   574 

   575     // make sure we test some points that are outside both paths as well

   576     bounds = bounds.adjusted(-adjustX, -adjustY, adjustX, adjustY);

   577 

   578     const int dim = 256;

   579     const qreal scale = qMin(dim / bounds.width(), dim / bounds.height());

   580 

   581     QPathClipper clipper(subject, clip);

   582     QPainterPath result = clipper.clip(op);

   583 

   584     // using the image here is a bit of a hacky way to make sure we don't test points that

   585     // are too close to the path edges to avoid test fails that are due to numerical errors

   586     QImage img(dim, dim, QImage::Format_ARGB32_Premultiplied);

   587     img.fill(0x0);

   588     QPainter p(&img);

   589     p.setRenderHint(QPainter::Antialiasing);

   590     p.scale(scale, scale);

   591     p.translate(-bounds.topLeft());

   592     p.setPen(Qt::black);

   593     p.drawPath(subject);

   594     p.setPen(Qt::red);

   595     p.drawPath(clip);

   596     p.end();

   597 

   598     for (int i = 0; i < count; ++i) {

   599         QPointF point;

   600         QRgb pixel;

   601         do {

   602             point = randomPointInRect(bounds);

   603             const QPointF imagePoint = (point - bounds.topLeft()) * scale;

   604 

   605             pixel = img.pixel(int(imagePoint.x()), int(imagePoint.y()));

   606         } while (qAlpha(pixel) > 0);

   607 

   608         const bool inSubject = subject.contains(point);

   609         const bool inClip = clip.contains(point);

   610 

   611         const bool inResult = result.contains(point);

   612 

   613         bool expected = false;

   614         switch (op) {

   615         case QPathClipper::BoolAnd:

   616             expected = inSubject && inClip;

   617             break;

   618         case QPathClipper::BoolOr:

   619             expected = inSubject || inClip;

   620             break;

   621         case QPathClipper::BoolSub:

   622             expected = inSubject && !inClip;

   623             break;

   624         default:

   625             break;

   626         }

   627 

   628         if (expected != inResult) {

   629             char str[256];

   630             const char *opStr =

   631                  op == QPathClipper::BoolAnd ? "and" :

   632                  op == QPathClipper::BoolOr ? "or" : "sub";

   633             sprintf(str, "Expected: %d, actual: %d, subject: %d, clip: %d, op: %s\n",

   634                      int(expected), int(inResult), subjectIndex, clipIndex, opStr);

   635 

   636             // debugging

   637 #if 0

   638             QRect rect = bounds.toAlignedRect();

   639 

   640             QPainter p(&img);

   641             p.scale(scale, scale);

   642             p.translate(-bounds.topLeft());

   643 

   644             p.setPen(Qt::NoPen);

   645             p.setBrush(QColor(0x700ff00));

   646             p.drawPath(result);

   647 

   648             p.setPen(Qt::blue);

   649             p.drawPoint(point);

   650             p.end();

   651 

   652             char str2[256];

   653             sprintf(str2, "fail-%d-%d-%s.png", subjectIndex, clipIndex, opStr);

   654             img.save(str2);

   655 #endif

   656             QFAIL(str);

   657         }

   658     }

   659 }

   660 

   661 void tst_QPathClipper::clip2()

   662 {

   663     if (sizeof(double) != sizeof(qreal))

   664         QSKIP("This test only works for qreal=double, otherwise ends in rounding errors", SkipAll);

   665 

   666     int operation = 0;

   667 

   668     for (int i = 0; i < paths.size(); ++i) {

   669         for (int j = 0; j <= i; ++j) {

   670             QPathClipper::Operation op = QPathClipper::Operation((operation++) % 3);

   671             clipTest(i, j, op);

   672         }

   673     }

   674 }

   675 

   676 void tst_QPathClipper::clip3()

   677 {

   678     int operation = 0;

   679 

   680     // this subset should work correctly for qreal = float

   681     for (int i = 0; i < 20; ++i) {

   682         for (int j = 0; j <= i; ++j) {

   683             QPathClipper::Operation op = QPathClipper::Operation((operation++) % 3);

   684             clipTest(i, j, op);

   685         }

   686     }

   687 }

   688 

   689 void tst_QPathClipper::testIntersections()

   690 {

   691     QPainterPath path1;

   692     QPainterPath path2;

   693 

   694     path1.addRect(0, 0, 100, 100);

   695     path2.addRect(20, 20, 20, 20);

   696     QVERIFY(path1.intersects(path2));

   697     QVERIFY(path2.intersects(path1));

   698     QVERIFY(path1.contains(path2));

   699     QVERIFY(!path2.contains(path1));

   700 

   701     path1 = QPainterPath();

   702     path2 = QPainterPath();

   703     path1.addEllipse(0, 0, 100, 100);

   704     path2.addEllipse(200, 200, 100, 100);

   705     QVERIFY(!path1.intersects(path2));

   706     QVERIFY(!path2.intersects(path1));

   707     QVERIFY(!path1.contains(path2));

   708     QVERIFY(!path2.contains(path1));

   709 

   710     path1 = QPainterPath();

   711     path2 = QPainterPath();

   712     path1.addEllipse(0, 0, 100, 100);

   713     path2.addEllipse(50, 50, 100, 100);

   714     QVERIFY(path1.intersects(path2));

   715     QVERIFY(path2.intersects(path1));

   716     QVERIFY(!path1.contains(path2));

   717     QVERIFY(!path2.contains(path1));

   718 

   719     path1 = QPainterPath();

   720     path2 = QPainterPath();

   721     path1.addRect(100, 100, 100, 100);

   722     path2.addRect(50, 100, 100, 20);

   723     QVERIFY(path1.intersects(path2));

   724     QVERIFY(path2.intersects(path1));

   725     QVERIFY(!path1.contains(path2));

   726     QVERIFY(!path2.contains(path1));

   727 

   728     path1 = QPainterPath();

   729     path2 = QPainterPath();

   730     path1.addRect(100, 100, 100, 100);

   731     path2.addRect(110, 201, 100, 20);

   732     QVERIFY(!path1.intersects(path2));

   733     QVERIFY(!path2.intersects(path1));

   734     QVERIFY(!path1.contains(path2));

   735     QVERIFY(!path2.contains(path1));

   736 

   737     path1 = QPainterPath();

   738     path2 = QPainterPath();

   739     path1.addRect(0, 0, 100, 100);

   740     path2.addRect(20, 20, 20, 20);

   741     path2.addRect(25, 25, 5, 5);

   742     QVERIFY(path1.intersects(path2));

   743     QVERIFY(path2.intersects(path1));

   744     QVERIFY(path1.contains(path2));

   745     QVERIFY(!path2.contains(path1));

   746 }

   747 

   748 void tst_QPathClipper::testIntersections2()

   749 {

   750     QPainterPath path1;

   751     QPainterPath path2;

   752 

   753     path1 = QPainterPath();

   754     path2 = QPainterPath();

   755 

   756     path1.moveTo(-8,-8);

   757     path1.lineTo(107,-8);

   758     path1.lineTo(107,107);

   759     path1.lineTo(-8,107);

   760 

   761     path2.moveTo(0,0);

   762     path2.lineTo(100,0);

   763     path2.lineTo(100,100);

   764     path2.lineTo(0,100);

   765     path2.lineTo(0,0);

   766 

   767     QVERIFY(path1.intersects(path2));

   768     QVERIFY(path2.intersects(path1));

   769     QVERIFY(path1.contains(path2));

   770     QVERIFY(!path2.contains(path1));

   771 

   772     path1.closeSubpath();

   773 

   774     QVERIFY(path1.intersects(path2));

   775     QVERIFY(path2.intersects(path1));

   776     QVERIFY(path1.contains(path2));

   777     QVERIFY(!path2.contains(path1));

   778 }

   779 

   780 void tst_QPathClipper::testIntersections3()

   781 {

   782     QPainterPath path1 = Paths::node();

   783     QPainterPath path2 = Paths::interRect();

   784 

   785     QVERIFY(path1.intersects(path2));

   786     QVERIFY(path2.intersects(path1));

   787 }

   788 

   789 void tst_QPathClipper::testIntersections4()

   790 {

   791     QPainterPath path1;

   792     QPainterPath path2;

   793 

   794     path1.moveTo(-5, 0);

   795     path1.lineTo(5, 0);

   796 

   797     path2.moveTo(0, -5);

   798     path2.lineTo(0, 5);

   799 

   800     QVERIFY(path1.intersects(path2));

   801     QVERIFY(path2.intersects(path1));

   802 }

   803 

   804 void tst_QPathClipper::testIntersections5()

   805 {

   806     QPainterPath path1;

   807     QPainterPath path2;

   808 

   809     path1.addRect(0, 0, 4, 4);

   810     path1.addRect(2, 1, 1, 1);

   811     path2.addRect(0.5, 2, 1, 1);

   812 

   813     QVERIFY(path1.intersects(path2));

   814     QVERIFY(path2.intersects(path1));

   815 }

   816 

   817 void tst_QPathClipper::testIntersections6()

   818 {

   819     QPainterPath path1;

   820     QPainterPath path2;

   821 

   822     path1.moveTo(QPointF(-115.567, -98.3254));

   823     path1.lineTo(QPointF(-45.9007, -98.3254));

   824     path1.lineTo(QPointF(-45.9007, -28.6588));

   825     path1.lineTo(QPointF(-115.567, -28.6588));

   826 

   827     path2.moveTo(QPointF(-110, -110));

   828     path2.lineTo(QPointF(110, -110));

   829     path2.lineTo(QPointF(110, 110));

   830     path2.lineTo(QPointF(-110, 110));

   831     path2.lineTo(QPointF(-110, -110));

   832 

   833     QVERIFY(path1.intersects(path2));

   834     QVERIFY(path2.intersects(path1));

   835 }

   836 

   837 

   838 void tst_QPathClipper::testIntersections7()

   839 {

   840     QPainterPath path1;

   841     QPainterPath path2;

   842 

   843     path1.addRect(0, 0, 10, 10);

   844     path2.addRect(5, 0, 10, 10);

   845 

   846     QVERIFY(path1.intersects(path2));

   847     QVERIFY(path2.intersects(path1));

   848 

   849     path1 = QPainterPath();

   850     path2 = QPainterPath();

   851     path1.addRect(0, 0, 10, 10);

   852     path2.addRect(0, 5, 10, 10);

   853 

   854     QVERIFY(path1.intersects(path2));

   855     QVERIFY(path2.intersects(path1));

   856 

   857     path1 = QPainterPath();

   858     path2 = QPainterPath();

   859     path1.addRect(0, 0, 10, 10);

   860     path2.addRect(0, 0, 10, 10);

   861 

   862     QVERIFY(path1.intersects(path2));

   863     QVERIFY(path2.intersects(path1));

   864 

   865     ///

   866     path1 = QPainterPath();

   867     path2 = QPainterPath();

   868     path1.addRect(1, 1, 10, 10);

   869     path2.addRect(5, 1, 10, 10);

   870 

   871     QVERIFY(path1.intersects(path2));

   872     QVERIFY(path2.intersects(path1));

   873 

   874     path1 = QPainterPath();

   875     path2 = QPainterPath();

   876     path1.addRect(1, 1, 10, 10);

   877     path2.addRect(1, 5, 10, 10);

   878 

   879     QVERIFY(path1.intersects(path2));

   880     QVERIFY(path2.intersects(path1));

   881 

   882     path1 = QPainterPath();

   883     path2 = QPainterPath();

   884     path1.addRect(1, 1, 10, 10);

   885     path2.addRect(1, 1, 10, 10);

   886 

   887     QVERIFY(path1.intersects(path2));

   888     QVERIFY(path2.intersects(path1));

   889 

   890     path1 = QPainterPath();

   891     path2 = QPainterPath();

   892     path1.addRect(1, 1, 10, 10);

   893     path2.addRect(5, 5, 10, 10);

   894 

   895     QVERIFY(path1.intersects(path2));

   896     QVERIFY(path2.intersects(path1));

   897 

   898     path1 = QPainterPath();

   899     path2 = QPainterPath();

   900     path1.addRect(1, 1, 10, 10);

   901     path2.addRect(9, 9, 10, 10);

   902 

   903     QVERIFY(path1.intersects(path2));

   904     QVERIFY(path2.intersects(path1));

   905 

   906     path1 = QPainterPath();

   907     path2 = QPainterPath();

   908     path1.addRect(1, 1, 10, 10);

   909     path2.addRect(10, 10, 10, 10);

   910 

   911     QVERIFY(path1.intersects(path2));

   912     QVERIFY(path2.intersects(path1));

   913 

   914     path1 = QPainterPath();

   915     path2 = QPainterPath();

   916     path1.addRect(1, 1, 9, 9);

   917     path2.addRect(11, 11, 10, 10);

   918 

   919     QVERIFY(!path1.intersects(path2));

   920     QVERIFY(!path2.intersects(path1));

   921 

   922     path1 = QPainterPath();

   923     path2 = QPainterPath();

   924     path1.addRect(1, 1, 10, 10);

   925     path2.addRect(12, 12, 10, 10);

   926 

   927     QVERIFY(!path1.intersects(path2));

   928     QVERIFY(!path2.intersects(path1));

   929 

   930     path1 = QPainterPath();

   931     path2 = QPainterPath();

   932     path1.addRect(11, 11, 10, 10);

   933     path2.addRect(12, 12, 10, 10);

   934 

   935     QVERIFY(path1.intersects(path2));

   936     QVERIFY(path2.intersects(path1));

   937 

   938     path1 = QPainterPath();

   939     path2 = QPainterPath();

   940     path1.addRect(11, 11, 10, 10);

   941     path2.addRect(10, 10, 10, 10);

   942 

   943     QVERIFY(path1.intersects(path2));

   944     QVERIFY(path2.intersects(path1));

   945 }

   946 

   947 

   948 void tst_QPathClipper::testIntersections8()

   949 {

   950     QPainterPath path1 = Paths::node() * QTransform().translate(100, 50);

   951     QPainterPath path2 = Paths::node() * QTransform().translate(150, 50);;

   952 

   953     QVERIFY(path1.intersects(path2));

   954     QVERIFY(path2.intersects(path1));

   955 

   956     path1 = Paths::node();

   957     path2 = Paths::node();

   958 

   959     QVERIFY(path1.intersects(path2));

   960     QVERIFY(path2.intersects(path1));

   961 

   962     path1 = Paths::node();

   963     path2 = Paths::node() * QTransform().translate(0, 30);

   964 

   965     QVERIFY(path1.intersects(path2));

   966     QVERIFY(path2.intersects(path1));

   967 

   968     path1 = Paths::node();

   969     path2 = Paths::node() * QTransform().translate(30, 0);

   970 

   971     QVERIFY(path1.intersects(path2));

   972     QVERIFY(path2.intersects(path1));

   973 

   974     path1 = Paths::node();

   975     path2 = Paths::node() * QTransform().translate(30, 30);

   976 

   977     QVERIFY(path1.intersects(path2));

   978     QVERIFY(path2.intersects(path1));

   979 

   980     path1 = Paths::node();

   981     path2 = Paths::node() * QTransform().translate(1, 1);

   982 

   983     QVERIFY(path1.intersects(path2));

   984     QVERIFY(path2.intersects(path1));

   985 }

   986 

   987 

   988 void tst_QPathClipper::testIntersections9()

   989 {

   990     QPainterPath path1;

   991     QPainterPath path2;

   992 

   993     path1.addRect(QRectF(-1,143, 146, 106));

   994     path2.addRect(QRectF(-9,145, 150, 100));

   995 

   996     QVERIFY(path1.intersects(path2));

   997     QVERIFY(path2.intersects(path1));

   998 

   999     path1 = QPainterPath();;

  1000     path2 = QPainterPath();

  1001 

  1002     path1.addRect(QRectF(-1,191, 136, 106));

  1003     path2.addRect(QRectF(-19,194, 150, 100));

  1004     QVERIFY(path1.intersects(path2));

  1005     QVERIFY(path2.intersects(path1));

  1006 

  1007     path1 = QPainterPath();;

  1008     path2 = QPainterPath();

  1009 

  1010     path1.moveTo(-1 ,  143);

  1011     path1.lineTo(148 ,  143);

  1012     path1.lineTo(148 ,  250);

  1013     path1.lineTo(-1 ,  250);

  1014 

  1015     path2.moveTo(-5 ,  146);

  1016     path2.lineTo(145 ,  146);

  1017     path2.lineTo(145 ,  246);

  1018     path2.lineTo(-5 ,  246);

  1019     path2.lineTo(-5 ,  146);

  1020 

  1021     QVERIFY(path1.intersects(path2));

  1022     QVERIFY(path2.intersects(path1));

  1023 }

  1024 

  1025 QPainterPath pathFromRect(qreal x, qreal y, qreal w, qreal h)

  1026 {

  1027     QPainterPath path;

  1028     path.addRect(QRectF(x, y, w, h));

  1029     return path;

  1030 }

  1031 

  1032 QPainterPath pathFromLine(qreal x1, qreal y1, qreal x2, qreal y2)

  1033 {

  1034     QPainterPath path;

  1035     path.moveTo(x1, y1);

  1036     path.lineTo(x2, y2);

  1037     return path;

  1038 }

  1039 

  1040 static int loopLength(const QWingedEdge &list, QWingedEdge::TraversalStatus status)

  1041 {

  1042     int start = status.edge;

  1043 

  1044     int length = 0;

  1045     do {

  1046         ++length;

  1047         status = list.next(status);

  1048     } while (status.edge != start);

  1049 

  1050     return length;

  1051 }

  1052 

  1053 void tst_QPathClipper::testWingedEdge()

  1054 {

  1055     {

  1056         QWingedEdge list;

  1057         int e1 = list.addEdge(QPointF(0, 0), QPointF(10, 0));

  1058         int e2 = list.addEdge(QPointF(0, 0), QPointF(0, 10));

  1059         int e3 = list.addEdge(QPointF(0, 0), QPointF(-10, 0));

  1060         int e4 = list.addEdge(QPointF(0, 0), QPointF(0, -10));

  1061 

  1062         QCOMPARE(list.edgeCount(), 4);

  1063         QCOMPARE(list.vertexCount(), 5);

  1064 

  1065         QWingedEdge::TraversalStatus status = { e1, QPathEdge::RightTraversal, QPathEdge::Forward };

  1066 

  1067         status = list.next(status);

  1068         QCOMPARE(status.direction, QPathEdge::Backward);

  1069         QCOMPARE(status.traversal, QPathEdge::LeftTraversal);

  1070         QCOMPARE(status.edge, e1);

  1071 

  1072         status = list.next(status);

  1073         QCOMPARE(status.direction, QPathEdge::Forward);

  1074         QCOMPARE(status.traversal, QPathEdge::RightTraversal);

  1075         QCOMPARE(status.edge, e4);

  1076 

  1077         status = list.next(status);

  1078         QCOMPARE(status.direction, QPathEdge::Backward);

  1079         QCOMPARE(status.traversal, QPathEdge::LeftTraversal);

  1080         QCOMPARE(status.edge, e4);

  1081 

  1082         status = list.next(status);

  1083         QCOMPARE(status.direction, QPathEdge::Forward);

  1084         QCOMPARE(status.traversal, QPathEdge::RightTraversal);

  1085         QCOMPARE(status.edge, e3);

  1086 

  1087         status = list.next(status);

  1088         QCOMPARE(status.direction, QPathEdge::Backward);

  1089         QCOMPARE(status.traversal, QPathEdge::LeftTraversal);

  1090         QCOMPARE(status.edge, e3);

  1091 

  1092         status = list.next(status);

  1093         QCOMPARE(status.direction, QPathEdge::Forward);

  1094         QCOMPARE(status.traversal, QPathEdge::RightTraversal);

  1095         QCOMPARE(status.edge, e2);

  1096 

  1097         status = list.next(status);

  1098         QCOMPARE(status.direction, QPathEdge::Backward);

  1099         QCOMPARE(status.traversal, QPathEdge::LeftTraversal);

  1100         QCOMPARE(status.edge, e2);

  1101 

  1102         status = list.next(status);

  1103         QCOMPARE(status.direction, QPathEdge::Forward);

  1104         QCOMPARE(status.traversal, QPathEdge::RightTraversal);

  1105         QCOMPARE(status.edge, e1);

  1106     }

  1107     {

  1108         QWingedEdge list;

  1109         int e1 = list.addEdge(QPointF(5, 0), QPointF(5, 10));

  1110         int e2 = list.addEdge(QPointF(5, 0), QPointF(10, 5));

  1111         int e3 = list.addEdge(QPointF(10, 5), QPointF(5, 10));

  1112         int e4 = list.addEdge(QPointF(5, 0), QPointF(0, 5));

  1113         int e5 = list.addEdge(QPointF(0, 5), QPointF(5, 10));

  1114 

  1115         QCOMPARE(list.edgeCount(), 5);

  1116         QCOMPARE(list.vertexCount(), 4);

  1117 

  1118         QWingedEdge::TraversalStatus status = { e1, QPathEdge::RightTraversal, QPathEdge::Forward };

  1119 

  1120         status = list.next(status);

  1121         QCOMPARE(status.direction, QPathEdge::Backward);

  1122         QCOMPARE(status.traversal, QPathEdge::LeftTraversal);

  1123         QCOMPARE(status.edge, e5);

  1124 

  1125         status = list.next(status);

  1126         QCOMPARE(status.direction, QPathEdge::Backward);

  1127         QCOMPARE(status.traversal, QPathEdge::LeftTraversal);

  1128         QCOMPARE(status.edge, e4);

  1129 

  1130         status = list.next(status);

  1131         QCOMPARE(status.direction, QPathEdge::Forward);

  1132         QCOMPARE(status.traversal, QPathEdge::RightTraversal);

  1133         QCOMPARE(status.edge, e1);

  1134