When defining a cubic bezier curve, is there a way to test if there is ever a value of X that contains more than one value for Y?

Question

We're trying to create a curve editor program for calibrating hardware. As such, Bezier curves seem to be the easiest UI for a person to work with. However, the problem with bezier curves is it's possible to create a curve where there is more than one Y value for a particular X, or vice versa.

Now I know I can constrain the control points (P1, P2) to the region defined by the anchors (P0, P3) which would block an S from being created, but it also limits other otherwise-valid curves.

What I'm wondering is if there is some test you can run, short of walking the curve manually, that you can tell if your curve has an S-bend in it and if so, to reject that curve.

BTW, this is for a cross-platform app, hence WPF and NSBezierCurve being keywords.

Answer 1

The good news is that we can find out all sorts of things about bezier curves. There are several shape interrogation techinques (works fairly well for curves of lower degree, and cubic is on the lower side :)).

S shaped cubic bezier curve

First, an S shaped cubic bezier curve, has an inflection point. Inflection points are points on the curve where the concavity changes to convexity or the other way around. This also means that at Inflection points, curvature of the curve is zero (Well, if any curve has to change from concave to convex, there has to be some place in between where the curve is straight —just look at "S").

https://en.wikipedia.org/wiki/Inflection_point

The Equation for curvature of a parametric curve is

We can ask Mathematica to simplify this, so that we can do some quick tests.

Here is some Javascript code (using paper.js library) which does the same thing:

// Method1 - Find inflection points
function hasInflection(p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y){
    var CURV_EPSILON = 1e-3;
    var e2 = 1 + CURV_EPSILON;
    var roots = [], a, b, c;

    // Solve for Numerator[k] == 0
    // Where, Curvature k = (dx d^2y - d^2x dy) / (dx^2 - dy^2)^(3/2)
    // Coefficients from Mathematica
    a = -p1x*p0y + 2*p2x*p0y - p3x*p0y + p0x*p1y - 3*p2x*p1y + 2*p3x*p1y - 2*p0x*p2y + 3*p1x*p2y - p3x*p2y + p0x*p3y - 2*p1x*p3y + p2x*p3y;
    b = (2*p1x*p0y - 3*p2x*p0y + p3x*p0y - 2*p0x*p1y + 3*p2x*p1y - p3x*p1y + 3*p0x*p2y - 3*p1x*p2y - p0x*p3y + p1x*p3y);
    c = (-p1x*p0y + p2x*p0y + p0x*p1y - p2x*p1y - p0x*p2y + p1x*p2y);

    // Use any method to solve the quadratic equation (a x^2 + b x + c = 0)
    Numerical.solveQuadratic(a, b, c, roots, 0, 1);
    // Find the root where, the curve changes from concave to convex
    for (i = 0, l = roots.length; i < l; ++i) {
        r = roots[i];
        if( r > -CURV_EPSILON && r < e2 ){
            // Here we basically evaluate the signed normals and look if they are of different signs
            if( Curve.evaluate(v,r-CURV_EPSILON,3) * Curve.evaluate(v,r+CURV_EPSILON,3) < 0 )
                return true;
        }
    }
    return false;
}

Or see the complete example here

Curves where, more than a single Y value for any X

From your question, I think there is room for a better definition of what exactly is that you want.

The condition of more than a Y value for any X (or vice versa) can occur even if the curve is not S shaped —the curvature never changes sign.

The same is true even if the curve does not self-intersect. So that is probably not a good good test for what you are looking for.

If you need curves that are monotone in X and Y direction —that is, the X and Y value are either decreasing or increasing monotonically along the length of the curve; you can solve the derivative of the cubic equation instead (in both X and Y).