qpainterpath.cpp

qt-x11-opensource-src-4.1.4.tar.gz源码

        } else {
            qreal t1 = (-bx + sqrt(bx * bx - 4 * ax * cx)) / (2 * ax);
            QT_BEZIER_CHECK_T(b, t1);

            qreal t2 = (-bx - sqrt(bx * bx - 4 * ax * cx)) / (2 * ax);
            QT_BEZIER_CHECK_T(b, t2);
        }
    }

    // Update for the Y extrema
    {
        qreal ay = QT_BEZIER_A(b, y);
        qreal by = QT_BEZIER_B(b, y);
        qreal cy = QT_BEZIER_C(b, y);

        // specialcase quadratic curves to avoid div by zero
        if (qFuzzyCompare(ay, 0)) {

            // linear curves are covered by initalization.
            if (!qFuzzyCompare(by, 0)) {
                qreal t = -cy / by;
                QT_BEZIER_CHECK_T(b, t);
            }

        } else {
            qreal t1 = (-by + sqrt(by * by - 4 * ay * cy)) / (2 * ay);
            QT_BEZIER_CHECK_T(b, t1);

            qreal t2 = (-by - sqrt(by * by - 4 * ay * cy)) / (2 * ay);
            QT_BEZIER_CHECK_T(b, t2);
        }
    }
    return QRectF(minx, miny, maxx - minx, maxy - miny);
}

/*!
    Returns the bounding rectangle of this painter path as a rectangle with
    floating point precision.

    \sa controlPointRect()
*/
QRectF QPainterPath::boundingRect() const
{
    Q_D(QPainterPath);
    if (isEmpty())
        return QRect();

    qreal minx, maxx, miny, maxy;
    minx = maxx = d->elements.at(0).x;
    miny = maxy = d->elements.at(0).y;
    for (int i=1; i<d->elements.size(); ++i) {
        const Element &e = d->elements.at(i);

        switch (e.type) {
        case MoveToElement:
        case LineToElement:
            if (e.x > maxx) maxx = e.x;
            else if (e.x < minx) minx = e.x;
            if (e.y > maxy) maxy = e.y;
            else if (e.y < miny) miny = e.y;
            break;
        case CurveToElement:
            {
                QBezier b = QBezier::fromPoints(d->elements.at(i-1),
                                                e,
                                                d->elements.at(i+1),
                                                d->elements.at(i+2));
                QRectF r = qt_painterpath_bezier_extrema(b);
                qreal right = r.right();
                qreal bottom = r.bottom();
                if (r.x() < minx) minx = r.x();
                if (right > maxx) maxx = right;
                if (r.y() < miny) miny = r.y();
                if (bottom > maxy) maxy = bottom;
                i += 2;
            }
            break;
        default:
            break;
        }
    }
    return QRectF(minx, miny, maxx - minx, maxy - miny);
}

/*!
    Returns the rectangle containing all the points and control points
    in this path.

    This function is significantly faster to compute than the exact
    boundingRect(), and the returned rectangle is always a superset of
    the rectangle returned by boundingRect().

    \sa boundingRect()
*/
QRectF QPainterPath::controlPointRect() const
{
    Q_D(QPainterPath);
    if (isEmpty())
        return QRect();

    qreal minx, maxx, miny, maxy;
    minx = maxx = d->elements.at(0).x;
    miny = maxy = d->elements.at(0).y;
    for (int i=1; i<d->elements.size(); ++i) {
        const Element &e = d->elements.at(i);
        if (e.x > maxx) maxx = e.x;
        else if (e.x < minx) minx = e.x;
        if (e.y > maxy) maxy = e.y;
        else if (e.y < miny) miny = e.y;
    }
    return QRectF(minx, miny, maxx - minx, maxy - miny);
}


/*!
    \fn bool QPainterPath::isEmpty() const

    Returns true if there are no elements in this path, otherwise
    returns false.

    \sa elementCount()
*/

/*!
    Creates and returns a reversed copy of the path.

    It is the order of the elements that is reversed: If a
    QPainterPath is composed by calling the moveTo(), lineTo() and
    cubicTo() functions in the specified order, the reversed copy is
    composed by calling cubicTo(), lineTo() and moveTo().
*/
QPainterPath QPainterPath::toReversed() const
{
    Q_D(const QPainterPath);
    QPainterPath rev;

    if (isEmpty()) {
        rev = *this;
        return rev;
    }

    rev.moveTo(d->elements.at(d->elements.size()-1).x, d->elements.at(d->elements.size()-1).y);

    for (int i=d->elements.size()-1; i>=1; --i) {
        const QPainterPath::Element &elm = d->elements.at(i);
        const QPainterPath::Element &prev = d->elements.at(i-1);
        switch (elm.type) {
        case LineToElement:
            rev.lineTo(prev.x, prev.y);
            break;
        case MoveToElement:
            rev.moveTo(prev.x, prev.y);
            break;
        case CurveToDataElement:
            {
                Q_ASSERT(i>=3);
                const QPainterPath::Element &cp1 = d->elements.at(i-2);
                const QPainterPath::Element &sp = d->elements.at(i-3);
                Q_ASSERT(prev.type == CurveToDataElement);
                Q_ASSERT(cp1.type == CurveToElement);
                rev.cubicTo(prev.x, prev.y, cp1.x, cp1.y, sp.x, sp.y);
                i -= 2;
                break;
            }
        default:
            Q_ASSERT(!"qt_reversed_path");
            break;
        }
    }
    //qt_debug_path(rev);
    return rev;
}


/*!
    Converts the path into a list of polygons using the given
    transformation \a matrix, and returns the list.

    This function creates one polygon for each subpath regardless of
    intersecting subpaths (i.e. overlapping bounding rectangles). To
    make sure that such overlapping subpaths are filled correctly, use
    the toFillPolygons() function instead.

    \sa toFillPolygons(), toFillPolygon(), {QPainterPath#QPainterPath
    Conversion}{QPainterPath Conversion}
*/
QList<QPolygonF> QPainterPath::toSubpathPolygons(const QMatrix &matrix) const
{
    Q_D(const QPainterPath);
    QList<QPolygonF> flatCurves;
    if (isEmpty())
        return flatCurves;

    QPolygonF current;
    for (int i=0; i<elementCount(); ++i) {
        const QPainterPath::Element &e = d->elements.at(i);
        switch (e.type) {
        case QPainterPath::MoveToElement:
            if (current.size() > 1)
                flatCurves += current;
            current.clear();
            current.reserve(16);
            current += QPointF(e.x, e.y) * matrix;
            break;
        case QPainterPath::LineToElement:
            current += QPointF(e.x, e.y) * matrix;
            break;
        case QPainterPath::CurveToElement: {
            Q_ASSERT(d->elements.at(i+1).type == QPainterPath::CurveToDataElement);
            Q_ASSERT(d->elements.at(i+2).type == QPainterPath::CurveToDataElement);
            QBezier bezier = QBezier::fromPoints(QPointF(d->elements.at(i-1).x, d->elements.at(i-1).y) * matrix,
                                       QPointF(e.x, e.y) * matrix,
                                       QPointF(d->elements.at(i+1).x, d->elements.at(i+1).y) * matrix,
                                                 QPointF(d->elements.at(i+2).x, d->elements.at(i+2).y) * matrix);
            bezier.addToPolygon(&current);
            i+=2;
            break;
        }
        case QPainterPath::CurveToDataElement:
            Q_ASSERT(!"QPainterPath::toSubpathPolygons(), bad element type");
            break;
        }
    }

    if (current.size()>1)
        flatCurves += current;

    return flatCurves;
}

/*!
    Converts the path into a polygon using the given transformation \a
    matrix, and returns the polygon.

    The polygon is created by first converting all subpaths to
    polygons, then using a rewinding technique to make sure that
    overlapping subpaths can be filled using the correct fill rule.

    Note that rewinding inserts addition lines in the polygon so
    the outline of the fill polygon does not match the outline of
    the path.

    \sa toSubpathPolygons(), toFillPolygons(),
    {QPainterPath#QPainterPath Conversion}{QPainterPath Conversion}
*/
QPolygonF QPainterPath::toFillPolygon(const QMatrix &matrix) const
{

    QList<QPolygonF> flats = toSubpathPolygons(matrix);
    QPolygonF polygon;
    if (flats.isEmpty())
        return polygon;
    QPointF first = flats.first().first();
    for (int i=0; i<flats.size(); ++i) {
        polygon += flats.at(i);
        if (!flats.at(i).isClosed())
            polygon += flats.at(i).first();
        if (i > 0)
            polygon += first;
    }
    return polygon;
}

static inline bool rect_intersects(const QRectF &r1, const QRectF &r2)
{
    return qMax(r1.left(), r2.left()) <= qMin(r1.right(), r2.right())
        && qMax(r1.top(), r2.top()) <= qMin(r1.bottom(), r2.bottom());
}
/*!
    Converts the path into a list of polygons using the given
    transformation \a matrix, and returns the list.

    The function differs from the toFillPolygon() function in that it
    creates several polygons. It is provided because it is usually
    faster to draw several small polygons than to draw one large
    polygon, even though the total number of points drawn is the same.

    The toFillPolygons() function differs from the toSubpathPolygons()
    function in that it create only polygon for subpaths that have
    overlapping bounding rectangles.

    Like the toFillPolygon() function, this function uses a rewinding
    technique to make sure that overlapping subpaths can be filled
    using the correct fill rule. Note that rewinding inserts addition
    lines in the polygons so the outline of the fill polygon does not
    match the outline of the path.

    \sa toSubpathPolygons(), toFillPolygon(),
    {QPainterPath#QPainterPath Conversion}{QPainterPath Conversion}
*/

// #define QPP_FILLPOLYGONS_DEBUG

QList<QPolygonF> QPainterPath::toFillPolygons(const QMatrix &matrix) const
{
    QList<QPolygonF> polys;

    QList<QPolygonF> subpaths = toSubpathPolygons(matrix);
    int count = subpaths.size();

    if (count == 0)
        return polys;

    QList<QRectF> bounds;
    for (int i=0; i<count; ++i)
        bounds += subpaths.at(i).boundingRect();

#ifdef QPP_FILLPOLYGONS_DEBUG
    printf("QPainterPath::toFillPolygons, subpathCount=%d\n", count);
    for (int i=0; i<bounds.size(); ++i)
        qDebug() << " bounds" << i << bounds.at(i);
#endif

    QVector< QList<int> > isects;
    isects.resize(count);

    // find all intersections
    for (int j=0; j<count; ++j) {
        QRectF cbounds = bounds.at(j);
        for (int i=0; i<count; ++i) {
            if (rect_intersects(cbounds, bounds.at(i))) {
                isects[j] << i;
            }
        }
    }

#ifdef QPP_FILLPOLYGONS_DEBUG
    printf("Intersections before flattening:\n");
    for (int i = 0; i < count; ++i) {
        printf("%d: ", i);
        for (int j = 0; j < isects[i].size(); ++j) {
            printf("%d ", isects[i][j]);
        }
        printf("\n");
    }
#endif

    // flatten the sets of intersections
    for (int i=0; i<count; ++i) {
        const QList<int> &current_isects = isects.at(i);
        for (int j=0; j<current_isects.size(); ++j) {
            int isect_j = current_isects.at(j);
            if (isect_j == i)
                continue;
            for (int k=0; k<isects[isect_j].size(); ++k) {
                int isect_k = isects[isect_j][k];
                if (isect_k != i && !isects.at(i).contains(isect_k)) {
                    isects[i] += isect_k;
                }
            }
            isects[isect_j].clear();
        }
    }

#ifdef QPP_FILLPOLYGONS_DEBUG
    printf("Intersections after flattening:\n");
    for (int i = 0; i < count; ++i) {
        printf("%d: ", i);
        for (int j = 0; j < isects[i].size(); ++j) {
            printf("%d ", isects[i][j]);
        }
        printf("\n");
    }
#endif

    // Join the intersected subpaths as rewinded polygons
    for (int i=0; i<count; ++i) {
        const QList<int> &subpath_list = isects[i];
        if (!subpath_list.isEmpty()) {
            QPolygonF buildUp;
            for (int j=0; j<subpath_list.size(); ++j) {
                buildUp += subpaths.at(subpath_list.at(j));
                if (!buildUp.isClosed())
                    buildUp += buildUp.first();
            }
            polys += buildUp;
        }
    }

    return polys;
}

static void qt_painterpath_isect_line(const QPointF &p1, const QPointF &p2, const QPointF &pos,
                                      int *winding)
{
    qreal x1 = p1.x();
    qreal y1 = p1.y();
    qreal x2 = p2.x();
    qreal y2 = p2.y();
    qreal y = pos.y();

    int dir = 1;

    if (qFuzzyCompare(y1, y2)) {
        // ignore horizontal lines according to scan conversion rule
        return;
    } else if (y2 < y1) {
        qreal x_tmp = x2; x2 = x1; x1 = x_tmp;
        qreal y_tmp = y2; y2 = y1; y1 = y_tmp;
        dir = -1;
    }

    if (y >= y1 && y < y2) {
        qreal x = x1 + ((x2 - x1) / (y2 - y1)) * (y - y1);

        // count up the winding number if we're
        if (x<=pos.x()) {
            (*winding) += dir;
        }
    }
}

static void qt_painterpath_isect_curve(const QBezier &bezier, const QPointF &pt,
                                       int *winding)
{
    qreal y = pt.y();
    qreal x = pt.x();
    QRectF bounds = bezier.bounds();

    // potential intersection, divide and try again...
    // Please note that a sideeffect of the bottom exclusion is that
    // horizontal lines are dropped, but this is correct according to
    // scan conversion rules.
    if (y >= bounds.y() && y < bounds.y() + bounds.height()) {

        // hit lower limit... This is a rough threshold, but its a
        // tradeoff between speed and precision.
        const qreal lower_bound = .01;