/****************************************************************************

**

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

** All rights reserved.

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

**

** This file is part of the test suite of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

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

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

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

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

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

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

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

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

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

**

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

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

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

**

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

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

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "private/qpathclipper_p.h"

#include "paths.h"

#include <QtTest/QtTest>

#include <qpainterpath.h>

#include <qpolygon.h>

#include <qdebug.h>

#include <qpainter.h>

#include <math.h>

class tst_QPathClipper : public QObject

{

    Q_OBJECT

public:

    tst_QPathClipper();

    virtual ~tst_QPathClipper();

private:

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

    QList<QPainterPath> paths;

public slots:

    void initTestCase();

private slots:

    void testWingedEdge();

    void testComparePaths();

    void clip_data();

    void clip();

    void clip2();

    void clip3();

    void testIntersections();

    void testIntersections2();

    void testIntersections3();

    void testIntersections4();

    void testIntersections5();

    void testIntersections6();

    void testIntersections7();

    void testIntersections8();

    void testIntersections9();

    void zeroDerivativeCurves();

    void task204301_data();

    void task204301();

    void task209056();

    void task251909();

};

Q_DECLARE_METATYPE(QPainterPath)

Q_DECLARE_METATYPE(QPathClipper::Operation)

tst_QPathClipper::tst_QPathClipper()

{

}

tst_QPathClipper::~tst_QPathClipper()

{

}

void tst_QPathClipper::initTestCase()

{

    paths << Paths::rect();

    paths << Paths::heart();

    paths << Paths::body();

    paths << Paths::mailbox();

    paths << Paths::deer();

    paths << Paths::fire();

    paths << Paths::random1();

    paths << Paths::random2();

    paths << Paths::heart2();

    paths << Paths::rect2();

    paths << Paths::rect3();

    paths << Paths::rect4();

    paths << Paths::rect5();

    paths << Paths::rect6();

    paths << Paths::frame1();

    paths << Paths::frame2();

    paths << Paths::frame3();

    paths << Paths::frame4();

    paths << Paths::triangle1();

    paths << Paths::triangle2();

    paths << Paths::node();

    paths << Paths::interRect();

    paths << Paths::simpleCurve();

    paths << Paths::simpleCurve2();

    paths << Paths::simpleCurve3();

    paths << Paths::bezier1();

    paths << Paths::bezier2();

    paths << Paths::bezier3();

    paths << Paths::bezier4();

    paths << Paths::bezierFlower();

    paths << Paths::lips();

    paths << Paths::clover();

    paths << Paths::ellipses();

    paths << Paths::windingFill();

    paths << Paths::oddEvenFill();

    paths << Paths::squareWithHole();

    paths << Paths::circleWithHole();

    paths << Paths::bezierQuadrant();

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

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

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

        QMatrix m(1, 0,

                  0, 1,

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

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

    }

}

static QPainterPath samplePath1()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath2()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath3()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath4()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath5()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath6()

{

    QPainterPath path;

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

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

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

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

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

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

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

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

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

    return path;

}

static QPainterPath samplePath7()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath8()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath9()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath10()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath11()

{

    QPainterPath path;

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

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

    path.cubicTo(QPointF(232.95048, 338.79076),

                 QPointF(237.14288, 342.88102),

                 QPointF(237.14288, 347.96176));

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

    path.cubicTo(QPointF(237.14288, 371.84335),

                 QPointF(232.95048, 375.93361),

                 QPointF(227.74288, 375.93361));

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

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

    return path;

}

static QPainterPath samplePath12()

{

    QPainterPath path;

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

    path.cubicTo(QPointF(339.851755668807, 65.26555884471786),

                 QPointF(346.7164458828328, 69.04482864715078),

                 QPointF(353.4159970843586, 72.56059416636147));

    path.cubicTo(QPointF(353.4166971116034, 72.56155590850551),

                 QPointF(353.4173961086004, 72.56251809989483),

                 QPointF(353.4180950127331, 72.56348028832946));

    path.cubicTo(QPointF(342.4340366381152, 76.42344228577481),

                 QPointF(317.0596805768079, 94.67086588954379),

                 QPointF(309.78055, 101.00195));

    path.cubicTo(QPointF(286.0370715501102, 121.6530659984711),

                 QPointF(272.7748256344584, 134.1525788344904),

                 QPointF(250.7436468364447, 150.4434491585085));

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

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

    path.cubicTo(QPointF(240.71086, 91.501867),

                 QPointF(305.6382515924416, 62.21715375368672),

                 QPointF(333.297085225735, 61.53486494396167));

    return path;

}

static QPainterPath samplePath13()

{

    QPainterPath path;

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

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

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

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

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

    return path;

}

static QPainterPath samplePath14()

{

    QPainterPath path;

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

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

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

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

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

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

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

    return path;

}

void tst_QPathClipper::clip_data()

{

    //create the testtable instance and define the elements

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

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

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

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

    //next we fill it with data

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

                                << Paths::frame4()

                                << QPathClipper::BoolAnd

                                << samplePath1();

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

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

                                << QPathClipper::BoolAnd

                                << samplePath2();

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

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

                                << QPathClipper::BoolAnd

                                << samplePath3();

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

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

                                << QPathClipper::BoolAnd

                                << samplePath4();

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

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

                                << QPathClipper::BoolAnd

                                << samplePath5();

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

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

                                << QPathClipper::BoolOr

                                << samplePath6();

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

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

                                << QPathClipper::BoolAnd

                                << samplePath7();

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

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

                                << QPathClipper::BoolAnd

                                << samplePath8();

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

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

                                << QPathClipper::BoolAnd

                                << samplePath9();

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

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

                                 << QPathClipper::BoolAnd

                                 << samplePath10();

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

                                 << Paths::frame1()

                                 << QPathClipper::BoolAnd

                                 << samplePath11();

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

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

                                             << QPathClipper::BoolAnd

                                             << samplePath12();

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

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

                                       << QPathClipper::BoolAnd

                                       << samplePath13();

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

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

                                        << QPathClipper::BoolAnd

                                        << samplePath14();

}

static const int precision = 8;

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

static inline bool fuzzyIsZero(qreal x, qreal relative)

{

    if (qAbs(relative) < epsilon)

        return qAbs(x) < epsilon;

    else

        return qAbs(x / relative) < epsilon;

}

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

{

    const QPointF delta = a - b;

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

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

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

}

static bool isClosed(const QPainterPath &path)

{

    if (path.elementCount() == 0)

        return false;

    QPointF first = path.elementAt(0);

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

    return fuzzyCompare(first, last);

}

// rotation and direction independent path comparison

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

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

{

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

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

    if (endActual != endExpected)

        return false;

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

        int k = 0;

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

            int i1 = k;

            int i2 = (i + k) % endActual;

            QPointF a = actual.elementAt(i1);

            QPointF b = expected.elementAt(i2);

            if (!fuzzyCompare(a, b))

                break;

        }

        if (k == endActual)

            return true;

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

            int i1 = k;

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

            QPointF a = actual.elementAt(i1);

            QPointF b = expected.elementAt(i2);

            if (!fuzzyCompare(a, b))

                break;

        }

        if (k == endActual)

            return true;

    }

    return false;

}

// sanity check to make sure comparePaths declared above works

void tst_QPathClipper::testComparePaths()

{

    QPainterPath a;

    QPainterPath b;

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

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

    QVERIFY(!comparePaths(a, b));

    b = QPainterPath();

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

    QVERIFY(comparePaths(a, b));

    b = QPainterPath();

    b.moveTo(10, 0);

    b.lineTo(0, 0);

    b.lineTo(0, 10);

    b.lineTo(10, 10);

    QVERIFY(comparePaths(a, b));

    b.lineTo(10, 0);