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

**

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

** All rights reserved.

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

**

** This file is part of the QtGui module 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 "qpathclipper_p.h"

#include <private/qbezier_p.h>

#include <private/qdatabuffer_p.h>

#include <qmath.h>

/**

  The algorithm is as follows:

  1. Find all intersections between the two paths (including self-intersections),

     and build a winged edge structure of non-intersecting parts.

  2. While there are more unhandled edges:

    3. Pick a y-coordinate from an unhandled edge.

    4. Intersect the horizontal line at y-coordinate with all edges.

    5. Traverse intersections left to right deciding whether each subpath should be added or not.

    6. If the subpath should be added, traverse the winged-edge structure and add the edges to

       a separate winged edge structure.

    7. Mark all edges in subpaths crossing the horizontal line as handled.

 8. (Optional) Simplify the resulting winged edge structure by merging shared edges.

 9. Convert the resulting winged edge structure to a painter path.

 */

#include <qdebug.h>

QT_BEGIN_NAMESPACE

static inline bool fuzzyIsNull(qreal d)

{

    if (sizeof(qreal) == sizeof(double))

        return qAbs(d) <= 1e-12;

    else

        return qAbs(d) <= 1e-5f;

}

static inline bool comparePoints(const QPointF &a, const QPointF &b)

{

    return fuzzyIsNull(a.x() - b.x())

           && fuzzyIsNull(a.y() - b.y());

}

//#define QDEBUG_CLIPPER

static qreal dot(const QPointF &a, const QPointF &b)

{

    return a.x() * b.x() + a.y() * b.y();

}

static QPointF normalize(const QPointF &p)

{

    return p / qSqrt(p.x() * p.x() + p.y() * p.y());

}

struct QIntersection

{

    qreal alphaA;

    qreal alphaB;

    QPointF pos;

};

class QIntersectionFinder

{

public:

    void produceIntersections(QPathSegments &segments);

    bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const;

private:

    bool linesIntersect(const QLineF &a, const QLineF &b) const;

};

bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const

{

    const QPointF p1 = a.p1();

    const QPointF p2 = a.p2();

    const QPointF q1 = b.p1();

    const QPointF q2 = b.p2();

    if (comparePoints(p1, p2) || comparePoints(q1, q2))

        return false;

    const bool p1_equals_q1 = comparePoints(p1, q1);

    const bool p2_equals_q2 = comparePoints(p2, q2);

    if (p1_equals_q1 && p2_equals_q2)

        return true;

    const bool p1_equals_q2 = comparePoints(p1, q2);

    const bool p2_equals_q1 = comparePoints(p2, q1);

    if (p1_equals_q2 && p2_equals_q1)

        return true;

    const QPointF pDelta = p2 - p1;

    const QPointF qDelta = q2 - q1;

    const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();

    if (qFuzzyIsNull(par)) {

        const QPointF normal(-pDelta.y(), pDelta.x());

        // coinciding?

        if (qFuzzyIsNull(dot(normal, q1 - p1))) {

            const qreal dp = dot(pDelta, pDelta);

            const qreal tq1 = dot(pDelta, q1 - p1);

            const qreal tq2 = dot(pDelta, q2 - p1);

            if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp))

                return true;

            const qreal dq = dot(qDelta, qDelta);

            const qreal tp1 = dot(qDelta, p1 - q1);

            const qreal tp2 = dot(qDelta, p2 - q1);

            if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq))

                return true;

        }

        return false;

    }

    const qreal invPar = 1 / par;

    const qreal tp = (qDelta.y() * (q1.x() - p1.x()) -

                      qDelta.x() * (q1.y() - p1.y())) * invPar;

    if (tp < 0 || tp > 1)

        return false;

    const qreal tq = (pDelta.y() * (q1.x() - p1.x()) -

                      pDelta.x() * (q1.y() - p1.y())) * invPar;

    return tq >= 0 && tq <= 1;

}

{

    }

        } else {

        }

    }

}

{

    const QPointF p1 = a.p1();

    const QPointF p2 = a.p2();

    const QPointF q1 = b.p1();

    const QPointF q2 = b.p2();

    if (comparePoints(p1, p2) || comparePoints(q1, q2))

        return;

    const bool p1_equals_q1 = comparePoints(p1, q1);

    const bool p2_equals_q2 = comparePoints(p2, q2);

    if (p1_equals_q1 && p2_equals_q2)

        return;

    const bool p1_equals_q2 = comparePoints(p1, q2);

    const bool p2_equals_q1 = comparePoints(p2, q1);

    if (p1_equals_q2 && p2_equals_q1)

        return;

    const QPointF pDelta = p2 - p1;

    const QPointF qDelta = q2 - q1;

    const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();

    if (qFuzzyIsNull(par)) {

        const QPointF normal(-pDelta.y(), pDelta.x());

        // coinciding?

        if (qFuzzyIsNull(dot(normal, q1 - p1))) {

            const qreal invDp = 1 / dot(pDelta, pDelta);

            const qreal tq1 = dot(pDelta, q1 - p1) * invDp;

            const qreal tq2 = dot(pDelta, q2 - p1) * invDp;

            if (tq1 > 0 && tq1 < 1) {

                QIntersection intersection;

                intersection.alphaA = tq1;

                intersection.alphaB = 0;

                intersection.pos = q1;

                intersections.add(intersection);

            }

            if (tq2 > 0 && tq2 < 1) {

                QIntersection intersection;

                intersection.alphaA = tq2;

                intersection.alphaB = 1;

                intersection.pos = q2;

                intersections.add(intersection);

            }

            const qreal invDq = 1 / dot(qDelta, qDelta);

            const qreal tp1 = dot(qDelta, p1 - q1) * invDq;

            const qreal tp2 = dot(qDelta, p2 - q1) * invDq;

            if (tp1 > 0 && tp1 < 1) {

                QIntersection intersection;

                intersection.alphaA = 0;

                intersection.alphaB = tp1;

                intersection.pos = p1;

                intersections.add(intersection);

            }

            if (tp2 > 0 && tp2 < 1) {

                QIntersection intersection;

                intersection.alphaA = 1;

                intersection.alphaB = tp2;

                intersection.pos = p2;

                intersections.add(intersection);

            }

        }

        return;

    }

    // if the lines are not parallel and share a common end point, then they

    // don't intersect

    if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2)

        return;

    const qreal tp = (qDelta.y() * (q1.x() - p1.x()) -

                      qDelta.x() * (q1.y() - p1.y())) / par;

    const qreal tq = (pDelta.y() * (q1.x() - p1.x()) -

                      pDelta.x() * (q1.y() - p1.y())) / par;

    if (tp<0 || tp>1 || tq<0 || tq>1)

        return;

    const bool p_zero = qFuzzyIsNull(tp);

    const bool p_one = qFuzzyIsNull(tp - 1);

    const bool q_zero = qFuzzyIsNull(tq);

    const bool q_one = qFuzzyIsNull(tq - 1);

    if ((q_zero || q_one) && (p_zero || p_one))

        return;

    QPointF pt;

    if (p_zero) {

        pt = p1;

    } else if (p_one) {

        pt = p2;

    } else if (q_zero) {

        pt = q1;

    } else if (q_one) {

        pt = q2;

    } else {

        pt = q1 + (q2 - q1) * tq;

    }

    QIntersection intersection;

    intersection.alphaA = tp;

    intersection.alphaB = tq;