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

Question

我正在寻找一种算法来找到笛卡尔轴上闭合二次贝塞尔曲线的边界框(最大/最小点):

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

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

注意:上图为平滑曲线。它可能不顺利。 (有角)

Answer 1

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

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

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

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

下面是三个 Javascript 代码，我建议使用第一个(代码 1)。

---

** 代码 1 **

在测试 processingjs 和 Raphael 的解决方案后，我发现它们有一些限制和/或错误。然后更多的搜索，找到了盆景，它是bounding box function ，它基于 NISHIO Hirokazu 的 Python 脚本。两者都有一个缺点，即使用 == 测试双重相等性。当我将这些更改为数字稳健比较时，脚本在所有情况下都 100% 成功。我用数以千计的随机路径和所有共线案例测试了脚本，并且都成功了:

Various cubic curves

Random cubic curves

Collinear cubic curves

代码如下。通常左、右、上、下值都是需要的，但在某些情况下，知道局部极值点的坐标和对应的 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 相同的一阶导数方法。我还添加了一个返回值 dots，它具有极值点，因为总是知道边界框的最小和最大坐标是不够的，但我们想知道确切的极值坐标。

编辑:发现另一个错误。失败例如。在 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
      };
    };