Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

An algorithm to find bounding box of closed bezier curves?

Tags:

I'm looking for an algorithm to find bounding box (max/min points) of a closed quadratic bezier curve in Cartesian axis:

input: C (a closed bezier curve) output: A B C D points 

Image http://www.imagechicken.com/uploads/1270586513022388700.jpg

Note: above image shows a smooth curve. it could be not smooth. (have corners)

like image 847
sorush-r Avatar asked Apr 06 '10 19:04

sorush-r


People also ask

What is a Bezier curve algorithm?

A Bezier curve is a mathematically defined curve used in two-dimensional graphic applications. The curve is defined by four points: the initial position and the terminating position (which are called "anchors") and two separate middle points (which are called "handles").

Can Bézier curves be closed?

A single bezier spline segment, whether it's cubic or quadratic or quartic, can't represent that kind of closed shape. Yet multiple segments can. So you typically don't want to modify your multi-segment curve drawing function, per se, but rather the control points you feed into it.

How do you find the Bezier curve?

Bézier Curves Are Tangent to Their First and Last Legs Letting u = 0 and u = 1 gives C'(0) = n (P1 - P0) and C'(1) = n (Pn - Pn-1) The first means that the tangent vector at u = 0 is in the direction of P1 - P0 multiplied by n. Therefore, the first leg in the indicated direction is tangent to the Bézier curve.

What are Bézier curves what are its types?

The term Bézier curve actually refers to a family of similar curves. SkiaSharp supports three types of Bézier curves, called the cubic, the quadratic, and the conic. The conic is also known as the rational quadratic.


2 Answers

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       };     }; 
like image 96
Timo Kähkönen Avatar answered Oct 14 '22 23:10

Timo Kähkönen


Well, I would say you start by adding all endpoints to your bounding box. Then, you go through all the bezier elements. I assume the formula in question is this one:

Quadratic Bezier from Wikipedia

From this, extract two formulas for X and Y, respectively. Test both for extrema by taking the derivative (zero crossings). Then add the corresponding points to your bounding box as well.

like image 32
ypnos Avatar answered Oct 15 '22 01:10

ypnos