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

**

** 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 <private/qnumeric_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 void normalize(double &x, double &y)

{

    double reciprocal = 1 / qSqrt(x * x + y * y);

    x *= reciprocal;

    y *= reciprocal;

}

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;

}

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

{

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

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

                return true;

        }

    }

    return false;

}

namespace {

struct TreeNode

{

    qreal splitLeft;

    qreal splitRight;

    bool leaf;

    int lowestLeftIndex;

    int lowestRightIndex;

    union {

        struct {

            int first;

            int last;

        } interval;

        struct {

            int left;

            int right;

        } children;

    } index;

};

struct RectF

{

    qreal x1;

    qreal y1;

    qreal x2;

    qreal y2;

};

class SegmentTree

{

public:

    SegmentTree(QPathSegments &segments);

    QRectF boundingRect() const;

    void produceIntersections(int segment);

private:

    TreeNode buildTree(int first, int last, int depth, const RectF &bounds);

    void produceIntersectionsLeaf(const TreeNode &node, int segment);

    void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis);

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

    QPathSegments &m_segments;

    QVector<int> m_index;

    RectF m_bounds;

    QVector<TreeNode> m_tree;

    QDataBuffer<QIntersection> m_intersections;

};

SegmentTree::SegmentTree(QPathSegments &segments)

    : m_segments(segments),

      m_intersections(0)

{

    m_bounds.x1 = qt_inf();

    m_bounds.y1 = qt_inf();

    m_bounds.x2 = -qt_inf();

    m_bounds.y2 = -qt_inf();

    m_index.resize(m_segments.segments());

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

        m_index[i] = i;

        const QRectF &segmentBounds = m_segments.elementBounds(i);

        if (segmentBounds.left() < m_bounds.x1)

            m_bounds.x1 = segmentBounds.left();

        if (segmentBounds.top() < m_bounds.y1)

            m_bounds.y1 = segmentBounds.top();

        if (segmentBounds.right() > m_bounds.x2)

            m_bounds.x2 = segmentBounds.right();

        if (segmentBounds.bottom() > m_bounds.y2)

            m_bounds.y2 = segmentBounds.bottom();

    }

    m_tree.resize(1);

    TreeNode root = buildTree(0, m_index.size(), 0, m_bounds);

    m_tree[0] = root;

}

QRectF SegmentTree::boundingRect() const

{

    return QRectF(QPointF(m_bounds.x1, m_bounds.y1),

                  QPointF(m_bounds.x2, m_bounds.y2));

}

static inline qreal coordinate(const QPointF &pos, int axis)

{

    return axis == 0 ? pos.x() : pos.y();

}

TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds)

{

    if (depth >= 24 || (last - first) <= 10) {

        TreeNode node;

        node.leaf = true;

        node.index.interval.first = first;

        node.index.interval.last = last;

        return node;

    }

    int splitAxis = (depth & 1);

    TreeNode node;

    node.leaf = false;

    qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]);

    node.splitLeft = (&bounds.x1)[splitAxis];

    node.splitRight = (&bounds.x2)[splitAxis];

    node.lowestLeftIndex = INT_MAX;

    node.lowestRightIndex = INT_MAX;

    const int treeSize = m_tree.size();

    node.index.children.left = treeSize;

    node.index.children.right = treeSize + 1;

    m_tree.resize(treeSize + 2);

    int l = first;

    int r = last - 1;

    // partition into left and right sets

    while (l <= r) {

        const int index = m_index.at(l);

        const QRectF &segmentBounds = m_segments.elementBounds(index);

        qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis);

        if (coordinate(segmentBounds.center(), splitAxis) < split) {

            qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis);

            if (highCoordinate > node.splitLeft)

                node.splitLeft = highCoordinate;

            if (index < node.lowestLeftIndex)

                node.lowestLeftIndex = index;

            ++l;

        } else {

            if (lowCoordinate < node.splitRight)

                node.splitRight = lowCoordinate;

            if (index < node.lowestRightIndex)

                node.lowestRightIndex = index;

            qSwap(m_index[l], m_index[r]);

            --r;

        }

    }

    RectF lbounds = bounds;

    (&lbounds.x2)[splitAxis] = node.splitLeft;

    RectF rbounds = bounds;

    (&rbounds.x1)[splitAxis] = node.splitRight;

    TreeNode left = buildTree(first, l, depth + 1, lbounds);

    m_tree[node.index.children.left] = left;

    TreeNode right = buildTree(l, last, depth + 1, rbounds);

    m_tree[node.index.children.right] = right;

    return node;

}

void SegmentTree::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;