計算立方貝塞爾長度的廉價方法

Question

立方貝塞爾長度爲 的解析解似乎並不存在，但這並不意味着編碼廉價解決方案的 不存在。便宜我的意思是在50-100納秒（或更少）的範圍內。

有人知道這樣的事嗎？也許在兩個類別：

1）少1％的錯誤，但更慢的代碼。 2）更多的錯誤，如20％但更快？

我通過谷歌掃描了一下，但它不 找到任何看起來像一個不錯的解決方案。只有像N線段 劃分的東西並且求和N sqrt - 對於更高精度而言太慢了， 並且對於2或3段可能太不準確。

還有什麼更好的嗎？

Answer 1

最簡單的算法：展平曲線和歐幾里得距離。只要你想要一個近似的弧長，這個解決方案既快又便宜。考慮到你的曲線的座標LUT--你談論的是速度，所以我假設你使用這些座標，並且不要經常重新計算座標 - 這對於使用計數器的循環很簡單。在通用代碼，具有dist函數計算兩個點之間的歐氏距離：

var arclength = 0, 
    last=LUT.length-1, 
    i; 
for (i=0; i<last; i++) { 
    arclength += dist(LUT[i], LUT[i+1]); 
} 

DONE。 arclength現在是基於您可以根據LUT在曲線中形成的最大片段數的近似弧長。需要更快的速度和更大的潛在錯誤？控制段數。

var arclength = 0, 
    segCount = ..., 
    last=LUT.length-2, 
    step = last/segCount, 
    s, i; 
for (s=0; s<=segCount; s++) { 
    i = (s*step/last)|0; 
    arclength += dist(LUT[i], LUT[i+1]); 
} 

這幾乎是最簡單的算法，仍然可以生成值甚至接近真正的弧長。對於更好的事情，你將不得不使用更昂貴的數值方法（如Legendre-Gauss正交技術）。

如果您想知道爲什麼，請點擊「Bézier曲線入門」的the arc length section。

Answer 2

另一種選擇是將弧長估計爲弦和控制網之間的平均值。實踐中：

Bezier bezier = Bezier (p0, p1, p2, p3); 

chord = (p3-p0).Length; 
cont_net = (p0 - p1).Length + (p2 - p1).Length + (p3 - p2).Length; 

app_arc_length = (cont_net + chord)/2; 

然後，您可以遞歸地將樣條線段分成兩段，並計算到收斂的弧長。我測試了自己，實際上它收斂得非常快。我從這個forum得到了這個想法。

Answer 3

首先你應該瞭解Bezier中的算法使用，當我編寫一個由c＃編寫的程序時，我使用了很多圖形材料，我使用了bezier，很多時候我不得不在bezier中找到一個座標點，在第一眼看來是不可能的。所以我做的事情是在我的項目中的服裝數學課上寫立方貝塞爾函數。所以我會先與你分享代碼。

//--------------- My Costum Power Method ------------------\\ 

public static float FloatPowerX(float number, int power) 
     { 
      float temp = number; 
      for (int i = 0; i < power - 1; i++) 
      { 
       temp *= number; 
      } 
      return temp; 
     } 

    //--------------- Bezier Drawer Code Bellow ------------------\\ 

public static void CubicBezierDrawer(Graphics graphics, Pen pen, float[] startPointPixel, float[] firstControlPointPixel 
       , float[] secondControlPointPixel, float[] endPointPixel) 
     { 
      float[] px = new float[1111], py = new float[1111]; 
      float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0], secondControlPointPixel[0], endPointPixel[0] }; 
      float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1], secondControlPointPixel[1], endPointPixel[1] }; 
     int i = 0; 

     for (float t = 0; t <= 1F; t += 0.001F) 
     { 
      px[i] = FloatPowerX((1F - t), 3) * x[0] + 3 * t * FloatPowerX((1F - t), 2) * x[1] + 3 * FloatPowerX(t, 2) * (1F - t) * x[2] + FloatPowerX(t, 3) * x[3]; 
      py[i] = FloatPowerX((1F - t), 3) * y[0] + 3 * t * FloatPowerX((1F - t), 2) * y[1] + 3 * FloatPowerX(t, 2) * (1F - t) * y[2] + FloatPowerX(t, 3) * y[3]; 
      graphics.DrawLine(pen, px[i - 1], py[i - 1], px[i], py[i]); 
      i++; 
     } 
    } 

正如你看到的上面，這是方式的貝塞爾函數工作，它得出同樣的貝塞爾微軟貝塞爾函數做（我已經測試）。您可以通過增加數組大小和計數器大小，或者繪製橢圓而不是行& ...來使其更加準確。所有這些都取決於您的需求和您需要的準確度水平......。

回到主要目標，問題是如何計算長度？

好的答案是我們有噸的點，他們每個人都有一個x座標和y座標，記得我們三角形&尤其是一個RightTriabgle形狀。所以如果我們有點p1 & p2，我們可以計算它們作爲RightTriangle Chord的距離。正如我們在學校的數學課上所記得的那樣，在ABC Triangle類型的RightTriangle中，和絃長度是 - > Sqrt（Angle's FrontCostalLenght^2 + Angle's SideCostalLeghth^2）;

並且在所有點之間存在這種關係，我們計算當前點和當前點之前的最後一點之間的距離（exmp p [i - 1] & p [i]）並將它們的總和存儲在變量中。讓顯示它的代碼波紋管

//--------------- My Costum Power Method ------------------\\ 

public static float FloatPower2(float number) 
     { 
      return number * number; 
     } 

//--------------- My Bezier Lenght Calculator Method ------------------\\ 

public static float CubicBezierLenghtCalculator(float[] startPointPixel 
      , float[] firstControlPointPixel, float[] secondControlPointPixel, float[] endPointPixel) 
     { 
      float[] tmp = new float[2]; 
      float lenght = 0; 
      float[] px = new float[1111], py = new float[1111]; 

      float[] x = new float[4] { startPointPixel[0], firstControlPointPixel[0] 
       , secondControlPointPixel[0], endPointPixel[0] }; 

      float[] y = new float[4] { startPointPixel[1], firstControlPointPixel[1] 
       , secondControlPointPixel[1], endPointPixel[1] }; 

      int i = 0; 

      for (float t = 0; t <= 1.0; t += 0.001F) 
      { 
       px[i] = FloatPowerX((1.0F - t), 3) * x[0] + 3 * t * FloatPowerX((1.0F - t), 2) * x[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * x[2] + FloatPowerX(t, 3) * x[3]; 
       py[i] = FloatPowerX((1.0F - t), 3) * y[0] + 3 * t * FloatPowerX((1.0F - t), 2) * y[1] + 3F * FloatPowerX(t, 2) * (1.0F - t) * y[2] + FloatPowerX(t, 3) * y[3]; 
       if (i > 0) 
       { 
        tmp[0] = Math.Abs(px[i - 1] - px[i]);// calculating costal lenght 
        tmp[1] = Math.Abs(py[i - 1] - py[i]);// calculating costal lenght 
        lenght += (float)Math.Sqrt(FloatPower2(tmp[0]) + FloatPower2(tmp[1]));// calculating the lenght of current RightTriangle Chord & add it each time to variable 
       } 
       i++; 
      } 
      return lenght; 
     } 

如果你希望有更快的計算只需要降低PX & PY陣列lenght和100b計數。

我們還可以通過將px和py減少到數組長度1來減少內存需求，或者創建一個簡單的雙變量，但是因爲條件的情況而導致增大我們的大O我沒有這樣做。

希望它對你有所幫助。如果有另一個問題就問。最好的問候，海達爾 - 伊朗伊斯蘭共和國。

Answer 4

我找出了3點貝塞爾長度的封閉形式表達式（下圖）。我沒有試圖找出一個封閉的表格4點以上。這很可能是難以或複雜的代表和處理。然而，使用arc length formula進行集成，諸如Runge-Kutta積分算法的數值近似技術可以很好地工作。

這裏是一些3點貝塞爾弧長的Java代碼，點數爲a,b和c。

v.x = 2*(b.x - a.x); 
    v.y = 2*(b.y - a.y); 
    w.x = c.x - 2*b.x + a.x; 
    w.y = c.y - 2*b.y + a.y; 

    uu = 4*(w.x*w.x + w.y*w.y); 

    if(uu < 0.00001) 
    { 
     return (float) Math.sqrt((c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y)); 
    } 

    vv = 4*(v.x*w.x + v.y*w.y); 
    ww = v.x*v.x + v.y*v.y; 

    t1 = (float) (2*Math.sqrt(uu*(uu + vv + ww))); 
    t2 = 2*uu+vv; 
    t3 = vv*vv - 4*uu*ww; 
    t4 = (float) (2*Math.sqrt(uu*ww)); 

    return (float) ((t1*t2 - t3*Math.log(t2+t1) -(vv*t4 - t3*Math.log(vv+t4)))/(8*Math.pow(uu, 1.5)));