Tani sposób obliczania kubicznej długości beziera

Question

Rozwiązanie analityczne dla sześciennej długości beziera wydaje się nie istnieć, ale to nie znaczy, że kodowanie taniego rozwiązania nie istnieje. Przez tanie rozumiem coś w rodzaju 50-100 ns (lub mniej).

Czy ktoś wie coś takiego? Może w dwóch kategoriach:

1) mniejszy błąd jak 1%, ale wolniejszy kod. 2) więcej błąd jak 20%, ale szybciej?

Zeskanowałem za pomocą wyszukiwarki google, ale nie jest to znaleźć niczego, co wygląda jak dobre rozwiązanie. Tylko coś takiego, jak dzielenie na segmenty linii N i sumowanie N sqrt - zbyt wolne dla większej precyzji, i prawdopodobnie zbyt niedokładne dla 2 lub 3 segmentów.

Czy jest coś lepszego?

Answer 1

Najprostszy algorytm: spłaszcz krzywą i wyrównaj odległość euklidesową. Tak długo, jak chcesz uzyskać przybliżoną długość łuku, to rozwiązanie jest szybkie i tanie. Biorąc pod uwagę współrzędną twojej krzywej LUT-mówisz o prędkości, więc zakładam, że używasz tych i nie przeliczasz stale współrzędnych - to prosta pętla dla ciebie z tally. W kodzie generycznych, z dist funkcji, która oblicza odległość euklidesowa pomiędzy dwoma punktami:

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

zrobić. arclength jest teraz przybliżoną długością łuku w oparciu o maksymalną liczbę segmentów, które można utworzyć na krzywej w oparciu o LUT. Potrzebujesz rzeczy szybciej z większym potencjalnym błędem? Kontroluj liczbę segmentów.

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

Jest to najprostszy możliwy algorytm, który nadal generuje wartości zbliżone do rzeczywistej długości łuku. Na cokolwiek lepiej, będziesz musiał użyć droższych metod numerycznych (takich jak technika kwadratury Legendre-Gaussa).

Jeśli chcesz wiedzieć dlaczego, naciśnij the arc length section "A Primer on Bézier Curves".

Answer 2

Inną opcją jest oszacowanie długości łuku jako średniej między cięciwą a siatką kontrolną. W praktyce:

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; 

Następnie można rekursywnie podzielić segment splajnu na dwa segmenty i obliczyć długość łuku do konwergencji. Testowałem siebie i to dość szybko. Mam pomysł z tego forum.

Answer 3

pierwszy z pierwszych Należy zrozumieć użycie algorytmu w Bezier, Kiedy koduję program przez C# Który był pełen materiału graficznego użyłem beziers i wiele razy musiałem znaleźć punkt współrzędnych w beziera, który wydaje się nieprzyzwoicie na pierwszy rzut oka. więc to, co zrobiłem, to napisanie funkcji Cubic bezier w mojej klasie math kostiumów, która była w moim projekcie. więc najpierw podzielę się z tobą kodem.

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

jak widać powyżej, to jest droga dzieło Funkcja Beziera i czerpać taką samą Baziera jak Microsoft Beziera Funkcja zrobić (mam go przetestować). możesz uczynić go jeszcze bardziej dokładnym poprzez zwiększenie rozmiaru tablicy i rozmiaru licznika lub narysować elipse zamiast linii & .... Wszystkie one zależą od potrzeb i poziomu dokładności, jakich potrzebujesz i ....

Powracając do głównego celu, pytanie brzmi: jak obliczyć długość?

dobrze Odpowiedź jest taka, że ​​mamy tony punktu, a każdy z nich ma współrzędną xi współrzędną y, która pamięta nas w kształcie trójkąta &, szczególnie w kształcie Right Right. więc jeśli mamy punkt p1 & p2, możemy obliczyć odległość ich jako akordu RightTriangle. jak pamiętamy z naszej lekcji matematyki w szkole, w ABC Triangle typu RightTriangle, acord Lenght to -> Sqrt (Angle's FrontCostalLenght^2 + Angle's SideCostalLeghth^2);

i istnieje ta relacja między wszystkimi punktami, dla których obliczamy długość między bieżącym punktem a ostatnim punktem przed bieżącym punktem (exmp p [i - 1] & p [i]) i zapisujemy ich sumę w zmiennej. pozwala pokazać go w kodzie poniżej

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

jeśli chcesz mieć szybsze obliczanie wystarczy zmniejszyć px & py długość tablicy i liczyć loob.

Możemy również zmniejszyć zapotrzebowanie na pamięć, zmniejszając px i py do długości tablicy do 1 lub utworzyć prostą podwójną zmienną, ale ze względu na sytuację warunkową, która spowodowała zwiększenie naszego dużego O, nie zrobiłem tego.

Mam nadzieję, że to ci pomogło. jeśli masz inne pytanie, po prostu zapytaj. Z pozdrowieniami, Hejdar - Islamska Republika Iranu.

Answer 4

Wykreśliłem zamknięty formularz wyrażenia długości dla 3-punktowego Beziera (poniżej). Nie próbowałem wypracować zamkniętego formularza dla 4+ punktów. Najprawdopodobniej byłoby to trudne lub skomplikowane do reprezentowania i obsługi. Jednak numeryczna technika aproksymacji, taka jak algorytm integracji Runge-Kutta, działałby całkiem dobrze, integrując się przy użyciu arc length formula.

Oto kod Java dla długości łuku 3-punktowego Beziera, z punktami a, b i 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)));