The Pro Hands The Pro Hands - 2 months ago 13
Javascript Question

How to get bezier curve size in HTML5 canvas with cp2 point?

I want to get the rendered size (width/height) of a bézier curve in HTML5 canvas

context.bezierCurveTo(cp1x, cp1y, cp2x, cp2y, x, y);


with this code, for instance

// control points
var cp1x = 200,
cp1y = 150,
cp2x = 260,
cp2y = 10;

var x = 0,
y = 0;

// calculation
var curveWidth = cp1x > x ? cp1x - x : x - cp1x,
curveHeight = cp1y > y ? cp1y - y : y - cp1y;


However, the cp2 point can increase the curve distance (length, size). I.e., suppose cp2 point is the red point in this image and its x coordinate is bigger than cp1's x, which looks to be the end point of the bézier curve:

cp2 point

So, how can I consider the length of cp2 point in
curveWidth
and in
curveHeight
to be exact?

Answer

To get extent of a quadratic bezier

The points

var x1 = ?   // start
var y1 = ?
var x2 = ?  // control
var y2 = ?
var x3 = ?  // end
var y3 = ?

The extent

extent = {
    minx : null,
    miny : null,
    maxx : null,
    maxy : null,
}

The Math.

These equation apply for the x and y axis (thus two equations) For quadratic bezier

F(u) = a(1-u)^2+2b(1-u)u+cu^2 

which is more familiar in the form of a quadratic equation

Ax^2 + Bx + C = 0

so the bezier rearranged

F(u) =  (a-2b+c)u^2+2(-a+b)u+a 

We need the derivative so that becomes

2(a-2b+c)u-2a+2b

simplify divide common factor 2 to give

(a-2b+c)u + b - a = 0

separate out u

  b-a = (a-2b + c)u
 (b-a) / (a - 2b + c)  = u

Then algorithm optimised for the fact the (b-a) part of (a-2b-c)

function solveB2(a,b,c){
    var ba = b-a;
    return ba / (ba - (c-b));  // the position on the curve of the maxima
}

var ux = solveB2(x1,x2,x3);
var uy = solveB2(y1,y2,y3);

These two values are positions along the curve so we now just have to find the coordinates of these two points. We need a function that finds a point on a quadratic bezier

function findPoint(u,x1,y1,x2,y2,x3,y3){ // returns array with x, and y at u
    var xx1 = x1 + (x2 - x1) * u;
    var yy1 = y1 + (y2 - y1) * u;
    var xx2 = x2 + (x3 - x2) * u;
    var yy2 = y2 + (y3 - y2) * u;
    return [
        xx1 + (xx2 - xx1) * u,
        yy1 + (yy2 - yy1) * u
    ]
}

First check that they are on the curve and find the point at ux,uy

if(ux >= 0 && ux <= 1){
     var px = findPoint(ux,x1,y1,x2,y2,x3,y3);
}
if(uy >= 0 && uy <= 1){
     var py = findPoint(uy,x1,y1,x2,y2,x3,y3);
}

Now test against the extent

extent.minx = Math.min(x1,x3,px[0],py[0]);
extent.miny = Math.min(y1,y3,px[1],py[1]);
extent.maxx = Math.max(x1,x3,px[0],py[0]);
extent.maxy = Math.max(y1,y3,px[1],py[1]);

And you are done

extent has the coordinates of the box around the bezier. Top left (min) and bottom right (max)

You can also get the minimum bounding box if you rotate the bezier so that the start and end points fall on the x axis. Then do the above and the resulting rectangle is the minimum sized rectangle that can be placed around the bezier.

Cubics are much the same but just a lot more typing.

And a demo, just to make sure I got it all correct.

var canvas = document.createElement("canvas");
canvas.width = 800;
canvas.height = 400;
var ctx = canvas.getContext("2d");
document.body.appendChild(canvas);

var x1,y1,x2,y2,x3,y3;
var ux,uy,px,py;
var extent = {
    minx : null,
    miny : null,
    maxx : null,
    maxy : null,
}
function solveB2(a,b,c){
    var ba = b-a;
    return ba / (ba - (c-b));  // the position on the curve of the maxima
}

function findPoint(u,x1,y1,x2,y2,x3,y3){ // returns array with x, and y at u
    var xx1 = x1 + (x2 - x1) * u;
    var yy1 = y1 + (y2 - y1) * u;
    var xx2 = x2 + (x3 - x2) * u;
    var yy2 = y2 + (y3 - y2) * u;
    return [
        xx1 + (xx2 - xx1) * u,
        yy1 + (yy2 - yy1) * u
    ]
}

function update(time){
    ctx.clearRect(0,0,800,400);
    // create random bezier
    x1 = Math.cos(time / 1000) * 300 + 400;
    y1 = Math.sin(time / 2100) * 150 + 200;
    x2 = Math.cos((time + 3000) / 1200) * 300 + 400;
    y2 = Math.sin(time / 2300) * 150 + 200;
    x3 = Math.cos(time / 1400) * 300 + 400;
    y3 = Math.sin(time / 2500) * 150 + 200;
    
    // solve for bounds
    var ux = solveB2(x1,x2,x3);
    var uy = solveB2(y1,y2,y3);
    if(ux >= 0 && ux <= 1){
        px = findPoint(ux,x1,y1,x2,y2,x3,y3);
    }else{
        px = [x1,y1]; // a bit of a cheat but saves having to put in extra conditions
    }
    if(uy >= 0 && uy <= 1){
        py = findPoint(uy,x1,y1,x2,y2,x3,y3);
    }else{
        py = [x3,y3]; // a bit of a cheat but saves having to put in extra conditions
    }
    extent.minx = Math.min(x1,x3,px[0],py[0]);
    extent.miny = Math.min(y1,y3,px[1],py[1]);
    extent.maxx = Math.max(x1,x3,px[0],py[0]);
    extent.maxy = Math.max(y1,y3,px[1],py[1]);
  
    // draw the rectangle
    ctx.strokeStyle = "red";
    ctx.lineWidth = 2;
    ctx.strokeRect(extent.minx,extent.miny,extent.maxx-extent.minx,extent.maxy-extent.miny);
    ctx.fillStyle = "rgba(255,200,0,0.2)";
    ctx.fillRect(extent.minx,extent.miny,extent.maxx-extent.minx,extent.maxy-extent.miny);

   // show points
    ctx.fillStyle = "blue";
    ctx.fillRect(x1-3,y1-3,6,6);
    ctx.fillRect(x3-3,y3-3,6,6);
  
    ctx.fillStyle = "black";
    ctx.fillRect(px[0]-4,px[1]-4,8,8);
    ctx.fillRect(py[0]-4,py[1]-4,8,8);
    
  
    ctx.lineWidth = 3;
    ctx.strokeStyle = "black";
    ctx.beginPath();
    ctx.moveTo(x1,y1);
    ctx.quadraticCurveTo(x2,y2,x3,y3);
    ctx.stroke();

  
     // control point
     ctx.lineWidth = 1;
     ctx.strokeStyle = "#0a0";
     ctx.strokeRect(x2-3,y2-3,6,6);
     ctx.beginPath();
     ctx.moveTo(x1,y1);
     ctx.lineTo(x2,y2);
     ctx.lineTo(x3,y3);
     ctx.stroke();

  
    // do it all again
    requestAnimationFrame(update);
}
requestAnimationFrame(update);

UPDATE

While musing over the bezier I realised that I could remove a lot of code if I assumed that the bezier was normalised (the end points start at (0,0) and end at (1,1)) because the zeros can be removed and the ones simplified.

While changing the code I also realized that I had needlessly calculated the x and y for both the x and y extent coordinates. Giving 4 values while I only need 2.

The resulting code is much simpler. I remove the function solveB2 and findPoint as the calculations seam too trivial to bother with functions.

To find the x and y maxima from quadratic bezier defined with x1, y1, x2, y2, x3, y3

// solve quadratic for bounds by normalizing equation 
var brx = x3 - x1;  // get x range
var bx = x2 - x1;   // get x control point offset
var x = bx / brx;   // normalise control point which is used to check if maxima is in range
// do the same for the y points
var bry = y3 - y1;
var by = y2 - y1
var y = by / bry;

var px = [x1,y1]; // set defaults in case maximas outside range

if(x < 0 || x > 1){  // check if x maxima is on the curve
   px[0] = bx * bx / (2 * bx - brx) + x1; // get the x maxima
}

if(y < 0 || y > 1){  // same as x
    px[1] = by * by / (2 * by - bry) + y1;
}

// now only need to check the x and y maxima not the coordinates of the maxima
extent.minx = Math.min(x1,x3,px[0]);
extent.miny = Math.min(y1,y3,px[1]);
extent.maxx = Math.max(x1,x3,px[0]);
extent.maxy = Math.max(y1,y3,px[1]);

And the example code which has far better performance but unlike the previous demo this version does not calculate the actual coordinates of the x and y maximas.

var canvas = document.createElement("canvas");
canvas.width = 800;
canvas.height = 400;
var ctx = canvas.getContext("2d");
document.body.appendChild(canvas);

var x1,y1,x2,y2,x3,y3;
var ux,uy,px,py;
var extent = {
    minx : null,
    miny : null,
    maxx : null,
    maxy : null,
}

function update(time){
    ctx.clearRect(0,0,800,400);
    // create random bezier
    x1 = Math.cos(time / 1000) * 300 + 400;
    y1 = Math.sin(time / 2100) * 150 + 200;
    x2 = Math.cos((time + 3000) / 1200) * 300 + 400;
    y2 = Math.sin(time / 2300) * 150 + 200;
    x3 = Math.cos(time / 1400) * 300 + 400;
    y3 = Math.sin(time / 2500) * 150 + 200;
    
    // solve quadratic for bounds by normalizing equation 
    var brx = x3 - x1;  // get x range
    var bx = x2 - x1;   // get x control point offset
    var x = bx / brx;   // normalise control point which is used to check if maxima is in range
    // do the same for the y points
    var bry = y3 - y1;
    var by = y2 - y1
    var y = by / bry;

    var px = [x1,y1]; // set defaults in case maximas outside range

    if(x < 0 || x > 1){  // check if x maxima is on the curve
       px[0] = bx * bx / (2 * bx - brx) + x1; // get the x maxima
    }
    if(y < 0 || y > 1){  // same as x
        px[1] = by * by / (2 * by - bry) + y1;
    }

    // now only need to check the x and y maxima not the coordinates of the maxima
    extent.minx = Math.min(x1,x3,px[0]);
    extent.miny = Math.min(y1,y3,px[1]);
    extent.maxx = Math.max(x1,x3,px[0]);
    extent.maxy = Math.max(y1,y3,px[1]);
  
    // draw the rectangle
    ctx.strokeStyle = "red";
    ctx.lineWidth = 2;
    ctx.strokeRect(extent.minx,extent.miny,extent.maxx-extent.minx,extent.maxy-extent.miny);
    ctx.fillStyle = "rgba(255,200,0,0.2)";
    ctx.fillRect(extent.minx,extent.miny,extent.maxx-extent.minx,extent.maxy-extent.miny);

   // show points
    ctx.fillStyle = "blue";
    ctx.fillRect(x1-3,y1-3,6,6);
    ctx.fillRect(x3-3,y3-3,6,6);
  
    ctx.fillStyle = "black";
    ctx.fillRect(px[0]-4,px[1]-4,8,8);
    
  
    ctx.lineWidth = 3;
    ctx.strokeStyle = "black";
    ctx.beginPath();
    ctx.moveTo(x1,y1);
    ctx.quadraticCurveTo(x2,y2,x3,y3);
    ctx.stroke();

  
     // control point
     ctx.lineWidth = 1;
     ctx.strokeStyle = "#0a0";
     ctx.strokeRect(x2-3,y2-3,6,6);
     ctx.beginPath();
     ctx.moveTo(x1,y1);
     ctx.lineTo(x2,y2);
     ctx.lineTo(x3,y3);
     ctx.stroke();
    // do it all again
    requestAnimationFrame(update);
}
requestAnimationFrame(update);

Comments