24

デカルト軸の閉じた二次ベジエ曲線の境界ボックス (最大/最小ポイント) を見つけるアルゴリズムを探しています:

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

画像 http://www.imagechicken.com/uploads/1270586513022388700.jpg

注：上の画像は滑らかな曲線を示しています。それは滑らかではないかもしれません。(角があります)

4

8 に答える 8

27

Ivan Kuckir の DeCasteljauは強引ですが、多くの場合に機能します。問題は反復回数です。実際の形状と座標間の距離は、結果の精度に影響します。そして、十分に正確な答えを見つけるには、何十回も繰​​り返す必要があります。また、カーブに急カーブがあると失敗する場合があります。

優れたサイトhttp://processingjs.nihongoresources.com/bezierinfo/で説明されているように、より良い解決策は一次微分根を見つけることです。セクション曲線の端を見つけるを読んでください。

上記のリンクには、二次曲線と三次曲線の両方のアルゴリズムがあります。

質問者は二次曲線に興味があるため、この回答の残りの部分は無関係かもしれません。これは、3 次曲線の端点を計算するためのコードを提供するためです。

以下に 3 つの Javascript コードを示します。最初のコード (コード 1) は、私が使用することをお勧めします。

** コード 1 **

processingjs と Raphael のソリューションをテストした後、いくつかの制限やバグがあることがわかりました。さらに検索すると、Bonsai と、西尾浩和の Python スクリプトに基づくバウンディング ボックス関数が見つかりました。どちらにも、 を使用して二重等価性がテストされるという欠点があり==ます。これらを数値的に堅牢な比較に変更すると、スクリプトはすべての場合で 100% 正しく成功します。何千ものランダムなパスと、すべての共線ケースでスクリプトをテストし、すべて成功しました。

さまざまな 3 次曲線

ランダム 3 次曲線

共線 3 次曲線

コードは次のとおりです。通常、必要なのは左、右、上、下の値だけですが、場合によっては、ローカルの極値と対応する t 値の座標を知っていれば問題ありません。そこで、 と の 2 つの変数を追加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]}

コード 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;
}

コード 3 (ほとんどの場合に機能します):

コリニア ケースも処理するために、CODE 2 と同じ一次微分法に基づく Raphael のソリューションを見つけました。dots境界ボックスの最小値と最大値を知るだけでは常に十分ではないため、極値点を持つreturn value も追加しました。座標ですが、正確な極値座標を知りたいです。

編集：別のバグが見つかりました。失敗します。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
      };
    };
于 2013-01-20T21:51:27.330 に答える
7

まず、境界ボックスにすべてのエンドポイントを追加することから始めます。次に、すべてのベジエ要素を調べます。問題の式は次の式だと思います。

ウィキペディアの二次ベジエ

これから、X と Y の 2 つの式をそれぞれ抽出します。導関数 (ゼロクロッシング) を取得して、両方の極値をテストします。次に、対応するポイントをバウンディング ボックスにも追加します。

于 2010-04-06T20:07:05.753 に答える
7

De Casteljau アルゴリズムを使用して、高次の曲線を近似します。3次曲線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};
}
于 2012-11-14T12:38:46.050 に答える
5

ベジェ曲線の制御点は、曲線を囲む凸包を形成していると思います。軸に沿ったバウンディングボックスが必要な場合は、すべてのセグメントの各コントロールポイントの各（x、y）の最小値と最大値を見つける必要があると思います。

それはタイトな箱ではないかもしれないと思います。つまり、ボックスは必要以上に大きくなる可能性がありますが、計算は簡単で高速です。私はそれがあなたの要件に依存すると思います。

于 2010-04-06T20:49:12.313 に答える
4

受け入れられた答えは問題ないと思いますが、これをやろうとしている他の人にもう少し説明を提供したかっただけです。

p1開始点、終了点p2、および「制御点」を持つ二次ベジエを考えてみましょうpc。この曲線には、次の 3 つのパラメトリック方程式があります。

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

いずれの場合も、t0 から 1 まで (両端を含む) で実行されます。

最初の 2 つは線形で、それぞれ fromp1とpcfromの線分を定義します。と の式を代入すると、3 番目は 2 次になります。これは、曲線上の点を実際に定義するものです。pcp2pa(t)pb(t)

実際には、これらの各方程式は、水平方向と垂直方向の 1 対の方程式です。パラメトリック カーブの優れた点は、x と y を互いに独立して処理できることです。方程式はまったく同じで、上記の方程式でxまたはyを置き換えるだけです。p

重要な点は、式 3 で定義された、特定の値 のからpa(t)までの線分が、対応する点 で曲線に接していることです。曲線の局所的な極値を見つけるには、接線が平らな場所 (つまり臨界点) のパラメーター値を見つける必要があります。垂直寸法では、接線に 0 の勾配を与えるようなの値を見つけます。水平寸法では、接線に無限の勾配 (つまり、垂直線) を与えるような を見つけます。いずれの場合も、t の値を方程式 1 (または 2、または 3) に戻すだけで、その極値の位置を取得できます。pb(t)tp(t)tya(t) = yb(t)txa(t) = xb(t)

言い換えると、曲線の垂直方向の極値を見つけるには、式 1 と 2 の y 成分だけを取り、それらを互いに等しく設定して を解きtます。これを方程式 1 の y 成分に戻して、その極値の y 値を取得します。曲線の完全な y 範囲を取得するには、この極端な y 値の最小値と 2 つの端点の y 成分を見つけ、同様に 3 つすべての最大値を見つけます。x について繰り返して、水平方向の範囲を取得します。

[0, 1]でtのみ実行されることに注意してください。したがって、この範囲外の値を取得した場合は、曲線に極値がないことを意味します (少なくとも 2 つのエンドポイントの間にはありません)。これには、 を解くときに 0 で除算する場合が含まれます。これは、t実行する前に確認する必要があるでしょう。

同じ考えを高次のベジエに適用できます。高次の方程式が増えるだけです。これは、曲線ごとにより多くの局所極値が存在する可能性があることも意味します。たとえば、3 次ベジエ (2 つの制御点) ではt、ローカル極値を見つけるための解は 2 次方程式であるため、0、1、または 2 の値を取得できます (分母が 0 であるか、負の 2 乗であるかを確認することを忘れないでください)。どちらも、その次元には極値がないことを示しています)。範囲を見つけるには、すべての極値の最小値/最大値と 2 つの端点を見つける必要があります。

于 2013-04-09T17:08:31.350 に答える