Długość łuku krzywej Beziera

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.)

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.

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

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.

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