QWingedEdge Class Reference

#include <qpathclipper_p.h>

Classes
struct	TraversalStatus

Public Functions
int	addEdge (const QPointF &a, const QPointF &b)
int	addEdge (int vertexA, int vertexB)
int	addVertex (const QPointF &p)
QPathEdge *	edge (int edge)
const QPathEdge *	edge (int edge) const
int	edgeCount () const
bool	isInside (qreal x, qreal y) const
TraversalStatus	next (const TraversalStatus &status) const
	QWingedEdge ()
	QWingedEdge (const QPainterPath &subject, const QPainterPath &clip)
void	simplify ()
QPainterPath	toPath () const
QPathVertex *	vertex (int vertex)
const QPathVertex *	vertex (int vertex) const
int	vertexCount () const

Static Public Functions
static QPathEdge::Traversal	flip (QPathEdge::Traversal traversal)
static QPathEdge::Direction	flip (QPathEdge::Direction direction)

Private Functions
qreal	delta (int vertex, int a, int b) const
TraversalStatus	findInsertStatus (int vertex, int edge) const
int	insert (const QPathVertex &vertex)
void	intersectAndAdd ()
void	printNode (int i, FILE *handle)
void	removeEdge (int ei)

Properties
QDataBuffer< QPathEdge >	m_edges
QPathSegments	m_segments
QVector< qreal >	m_splitPoints
QDataBuffer< QPathVertex >	m_vertices

Detailed Description

Definition at line 232 of file qpathclipper_p.h.

Constructors and Destructors

QWingedEdge() [1/2]

QWingedEdge::QWingedEdge

(

)

Definition at line 863 of file qpathclipper.cpp.

                         :
    m_edges(0),
    m_vertices(0),
    m_segments(0)
{
}

QWingedEdge() [2/2]

QWingedEdge::QWingedEdge	(	const QPainterPath &	subject,
		const QPainterPath &	clip
	)

Definition at line 870 of file qpathclipper.cpp.

                                                                              :
    m_edges(subject.elementCount()),
    m_vertices(subject.elementCount()),
    m_segments(subject.elementCount())
{
    m_segments.setPath(subject);
    m_segments.addPath(clip);

    intersectAndAdd();
}

Functions

addEdge() [1/2]

int QWingedEdge::addEdge	(	const QPointF &	a,
		const QPointF &	b
	)

Definition at line 1203 of file qpathclipper.cpp.

{
    int fi = insert(a);
    int si = insert(b);

    return addEdge(fi, si);
}

addEdge() [2/2]

int QWingedEdge::addEdge	(	int	vertexA,
		int	vertexB
	)

Definition at line 1211 of file qpathclipper.cpp.

{
    if (fi == si)
        return -1;

    int common = commonEdge(*this, fi, si);
    if (common >= 0)
        return common;

    m_edges << QPathEdge(fi, si);

    int ei = m_edges.size() - 1;

    QPathVertex *fp = vertex(fi);
    QPathVertex *sp = vertex(si);

    QPathEdge *ep = edge(ei);

    const QPointF tangent = QPointF(*sp) - QPointF(*fp);
    ep->angle = computeAngle(tangent);
    ep->invAngle = ep->angle + 64;
    if (ep->invAngle >= 128)
        ep->invAngle -= 128;

    QPathVertex *vertices[2] = { fp, sp };
    QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward };

#ifdef QDEBUG_CLIPPER
    printf("** Adding edge %d / vertices: %.07f %.07f, %.07f %.07f\n", ei, fp->x, fp->y, sp->x, sp->y);
#endif

    for (int i = 0; i < 2; ++i) {
        QPathVertex *vp = vertices[i];
        if (vp->edge < 0) {
            vp->edge = ei;
            ep->setNext(dirs[i], ei);
        } else {
            int vi = ep->vertex(dirs[i]);
            Q_ASSERT(vertex(vi) == vertices[i]);

            TraversalStatus os = findInsertStatus(vi, ei);
            QPathEdge *op = edge(os.edge);

            Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]);

            TraversalStatus ns = next(os);
            ns.flipDirection();
            QPathEdge *np = edge(ns.edge);

            op->setNext(os.traversal, os.direction, ei);
            np->setNext(ns.traversal, ns.direction, ei);

            int oe = os.edge;
            int ne = ns.edge;

            os = next(os);
            ns = next(ns);

            os.flipDirection();
            ns.flipDirection();

            Q_ASSERT(os.edge == ei);
            Q_ASSERT(ns.edge == ei);

            ep->setNext(os.traversal, os.direction, oe);
            ep->setNext(ns.traversal, ns.direction, ne);
        }
    }

    Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Forward) >= 0);
    Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Backward) >= 0);
    Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Forward) >= 0);
    Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0);

    return ei;
}

addVertex()

int QWingedEdge::addVertex ( const QPointF &  p )

inline

Definition at line 464 of file qpathclipper_p.h.

{
    m_vertices << p;
    return m_vertices.size() - 1;
}

delta()

qreal QWingedEdge::delta ( int  vertex, int  a, int  b  ) const

private

Definition at line 1017 of file qpathclipper.cpp.

Referenced by findInsertStatus().

{
    const QPathEdge *ap = edge(a);
    const QPathEdge *bp = edge(b);

    double a_angle = ap->angle;
    double b_angle = bp->angle;

    if (vertex == ap->second)
        a_angle = ap->invAngle;

    if (vertex == bp->second)
        b_angle = bp->invAngle;

    double result = b_angle - a_angle;

    if (result >= 128.)
        return result - 128.;
    else if (result < 0)
        return result + 128.;
    else
        return result;
}

edge() [1/2]

QPathEdge * QWingedEdge::edge ( int  edge )

inline

Definition at line 449 of file qpathclipper_p.h.

Referenced by add(), addEdge(), clear(), commonEdge(), delta(), QPathClipper::doClip(), findCrossings(), findInsertStatus(), QPathClipper::handleCrossingEdges(), midPoint(), next(), removeEdge(), simplify(), toPath(), and traverse().

{
    return edge < 0 ? 0 : &m_edges.at(edge);
}

edge() [2/2]

const QPathEdge * QWingedEdge::edge ( int  edge ) const

inline

Definition at line 454 of file qpathclipper_p.h.

{
    return edge < 0 ? 0 : &m_edges.at(edge);
}

edgeCount()

int QWingedEdge::edgeCount ( ) const

inline

Definition at line 444 of file qpathclipper_p.h.

Referenced by QPathClipper::doClip(), findCrossings(), simplify(), and toPath().

{
    return m_edges.size();
}

findInsertStatus()

QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus ( int  vertex, int  edge  ) const

private

Definition at line 1051 of file qpathclipper.cpp.

Referenced by addEdge().

{
    const QPathVertex *vp = vertex(vi);

    Q_ASSERT(vp);
    Q_ASSERT(ei >= 0);
    Q_ASSERT(vp->edge >= 0);

    int position = vp->edge;
    qreal d = 128.;

    TraversalStatus status;
    status.direction = edge(vp->edge)->directionTo(vi);
    status.traversal = QPathEdge::RightTraversal;
    status.edge = vp->edge;

#ifdef QDEBUG_CLIPPER
    const QPathEdge *ep = edge(ei);
    qDebug() << "Finding insert status for edge" << ei << "at vertex" << QPointF(*vp) << ", angles: " << ep->angle << ep->invAngle;
#endif

    do {
        status = next(status);
        status.flip();

        Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);
        qreal d2 = delta(vi, ei, status.edge);

#ifdef QDEBUG_CLIPPER
        const QPathEdge *op = edge(status.edge);
        qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle;
#endif

        if (d2 < d) {
            position = status.edge;
            d = d2;
        }
    } while (status.edge != vp->edge);

    status.traversal = QPathEdge::LeftTraversal;
    status.direction = QPathEdge::Forward;
    status.edge = position;

    if (edge(status.edge)->vertex(status.direction) != vi)
        status.flip();

#ifdef QDEBUG_CLIPPER
    qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge;
#endif

    Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);

    return status;
}

flip() [1/2]

QPathEdge::Traversal QWingedEdge::flip ( QPathEdge::Traversal  traversal )

inlinestatic

Definition at line 480 of file qpathclipper_p.h.

Referenced by QWingedEdge::TraversalStatus::flipDirection(), and QWingedEdge::TraversalStatus::flipTraversal().

{
    return traversal == QPathEdge::RightTraversal ? QPathEdge::LeftTraversal : QPathEdge::RightTraversal;
}

flip() [2/2]

QPathEdge::Direction QWingedEdge::flip ( QPathEdge::Direction  direction )

inlinestatic

Definition at line 485 of file qpathclipper_p.h.

{
    return direction == QPathEdge::Forward ? QPathEdge::Backward : QPathEdge::Forward;
}

insert()

int QWingedEdge::insert ( const QPathVertex &  vertex )

private

Definition at line 1288 of file qpathclipper.cpp.

Referenced by addEdge().

{
    if (!m_vertices.isEmpty()) {
        const QPathVertex &last = m_vertices.last();
        if (vertex.x == last.x && vertex.y == last.y)
            return m_vertices.size() - 1;

        for (int i = 0; i < m_vertices.size(); ++i) {
            const QPathVertex &v = m_vertices.at(i);
            if (qFuzzyCompare(v.x, vertex.x) && qFuzzyCompare(v.y, vertex.y)) {
                return i;
            }
        }
    }

    m_vertices << vertex;
    return m_vertices.size() - 1;
}

intersectAndAdd()

void QWingedEdge::intersectAndAdd ( )

private

Definition at line 802 of file qpathclipper.cpp.

Referenced by QWingedEdge().

{
    QIntersectionFinder finder;
    finder.produceIntersections(m_segments);

    m_segments.mergePoints();

    for (int i = 0; i < m_segments.points(); ++i)
        addVertex(m_segments.pointAt(i));

    QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments());
    for (int i = 0; i < m_segments.segments(); ++i) {
        intersections.reset();

        int pathId = m_segments.pathId(i);

        const QPathSegments::Intersection *isect = m_segments.intersectionAt(i);
        while (isect) {
            intersections << *isect;

            if (isect->next) {
                isect += isect->next;
            } else {
                isect = 0;
            }
        }

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

        int first = m_segments.segmentAt(i).va;
        int second = m_segments.segmentAt(i).vb;

        int last = first;
        for (int j = 0; j < intersections.size(); ++j) {
            const QPathSegments::Intersection &isect = intersections.at(j);

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

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

            last = isect.vertex;
        }

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

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

isInside()

bool QWingedEdge::isInside	(	qreal	x,
		qreal	y
	)		const

Definition at line 1795 of file qpathclipper.cpp.

{
    int winding = 0;
    for (int i = 0; i < edgeCount(); ++i) {
        const QPathEdge *ep = edge(i);

        // left xor right
        int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1;

        if (!w)
            continue;

        QPointF a = *vertex(ep->first);
        QPointF b = *vertex(ep->second);

        if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
            qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());

            if (intersectionX > x)
                winding += w;
        }
    }

    return winding & 1;
}

next()

QWingedEdge::TraversalStatus QWingedEdge::next

(

const TraversalStatus &

status

)

const

Definition at line 881 of file qpathclipper.cpp.

Referenced by add(), addEdge(), clear(), commonEdge(), findInsertStatus(), removeEdge(), and traverse().

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

printNode()

void QWingedEdge::printNode ( int  i, FILE *  handle  )

private

removeEdge()

void QWingedEdge::removeEdge ( int  ei )

private

Definition at line 1106 of file qpathclipper.cpp.

Referenced by simplify().

{
    QPathEdge *ep = edge(ei);

    TraversalStatus status;
    status.direction = QPathEdge::Forward;
    status.traversal = QPathEdge::RightTraversal;
    status.edge = ei;

    TraversalStatus forwardRight = next(status);
    forwardRight.flipDirection();

    status.traversal = QPathEdge::LeftTraversal;
    TraversalStatus forwardLeft = next(status);
    forwardLeft.flipDirection();

    status.direction = QPathEdge::Backward;
    TraversalStatus backwardLeft = next(status);
    backwardLeft.flipDirection();

    status.traversal = QPathEdge::RightTraversal;
    TraversalStatus backwardRight = next(status);
    backwardRight.flipDirection();

    edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge);
    edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge);

    edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge);
    edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge);

    ep->setNext(QPathEdge::Forward, ei);
    ep->setNext(QPathEdge::Backward, ei);

    QPathVertex *a = vertex(ep->first);
    QPathVertex *b = vertex(ep->second);

    a->edge = backwardRight.edge;
    b->edge = forwardRight.edge;
}

simplify()

void QWingedEdge::simplify

(

)

Definition at line 1352 of file qpathclipper.cpp.

Referenced by QPathClipper::doClip().

{
    for (int i = 0; i < edgeCount(); ++i) {
        const QPathEdge *ep = edge(i);

        // if both sides are part of the inside then we can collapse the edge
        int flag = 0x3 << 4;
        if ((ep->flag & flag) == flag) {
            removeEdge(i);

            ep->flag &= ~flag;
        }
    }
}

toPath()

QPainterPath QWingedEdge::toPath

(

)

const

Definition at line 1367 of file qpathclipper.cpp.

Referenced by QPathClipper::clip().

{
    QPainterPath path;

    for (int i = 0; i < edgeCount(); ++i) {
        const QPathEdge *ep = edge(i);

        if (ep->flag & 16) {
            add(path, *this, i, QPathEdge::LeftTraversal);
        }

        if (ep->flag & 32)
            add(path, *this, i, QPathEdge::RightTraversal);
    }

    return path;
}

vertex() [1/2]

QPathVertex * QWingedEdge::vertex ( int  vertex )

inline

Definition at line 470 of file qpathclipper_p.h.

Referenced by add(), addEdge(), commonEdge(), QPathClipper::doClip(), findCrossings(), findInsertStatus(), QPathClipper::handleCrossingEdges(), insert(), midPoint(), and removeEdge().

{
    return vertex < 0 ? 0 : &m_vertices.at(vertex);
}

vertex() [2/2]

const QPathVertex * QWingedEdge::vertex ( int  vertex ) const

inline

Definition at line 475 of file qpathclipper_p.h.

{
    return vertex < 0 ? 0 : &m_vertices.at(vertex);
}

vertexCount()

int QWingedEdge::vertexCount ( ) const

inline

Definition at line 459 of file qpathclipper_p.h.

Referenced by QPathClipper::doClip().

{
    return m_vertices.size();
}

Properties

m_edges

QDataBuffer<QPathEdge> QWingedEdge::m_edges

private

Definition at line 287 of file qpathclipper_p.h.

Referenced by addEdge().

m_segments

QPathSegments QWingedEdge::m_segments

private

Definition at line 292 of file qpathclipper_p.h.

Referenced by QPathSegments::addPath(), QWingedEdge(), and QPathSegments::setPath().

m_splitPoints

QVector<qreal> QWingedEdge::m_splitPoints

private

Definition at line 290 of file qpathclipper_p.h.

m_vertices

QDataBuffer<QPathVertex> QWingedEdge::m_vertices

private

Definition at line 288 of file qpathclipper_p.h.

Referenced by insert().

---

The documentation for this class was generated from the following files:

• /src/gui/painting/qpathclipper_p.h
• /src/gui/painting/qpathclipper.cpp