Długość łuku krzywej Beziera


23

Zobacz także: to samo pytanie na Math.SE

Jak znaleźć długość łuku krzywej Beziera? Na przykład liniowa krzywa Beziera ma długość:

length = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));

Ale co z kwadratowymi, sześciennymi lub n-stopniowymi krzywymi Beziera?

(Moim celem było wcześniejsze oszacowanie rozdzielczości próbkowania, więc nie muszę tracić czasu na sprawdzanie, czy następny punkt dotyka poprzedniego punktu.)


1
Powinieneś przeredagować pytanie, aby odnosić się do długości krzywej, która jest znacznie prostszym (i możliwym do przeszukiwania) terminem.
Sparr

proponuję opublikować to na matematyce, jestem pewien, że jakaś sprytna twarz da ci odpowiedź w jednej z nich sprytnych czcionek internetowych: p
Tor Valamo

2
@Tor zrobiłem (wczoraj), ale powiedziano mi, że jest to bardzo skomplikowane, a zatem niepraktyczne. [ math.stackexchange.com/q/12186/2736 ]
Mateen

Podobno krzywe / splajny typu kloidoidy są alternatywą dla Beziers i mają wyrażenia o zamkniętej formie, ale jeszcze niewiele o tym wiem. (Próbujesz wygenerować punkty o równej odległości wzdłuż krzywej.) Sieci trakcyjne mają również wyrażenia długości łuku w postaci zamkniętej?
endolith

Odpowiedzi:


9

Prostym sposobem na sześcienne Beziers jest podzielenie krzywej na N segmentów i zsumowanie długości segmentów.

Jednak gdy tylko potrzebujesz długości tylko części krzywej (np. Do 30% długości wzdłuż), rozpocznie się parametryzacja długości łuku . Na jedno z moich własnych pytań na temat Béziersa zamieściłem dość długą odpowiedź , z prostym przykładowym kodem.


Robię to dla LEGO Mindstorms NXT, który ma naprawdę słaby procesor (48 MHz), więc potrzebuję jak największej prędkości. Podejdę do dzielenia, aby zaoszczędzić trochę prędkości i uzyskać ją wystarczająco dokładną (do renderowania „w czasie rzeczywistym”). Mam również opcję, w której możesz ustawić wartość 1.0/t(wywoływana resolution), więc to jest dla „czasu rzeczywistego” (czyli co najwyżej 10 fps na wolnym NXT). Rysowana jest każda iteracja t += resolutionoraz nowy punkt / linia. W każdym razie dzięki za pomysł.
Mateen Ulhaq

4

Chociaż jestem z odpowiedziami, które już otrzymałeś, chcę dodać prosty, ale potężny mechanizm aproksymacji, którego możesz użyć dla krzywych Béziera o dowolnym stopniu: Ciągle dzielisz krzywą za pomocą podziału de Casteljau, aż do maksymalnej odległości punktów kontrolnych pod-krzywej do linii bazowej pod-krzywej jest poniżej pewnego stałego epsilon . W takim przypadku pod-krzywą można aproksymować za pomocą linii podstawowej.

W rzeczywistości uważam, że takie podejście jest zwykle stosowane, gdy podsystem graficzny musi narysować krzywą Béziera. Ale nie cytuj mnie na ten temat, w tej chwili nie mam pod ręką referencji.

W praktyce będzie to wyglądać tak: (z wyjątkiem tego, że język nie ma znaczenia)

public static Line[] toLineStrip(BezierCurve bezierCurve, double epsilon) {
    ArrayList<Line> lines = new ArrayList<Line>();

    Stack<BezierCurve> parts = new Stack<BezierCurve>();
    parts.push(bezierCurve);

    while (!parts.isEmpty()) {
        BezierCurve curve = parts.pop();
        if (distanceToBaseline(curve) < epsilon) {
            lines.add(new Line(curve.get(0), curve.get(1)));
        } else {
            parts.addAll(curve.split(0.5));
        }
    }

    return lines.toArray(new Line[0]);
}

Chociaż jest to dobre podejście, słyszałem o niestabilności numerycznej przy wysokich krzywych Beziera, które wymagają innego pomysłu: podzielenie krzywych wyższego rzędu na mniejsze krzywe sześcienne.
Mateen Ulhaq,

Ponadto, jeśli celem końcowym jest dokładne oszacowanie, dobrym pomysłem może być przybliżenie za pomocą kwadratów zamiast linii, aby upewnić się, że nie zaniżamy naszych oszacowań w miejscach o wysokiej krzywiźnie.
Mateen Ulhaq,

2

Długości łuku dla krzywych Beziera są tylko zamknięte dla krzywych liniowych i kwadratowych. W przypadku sześciennych nie ma gwarancji posiadania zamkniętego rozwiązania. Powodem jest to, że długość łuku jest zdefiniowana przez całkę radykalną, dla której jest zamknięty tylko dla wielomianów drugiego stopnia.

Tylko w celach informacyjnych: Długość kwadratowego Beziera dla punktów (a, p) (b, q) i (c, r) wynosi

(a ^ 2 · (q ^ 2 - 2 · q · r + r ^ 2) + 2 · a · (r - q) · (b · (p - r) + c · (q - p)) + ( b · (p - r) + c · (q - p)) ^ 2) · LN ((√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · √ (a ^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) + a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) / (√ (a ^ 2 + 2 · A · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) · √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) + a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2) ^ (3/2) + (√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · (a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) - √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) · (a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2)

Gdzie LN jest logarytmem naturalnym, a ^ oznacza moc i root pierwiastek kwadratowy.

Dlatego przybliżenie łuku powinno być łatwiejsze i tańsze według innej reguły, takiej jak wielokąt lub schemat integracji, taki jak reguła Simpsona, ponieważ pierwiastki kwadratowe LN są kosztownymi operacjami.


2

Opracowałem wyrażenie długości w postaci zamkniętej dla 3-punktowego Beziera (poniżej). Nie próbowałem wypracować zamkniętego formularza dla 4+ punktów. Reprezentacja i obsługa najprawdopodobniej byłaby trudna lub skomplikowana. Jednak numeryczna technika aproksymacji, taka jak algorytm całkowania Runge-Kutta, działałaby całkiem dobrze, integrując przy użyciu wzoru długości łuku . Moje pytania i odpowiedzi na temat RK45 na MSE mogą pomóc w implementacji RK45.

Oto niektóre kodu Java dla długości łuku 3 pkt Beziera z punktów a, bi 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)));
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.