Logo Search packages:      
Sourcecode: inkscape version File versions

static double Geom::compute_max_error_ratio ( Point const   d[],
double const   u[],
unsigned const   len,
BezierCurve const   bezCurve,
double const   tolerance,
unsigned *const   splitPoint 
) [static]

Find the maximum squared distance of digitized points to fitted curve, and (if this maximum error is non-zero) set *splitPoint to the corresponding index.

Precondition:
2 <= len.

u[0] == 0.

u[len - 1] == 1.0.

Postcondition:
((ret == 0.0) || ((*splitPoint < len - 1) && (*splitPoint != 0 || ret < 0.0))).

Definition at line 905 of file bezier-utils.cpp.

References bezier_pt(), and compute_hook().

Referenced by bezier_fit_cubic_full().

{
    assert( 2 <= len );
    unsigned const last = len - 1;
    assert( bezCurve[0] == d[0] );
    assert( bezCurve[3] == d[last] );
    assert( u[0] == 0.0 );
    assert( u[last] == 1.0 );
    /* I.e. assert that the error for the first & last points is zero.
     * Otherwise we should include those points in the below loop.
     * The assertion is also necessary to ensure 0 < splitPoint < last.
     */

    double maxDistsq = 0.0; /* Maximum error */
    double max_hook_ratio = 0.0;
    unsigned snap_end = 0;
    Point prev = bezCurve[0];
    for (unsigned i = 1; i <= last; i++) {
        Point const curr = bezier_pt(3, bezCurve, u[i]);
        double const distsq = lensq( curr - d[i] );
        if ( distsq > maxDistsq ) {
            maxDistsq = distsq;
            *splitPoint = i;
        }
        double const hook_ratio = compute_hook(prev, curr, .5 * (u[i - 1] + u[i]), bezCurve, tolerance);
        if (max_hook_ratio < hook_ratio) {
            max_hook_ratio = hook_ratio;
            snap_end = i;
        }
        prev = curr;
    }

    double const dist_ratio = sqrt(maxDistsq) / tolerance;
    double ret;
    if (max_hook_ratio <= dist_ratio) {
        ret = dist_ratio;
    } else {
        assert(0 < snap_end);
        ret = -max_hook_ratio;
        *splitPoint = snap_end - 1;
    }
    assert( ret == 0.0
              || ( ( *splitPoint < last )
                   && ( *splitPoint != 0 || ret < 0. ) ) );
    return ret;
}


Generated by  Doxygen 1.6.0   Back to index