An algorithm to find bounding box of closed bezier curves?
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)
Answer
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:
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
};
};