qpathclipper.cpp

奇趣公司比较新的qt/emd版本

/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the QtGui module of the Qt Toolkit.
**
** This file may be used under the terms of the GNU General Public
** License version 2.0 as published by the Free Software Foundation
** and appearing in the file LICENSE.GPL included in the packaging of
** this file.  Please review the following information to ensure GNU
** General Public Licensing requirements will be met:
** http://trolltech.com/products/qt/licenses/licensing/opensource/
**
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
** or contact the sales department at [e-mail].
**
** In addition, as a special exception, Trolltech gives you certain
** additional rights. These rights are described in the Trolltech GPL
** Exception version 1.0, which can be found at
** http://www.trolltech.com/products/qt/gplexception/ and in the file
** GPL_EXCEPTION.txt in this package.
**
** In addition, as a special exception, Trolltech, as the sole copyright
** holder for Qt Designer, grants users of the Qt/Eclipse Integration
** plug-in the right for the Qt/Eclipse Integration to link to
** functionality provided by Qt Designer and its related libraries.
**
** Trolltech reserves all rights not expressly granted herein.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/

#include "qpathclipper_p.h"

#include <private/qbezier_p.h>
#include <private/qdatabuffer_p.h>
#include <private/qmath_p.h>

#include <math.h>

#include <QImage>
#include <QPainter>

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

//#define QDEBUG_CLIPPER
static qreal dist(qreal x1, qreal y1, qreal x2, qreal y2)
{
    return qSqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

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 / sqrt(p.x() * p.x() + p.y() * p.y());
}

struct QIntersection
{
    qreal alpha;
    QPointF pos;

    bool operator<(const QIntersection &isect) const
    {
        return alpha < isect.alpha;
    }
};

class QIntersectionFinder
{
public:
    QIntersectionFinder(QDataBuffer<QIntersection> *intersections = 0);

    bool hasIntersections() const;
    void addIntersections(const QPathSegments *a, const QPathSegments *b, int i, bool ignoreAutoClosing = false);

private:
    void intersectBeziers(const QBezier &one, const QBezier &two, bool swap);
    void intersectLines(const QLineF &a, const QLineF &b, bool swap);

    QDataBuffer<QIntersection> *m_intersections;

    QVector<qreal> m_t0;
    QVector<qreal> m_t1;

    bool m_hasIntersections;
};

QIntersectionFinder::QIntersectionFinder(QDataBuffer<QIntersection> *intersections)
    : m_intersections(intersections)
    , m_hasIntersections(false)
{
}

inline bool QIntersectionFinder::hasIntersections() const
{
    return m_hasIntersections;
}

void QIntersectionFinder::intersectBeziers(const QBezier &one, const QBezier &two, bool swap)
{
    if (one.pt1() == two.pt1() && one.pt2() == two.pt2() && one.pt3() == two.pt3() && one.pt4() == two.pt4() ||
        one.pt1() == two.pt4() && one.pt2() == two.pt3() && one.pt3() == two.pt2() && one.pt4() == two.pt1()) {

        m_hasIntersections = true;
        return;
    }

    int a = 0;
    int b = 1;

    if (swap)
        qSwap(a, b);

    const QBezier *bez[2] = { &one, &two };

    m_t0.clear();
    m_t1.clear();

    if (!QBezier::findIntersections(*bez[a], *bez[b], m_t0, m_t1))
        return;

    m_hasIntersections = true;

    if (!m_intersections)
        return;

    const QVector<qreal> &alpha_ps = m_t0;
    const QVector<qreal> &alpha_qs = m_t1;

    int count = alpha_ps.size();

    for (int i = 0; i < count; ++i) {
        qreal alpha_p = alpha_ps[i];
        qreal alpha_q = alpha_qs[i];

        QPointF pt;
        if (alpha_p == 0) {
            pt = bez[a]->pt1();
        } else if (alpha_p == 1) {
            pt = bez[a]->pt4();
        } else if (alpha_q == 0) {
            pt = bez[b]->pt1();
        } else if (alpha_q == 1) {
            pt = bez[b]->pt4();
        } else {
            pt = bez[a]->pointAt(alpha_p);
        }

        QIntersection intersection;
        intersection.alpha = (a == 0 ? alpha_p : alpha_q);
        intersection.pos = pt;
        m_intersections->add(intersection);
    }
}

void QIntersectionFinder::intersectLines(const QLineF &a, const QLineF &b, bool swap)
{
    const QPointF p1 = a.p1();
    const QPointF p2 = a.p2();

    const QPointF q1 = b.p1();
    const QPointF q2 = b.p2();

    const QPointF pDelta = p2 - p1;
    const QPointF qDelta = q2 - q1;

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

    if (qFuzzyCompare(par, qreal(0.0))) {
        const QPointF normal(-pDelta.y(), pDelta.x());

        // coinciding?
        if (qFuzzyCompare(dot(normal, q1 - p1), qreal(0.0))) {
            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) {
                m_hasIntersections = true;

                if (m_intersections) {
                    QIntersection intersection;
                    intersection.alpha = tq1;
                    intersection.pos = q1;
                    m_intersections->add(intersection);
                }
            }

            if (tq2 > 0 && tq2 < 1) {
                m_hasIntersections = true;

                if (m_intersections) {
                    QIntersection intersection;
                    intersection.alpha = tq2;
                    intersection.pos = q2;
                    m_intersections->add(intersection);
                }
            }

            if (!m_hasIntersections) {
                if (tq1 == 0 || tq1 == 1)
                    m_hasIntersections = true;
                else if (tq2 == 0 || tq2 == 1)
                    m_hasIntersections = true;
                else if (tq1 <= 0 && tq2 >= 1 || tq2 <= 0 && tq1 >= 1)
                    m_hasIntersections = true;
            }
        }

        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 qreal x = p1.x() + tp*(p2.x() - p1.x());
    const qreal y = p1.y() + tp*(p2.y() - p1.y());

    const qreal nalpha_p = dist(p1.x(), p1.y(), x, y) /
                           dist(p1.x(), p1.y(), p2.x(), p2.y());
    const qreal nalpha_q = dist(q1.x(), q1.y(), x, y) /
                           dist(q1.x(), q1.y(), q2.x(), q2.y());

    QPointF pt;
    if (qFuzzyCompare(nalpha_p, qreal(0)) || qFuzzyCompare(nalpha_p, qreal(1)))
        return;

    m_hasIntersections = true;

    if (!m_intersections)
        return;

    if (qFuzzyCompare(nalpha_q, qreal(0))) {
        pt = q1;
    } else if (qFuzzyCompare(nalpha_q, qreal(1))) {
        pt = q2;
    } else if (swap) {
        pt = p1 + (p2 - p1) * nalpha_p;
    } else {
        pt = q1 + (q2 - q1) * nalpha_q;
    }

    QIntersection intersection;
    intersection.alpha = nalpha_p;
    intersection.pos = pt;
    m_intersections->add(intersection);
}

void QIntersectionFinder::addIntersections(const QPathSegments *a, const QPathSegments *b, int i, bool ignoreAutoClosing)
{
    const QBezier *bezierA = a->bezierAt(i);
    bool isBezierA = bezierA != 0;

    QBezier tempA;
    QBezier tempB;

    if (!isBezierA && ignoreAutoClosing && a->isAutoClosingLine(i))
        return;

    for (int j = 0; j < b->segments(); ++j) {
        if (a == b && i == j)
            continue;

        bool swap = a < b || (a == b) && (i < j);

        bool isBezierB = b->bezierAt(j) != 0;

        if (!isBezierB && ignoreAutoClosing && b->isAutoClosingLine(j))
            continue;

        if (isBezierA || isBezierB) {
            if (!isBezierA)
                swap = false;
            else if (!isBezierB)
                swap = true;

            const QBezier *bezierB;
            if (isBezierB) {
                bezierB = b->bezierAt(j);
            } else {
                const QLineF *line = b->lineAt(j);
                QPointF p1 = line->p1();
                QPointF delta = (line->p2() - p1) / 3;
                tempB = QBezier::fromPoints(p1, p1 + delta, p1 + 2 * delta, p1 + 3 * delta);
                bezierB = &tempB;
            }

            if (!bezierA) {
                const QLineF *line = a->lineAt(i);
                QPointF p1 = line->p1();
                QPointF delta = (line->p2() - p1) / 3;
                tempA = QBezier::fromPoints(p1, p1 + delta, p1 + 2 * delta, p1 + 3 * delta);
                bezierA = &tempA;
            }

            intersectBeziers(*bezierA, *bezierB, swap);
        } else {
            const QLineF &lineA = *a->lineAt(i);
            const QLineF &lineB = *b->lineAt(j);

            intersectLines(lineA, lineB, swap);
        }
    }
}

void QWingedEdge::intersectAndAdd(bool mightIntersect)
{
    const QPathSegments *segments[2] = { &m_subjectSegments, &m_clipSegments };

    QDataBuffer<QIntersection> intersections;
    QIntersectionFinder finder(&intersections);
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < segments[i]->segments(); ++j) {
            intersections.reset();

            finder.addIntersections(segments[i], segments[i], j);

            if (mightIntersect)
                finder.addIntersections(segments[i], segments[(i+1)%2], j);

            qSort(intersections.data(), intersections.data() + intersections.size());

            const QBezier *bezier = segments[i]->bezierAt(j);
            if (bezier) {
                QPointF first = bezier->pt1();
                QPointF second = bezier->pt4();

                qreal alpha = 0.0;
                QPointF last = first;
                for (int j = 0; j < intersections.size(); ++j) {
                    const QIntersection &isect = intersections.at(j);

                    addBezierEdge(bezier, last, isect.pos, alpha, isect.alpha, i);

                    alpha = isect.alpha;
                    last = isect.pos;
                }

                addBezierEdge(bezier, last, second, alpha, 1.0, i);
            } else {
                QPointF first = segments[i]->lineAt(j)->p1();
                QPointF second = segments[i]->lineAt(j)->p2();

                QPointF last = first;
                for (int k = 0; k < intersections.size(); ++k) {
                    const QIntersection &isect = intersections.at(k);

                    QPathEdge *ep = edge(addEdge(last, isect.pos));

                    if (ep) {
                        const int dir = last.y() < isect.pos.y() ? 1 : -1;
                        if (i == 0)
                            ep->windingA += dir;
                        else
                            ep->windingB += dir;
                    }

                    last = isect.pos;
                }

                QPathEdge *ep = edge(addEdge(last, second));

                if (ep) {
                    const int dir = last.y() < second.y() ? 1 : -1;
                    if (i == 0)
                        ep->windingA += dir;
                    else
                        ep->windingB += dir;
                }
            }
        }
    }
}

QWingedEdge::QWingedEdge()
{
}

QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip)
{
    m_subjectSegments.setPath(subject);
    m_clipSegments.setPath(clip);

    const QRectF r1 = subject.controlPointRect();
    const QRectF r2 = clip.controlPointRect();

    // same as QRectF::intersets() except using <= instead of <
    const bool intersect = qMax(r1.x(), r2.x()) <= qMin(r1.x() + r1.width(), r2.x() + r2.width())
                           && qMax(r1.y(), r2.y()) <= qMin(r1.y() + r1.height(), r2.y() + r2.height());

    intersectAndAdd(intersect);
}

QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const
{
    const QPathEdge *sp = edge(status.edge);
    Q_ASSERT(sp);

    TraversalStatus result;
    result.edge = sp->next(status.traversal, status.direction);
    result.traversal = status.traversal;
    result.direction = status.direction;

    const QPathEdge *rp = edge(result.edge);
    Q_ASSERT(rp);

    if (sp->vertex(status.direction) == rp->vertex(status.direction))
        result.flip();

    return result;
}

static bool isLine(const QBezier &bezier)
{
    const bool equal_1_2 = bezier.pt1() == bezier.pt2();
    const bool equal_2_3 = bezier.pt2() == bezier.pt3();
    const bool equal_3_4 = bezier.pt3() == bezier.pt4();

    // point?
    if (equal_1_2 && equal_2_3 && equal_3_4)
        return true;

    if (bezier.pt1() == bezier.pt4())
        return equal_1_2 || equal_3_4;

    return equal_1_2 && equal_3_4 || equal_1_2 && equal_2_3 || equal_2_3 && equal_3_4;
}

void QPathSegments::setPath(const QPainterPath &path)
{
    m_lines.reset();
    m_beziers.reset();

    bool hasMoveTo = false;
    QPointF lastMoveTo;
    QPointF last;
    for (int i = 0; i < path.elementCount(); ++i) {
        QPointF current = path.elementAt(i);
        switch (path.elementAt(i).type) {
        case QPainterPath::MoveToElement:
            if (hasMoveTo && last != lastMoveTo) {
                Line line(QLineF(last, lastMoveTo), true);
                m_lines << line;
            }
            hasMoveTo = true;
            last = lastMoveTo = current;
            break;
        case QPainterPath::LineToElement:
            {
                Line line(QLineF(last, current));
                m_lines << line;
            }
            last = current;
            break;
        case QPainterPath::CurveToElement:
            {
                QBezier bezier = QBezier::fromPoints(last, path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2));
                if (isLine(bezier)) {