Calculate the length of a segment of a quadratic bezier

beziermath

I use this algorithm to calculate the length of a quadratic bezier:
http://www.malczak.linuxpl.com/blog/quadratic-bezier-curve-length/

However, what I wish to do is calculate the length of the bezier from 0 to t where 0 < t < 1

Is there any way to modify the formula used in the link above to get the length of the first segment of a bezier curve?

Just to clarify, I'm not looking for the distance between q(0) and q(t) but the length of the arc that goes between these points.

(I don't wish to use adaptive subdivision to aproximate the length)

Best Answer

Since I was sure a similar form solution would exist for that variable t case - I extended the solution given in the link.

Starting from the equation in the link:

$L=\int_0^t\sqrt{At^2+Bt+C}\;dt$

Which we can write as

$L=\sqrt{A}\int_0^t\sqrt{t^2+2bt+c}\;dt$

Where b = B/(2A) and c = C/A.

Then transforming u = t + b we get

$L=\sqrt{A}\int_{b}^u\sqrt{u^2+k}\;dt$

Where k = c - b^2

Now we can use the integral identity from the link to obtain:

$L=\frac{\sqrt{A}}{2}\left(u\sqrt{u^2+k}-b\sqrt{b^2+k}+k\log\left|\frac{u+\sqrt{u^2+k}}{b+\sqrt{b^2+k}}\right|\right)$

So, in summary, the required steps are:

Calculate A,B,C as in the original equation.
Calculate b = B/(2A) and c = C/A
Calculate u = t + b and k = c -b^2
Plug these values into the equation above.

Related Solutions

Quadratic Bezier Curve: Calculate Tangent

Using your formula for B'(t), evaluated at t=1/2, we get

B'(1/2) = -P0 + P2

From the look of your graph, P0 = (0,0) and P2 = (400,0). So

B'(1/2) = (400,0).

This is the "velocity" of a point traveling along B(t) at t=1/2.

(400,0) is a horizontal vector, with magnitude 400.

So all is as it should be. Since B'(t) is horizontal, it does have "slope" 0.

An algorithm to find bounding box of closed bezier curves

Ivan Kuckir's DeCasteljau is a brute force, but works in many cases. The problem with it is the count of iterations. The actual shape and the distance between coordinates affect to the precision of the result. And to find a precise enough answer, you have to iterate tens of times, may be more. And it may fail if there are sharp turns in curve.

Better solution is to find first derivative roots, as is described on the excellent site http://processingjs.nihongoresources.com/bezierinfo/. Please read the section Finding the extremities of the curves.

The link above has the algorithm for both quadratic and cubic curves.

The asker of question is interested in quadratic curves, so the rest of this answer may be irrelevant, because I provide codes for calculating extremities of Cubic curves.

Below are three Javascript codes of which the first (CODE 1) is the one I suggest to use.

** CODE 1 **

After testing processingjs and Raphael's solutions I find they had some restrictions and/or bugs. Then more search and found Bonsai and it's bounding box function, which is based on NISHIO Hirokazu's Python script. Both have a downside where double equality is tested using ==. When I changed these to numerically robust comparisons, then script succeeds 100% right in all cases. I tested the script with thousands of random paths and also with all collinear cases and all succeeded:

Various cubic curves

Random cubic curves

Collinear cubic curves

The code is as follows. Usually left, right, top and bottom values are the all needed, but in some cases it's fine to know the coordinates of local extreme points and corresponding t values. So I added there two variables: tvalues and points. Remove code regarding them and you have fast and stable bounding box calculation function.

// Source: http://blog.hackers-cafe.net/2009/06/how-to-calculate-bezier-curves-bounding.html
// Original version: NISHIO Hirokazu
// Modifications: Timo

var pow = Math.pow,
  sqrt = Math.sqrt,
  min = Math.min,
  max = Math.max;
  abs = Math.abs;

function getBoundsOfCurve(x0, y0, x1, y1, x2, y2, x3, y3)
{
  var tvalues = new Array();
  var bounds = [new Array(), new Array()];
  var points = new Array();

  var a, b, c, t, t1, t2, b2ac, sqrtb2ac;
  for (var i = 0; i < 2; ++i)
  {
    if (i == 0)
    {
      b = 6 * x0 - 12 * x1 + 6 * x2;
      a = -3 * x0 + 9 * x1 - 9 * x2 + 3 * x3;
      c = 3 * x1 - 3 * x0;
    }
    else
    {
      b = 6 * y0 - 12 * y1 + 6 * y2;
      a = -3 * y0 + 9 * y1 - 9 * y2 + 3 * y3;
      c = 3 * y1 - 3 * y0;
    }

    if (abs(a) < 1e-12) // Numerical robustness
    {
      if (abs(b) < 1e-12) // Numerical robustness
      {
        continue;
      }
      t = -c / b;
      if (0 < t && t < 1)
      {
        tvalues.push(t);
      }
      continue;
    }
    b2ac = b * b - 4 * c * a;
    sqrtb2ac = sqrt(b2ac);
    if (b2ac < 0)
    {
      continue;
    }
    t1 = (-b + sqrtb2ac) / (2 * a);
    if (0 < t1 && t1 < 1)
    {
      tvalues.push(t1);
    }
    t2 = (-b - sqrtb2ac) / (2 * a);
    if (0 < t2 && t2 < 1)
    {
      tvalues.push(t2);
    }
  }

  var x, y, j = tvalues.length,
    jlen = j,
    mt;
  while (j--)
  {
    t = tvalues[j];
    mt = 1 - t;
    x = (mt * mt * mt * x0) + (3 * mt * mt * t * x1) + (3 * mt * t * t * x2) + (t * t * t * x3);
    bounds[0][j] = x;

    y = (mt * mt * mt * y0) + (3 * mt * mt * t * y1) + (3 * mt * t * t * y2) + (t * t * t * y3);
    bounds[1][j] = y;
    points[j] = {
      X: x,
      Y: y
    };
  }

  tvalues[jlen] = 0;
  tvalues[jlen + 1] = 1;
  points[jlen] = {
    X: x0,
    Y: y0
  };
  points[jlen + 1] = {
    X: x3,
    Y: y3
  };
  bounds[0][jlen] = x0;
  bounds[1][jlen] = y0;
  bounds[0][jlen + 1] = x3;
  bounds[1][jlen + 1] = y3;
  tvalues.length = bounds[0].length = bounds[1].length = points.length = jlen + 2;

  return {
    left: min.apply(null, bounds[0]),
    top: min.apply(null, bounds[1]),
    right: max.apply(null, bounds[0]),
    bottom: max.apply(null, bounds[1]),
    points: points, // local extremes
    tvalues: tvalues // t values of local extremes
  };
};

// Usage:
var bounds = getBoundsOfCurve(532,333,117,305,28,93,265,42);
console.log(JSON.stringify(bounds));
// Prints: {"left":135.77684049079755,"top":42,"right":532,"bottom":333,"points":[{"X":135.77684049079755,"Y":144.86387466397255},{"X":532,"Y":333},{"X":265,"Y":42}],"tvalues":[0.6365030674846626,0,1]}

CODE 2 (which fails in collinear cases):

I translated the code from http://processingjs.nihongoresources.com/bezierinfo/sketchsource.php?sketch=tightBoundsCubicBezier to Javascript. The code works fine in normal cases, but not in collinear cases where all points lie on the same line.

For reference, here is the Javascript code.

function computeCubicBaseValue(a,b,c,d,t) {
    var mt = 1-t;
    return mt*mt*mt*a + 3*mt*mt*t*b + 3*mt*t*t*c + t*t*t*d; 
}

function computeCubicFirstDerivativeRoots(a,b,c,d) {
    var ret = [-1,-1];
  var tl = -a+2*b-c;
  var tr = -Math.sqrt(-a*(c-d) + b*b - b*(c+d) +c*c);
  var dn = -a+3*b-3*c+d;
    if(dn!=0) { ret[0] = (tl+tr)/dn; ret[1] = (tl-tr)/dn; }
    return ret; 
}

function computeCubicBoundingBox(xa,ya,xb,yb,xc,yc,xd,yd)
{
    // find the zero point for x and y in the derivatives
  var minx = 9999;
  var maxx = -9999;
    if(xa<minx) { minx=xa; }
    if(xa>maxx) { maxx=xa; }
    if(xd<minx) { minx=xd; }
    if(xd>maxx) { maxx=xd; }
    var ts = computeCubicFirstDerivativeRoots(xa, xb, xc, xd);
    for(var i=0; i<ts.length;i++) {
      var t = ts[i];
        if(t>=0 && t<=1) {
          var x = computeCubicBaseValue(t, xa, xb, xc, xd);
          var y = computeCubicBaseValue(t, ya, yb, yc, yd);
            if(x<minx) { minx=x; }
            if(x>maxx) { maxx=x; }}}

  var miny = 9999;
  var maxy = -9999;
    if(ya<miny) { miny=ya; }
    if(ya>maxy) { maxy=ya; }
    if(yd<miny) { miny=yd; }
    if(yd>maxy) { maxy=yd; }
    ts = computeCubicFirstDerivativeRoots(ya, yb, yc, yd);
    for(i=0; i<ts.length;i++) {
      var t = ts[i];
        if(t>=0 && t<=1) {
          var x = computeCubicBaseValue(t, xa, xb, xc, xd);
          var y = computeCubicBaseValue(t, ya, yb, yc, yd);
            if(y<miny) { miny=y; }
            if(y>maxy) { maxy=y; }}}

    // bounding box corner coordinates
    var bbox = [minx,miny, maxx,miny, maxx,maxy, minx,maxy ];
    return bbox;
}

CODE 3 (works in most cases):

To handle also collinear cases, I found Raphael's solution, which is based on the same first derivative method as the CODE 2. I added also a return value dots, which has the extrema points, because always it's not enough to know bounding boxes min and max coordinates, but we want to know the exact extrema coordinates.

EDIT: found another bug. Fails eg. in 532,333,117,305,28,93,265,42 and also many other cases.

The code is here:

Array.max = function( array ){
  return Math.max.apply( Math, array );
};
Array.min = function( array ){
  return Math.min.apply( Math, array );
};

var findDotAtSegment = function (p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t) {
        var t1 = 1 - t;
        return {
            x: t1*t1*t1*p1x + t1*t1*3*t*c1x + t1*3*t*t * c2x + t*t*t * p2x,
            y: t1*t1*t1*p1y + t1*t1*3*t*c1y + t1*3*t*t * c2y + t*t*t * p2y
        };
};
var cubicBBox = function (p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y) {
        var a = (c2x - 2 * c1x + p1x) - (p2x - 2 * c2x + c1x),
            b = 2 * (c1x - p1x) - 2 * (c2x - c1x),
            c = p1x - c1x,
            t1 = (-b + Math.sqrt(b * b - 4 * a * c)) / 2 / a,
            t2 = (-b - Math.sqrt(b * b - 4 * a * c)) / 2 / a,
            y = [p1y, p2y],
            x = [p1x, p2x],
            dot, dots=[];
        Math.abs(t1) > "1e12" && (t1 = 0.5);
        Math.abs(t2) > "1e12" && (t2 = 0.5);
        if (t1 >= 0 && t1 <= 1) {
            dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t1);
            x.push(dot.x);
            y.push(dot.y);
            dots.push({X:dot.x, Y:dot.y});
        }
        if (t2 >= 0 && t2 <= 1) {
            dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t2);
            x.push(dot.x);
            y.push(dot.y);
            dots.push({X:dot.x, Y:dot.y});
        }
        a = (c2y - 2 * c1y + p1y) - (p2y - 2 * c2y + c1y);
        b = 2 * (c1y - p1y) - 2 * (c2y - c1y);
        c = p1y - c1y;
        t1 = (-b + Math.sqrt(b * b - 4 * a * c)) / 2 / a;
        t2 = (-b - Math.sqrt(b * b - 4 * a * c)) / 2 / a;
        Math.abs(t1) > "1e12" && (t1 = 0.5);
        Math.abs(t2) > "1e12" && (t2 = 0.5);
        if (t1 >= 0 && t1 <= 1) {
            dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t1);
            x.push(dot.x);
            y.push(dot.y);
            dots.push({X:dot.x, Y:dot.y});
        }
        if (t2 >= 0 && t2 <= 1) {
            dot = findDotAtSegment(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y, t2);
            x.push(dot.x);
            y.push(dot.y);
            dots.push({X:dot.x, Y:dot.y});
        }
        // remove duplicate dots
                var dots2 = [];
                var l = dots.length;
                for(var i=0; i<l; i++) {
                  for(var j=i+1; j<l; j++) {
                    if (dots[i].X === dots[j].X && dots[i].Y === dots[j].Y)
                      j = ++i;
                  }
                  dots2.push({X: dots[i].X, Y: dots[i].Y});
                }
        return {
        min: {x: Array.min(x), y: Array.min(y)},
        max: {x: Array.max(x), y: Array.max(y)},
        dots: dots2 // these are the extrema points
      };
    };

Best Answer

Related Solutions

Quadratic Bezier Curve: Calculate Tangent

An algorithm to find bounding box of closed bezier curves

Related Topic