algorithm - 找到封闭贝塞尔曲线边界框的算法？

Question

我正在寻找一种算法来找到笛卡尔轴中封闭二次贝塞尔曲线的边界框（最大/最小点）：

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

图片 http://www.imagechicken.com/uploads/1270586513022388700.jpg

注意：上图显示平滑曲线。它可能并不顺利。（有角）

Answer 1

Ivan Kuckir 的 DeCasteljau是一种蛮力，但在许多情况下都有效。它的问题是迭代次数。实际形状和坐标之间的距离会影响结果的精度。而要找到一个足够精确的答案，你必须迭代数十次，可能更多。如果曲线出现急转弯，它可能会失败。

更好的解决方案是找到一阶导数根，如优秀网站http://processingjs.nihongoresources.com/bezierinfo/中所述。请阅读寻找曲线末端部分。

上面的链接具有二次曲线和三次曲线的算法。

提问者对二次曲线感兴趣，所以这个答案的其余部分可能无关紧要，因为我提供了计算三次曲线极值的代码。

下面是三个 Javascript 代码，其中第一个（CODE 1）是我建议使用的。

---

** 代码 1 **

在测试了 processingjs 和 Raphael 的解决方案后，我发现他们有一些限制和/或错误。然后更多搜索，发现 Bonsai是基于 NISHIO Hirokazu 的 Python 脚本的边界框功能。两者都有一个缺点，即使用==. 当我将这些更改为数值稳健的比较时，脚本在所有情况下都 100% 成功。我用数千个随机路径以及所有共线案例测试了脚本，并且都成功了：

各种三次曲线

随机三次曲线

共线三次曲线

代码如下。通常left、right、top和bottom值都是需要的，但在某些情况下，知道局部极值点的坐标和相应的t值就可以了。所以我在那里添加了两个变量：tvalues和points。删除有关它们的代码，您将拥有快速稳定的边界框计算功能。

// 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（在共线情况下失败）：

我将代码从http://processingjs.nihongoresources.com/bezierinfo/sketchsource.php?sketch=tightBoundsCubicBezier翻译成 Javascript。该代码在正常情况下工作正常，但在所有点都位于同一条线上的共线情况下则不行。

作为参考，这里是 Javascript 代码。

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（在大多数情况下有效）：

为了处理共线的情况，我找到了 Raphael 的解决方案，它基于与 CODE 2 相同的一阶导数方法。我还添加了一个 return value dots，它具有极值点，因为知道边界框 min 和 max 总是不够的坐标，但我们想知道确切的极值坐标。

编辑：发现另一个错误。失败例如。在 532,333,117,305,28,93,265,42 以及许多其他情况下。

代码在这里：

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
      };
    };

Answer 2

好吧，我会说您首先将所有端点添加到您的边界框。然后，您遍历所有贝塞尔元素。我假设有问题的公式是这个：

从中，分别提取 X 和 Y 的两个公式。通过求导数（零交叉）测试两者的极值。然后将相应的点也添加到您的边界框。

Answer 3

使用 De Casteljau 算法逼近高阶曲线。这是三次曲线的工作原理 http://jsfiddle.net/4VCVX/25/

function getCurveBounds(ax, ay, bx, by, cx, cy, dx, dy)
{
        var px, py, qx, qy, rx, ry, sx, sy, tx, ty,
            tobx, toby, tocx, tocy, todx, tody, toqx, toqy, 
            torx, tory, totx, toty;
        var x, y, minx, miny, maxx, maxy;

        minx = miny = Number.POSITIVE_INFINITY;
        maxx = maxy = Number.NEGATIVE_INFINITY;

        tobx = bx - ax;  toby = by - ay;  // directions
        tocx = cx - bx;  tocy = cy - by;
        todx = dx - cx;  tody = dy - cy;
        var step = 1/40;      // precision
        for(var d=0; d<1.001; d+=step)
        {
            px = ax +d*tobx;  py = ay +d*toby;
            qx = bx +d*tocx;  qy = by +d*tocy;
            rx = cx +d*todx;  ry = cy +d*tody;
            toqx = qx - px;      toqy = qy - py;
            torx = rx - qx;      tory = ry - qy;

            sx = px +d*toqx;  sy = py +d*toqy;
            tx = qx +d*torx;  ty = qy +d*tory;
            totx = tx - sx;   toty = ty - sy;

            x = sx + d*totx;  y = sy + d*toty;                
            minx = Math.min(minx, x); miny = Math.min(miny, y);
            maxx = Math.max(maxx, x); maxy = Math.max(maxy, y);
        }        
        return {x:minx, y:miny, width:maxx-minx, height:maxy-miny};
}

Answer 4

我相信贝塞尔曲线的控制点形成了一个包围曲线的凸包。如果您只想要一个轴对齐的边界框，我认为您需要为所有段的每个控制点找到每个 (x, y) 的最小值和最大值。

我想这可能不是一个紧凑的盒子。也就是说，盒子可能比它需要的稍大，但计算起来既简单又快速。我想这取决于你的要求。

Answer 5

我认为接受的答案很好，但只是想为其他尝试这样做的人提供更多解释。

考虑一个具有起点p1、终点p2和“控制点”的二次贝塞尔曲线pc。该曲线具有三个参数方程：

1. pa(t) = p1 + t(pc-p1)
2. pb(t) = pc + t(p2-pc)
3. p(t) = pa(t) + t*(pb(t) - pa(t))

在所有情况下，t从 0 运行到 1，包括 0 和 1。

p1前两个是线性的，分别定义从topc和 from pcto 的线段p2。第三个是二次的，一旦你将表达式替换为pa(t)and pb(t); 这是实际定义曲线上的点的那个。

实际上，这些方程中的每一个都是一对方程，一个用于水平维度，一个用于垂直维度。参数曲线的好处是 x 和 y 可以相互独立地处理。方程完全一样，只是在上面的方程中替换x或y代替。p

重要的一点是等式 3 中定义的线段，从pa(t)到pb(t)的特定值与对应点处的t曲线相切p(t)。要找到曲线的局部极值，需要找到切线平坦处（即临界点）的参数值。对于垂直尺寸，您想找到t这样的值ya(t) = yb(t)，它使切线的斜率为 0。对于水平尺寸，找到t这样的xa(t) = xb(t)，它使切线具有无限斜率（即，一条垂直线）。在每种情况下，您只需将 t 的值插入方程式 1（或 2，甚至 3）即可获得该极值的位置。

换句话说，要找到曲线的垂直极值，只需取方程 1 和 2 的 y 分量，使它们彼此相等并求解t; 将其插入等式 1 的 y 分量，以获得该极值的 y 值。要获得曲线的完整 y 范围，请找到该 y 极端值的最小值和两个端点的 y 分量，并同样找到所有三个中的最大值。重复 x 以获得水平限制。

请记住，它t仅在 [0, 1] 中运行，因此如果您得到的值超出此范围，则意味着曲线上没有局部极值（至少在两个端点之间没有）。这包括在求解 时最终除以零的情况，t您可能需要在执行此操作之前进行检查。

同样的想法可以应用于高阶贝塞尔曲线，只是更高阶的方程更多，这也意味着每条曲线可能有更多的局部极值。例如，在三次贝塞尔曲线（两个控制点）上，求解t局部极值是一个二次方程，因此您可以获得 0、1 或 2 个值（请记住检查 0 分母和负平方 -根，这两个都表明该维度没有局部极值）。要找到范围，您只需要找到所有局部极值的最小值/最大值，以及两个端点。

Answer 6

我在计算三次贝塞尔曲线的边界框中回答了这个问题

这篇文章解释了细节，还有一个现场 html5 演示：
计算/计算三次贝塞尔的边界框

我在 Snap.svg 中找到了一个 javascript 来计算：这里
查看 bezierBBox 和 curveDim 函数。

我重写了一个javascript函数。

//(x0,y0) is start point; (x1,y1),(x2,y2) is control points; (x3,y3) is end point.
function bezierMinMax(x0, y0, x1, y1, x2, y2, x3, y3) {
    var tvalues = [], xvalues = [], yvalues = [],
        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 (Math.abs(a) < 1e-12) {
            if (Math.abs(b) < 1e-12) {
                continue;
            }
            t = -c / b;
            if (0 < t && t < 1) {
                tvalues.push(t);
            }
            continue;
        }
        b2ac = b * b - 4 * c * a;
        if (b2ac < 0) {
            continue;
        }
        sqrtb2ac = Math.sqrt(b2ac);
        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 j = tvalues.length, mt;
    while (j--) {
        t = tvalues[j];
        mt = 1 - t;
        xvalues[j] = (mt * mt * mt * x0) + (3 * mt * mt * t * x1) + (3 * mt * t * t * x2) + (t * t * t * x3);
        yvalues[j] = (mt * mt * mt * y0) + (3 * mt * mt * t * y1) + (3 * mt * t * t * y2) + (t * t * t * y3);
    }

    xvalues.push(x0,x3);
    yvalues.push(y0,y3);

    return {
        min: {x: Math.min.apply(0, xvalues), y: Math.min.apply(0, yvalues)},
        max: {x: Math.max.apply(0, xvalues), y: Math.max.apply(0, yvalues)}
    };
}

Answer 7

Timo-s 第一个适应 Objective-C 的变体

CGPoint CubicBezierPointAt(CGPoint p1, CGPoint p2, CGPoint p3, CGPoint p4, CGFloat t) {

   CGFloat x = CubicBezier(p1.x, p2.x, p3.x, p4.x, t);
   CGFloat y = CubicBezier(p1.y, p2.y, p3.y, p4.y, t);

   return CGPointMake(x, y);
}

// array containing TopLeft and BottomRight points for curve`s enclosing bounds
NSArray* CubicBezierExtremums(CGPoint p1, CGPoint p2, CGPoint p3, CGPoint p4) {

   CGFloat a, b, c, t, t1, t2, b2ac, sqrtb2ac;
   NSMutableArray *tValues = [NSMutableArray new];

   for (int i = 0; i < 2; i++) {
      if (i == 0) {
         a = 3 * (-p1.x + 3 * p2.x - 3 * p3.x + p4.x);
         b = 6 * (p1.x - 2 * p2.x +  p3.x);
         c = 3 * (p2.x - p1.x);
      }
      else {
         a = 3 * (-p1.y + 3 * p2.y - 3 * p3.y + p4.y);
         b = 6 * (p1.y - 2 * p2.y +  p3.y);
         c = 3 * (p2.y - p1.y);
      }

      if(ABS(a) < CGFLOAT_MIN) {// Numerical robustness
         if (ABS(b) < CGFLOAT_MIN) {// Numerical robustness
            continue;
         }

         t = -c / b;

         if (t > 0 && t < 1) {
            [tValues addObject:[NSNumber numberWithDouble:t]];
         }
         continue;
      }

      b2ac = pow(b, 2) - 4 * c * a;

      if (b2ac < 0) {
         continue;
      }

      sqrtb2ac = sqrt(b2ac);

      t1 = (-b + sqrtb2ac) / (2 * a);

      if (t1 > 0.0 && t1 < 1.0) {
         [tValues addObject:[NSNumber numberWithDouble:t1]];
      }

      t2 = (-b - sqrtb2ac) / (2 * a);

      if (t2 > 0.0 && t2 < 1.0) {
         [tValues addObject:[NSNumber numberWithDouble:t2]];
      }
   }

   int j = (int)tValues.count;

   CGFloat x = 0;
   CGFloat y = 0;
   NSMutableArray *xValues = [NSMutableArray new];
   NSMutableArray *yValues = [NSMutableArray new];

   while (j--) {
      t = [[tValues objectAtIndex:j] doubleValue];
      x = CubicBezier(p1.x, p2.x, p3.x, p4.x, t);
      y = CubicBezier(p1.y, p2.y, p3.y, p4.y, t);
      [xValues addObject:[NSNumber numberWithDouble:x]];
      [yValues addObject:[NSNumber numberWithDouble:y]];
   }

   [xValues addObject:[NSNumber numberWithDouble:p1.x]];
   [xValues addObject:[NSNumber numberWithDouble:p4.x]];
   [yValues addObject:[NSNumber numberWithDouble:p1.y]];
   [yValues addObject:[NSNumber numberWithDouble:p4.y]];

   //find minX, minY, maxX, maxY
   CGFloat minX = [[xValues valueForKeyPath:@"@min.self"] doubleValue];
   CGFloat minY = [[yValues valueForKeyPath:@"@min.self"] doubleValue];
   CGFloat maxX = [[xValues valueForKeyPath:@"@max.self"] doubleValue];
   CGFloat maxY = [[yValues valueForKeyPath:@"@max.self"] doubleValue];

   CGPoint origin = CGPointMake(minX, minY);
   CGPoint bottomRight = CGPointMake(maxX, maxY);

   NSArray *toReturn = [NSArray arrayWithObjects:
                        [NSValue valueWithCGPoint:origin],
                        [NSValue valueWithCGPoint:bottomRight],
                        nil];

   return toReturn;
}

Answer 8

Timo 的 CODE 2 答案有一个小错误：函数t中的参数computeCubicBaseValue应该是最后一个。尽管如此，干得好，像魅力一样工作；）

C# 中的解决方案：

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

double[] computeCubicFirstDerivativeRoots(double a, double b, double c, double d)
{
    var ret = new double[2] { -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;
}

public double[] ComputeCubicBoundingBox(Point start, Point firstControl, Point secondControl, Point end)
{
    double xa, ya, xb, yb, xc, yc, xd, yd;
    xa = start.X;
    ya = start.Y;
    xb = firstControl.X;
    yb = firstControl.Y;
    xc = secondControl.X;
    yc = secondControl.Y;
    xd = end.X;
    yd = end.Y;
    // find the zero point for x and y in the derivatives
    double minx = Double.MaxValue;
    double maxx = Double.MinValue;
    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(xa, xb, xc, xd,t);
            var y = computeCubicBaseValue(ya, yb, yc, yd,t);
            if (x < minx) { minx = x; }
            if (x > maxx) { maxx = x; }
        }
    }

    double miny = Double.MaxValue;
    double maxy = Double.MinValue;
    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 (var i = 0; i < ts.Length; i++)
    {
        var t = ts[i];
        if (t >= 0 && t <= 1)
        {
            var x = computeCubicBaseValue(xa, xb, xc, xd,t);
            var y = computeCubicBaseValue(ya, yb, yc, yd,t);
            if (y < miny) { miny = y; }
            if (y > maxy) { maxy = y; }
        }
    }

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