Approximierender nichtparametrischer kubischer Bezier

Question

Wie lässt sich eine kubische Bezierkurve am besten approximieren? Idealerweise würde ich eine Funktion y (x) haben, die für jedes gegebene x den exakten y-Wert liefert, aber das würde beinhalten, eine kubische Gleichung für jeden x-Wert zu lösen, was für meine Bedürfnisse zu langsam ist, und es mag numerische Stabilitätsprobleme geben auch mit diesem Ansatz.

Wäre this eine gute Lösung?

Answer 1

Lösen Sie einfach die kubische.

Wenn Sie über Bezier-Ebenen-Kurven sprechen, wobei x (t) und y (t) kubische Polynome sind, dann könnte y (x) undefiniert sein oder mehrere Werte haben. Ein extrem degenerierter Fall wäre die Linie x = 1,0, die als kubische Bezier ausgedrückt werden kann (Kontrollpunkt 2 ist derselbe wie Endpunkt 1; Kontrollpunkt 3 ist derselbe wie Endpunkt 4). In diesem Fall hat y (x) keine Lösungen für x! = 1.0 und unendliche Lösungen für x == 1.0.

Eine Methode der rekursiven Unterteilung funktioniert, aber ich würde erwarten, dass sie viel langsamer ist, als nur das Kubische zu lösen. (Es sei denn, Sie arbeiten mit einer Art von eingebettetem Prozessor mit ungewöhnlich schlechter Gleitkomma-Kapazität.)

Sie sollten keine Probleme haben, einen Code zu finden, der ein bereits gründlich getestetes und debuggedes Cubic löst. Wenn Sie Ihre eigene Lösung mit rekursiver Unterteilung implementieren, haben Sie diesen Vorteil nicht.

Schließlich, ja, kann es numerische Stabilitätsprobleme geben, wie wenn der Punkt, den Sie wollen, in der Nähe einer Tangente ist, aber eine Unterteilung Methode wird diese nicht verschwinden lassen. Es wird sie nur weniger offensichtlich machen.

EDIT: Antwort auf Ihren Kommentar, aber ich brauche mehr als 300 Zeichen.

Ich habe es nur mit Bezierkurven zu tun, bei denen y (x) nur eine (echte) Wurzel hat. In Bezug auf die numerische Stabilität, mit der Formel von http://en.wikipedia.org/wiki/Cubic_equation#Summary, scheint es, dass es Probleme geben könnte, wenn du sehr klein bist. - jtxx000

Der wackypedia Artikel ist Mathe ohne Code. Ich vermute, du kannst einen Kochbuchcode finden, der irgendwo gebrauchsfertiger ist. Vielleicht haben Numerische Rezepte oder ACM Algorithmen gesammelt.

Zu Ihrer spezifischen Frage, und mit der gleichen Notation wie der Artikel, ist u nur Null oder nahe Null, wenn p auch Null oder nahe Null ist. Sie werden durch die Gleichung:
u^^6 + q u^^3 == p^^3 /27
in der Nähe von Null, können Sie die Annäherung verwenden können:
q u^^3 == p^^3 /27
oder p/3u == Kubikwurzel von q
So ist die Berechnung von x von u sollte so etwas wie enthalten:

(fabs(u) >= somesmallvalue) ? (p/u/3.0) : cuberoot (q) 

Wie "nahe" Null ist nahe? Hängt davon ab, wie viel Genauigkeit Sie benötigen. Sie könnten etwas Zeit mit Maple oder Matlab verbringen, um zu sehen, wie viel Fehler für welche Größen von u verursacht wird. Natürlich wissen nur Sie, wie viel Genauigkeit Sie brauchen.

Der Artikel gibt 3 Formeln für Sie für die 3 Wurzeln der kubischen. Mit den drei u-Werten erhalten Sie die 3 entsprechenden x-Werte. Die 3 Werte für u und x sind alle komplexe Zahlen mit einer imaginären Komponente. Wenn Sie sicher sind, dass es nur eine echte Lösung geben muss, dann erwarten Sie, dass eine der Nullstellen eine imaginäre Nullkomponente hat und die anderen zwei komplexe Konjugate sind. Es sieht so aus, als müssten Sie alle drei berechnen und dann den richtigen auswählen. (Beachten Sie, dass ein komplexes u einem reellen x entsprechen kann!) Allerdings gibt es dort ein anderes Problem der numerischen Stabilität: Gleitkommaarithmetik ist das, was es ist, die imaginäre Komponente der realen Lösung wird nicht genau Null sein, und die imaginären Komponenten von die nicht-realen Wurzeln können beliebig nahe Null sein. Eine numerische Abrundung kann also dazu führen, dass Sie die falsche Wurzel auswählen. Es wäre hilfreich, wenn es aus Ihrer Bewerbung eine Plausibilitätsprüfung gibt, die Sie dort anwenden können.

Wenn Sie die richtige Wurzel auswählen, können eine oder mehrere Iterationen von Newton-Raphson die Genauigkeit erheblich verbessern.

Answer 2

Ja, de Casteljau Algorithmus würde für Sie arbeiten. Ich weiß jedoch nicht, ob es schneller sein wird, als die kubische Gleichung nach Cardanos Methode zu lösen.