Bogenlänge der Bézier-Kurve

Siehe auch: gleiche Frage zu Math.SE

Wie finde ich die Bogenlänge einer Bézier-Kurve? Beispielsweise hat eine lineare Bezier-Kurve die Länge:

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

Aber was ist mit quadratischen, kubischen oder n-Grad-Bezier-Kurven?

(Mein Ziel war es, vorher eine Abtastauflösung zu schätzen, damit ich keine Zeit verschwenden muss, um zu prüfen, ob der nächste Punkt den vorherigen Punkt berührt.)

Eine einfache Möglichkeit für kubische Beziers besteht darin, die Kurve in N Segmente aufzuteilen und die Segmentlängen zu summieren.

Sobald Sie jedoch nur die Länge eines Teils der Kurve benötigen (z. B. bis zu einem Punkt, der 30% der Länge entspricht), kommt die Parametrierung der Bogenlänge zum Tragen. Ich habe eine ziemlich lange Antwort auf eine meiner Fragen zu Béziers mit einfachem Beispielcode gepostet .

Während ich mit den bereits erhaltenen Antworten einverstanden bin, möchte ich einen einfachen, aber leistungsstarken Näherungsmechanismus hinzufügen, den Sie für Bézier-Kurven mit beliebigem Grad verwenden können: Sie unterteilen die Kurve kontinuierlich mit der Unterteilung de Casteljau bis zum maximalen Abstand der Kontrollpunkte einer Unterkurve zur Grundlinie der Unterkurve liegt unter einem konstanten Epsilon . In diesem Fall kann die Unterkurve durch ihre Grundlinie angenähert werden.

Tatsächlich glaube ich, dass dies der Ansatz ist, der normalerweise angewendet wird, wenn ein Grafiksubsystem eine Bézier-Kurve zeichnen muss. Aber zitieren Sie mich nicht dazu, ich habe im Moment keine Referenzen zur Hand.

In der Praxis wird es so aussehen: (außer die Sprache ist irrelevant)

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

Bogenlängen für Bezier-Kurven sind nur für lineare und quadratische geschlossen. Für Cubics kann keine geschlossene Lösung garantiert werden. Der Grund dafür ist, dass die Bogenlänge durch ein Radikalintegral definiert ist, für das nur Polynome 2. Grades geschlossen sind.

Nur als Referenz: Die Länge eines quadratischen Beziers für die Punkte (a, p) (b, q) und (c, r) ist

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

Wobei LN der natürliche Logarithmus ist und ^ die Potenz und √ die Quadratwurzel bezeichnet.

Daher sollte es einfacher und billiger sein, den Bogen durch eine andere Regel, wie ein Polygon oder ein Integrationsschema wie die Simpson-Regel, zu approximieren, da die Quadratwurzeln der LN teure Operationen sind.

Ich habe den Längenausdruck in geschlossener Form für einen 3-Punkt-Bezier (unten) erarbeitet. Ich habe nicht versucht, ein geschlossenes Formular für 4+ Punkte zu erstellen. Dies wäre höchstwahrscheinlich schwierig oder kompliziert darzustellen und zu handhaben. Eine numerische Approximationstechnik wie ein Runge-Kutta-Integrationsalgorithmus funktioniert jedoch recht gut, wenn die Integration unter Verwendung der Bogenlängenformel erfolgt . Meine Fragen und Antworten zu RK45 unter MSE können bei der Implementierung von RK45 hilfreich sein.

Hier ist ein Java-Code für die Bogenlänge eines 3-Punkt-Beziers mit Punkten a , bund 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)));