www.wikidata.de-de.nina.az

De Casteljau Algorithmus Der Algorithmus von de Casteljau ermöglicht die effiziente Berechnung einer beliebig genauen Nä

De-Casteljau-Algorithmus

Der Algorithmus von de Casteljau ermöglicht die effiziente Berechnung einer beliebig genauen Näherungsdarstellung von Bézierkurven durch einen Polygonzug. Der Algorithmus wurde Anfang der 1960er Jahre von Paul de Faget de Casteljau bei Citroën entwickelt.

Idee Bearbeiten

Der Algorithmus von de Casteljau beruht darauf, dass eine Bézierkurve geteilt und durch zwei aneinandergesetzte Bézierkurven dargestellt werden kann. Diese Unterteilung kann rekursiv fortgesetzt werden. Das Kontrollpolygon der zusammengesetzten Bézierkurve nähert sich dabei der Originalkurve an. Nach ausreichend vielen Verfeinerungsschritten kann der entstandene Polygonzug als Näherung für die Originalkurve verwendet werden. Ein Verfeinerungsschritt, der das Kontrollpolygon einer Ausgangskurve in ein Kontrollpolygon einer zusammengesetzten Kurve zerlegt, besteht nur aus wenigen einfachen Teilungen von Polygonkanten.

Darüber hinaus ermöglicht der Algorithmus die schnelle Bestimmung jedes einzelnen Punktes auf der Bézierkurve durch seine parametrische Darstellung.

Erweiterungen findet der Algorithmus im Blossoming wie auch im fokalen Algorithmus von de Casteljau.

Algorithmus Bearbeiten

Gegeben sind die Kontrollpunkte der Ausgangskurve mit .

Von den Kontrollpunkten der Ausgangskurve liegen im Allgemeinen nur und auf der Kurve. Der Algorithmus berechnet im ersten Schritt einen weiteren Punkt der Kurve. Dabei kann frei gewählt werden. Die Kurve wird im Weiteren an diesem Punkt geteilt. Es bietet sich daher die Wahl von an, weil dies eine gleichmäßige Aufteilung und damit eine schnelle Annäherung des Kontrollpolygons an die Ausgangskurve gewährleistet.

Bilden von Teilverhältnissen Bearbeiten

Konstruktion der ersten Folge von Hilfspunkten Pi(1) aus den Ausgangspunkten Pi(0).

Statt durch direktes Einsetzen von in die Gleichung der Kurve geschieht die Berechnung von über die Konstruktion von Punkten aus den gegebenen Kontrollpunkten . Die Konstruktion startet mit den Ausgangspunkten . Aus diesen werden durch Teilen der Verbindungslinien im Verhältnis neue Punkte konstruiert. Der Punkt berechnet sich nach der intuitiv einsichtigen Formel:

In nebenstehender Abbildung sind die Punkte , die aus den Ausgangspunkten hervorgegangen sind, rot eingezeichnet. Durch Fortsetzen der Berechnungsvorschrift werden in gleicher Weise Punkte bestimmt. Zur Berechnung von werden dazu die blau gestrichelten Verbindungslinien der im ersten Schritt berechneten Punkte im selben Verhältnis geteilt usw.

Konstruktion eines Kurvenpunktes Bearbeiten

Es gilt die folgende Aussage (siehe Beweis der Punktkonstruktion):

Komplette Konstruktion von P0(3) für n=3

Das heißt, dass der Punkt , welcher in der ten Iteration durch fortgesetztes Streckenteilen konstruiert wird, ein Punkt der Kurve ist. Das Teilungsverhältnis bestimmt dabei seine Lage auf der Kurve.

In nebenstehender Abbildung ist die Konstruktion für vollständig durchgeführt. Der Punkt , der durch dreifache Anwendung der Teilungsvorschrift aus den Ausgangspunkten hervorgegangen ist, liegt auf der gesuchten Kurve.

Die bei weitem interessantere Aussage ist aber, dass dieser Punkt die Kurve in zwei Bézierkurven und teilt und dass die Punkte das Kontrollpolygon von und die Punkte das Kontrollpolygon von bilden.

Teilen in zwei Bézierkurven Bearbeiten

Zerlegung von C(t) in C1(t) und C2(t)

Nebenstehende Abbildung zeigt die Zerlegung von in und für . Dabei bilden die Punkte , , und das Kontrollpolygon von und entsprechend die Punkte , , und das Kontrollpolygon von .

An der Abbildung erkennt man außerdem, warum in der Regel ein Teilungsverhältnis von verwendet wird. Da in diesem Beispiel ein Teilungsverhältnis kleiner ½ verwendet wurde, teilt sich die Kurve in einem ungleichen Verhältnis in eine kurze Kurve und eine lange Kurve auf. Der kürzere Teil ist viel besser an sein Kontrollpolygon angenähert als der längere. Möchte man (bei ungefähr gleich langen Strecken des Ausgangskontrollpolygons) eine gleichmäßige Näherung erreichen, eignet sich dazu das Teilungsverhältnis .

Die Unterteilung der Kurven wird so lange fortgesetzt, bis sie hinreichend genau durch ihre Kontrollpolygone angenähert sind.

Komplexität Bearbeiten

Eine native Implementierung des Algorithmus benötigt Rechenschritte für jeden zu berechnenden Näherungspunkt, wobei die Anzahl der Kontrollpunkte ist. Durch Optimierungen kann eine Laufzeit von erreicht werden.

Pseudocode Bearbeiten

Zu Beginn liegen die Punkte des Kontrollpolygons in einem Feld vor. Bei gegebenem Parameter wird der Punkt folgendermaßen berechnet: 

BEGIN FOR i:=0..n  
 FOR j:=1..n FOR i:=0..(n-j) // Unterteilung mit Faktor t  
 RETURN  END

Der obige Algorithmus ist insoweit unvollständig, dass nur der Punkt bestimmt, aber keine fortgesetzte Unterteilung von durchgeführt wird. Der Algorithmus ist nicht speichereffizient, da für alle neue Speicherplätze belegt werden.

Beweis der Punktkonstruktion Bearbeiten

Die Aussage, dass über -fach fortgesetzte Streckenteilung ein weiterer Punkt der Kurve konstruiert werden kann, lässt sich über Lösen der Rekursion beweisen, die definiert.

Rekursionsgleichung Bearbeiten

Die Rekursionsgleichung definiert die Punkte in Abhängigkeit von den in der letzten Iteration berechneten Punkten . Den Start der Rekursion bilden die Punkte :

Zu beweisende Aussage Bearbeiten

Zu beweisen ist die Aussage, dass der Punkt ein Punkt der Kurve an der Stelle ist:

Verallgemeinerung der Aussage Bearbeiten

Um eine Lösung der Rekursion für den speziellen Punkt zu finden, wird eine geschlossene Form für alle Punkte der Rekursion gesucht und gezeigt, dass diese insbesondere für das gesuchte Resultat liefert. Der Beweis für wird über vollständige Induktion mit folgender Induktionsannahme geführt:

Der Induktionsschritt ist dann eine gradlinige Rechnung, bei der Aussagen über Binomialkoeffizienten benutzt werden.

Siehe auch Bearbeiten

Anwendung Bearbeiten

Mit Hilfe des Algorithmus von de Casteljau ist es möglich, Näherungen von Bézierkurven durch gerade Linien zu errechnen. Dadurch kann eine Bézierkurve effizient mit dem Rechner gezeichnet werden.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Fast and Stable Pascal Matrix Algorithms. (PDF) Abgerufen am 13. September 2021.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Algorithmus von de Casteljau ermoglicht die effiziente Berechnung einer beliebig genauen Naherungsdarstellung von Bezierkurven durch einen Polygonzug Der Algorithmus wurde Anfang der 1960er Jahre von Paul de Faget de Casteljau bei Citroen entwickelt Inhaltsverzeichnis 1 Idee 2 Algorithmus 2 1 Bilden von Teilverhaltnissen 2 2 Konstruktion eines Kurvenpunktes 2 3 Teilen in zwei Bezierkurven 2 4 Komplexitat 3 Pseudocode 4 Beweis der Punktkonstruktion 4 1 Rekursionsgleichung 4 2 Zu beweisende Aussage 4 3 Verallgemeinerung der Aussage 5 Siehe auch 6 Anwendung 7 Weblinks 8 EinzelnachweiseIdee BearbeitenDer Algorithmus von de Casteljau beruht darauf dass eine Bezierkurve geteilt und durch zwei aneinandergesetzte Bezierkurven dargestellt werden kann Diese Unterteilung kann rekursiv fortgesetzt werden Das Kontrollpolygon der zusammengesetzten Bezierkurve nahert sich dabei der Originalkurve an Nach ausreichend vielen Verfeinerungsschritten kann der entstandene Polygonzug als Naherung fur die Originalkurve verwendet werden Ein Verfeinerungsschritt der das Kontrollpolygon einer Ausgangskurve in ein Kontrollpolygon einer zusammengesetzten Kurve zerlegt besteht nur aus wenigen einfachen Teilungen von Polygonkanten Daruber hinaus ermoglicht der Algorithmus die schnelle Bestimmung jedes einzelnen Punktes auf der Bezierkurve durch seine parametrische Darstellung Erweiterungen findet der Algorithmus im Blossoming wie auch im fokalen Algorithmus von de Casteljau Algorithmus BearbeitenGegeben sind die Kontrollpunkte P 0 P 1 P n displaystyle P 0 P 1 dots P n nbsp der Ausgangskurve C t i 0 n B i n t P i displaystyle C t sum i 0 n B i n t P i nbsp mit t 0 1 displaystyle t in 0 1 nbsp Von den Kontrollpunkten der Ausgangskurve C t displaystyle C t nbsp liegen im Allgemeinen nur P 0 displaystyle P 0 nbsp und P n displaystyle P n nbsp auf der Kurve Der Algorithmus berechnet im ersten Schritt einen weiteren Punkt C t 0 displaystyle C t 0 nbsp der Kurve Dabei kann t 0 0 1 displaystyle t 0 in 0 1 nbsp frei gewahlt werden Die Kurve wird im Weiteren an diesem Punkt C t 0 displaystyle C t 0 nbsp geteilt Es bietet sich daher die Wahl von t 0 1 2 displaystyle t 0 frac 1 2 nbsp an weil dies eine gleichmassige Aufteilung und damit eine schnelle Annaherung des Kontrollpolygons an die Ausgangskurve gewahrleistet Bilden von Teilverhaltnissen Bearbeiten nbsp Konstruktion der ersten Folge von Hilfspunkten Pi 1 aus den Ausgangspunkten Pi 0 Statt durch direktes Einsetzen von t 0 displaystyle t 0 nbsp in die Gleichung der Kurve C t displaystyle C t nbsp geschieht die Berechnung von C t 0 displaystyle C t 0 nbsp uber die Konstruktion von Punkten P i k displaystyle P i k nbsp aus den gegebenen Kontrollpunkten P 0 P n displaystyle P 0 dots P n nbsp Die Konstruktion startet mit den Ausgangspunkten P i 0 P i displaystyle P i 0 P i nbsp Aus diesen werden durch Teilen der Verbindungslinien P i k P i 1 k displaystyle overline P i k P i 1 k nbsp im Verhaltnis t 0 1 t 0 displaystyle t 0 1 t 0 nbsp neue Punkte P i k 1 displaystyle P i k 1 nbsp konstruiert Der Punkt P i k 1 displaystyle P i k 1 nbsp berechnet sich nach der intuitiv einsichtigen Formel P i k 1 1 t 0 P i k t 0 P i 1 k displaystyle P i k 1 1 t 0 cdot P i k t 0 cdot P i 1 k nbsp In nebenstehender Abbildung sind die Punkte P i 1 displaystyle P i 1 nbsp die aus den Ausgangspunkten P i 0 P i displaystyle P i 0 P i nbsp hervorgegangen sind rot eingezeichnet Durch Fortsetzen der Berechnungsvorschrift werden in gleicher Weise Punkte P i 2 P i 3 P i n displaystyle P i 2 P i 3 dots P i n nbsp bestimmt Zur Berechnung von P i 2 displaystyle P i 2 nbsp werden dazu die blau gestrichelten Verbindungslinien der im ersten Schritt berechneten Punkte P i 1 P i 1 1 displaystyle overline P i 1 P i 1 1 nbsp im selben Verhaltnis geteilt usw Konstruktion eines Kurvenpunktes Bearbeiten Es gilt die folgende Aussage siehe Beweis der Punktkonstruktion C t 0 P 0 n displaystyle C t 0 P 0 n nbsp nbsp Komplette Konstruktion von P0 3 fur n 3Das heisst dass der Punkt P 0 n displaystyle P 0 n nbsp welcher in der n displaystyle n nbsp ten Iteration durch fortgesetztes Streckenteilen konstruiert wird ein Punkt der Kurve ist Das Teilungsverhaltnis t 0 displaystyle t 0 nbsp bestimmt dabei seine Lage auf der Kurve In nebenstehender Abbildung ist die Konstruktion fur n 3 displaystyle n 3 nbsp vollstandig durchgefuhrt Der Punkt P 0 3 displaystyle P 0 3 nbsp der durch dreifache Anwendung der Teilungsvorschrift aus den Ausgangspunkten P 0 P 3 displaystyle P 0 dots P 3 nbsp hervorgegangen ist liegt auf der gesuchten Kurve Die bei weitem interessantere Aussage ist aber dass dieser Punkt P 0 n displaystyle P 0 n nbsp die Kurve C t displaystyle C t nbsp in zwei Bezierkurven C 1 t displaystyle C 1 t nbsp und C 2 t displaystyle C 2 t nbsp teilt und dass die Punkte P 0 i i 0 n displaystyle P 0 i i 0 dots n nbsp das Kontrollpolygon von C 1 t displaystyle C 1 t nbsp und die Punkte P i n i i 0 n displaystyle P i n i i 0 dots n nbsp das Kontrollpolygon von C 2 t displaystyle C 2 t nbsp bilden Teilen in zwei Bezierkurven Bearbeiten nbsp Zerlegung von C t in C1 t und C2 t Nebenstehende Abbildung zeigt die Zerlegung von C t displaystyle C t nbsp in C 1 t displaystyle C 1 t nbsp und C 2 t displaystyle C 2 t nbsp fur n 3 displaystyle n 3 nbsp Dabei bilden die Punkte P 0 0 displaystyle P 0 0 nbsp P 0 1 displaystyle P 0 1 nbsp P 0 2 displaystyle P 0 2 nbsp und P 0 3 displaystyle P 0 3 nbsp das Kontrollpolygon von C 1 t displaystyle C 1 t nbsp und entsprechend die Punkte P 0 3 displaystyle P 0 3 nbsp P 1 2 displaystyle P 1 2 nbsp P 2 1 displaystyle P 2 1 nbsp und P 3 0 displaystyle P 3 0 nbsp das Kontrollpolygon von C 2 t displaystyle C 2 t nbsp An der Abbildung erkennt man ausserdem warum in der Regel ein Teilungsverhaltnis von t 0 1 2 displaystyle t 0 frac 1 2 nbsp verwendet wird Da in diesem Beispiel ein Teilungsverhaltnis kleiner verwendet wurde teilt sich die Kurve C t displaystyle C t nbsp in einem ungleichen Verhaltnis in eine kurze Kurve C 1 t displaystyle C 1 t nbsp und eine lange Kurve C 2 t displaystyle C 2 t nbsp auf Der kurzere Teil ist viel besser an sein Kontrollpolygon angenahert als der langere Mochte man bei ungefahr gleich langen Strecken des Ausgangskontrollpolygons eine gleichmassige Naherung erreichen eignet sich dazu das Teilungsverhaltnis t 0 1 2 displaystyle t 0 frac 1 2 nbsp Die Unterteilung der Kurven wird so lange fortgesetzt bis sie hinreichend genau durch ihre Kontrollpolygone angenahert sind Komplexitat Bearbeiten Eine native Implementierung des Algorithmus benotigt O n 2 displaystyle mathcal O n 2 nbsp Rechenschritte fur jeden zu berechnenden Naherungspunkt wobei n displaystyle n nbsp die Anzahl der Kontrollpunkte ist Durch Optimierungen kann eine Laufzeit von O n log n displaystyle mathcal O n log n nbsp erreicht werden 1 Pseudocode BearbeitenZu Beginn liegen die Punkte des Kontrollpolygons in einem Feld P i i 0 n displaystyle P i i 0 ldots n nbsp vor Bei gegebenem Parameter t 0 displaystyle t 0 nbsp wird der Punkt C t 0 displaystyle C t 0 nbsp folgendermassen berechnet BEGIN FOR i 0 n P i 0 P i displaystyle P i 0 P i nbsp FOR j 1 n FOR i 0 n j Unterteilung mit Faktor t P i j 1 t 0 P i j 1 t 0 P i 1 j 1 displaystyle P i j 1 t 0 cdot P i j 1 t 0 cdot P i 1 j 1 nbsp RETURN P 0 n displaystyle P 0 n nbsp END Der obige Algorithmus ist insoweit unvollstandig dass nur der Punkt C t 0 displaystyle C t 0 nbsp bestimmt aber keine fortgesetzte Unterteilung von C t displaystyle C t nbsp durchgefuhrt wird Der Algorithmus ist nicht speichereffizient da fur alle P i j displaystyle P i j nbsp neue Speicherplatze belegt werden Beweis der Punktkonstruktion BearbeitenDie Aussage dass uber n displaystyle n nbsp fach fortgesetzte Streckenteilung ein weiterer Punkt der Kurve konstruiert werden kann lasst sich uber Losen der Rekursion beweisen die P i j displaystyle P i j nbsp definiert Rekursionsgleichung Bearbeiten Die Rekursionsgleichung definiert die Punkte P i k displaystyle P i k nbsp in Abhangigkeit von den in der letzten Iteration berechneten Punkten P i k 1 displaystyle P i k 1 nbsp Den Start der Rekursion bilden die Punkte P i displaystyle P i nbsp P i 0 P i displaystyle P i 0 P i nbsp P i k 1 t 0 P i k 1 t 0 P i 1 k 1 displaystyle P i k 1 t 0 cdot P i k 1 t 0 cdot P i 1 k 1 nbsp Zu beweisende Aussage Bearbeiten Zu beweisen ist die Aussage dass der Punkt P 0 n displaystyle P 0 n nbsp ein Punkt der Kurve an der Stelle t 0 displaystyle t 0 nbsp ist P 0 n C t 0 displaystyle P 0 n C t 0 nbsp Verallgemeinerung der Aussage Bearbeiten Um eine Losung der Rekursion fur den speziellen Punkt P 0 n displaystyle P 0 n nbsp zu finden wird eine geschlossene Form fur alle Punkte P i k displaystyle P i k nbsp der Rekursion gesucht und gezeigt dass diese insbesondere fur P 0 n displaystyle P 0 n nbsp das gesuchte Resultat liefert Der Beweis fur P i k displaystyle P i k nbsp wird uber vollstandige Induktion mit folgender Induktionsannahme gefuhrt P i k m 0 k P i m k m t 0 m 1 t 0 k m displaystyle P i k sum m 0 k P i m k choose m t 0 m 1 t 0 k m nbsp Der Induktionsschritt ist dann eine gradlinige Rechnung bei der Aussagen uber Binomialkoeffizienten benutzt werden Siehe auch BearbeitenBernsteinpolynom KonvexkombinationAnwendung BearbeitenMit Hilfe des Algorithmus von de Casteljau ist es moglich Naherungen von Bezierkurven durch gerade Linien zu errechnen Dadurch kann eine Bezierkurve effizient mit dem Rechner gezeichnet werden Weblinks BearbeitenDe Casteljau Polygone und Bezierkurve Applet De Casteljau Bezierkurve Applet englisch Kaspar Fischer Piecewise Linear Approximation of Bezier Curves PDF englisch Paul de Faget de Casteljau De Casteljau s autobiography My time at Citroen In Computer Aided Geometric Design 16 Jahrgang Nr 7 August 1999 S 583 586 doi 10 1016 S0167 8396 99 00024 2 Wolfgang Boehm Andreas Mueller On de Casteljau s algorithm In Computer Aided Geometric Design 16 Jahrgang Nr 7 August 1999 S 587 605 doi 10 1016 S0167 8396 99 00023 0 Einzelnachweise Bearbeiten Fast and Stable Pascal Matrix Algorithms PDF Abgerufen am 13 September 2021 Abgerufen von https de wikipedia org w index php title De Casteljau Algorithmus amp oldid 224617113