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

**

** 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 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());

}

static bool pathToRect(const QPainterPath &path, QRectF *rect = 0);

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:

    void intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections);

    void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections);

    bool beziersIntersect(const QBezier &one, const QBezier &two) const;

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

};

bool QIntersectionFinder::beziersIntersect(const QBezier &one, const QBezier &two) const

{

    return (comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2())

            && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4()))

           || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3())

               && comparePoints(one.pt3(), two.pt2()) && comparePoints(one.pt4(), two.pt1()))

           || QBezier::findIntersections(one, two, 0);

}

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;

    }

    // 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 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;

}

void QIntersectionFinder::intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections)

{

    if ((comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2())

         && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4()))

        || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3())

            && comparePoints(one.pt3(), two.pt2()) && comparePoints(one.pt4(), two.pt1()))) {

        return;

    }

    t.clear();

    if (!QBezier::findIntersections(one, two, &t))

        return;

    int count = t.size();

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

        qreal alpha_p = t.at(i).first;

        qreal alpha_q = t.at(i).second;

        QPointF pt;

        if (qFuzzyIsNull(alpha_p)) {

            pt = one.pt1();

        } else if (qFuzzyIsNull(alpha_p - 1)) {

            pt = one.pt4();

        } else if (qFuzzyIsNull(alpha_q)) {

            pt = two.pt1();

        } else if (qFuzzyIsNull(alpha_q - 1)) {

            pt = two.pt4();

        } else {

            pt = one.pointAt(alpha_p);

        }

        QIntersection intersection;

        intersection.alphaA = alpha_p;

        intersection.alphaB = alpha_q;

        intersection.pos = pt;

        intersections.add(intersection);

    }

}

void QIntersectionFinder::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections)

{

    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;

    intersection.pos = pt;

    intersections.add(intersection);

}

static const QBezier bezierFromLine(const QLineF &line)

{

    const QPointF p1 = line.p1();

    const QPointF p2 = line.p2();

    const QPointF delta = (p2 - p1) / 3;

    return QBezier::fromPoints(p1, p1 + delta, p1 + 2 * delta, p2);

}

bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const

{

    QBezier tempA;

    QBezier tempB;

    if (a.segments() == 0 || b.segments() == 0)

        return false;

    const QRectF &rb0 = b.elementBounds(0);

    qreal minX = rb0.left();

    qreal minY = rb0.top();

    qreal maxX = rb0.right();

    qreal maxY = rb0.bottom();

    for (int i = 1; i < b.segments(); ++i) {

        const QRectF &r = b.elementBounds(i);

        minX = qMin(minX, r.left());

        minY = qMin(minY, r.top());

        maxX = qMax(maxX, r.right());

        maxY = qMax(maxY, r.bottom());

    }

    QRectF rb(minX, minY, maxX - minX, maxY - minY);

    for (int i = 0; i < a.segments(); ++i) {

        const QBezier *bezierA = a.bezierAt(i);

        bool isBezierA = bezierA != 0;

        const QRectF &r1 = a.elementBounds(i);

        if (r1.left() > rb.right() || rb.left() > r1.right())

            continue;

        if (r1.top() > rb.bottom() || rb.top() > r1.bottom())

            continue;

        for (int j = 0; j < b.segments(); ++j) {

            const QRectF &r2 = b.elementBounds(j);

            if (r1.left() > r2.right() || r2.left() > r1.right())

                continue;

            if (r1.top() > r2.bottom() || r2.top() > r1.bottom())

                continue;

            bool isBezierB = b.bezierAt(j) != 0;

            if (isBezierA || isBezierB) {

                const QBezier *bezierB;

                if (isBezierB) {

                    bezierB = b.bezierAt(j);

                } else {

                    tempB = bezierFromLine(b.lineAt(j));

                    bezierB = &tempB;

                }

                if (!bezierA) {

                    tempA = bezierFromLine(a.lineAt(i));

                    bezierA = &tempA;

                }

                if (beziersIntersect(*bezierA, *bezierB))

                    return true;

            } else {

                if (linesIntersect(a.lineAt(i), b.lineAt(j)))

                    return true;

            }

        }

    }

    return false;

}

void QIntersectionFinder::produceIntersections(QPathSegments &segments)

{

    QBezier tempA;

    QBezier tempB;

    QVector<QPair<qreal, qreal> > t;

    QDataBuffer<QIntersection> intersections;

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

        const QBezier *bezierA = segments.bezierAt(i);

        bool isBezierA = bezierA != 0;

        const QRectF &r1 = segments.elementBounds(i);

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

            const QRectF &r2 = segments.elementBounds(j);

            if (r1.left() > r2.right() || r2.left() > r1.right())

                continue;

            if (r1.top() > r2.bottom() || r2.top() > r1.bottom())

                continue;

            intersections.reset();

            bool isBezierB = segments.bezierAt(j) != 0;

            if (isBezierA || isBezierB) {

                const QBezier *bezierB;

                if (isBezierB) {

                    bezierB = segments.bezierAt(j);

                } else {

                    tempB = bezierFromLine(segments.lineAt(j));

                    bezierB = &tempB;

                }

                if (!bezierA) {

                    tempA = bezierFromLine(segments.lineAt(i));

                    bezierA = &tempA;

                }

                intersectBeziers(*bezierA, *bezierB, t, intersections);

            } else {

                const QLineF lineA = segments.lineAt(i);

                const QLineF lineB = segments.lineAt(j);

                intersectLines(lineA, lineB, intersections);

            }

            for (int k = 0; k < intersections.size(); ++k) {

                QPathSegments::Intersection i_isect, j_isect;

                i_isect.vertex = j_isect.vertex = segments.addPoint(intersections.at(k).pos);

                i_isect.t = intersections.at(k).alphaA;

                j_isect.t = intersections.at(k).alphaB;

                i_isect.next = 0;

                j_isect.next = 0;

                segments.addIntersection(i, i_isect);

                segments.addIntersection(j, j_isect);

            }

        }

    }

}

class QKdPointTree

{

public:

    enum Traversal {

        TraverseBoth,

        TraverseLeft,

        TraverseRight,

        TraverseNone

    };

    struct Node {

        int point;

        int id;

        Node *left;

        Node *right;

    };

    QKdPointTree(const QPathSegments &segments)

        : m_segments(&segments)

        , m_nodes(m_segments->points())

        , m_id(0)