Berechnen der Bounding Box der kubischen Bezierkurve

Question

Ich versuche einen Algorithmus zu finden, um die Bounding Box einer gegebenen kubischen Bezierkurve zu berechnen. Die Kurve befindet sich im 3D-Raum.

Gibt es einen mathematischen Weg, dies zu tun, außer den Probenahmestellen auf der Kurve und Berechnen den Begrenzungsrahmen dieser Punkte?

Answer 1

Das meiste davon ist in An algorithm to find bounding box of closed bezier curves? adressiert, außer hier haben wir kubische Beziers und da waren sie mit quadratischen Bezier-Kurven beschäftigt.

Im Wesentlichen müssen Sie die Derivate von jedem der Koordinatenfunktionen zu übernehmen. Wenn die x-Koordinate gegeben ist durch

differenzierend in Bezug auf t.

dx/dt = 3 (B - A) (1-t)^2 + 6 (C - B) (1-t) t + 3 (D - C) t^2 
     = [3 (D - C) - 6 (C - B) + 3 (B - A)] t^2 
     + [ -6 (B - A) - 6 (C - B)] t 
     + 3 (B - A) 
     = (3 D - 9 C + 9 B - 3 A) t^2 + (6 A - 12 B + 6 C) t + 3 (B - A) 

dies ist eine quadratische, die wir bei a t^2 + b t + c schreiben kann. Wir wollen dx/dt = 0 lösen, die Sie tun können, die quadratische Formel

- b +/- sqrt(b^2-4 a c) 
----------------------- 
     2 a 

Lösung dieser wird entweder gibt zwei Lösungen t0, t1 sagen, keine Lösungen oder in seltenen Fällen nur eine Lösung. Wir haben nur Interesse an Lösungen mit 0 < = t < = 1. Sie haben maximal vier Kandidatenpunkte, die zwei Endpunkte und die beiden Lösungen. Es ist eine einfache Frage zu finden, welche von diesen die extremen Punkte geben.

Sie können den gleichen Vorgang für jede Koordinate wiederholen und dann den Begrenzungsrahmen bekommen.

ich dies für den 2D-Fall in einer js Geige http://jsfiddle.net/SalixAlba/QQnvm/4/

Answer 2

Finden den Begrenzungsrahmen einer kubischen Bezier-Kurve (oder auch B-Spline-Kurve von jedem Grad) gesetzt haben wird in der Regel von der Suche nach dem Begrenzungsrahmen getan des Steuerpolygons der Kurve. Da die Kurve immer durch ihr Kontrollpolygon begrenzt ist, wird die über das Kontrollpolygon erhaltene Bounding Box garantiert die Kurve umschließen. Sie können auch Knoten in die Kurve einfügen und das Steuerpolygon näher an die Kurve bringen. So wird der allgemeine Algorithmus so gehen:

1) Finden Sie den Begrenzungsrahmen (bezeichnet als BBox1) der aktuellen B-Spline-Kurve von seinem Steuer Polygon.
2) Knoten in den mittleren Parameter jedes Bézier-Segments in der B-Spline-Kurve einfügen.
3) Finden Sie die Bounding Box (als BBox2 bezeichnet) der neuen B-Spline-Kurve.
4) Vergleichen Sie BBox2 gegen BBox1. Wenn BBox2 ungefähr die gleiche Größe wie BBox1 hat, sind wir fertig. Wenn BBox2 wesentlich kleiner als BBox1 ist, wiederholen Sie die Schritte 2 bis 4 bis zur Konvergenz.

Answer 3

dieser Artikel die Details erklären und hat auch eine Live-Demo html5:
Calculating/Computing the Bounding Box of Cubic Bezier

ich eine Javascript in Snap.svg festgestellt, dass zu berechnen: here
die bezierBBox und curveDim Funktionen zu sehen.

Ich schreibe eine JavaScript-Funktion um.

//(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) { 
      if (Math.abs(b2ac) < 1e-12) { 
       t = -b/(2 * a); 
       if (0 < t && t < 1) { 
        tvalues.push(t); 
       } 
      } 
      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)} 
    }; 
}