Bogenlänge der Bézier-Kurve

23

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

Mateen Ulhaq
quelle
1
Sie sollten die Frage umformulieren, um sich auf die Länge der Kurve zu beziehen. Dies ist ein sehr viel direkterer (und durchsuchbarer) Begriff.
Sparr
Ich schlage vor, dies in Mathe zu veröffentlichen. Ich bin sicher, dass ein kluges Gesicht dort drüben die Antwort in einer dieser klugen Web-Schriften gibt: p
Tor Valamo
2
@Tor ich tat (gestern), aber mir wurde gesagt, es ist sehr kompliziert und daher unpraktisch. [ math.stackexchange.com/q/12186/2736 ]
Mateen Ulhaq
Angeblich sind Klothoiden-Kurven / Splines eine Alternative zu Béziers und haben Bogenlängenausdrücke in geschlossener Form, aber ich weiß noch nicht viel darüber. (Versuchen Sie, Punkte mit gleichem Abstand entlang einer Kurve zu generieren.) Oberleitungen haben auch Bogenlängenausdrücke in geschlossener Form?
Endolith

Antworten:

9

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 .

Ivo Wetzel
quelle
Ich mache das für das LEGO Mindstorms NXT, das einen sehr schwachen Prozessor (48 MHz) hat, also brauche ich so viel Geschwindigkeit wie möglich. Ich werde den Teilungsansatz wählen, um etwas Geschwindigkeit zu sparen und genau genug zu erhalten (für "Nicht-Echtzeit" -Rendering). Ich habe auch eine Option, in der du den Wert von 1.0/t(called resolution) einstellen kannst , also ist das für "Realtime" (was bestenfalls 10fps auf dem langsamen NXT ist). Bei jeder Iteration wird t += resolutionein neuer Punkt / eine neue Linie gezeichnet. Trotzdem danke für die Idee.
Mateen Ulhaq
4

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]);
}
Matthias
quelle
Obwohl dies ein guter Ansatz ist, habe ich von numerischer Instabilität bei Bezier-Kurven höherer Ordnung gehört, für die eine andere Idee erforderlich ist: das Aufteilen der Kurven höherer Ordnung in kleinere kubische Kurven.
Mateen Ulhaq
Wenn das Endziel eine genaue Schätzung ist, ist es möglicherweise eine gute Idee, eine Annäherung an quadratische Werte anstelle von Linien vorzunehmen, um sicherzustellen, dass wir unsere Schätzung an Orten mit hoher Krümmung nicht unterschätzen.
Mateen Ulhaq
2

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.

Robert
quelle
2

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