86
Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation Florian Frank Friedrich-Alexander-Universität Erlangen-Nürnberg Sommersemster 2019

Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

  • Upload
    others

  • View
    13

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Übung zu Algorithmik kontinuierlicherSystemeÜbung 6 – Bézierkurven und Interpolation

Florian Frank

Friedrich-Alexander-Universität Erlangen-Nürnberg

Sommersemster 2019

Page 2: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Was machen wir heute?

Besprechung von Blatt 4

Rekapitulation — Globale Interpolation

Aufgabe 1 — Polynominterpolation (I)

Rekapitulation — Lokale Interpolation

Aufgabe 1 — Polynominterpolation (II)

Rekapitulation — Freiformmodellierung mit Bézierkurven

Rekapitulation — Multivariate Interpolation

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–2

Page 3: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Besprechung von Blatt 4

Page 4: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?

� Wie multipliziert man imCRS-Format richtig?

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 5: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 6: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

Sei ein Vektor b =(1 1 −1 1

)T und eine Matrix B im CRS-Format mit

val = [1, 4, 7, -2, 5]col_ind = [2, 3, 4, 2, 3]row_ptr = [1, 1, 2, 4, 6]

b = (1 1 -1 1)T

gegeben. Bestimmen Sie den Vektor Bb ohne die Matrix zu rekonstruieren.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 7: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

Algorithmus 6.1 (Multiplikation mit CRS-Matrizen)Eingabe : Eine Matrix A im CRS-Format, ein Vektor b ∈ Rn

Ausgabe : y = Ab1 m← maxi col_ind[i]2 y ← ~0 ∈ Rm

3 for i ← 1 to min{n,m} do

4 yi ←row_ptr[i+1]−1∑

k=row_ptr[i]

bcol_ind[k ] · val[k ]

5 end for

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 8: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

val = [1, 4, 7, -2, 5]col_ind = [2, 3, 4, 2, 3]row_ptr = [1, 1, 2, 4, 6]

b = (1 1 -1 1)T

y1 =

1−1∑i=1

bcol_ind[i] · val[i]

= 0

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 9: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

val = [1, 4, 7, -2, 5]col_ind = [2, 3, 4, 2, 3]row_ptr = [1, 1, 2, 4, 6]

b = (1 1 -1 1)T

y2 =

2−1∑i=1

bcol_ind[i] · val[i]

= 1 · 1 = 1

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 10: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

val = [1, 4, 7, -2, 5]col_ind = [2, 3, 4, 2, 3]row_ptr = [1, 1, 2, 4, 6]

b = (1 1 -1 1)T

y3 =

3−1∑i=2

brow_ind[i] · val[i]

= − 1 · 4 + 1 · 7 = 3

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 11: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

val = [1, 4, 7, -2, 5]col_ind = [2, 3, 4, 2, 3]row_ptr = [1, 1, 2, 4, 6]

b = (1 1 -1 1)T

y4 =

6−1∑i=4

brow_ind[i] · val[i]

= 1 · (−2) − 1 · 5 = −7.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 12: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Blatt 4 — Lineare Ausgleichsrechnung und Matrixformate

Hier gibt es nichts zu sehen!

Probleme:

� Was ist eine Skizze?� Wie multipliziert man im

CRS-Format richtig?

val = [1, 4, 7, -2, 5]col_ind = [2, 3, 4, 2, 3]row_ptr = [1, 1, 2, 4, 6]

b = (1 1 -1 1)Ty =

(0 1 3 −7

)T

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–4

Page 13: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Rekapitulation — Globale Interpolation

Page 14: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Motivation — Rudi, die rabiate Rennmaus

Rudi, ein Verwandter von Speedy Gonzales, möchte eine Rennstrecke umeinen See erstellen. Er gibt einige Punkte vor (in der Skizze durch Kreuzemarkiert), durch die die Strecke verlaufen soll. Gleichzeitig möchte er abereinen möglichst glatten Streckenverlauf ohne Spitzen.

ZielBestimme eine „glatte“ Funktion Φ : R→ R2, welche durch die Stützstellen verläuft.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–6

Page 15: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Motivation — Rudi, die rabiate Rennmaus

Rudi, ein Verwandter von Speedy Gonzales, möchte eine Rennstrecke umeinen See erstellen. Er gibt einige Punkte vor (in der Skizze durch Kreuzemarkiert), durch die die Strecke verlaufen soll. Gleichzeitig möchte er abereinen möglichst glatten Streckenverlauf ohne Spitzen.

ZielBestimme eine „glatte“ Funktion Φ : R→ R2, welche durch die Stützstellen verläuft.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–6

Page 16: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Problemstellung: Interpolation

ProblemstellungSeien n + 1 Punkte (xi , yi) ∈ R× R gegeben, dann ist eine Funktion

Φ : R→ R mit Φ(xi) = yi

einer bestimmten „Bauart“ gesucht.

Diese Bauart wird durch die Angabe eines Funktionenraums Vn vorgegeben,man fordert dann zusätzlich noch Φ ∈ Vn.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–7

Page 17: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Interpolationsverfahren

Interpolation

LOKAL GLOBAL

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–8

Page 18: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Interpolationsverfahren

Interpolation

LOKAL

Bei lokalen Verfahrenhängt der interpolierteWert nur von benachbar-ten Werten ab.

GLOBAL

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–8

Page 19: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Interpolationsverfahren

Interpolation

LOKAL

nearestneighbour linear

Catmull-Rom

GLOBAL

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–8

Page 20: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Interpolationsverfahren

Interpolation

LOKAL

nearestneighbour linear

Catmull-Rom

GLOBAL

Bei globalen Verfahrenhängt die Interpolations-funktion von allen Stütz-stellen ab.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–8

Page 21: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Interpolationsverfahren

Interpolation

LOKAL

nearestneighbour linear

Catmull-Rom

GLOBAL

PolynomSplineTrig.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–8

Page 22: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Unterschied: Interpolation←→ Approximation

Interpolation ←→ Approximation

Die Kurve muss durch jeden Kon-trollpunkt gehen.

Die Kurve wird von den Kontroll-punkten beeinflusst!

DaumenregelInterpolation ist bei exakten, korrekten Daten sinnvoll, man möchte diese als sol-che auch behandeln. Kam es allerdings zu Messfehlern, oder sind die Daten nurApproximationen, so ist eine Approximation sinnvoller

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–9

Page 23: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Unterschied: Interpolation←→ Approximation

Interpolation ←→ Approximation

1 2 3 4 5

2

4

6

8

Die Kurve muss durch jeden Kon-trollpunkt gehen.

1 2 3 4 5

2

4

6

8

Die Kurve wird von den Kontroll-punkten beeinflusst!

DaumenregelInterpolation ist bei exakten, korrekten Daten sinnvoll, man möchte diese als sol-che auch behandeln. Kam es allerdings zu Messfehlern, oder sind die Daten nurApproximationen, so ist eine Approximation sinnvoller

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–9

Page 24: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Globale Polynominterpolation (I) — Vandermondematrix

Wir betrachten die Monombasis:

{ p | p ist reelles Polynom vom Grad 6 n } =: Pn = span{

x i∣∣ 0 6 i 6 n

}Dann ergeben sich die Koeffizienten der Interpolationsfunktion für n + 1Stützstellen als Lösung des linearen Gleichungssystems1 x1 . . . xn

1...

.... . .

...1 xn+1 . . . xn

n+1

· c1

...cn+1

=

y1...

yn+1

.Die Systemmatrix heißt auch Vandermonde-Matrix. Man kann zeigen, dasswenn alle Stützstellen paarweise verschieden sind, A nicht singulär ist.

ProblemDennoch ist die Matrix voll besetzt und schlecht konditioniert, so ist für n = 20 beiäquidistanten Stützstellen die Kondition bereits bei κ∞ ≈ 11000.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–10

Page 25: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Globale Polynominterpolation (I) — Vandermondematrix

Wir betrachten die Monombasis:

{ p | p ist reelles Polynom vom Grad 6 n } =: Pn = span{

x i∣∣ 0 6 i 6 n

}Dann ergeben sich die Koeffizienten der Interpolationsfunktion für n + 1Stützstellen als Lösung des linearen Gleichungssystems1 x1 . . . xn

1...

.... . .

...1 xn+1 . . . xn

n+1

· c1

...cn+1

=

y1...

yn+1

.Die Systemmatrix heißt auch Vandermonde-Matrix. Man kann zeigen, dasswenn alle Stützstellen paarweise verschieden sind, A nicht singulär ist.

ProblemDennoch ist die Matrix voll besetzt und schlecht konditioniert, so ist für n = 20 beiäquidistanten Stützstellen die Kondition bereits bei κ∞ ≈ 11000.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–10

Page 26: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Globale Polynominterpolation (II) — Lagrangebasis

Wähle nun solche Basisfunktionen ϕi , so dass die Matrix imGleichungssystem der Koeffizienten zur Identität wird. Als Voraussetzung istdann

ϕj(xi) = δij =

{1 falls i = j0 sonst

für alle i, j = 1, . . . , n + 1.Eine Basis mit dieser Eigenschaft ist die Lagrangebasis:

ϕj(x) = Lj(x) :=

n+1∏i=1, i 6=j

(x − xi)

n+1∏i=1, i 6=j

(xj − xi)

für j = 1, . . . , n + 1

Die Koeffizienten sind dann genau die Stützwerte, es gilt also für dasPolynom:

pL(x) =n+1∑i=1

ci · Li(x) =n+1∑i=1

yi · Li(x)

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–11

Page 27: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Globale Polynominterpolation (II) — Lagrangebasis

Lagrangebasis:

ϕj(x) = Lj(x) :=

n+1∏i=1, i 6=j

(x − xi)

n+1∏i=1, i 6=j

(xj − xi)

für j = 1, . . . , n + 1

ProblemeJede Evaluation des Interpolationspolynoms benötigt O

(n2)

Operationen, dies kannaber zu O (n) abgeschwächt werden.

Bei Hinzufügen eines neuen Punktes (xn+2, yn+2) muss alles neu berechnet werden,da jedes Lj von allen Stützpunkten abhängt.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–12

Page 28: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Globale Polynominterpolation (III) — Newtonbasis

Versuche nun den zweiten Nachteil von Lagrange durch besondereBasisfunktionen anzupassen. Definiere

ϕj(x) = Nj(x) :=j−1∏i=1

(x − xi),

so hängt Nj(x) nur von den ersten j − 1 Stützstellen (x1, . . . , xj−1) ab.Die Koeffizienten berechnen sich als Lösung des linearenGleichungssystems

1 0 . . . 0

1 (x2 − x1). . .

......

.... . . 0

1 (xn+1 − x1) . . .∏n+1

i=1 (xn+1 − xi)

·

c1......

cn+1

=

y1......

yn+1

durch Vorwärtseinsetzen oder über den Algorithmus von Aitken-Neville.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–13

Page 29: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Globale Polynominterpolation (III) — Aitken-Neville

Algorithmus 6.1 (Algorithmus von Aitken-Neville)Eingabe : Stützstellen xi , Stützwerte yi mit 1 6 i 6 n.Ausgabe : Koeffizienten ai mit 1 6 i 6 n.

1 P ← (pik)16i6n−k06k6n−1

2 p1:n,0 ← y1:n.3 for k ← 1 to n do4 for i ← 1 to n − k do

5 pi,k ←pi+1,k−1 − pi,k−1

xi+k − xi6 end for7 end for8 a← p1

Aufwand ∈ O(n2)

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–14

Page 30: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Aufgabe 1 — Polynominterpolation (I)

Page 31: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Aufgabe 1 — Polynominterpolation (I)

a) Gegeben sind die Stützstellen x1 = −2, x2 = 0, x3 = 1, x4 = 4. BestimmenSie die Lagrange- und Newton-Polynombasen zu diesen Stützstellen.

b) An diesen Stützstellen sind die Werte {4,−2, 1, 4} gegeben. BestimmenSie die Koeffizienten des Interpolationspolynoms bzgl. der Lagrange- undNewton-Basis.

c) Bestimmen Sie den Wert der Polynome mit den Werten aus Teilaufgabe ban der Stelle x = 0.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–16

Page 32: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Aufgabe 1 — Polynominterpolation (I)

a) Gegeben sind die Stützstellen x1 = −2, x2 = 0, x3 = 1, x4 = 4. BestimmenSie die Lagrange- und Newton-Polynombasen zu diesen Stützstellen.

b) An diesen Stützstellen sind die Werte {4,−2, 1, 4} gegeben. BestimmenSie die Koeffizienten des Interpolationspolynoms bzgl. der Lagrange- undNewton-Basis.

c) Bestimmen Sie den Wert der Polynome mit den Werten aus Teilaufgabe ban der Stelle x = 0.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–16

Page 33: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Aufgabe 1 — Polynominterpolation (I)

a) Gegeben sind die Stützstellen x1 = −2, x2 = 0, x3 = 1, x4 = 4. BestimmenSie die Lagrange- und Newton-Polynombasen zu diesen Stützstellen.

b) An diesen Stützstellen sind die Werte {4,−2, 1, 4} gegeben. BestimmenSie die Koeffizienten des Interpolationspolynoms bzgl. der Lagrange- undNewton-Basis.

c) Bestimmen Sie den Wert der Polynome mit den Werten aus Teilaufgabe ban der Stelle x = 0.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–16

Page 34: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Aufgabe 1 — Polynominterpolation (I): Polynom

−3 −2 −1 1 2 3 4 5

−2

2

4

6

8

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–17

Page 35: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Rekapitulation — Lokale Interpolation

Page 36: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Lokale Interpolationsmethoden (I) — nearest neighbour

Um den Wert an der Stel-le x anzunähern, sucheden nähesten Nachbarn,sprich die nächst gelegeneStützstelle xj . Der interpo-lierte Wert ist dann mit yj

gegeben.−2 −1 1 2 3 4 5

−2−1

12345

Für das Polynom gilt dann:

p(x) =

y1 x1 6 x 6 1

2 (x1 + x2)

yi12 (xi−1 + xi) < x 6 1

2 (xi + xi+1) für alle 2 6 i 6 n − 1yn

12 (xn−1 + xn) < x 6 xn

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–19

Page 37: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Lokale Interpolationsmethoden (II) — Stückweise linear

Um den Wert an der Stellex hierbei anzunähern, su-chen wir zuerst die nächstgelegene linke und rechteStützstelle xi und xi+1, sodass xi 6 x 6 xi+1 gilt, undinterpolieren dann im Inter-vall [xi, xi+1] linear.

−2 −1 1 2 3 4 5

−2−1

12345

Für 1 6 i < n stelle die Polynome

pi(x) = mi · (x − xi) + yi =yi+1 − yi

xi+1 − xi︸ ︷︷ ︸=:mi

·(x − xi) + yi

auf, dann gilt insgesamt:

p(x) =n−1∑i=1

pi(x) · 1[xi ,xi+1](x).

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–20

Page 38: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Lokale Interpolationsmethoden (III) — Catmull-Rom

Wir finden dann auf jedemTeilintervall Ti := [xi, xi+1]das (eindeutige) kubischePolynom, welches in denEndpunkten neben denStützwerten auch noch diegeschätzten Ableitungeninterpoliert. Ableitungenwerden durch

y ′i =yi+1 − yi−1

xi+1 − xi−1

abgeschätzt.

−2 −1 1 2 3 4 5

−2−1

12345

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–21

Page 39: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Lokale Interpolationsmethoden (III) — Catmull-Rom

Man kann die kubischen Polynome auch explizit bestimmen durch dieFunktionen

pi(x) = a0·(xi+1−x)3+a1·(xi+1−x)2·(x−xi)+a2·(xi+1−x)·(x−xi)2+a3·(x−xi)

3,

wobei sich die Koeffizienten durch

a0 =yi

(xi+1 − xi)3 , a1 = 3 · a0 +y ′i

(xi+1 − xi)2 ,

a2 = 3 · a3 −y ′i+1

(xi+1 − xi)2 und a3 =yi+1

(xi+1 − xi)3

bestimmen lassen.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–22

Page 40: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Lokale Interpolationsmethoden (IV) —Fehlerabschätzungen

Sei h gegeben durchh = max

16i6n

{xi+1 − xi

}.

Dann kann man zeigen:

Verfahrensname obere Fehlerschranke „Fehlerkomplexität“

Konstante Interpolation6

|f ′(ξ)|2 · h

∈ O(h)(nearest neighbor )

Lineare Interpolation 6|f ′′(ξ)|8 · h2 ∈ O(h2)

Kubische Interpolation6

|f ′′′(ξ)|24 · h3

∈ O(h3)(catmull rom)

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–23

Page 41: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Aufgabe 1 — Polynominterpolation (II)

Page 42: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Aufgabe 1 — Polynominterpolation (II)

d) Nun sind an den Stützstellen {−3,−1, 1, 3} die Werte {−1, 1, 2, 2}gegeben. Skizzieren Sie das mittlere Segment desCatmull-Rom-Interpolanten.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–25

Page 43: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Rekapitulation — Freiformmodellierung mit Bézier-kurven

Page 44: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bernsteinpolynombasen

Definiere

Bni (x) :=

(ni

)· (1 − x)n−i · x i für 0 6 i 6 n,

so spannen diese Polynome ebenfalls den Polynomraum Pn auf. Man nenntdie Bn

i auch Bernsteinpolynome.

Eigenschaften dieser Polynome:

� Für t ∈ [0, 1] gilt, dass 0 6 Bni (t) 6 1

� Bni (t) hat eine i−fache Nullstelle in t = 0 und (n − i)-fache in t = 1.

� Für alle t gilt, dass∑n

i=0 Bni (t) = 1

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–27

Page 45: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bernsteinpolynombasen

Definiere

Bni (x) :=

(ni

)· (1 − x)n−i · x i für 0 6 i 6 n,

so spannen diese Polynome ebenfalls den Polynomraum Pn auf. Man nenntdie Bn

i auch Bernsteinpolynome.

Eigenschaften dieser Polynome:� Für t ∈ [0, 1] gilt, dass 0 6 Bn

i (t) 6 1

� Bni (t) hat eine i−fache Nullstelle in t = 0 und (n − i)-fache in t = 1.

� Für alle t gilt, dass∑n

i=0 Bni (t) = 1

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–27

Page 46: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bernsteinpolynombasen

Definiere

Bni (x) :=

(ni

)· (1 − x)n−i · x i für 0 6 i 6 n,

so spannen diese Polynome ebenfalls den Polynomraum Pn auf. Man nenntdie Bn

i auch Bernsteinpolynome.

Eigenschaften dieser Polynome:� Für t ∈ [0, 1] gilt, dass 0 6 Bn

i (t) 6 1� Bn

i (t) hat eine i−fache Nullstelle in t = 0 und (n − i)-fache in t = 1.

� Für alle t gilt, dass∑n

i=0 Bni (t) = 1

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–27

Page 47: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bernsteinpolynombasen

Definiere

Bni (x) :=

(ni

)· (1 − x)n−i · x i für 0 6 i 6 n,

so spannen diese Polynome ebenfalls den Polynomraum Pn auf. Man nenntdie Bn

i auch Bernsteinpolynome.

Eigenschaften dieser Polynome:� Für t ∈ [0, 1] gilt, dass 0 6 Bn

i (t) 6 1� Bn

i (t) hat eine i−fache Nullstelle in t = 0 und (n − i)-fache in t = 1.� Für alle t gilt, dass

∑ni=0 Bn

i (t) = 1

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–27

Page 48: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bernsteinpolynombasen

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

1

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–28

Page 49: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven

ZielKleine Änderungen an einzelnen Stützwerten, sollen nur geringe lokale Auswirkun-gen haben.

Eine Approximationstechnik, welche diese Eigenschaft besitzt ist dieBézierkurve. Gegeben eine Menge an Kontrollpunkten bi ∈ Rd mit 0 6 i 6 n,nennen wir die Kurve C ⊆ Rd Bézierkurve vom Grad n, wenn

C(t) =n∑

i=0

bi · Bni (t) mit t ∈ [0, 1].

Der Polygonzug aus denKontrollpunkten bezeich-net man als das zurBézierkurve gehöhrendeKontrollpolygon.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–29

Page 50: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Eigenschaften

(1) Interpolation der Endpunkte Es muss gelten, dass

C(0) = b0 und C(1) = bn.

(2) Tangentiale Tangentenbedingung In den Endpunkten nähert sich dieKurve tangential an das Kontrollpolygon an, es gilt also

C ′(0) = n(b1 − b0) und C ′(1) = n(bn − bn−1)

(3) Konvexe Hülle Die Bézierkurve liegt in der konvexen Hülle derKontrollpunkte. Die konvexe Hülle einer Menge M ist die kleinsteObermenge M ′ von M, welche ebenfalls konvex ist.

(4) Affine Invarianz Eine affine Abbildung ist mit Φ(x) = Ax + b gegeben,um eine Bézierkurve affin zu transformieren müssen bloß dieKontrollpunkte affin transformiert werden.

(5) Variationsreduzierend Für jede Gerade g gilt, dass die Anzahl anSchnittpunkten von g mit der Kurve kleiner oder gleich der Anzahl anSchnittpunkten von g mit dem Kontrollpolygon ist.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–30

Page 51: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Eigenschaften

(1) Interpolation der Endpunkte Es muss gelten, dass

C(0) = b0 und C(1) = bn.

(2) Tangentiale Tangentenbedingung In den Endpunkten nähert sich dieKurve tangential an das Kontrollpolygon an, es gilt also

C ′(0) = n(b1 − b0) und C ′(1) = n(bn − bn−1)

(3) Konvexe Hülle Die Bézierkurve liegt in der konvexen Hülle derKontrollpunkte. Die konvexe Hülle einer Menge M ist die kleinsteObermenge M ′ von M, welche ebenfalls konvex ist.

(4) Affine Invarianz Eine affine Abbildung ist mit Φ(x) = Ax + b gegeben,um eine Bézierkurve affin zu transformieren müssen bloß dieKontrollpunkte affin transformiert werden.

(5) Variationsreduzierend Für jede Gerade g gilt, dass die Anzahl anSchnittpunkten von g mit der Kurve kleiner oder gleich der Anzahl anSchnittpunkten von g mit dem Kontrollpolygon ist.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–30

Page 52: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Eigenschaften

(1) Interpolation der Endpunkte Es muss gelten, dass

C(0) = b0 und C(1) = bn.

(2) Tangentiale Tangentenbedingung In den Endpunkten nähert sich dieKurve tangential an das Kontrollpolygon an, es gilt also

C ′(0) = n(b1 − b0) und C ′(1) = n(bn − bn−1)

(3) Konvexe Hülle Die Bézierkurve liegt in der konvexen Hülle derKontrollpunkte. Die konvexe Hülle einer Menge M ist die kleinsteObermenge M ′ von M, welche ebenfalls konvex ist.

(4) Affine Invarianz Eine affine Abbildung ist mit Φ(x) = Ax + b gegeben,um eine Bézierkurve affin zu transformieren müssen bloß dieKontrollpunkte affin transformiert werden.

(5) Variationsreduzierend Für jede Gerade g gilt, dass die Anzahl anSchnittpunkten von g mit der Kurve kleiner oder gleich der Anzahl anSchnittpunkten von g mit dem Kontrollpolygon ist.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–30

Page 53: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Eigenschaften

(1) Interpolation der Endpunkte Es muss gelten, dass

C(0) = b0 und C(1) = bn.

(2) Tangentiale Tangentenbedingung In den Endpunkten nähert sich dieKurve tangential an das Kontrollpolygon an, es gilt also

C ′(0) = n(b1 − b0) und C ′(1) = n(bn − bn−1)

(3) Konvexe Hülle Die Bézierkurve liegt in der konvexen Hülle derKontrollpunkte. Die konvexe Hülle einer Menge M ist die kleinsteObermenge M ′ von M, welche ebenfalls konvex ist.

(4) Affine Invarianz Eine affine Abbildung ist mit Φ(x) = Ax + b gegeben,um eine Bézierkurve affin zu transformieren müssen bloß dieKontrollpunkte affin transformiert werden.

(5) Variationsreduzierend Für jede Gerade g gilt, dass die Anzahl anSchnittpunkten von g mit der Kurve kleiner oder gleich der Anzahl anSchnittpunkten von g mit dem Kontrollpolygon ist.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–30

Page 54: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Eigenschaften

(1) Interpolation der Endpunkte Es muss gelten, dass

C(0) = b0 und C(1) = bn.

(2) Tangentiale Tangentenbedingung In den Endpunkten nähert sich dieKurve tangential an das Kontrollpolygon an, es gilt also

C ′(0) = n(b1 − b0) und C ′(1) = n(bn − bn−1)

(3) Konvexe Hülle Die Bézierkurve liegt in der konvexen Hülle derKontrollpunkte. Die konvexe Hülle einer Menge M ist die kleinsteObermenge M ′ von M, welche ebenfalls konvex ist.

(4) Affine Invarianz Eine affine Abbildung ist mit Φ(x) = Ax + b gegeben,um eine Bézierkurve affin zu transformieren müssen bloß dieKontrollpunkte affin transformiert werden.

(5) Variationsreduzierend Für jede Gerade g gilt, dass die Anzahl anSchnittpunkten von g mit der Kurve kleiner oder gleich der Anzahl anSchnittpunkten von g mit dem Kontrollpolygon ist.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–30

Page 55: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Eigenschaften

(1) Interpolation der Endpunkte Es muss gelten, dass

C(0) = b0 und C(1) = bn.

(2) Tangentiale Tangentenbedingung In den Endpunkten nähert sich dieKurve tangential an das Kontrollpolygon an, es gilt also

C ′(0) = n(b1 − b0) und C ′(1) = n(bn − bn−1)

(3) Konvexe Hülle Die Bézierkurve liegt in der konvexen Hülle derKontrollpunkte. Die konvexe Hülle einer Menge M ist die kleinsteObermenge M ′ von M, welche ebenfalls konvex ist.

(4) Affine Invarianz Eine affine Abbildung ist mit Φ(x) = Ax + b gegeben,um eine Bézierkurve affin zu transformieren müssen bloß dieKontrollpunkte affin transformiert werden.

(5) Variationsreduzierend Für jede Gerade g gilt, dass die Anzahl anSchnittpunkten von g mit der Kurve kleiner oder gleich der Anzahl anSchnittpunkten von g mit dem Kontrollpolygon ist.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–30

Page 56: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (I)

Algorithmus 6.2 (Auswertungsalgorithmus nach DE CASTELJAU)Eingabe : Kontrollpunkte bi mit 0 6 i 6 n und Stelle t ∈ [0, 1].Ausgabe : Wert C(t)

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do4 for i ← k to n do5 bk

i ← (1 − t) · bk−1i−1 + t · bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–31

Page 57: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

()()()()

()()()

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do4 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 58: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()()()

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do4 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 59: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()()()

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do4 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 60: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()()()

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 14 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 61: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()()()

()()

()1/3

2/3 1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 14 for i ← k to n do // i = 15 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 62: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()()(

06

)

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 14 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 63: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()()(

06

)

()()

()1/3

2/3

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 14 for i ← k to n do // i = 25 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 64: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()(

30

)(

06

)

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 14 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 65: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

()(

30

)(

06

)

()()

()1/3

2/3

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 14 for i ← k to n do // i = 35 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 66: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do4 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 67: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 24 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 68: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

()()

()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 24 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 69: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

()(

14

)()1/3

2/3

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 24 for i ← k to n do // i = 25 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 70: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

()(

14

)()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 24 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 71: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

(51/32/3

)(

14

)()

1/3

2/3

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 24 for i ← k to n do // i = 35 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 72: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

(51/32/3

)(

14

)()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do4 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 73: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

(51/32/3

)(

14

)()

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 34 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 74: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

(51/32/3

)(

14

)(

22/9

3

)1/3

2/3

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do // k = 34 for i ← k to n do // i = 35 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 75: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Rechnerische Lösung:

(126

)(

90

)(

00

)(

09

)

(102

)(

30

)(

06

)

(51/32/3

)(

14

)(

22/9

3

)Damit ist C(1/3) durch (22/9 , 10/3)T gege-ben.

1 B← (bik)06i6n06k6n

2 b00:n ← b0:n.

3 for k ← 1 to n do4 for i ← k to n do5 bk

i ← (1− t) ·bk−1i−1 + t ·bk−1

i6 end for7 end for8 return bn

n

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–32

Page 76: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–33

Page 77: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Graphische Lösung:

2 4 6 8 10 12

2

4

6

8

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–33

Page 78: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Graphische Lösung:

2 4 6 8 10 12

2

4

6

8

1/3

2/3

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–33

Page 79: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Graphische Lösung:

2 4 6 8 10 12

2

4

6

8

1/3

2/3

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–33

Page 80: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Graphische Lösung:

2 4 6 8 10 12

2

4

6

8

1/3

2/3

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–33

Page 81: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Graphische Lösung:

2 4 6 8 10 12

2

4

6

8

1/3

2/3

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–33

Page 82: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Bézierkurven — Auswertung über DE CASTELJAU (II)

Sei eine kubische Bézier-Kurve mit den Kontrollpunkten

b0 =

(09

)b1 =

(00

)b2 =

(90

)und b3 =

(117

)gegeben. Werten Sie die Kurve an t = 1/3 aus.Graphische Lösung:

2 4 6 8 10 12

2

4

6

8

1/3

2/3

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–33

Page 83: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Rekapitulation — Multivariate Interpolation

Page 84: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Baryzentrische KoordinatenSeien drei Punkte R,S,T in der Ebene ge-geben, die nicht auf einer Geraden liegen.Dann lässt sich ein jeder Punkt P der Ebe-ne eindeutig darstellen durch

P = ρ · R + σ · S + τ · T ,

wobei ρ + σ + τ = 1 gelten muss. DasTupel (ρ, σ, τ) heißt dann baryzentrischeKoordinate von P bezüglich ∆(R,S,T ).

τ = 0

ρ=

0

σ=

0

ρ,σ,τ>

0

R S

T

τw

ird

größ

er

τw

ird

kleiner

ρ wird

größerρ wird

kleiner

σwirdgrößer

σwirdkleiner

Die Koordinaten werden über das Lösen des Gleichungssystems 1 1 1xR xS xT

yR yS yT

·ρστ

=

1xP

yP

mittels LR-Zerlegung.Zudem gilt:

ρ =area(∆(P,S,T ))

area(∆(R,S,T )), σ =

area(∆(R,P,T ))

area(∆(R,S,T ))und τ =

area(∆(R,S,P))

area(∆(R,S,T ))

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–35

Page 85: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Baryzentrische Koordinaten — Lineare Interpolation

Lineare InterpolationSeien nun in den Eckpunkten des Dreiecks ∆(R,S,T ) die Dtaen fR, fS und fT ge-geben, so erhält man den Wert des linearen Interpolanten an einer Stelle P ∈∆(R,S,T ) durch

fP = ρ · fR + σ · fS + τ · fT ,wobei ρ, σ, τ die baryzentrischen Koordinaten von P bezüglich ∆(R,S,T ) sind.

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–36

Page 86: Übung zu Algorithmik kontinuierlicher Systeme ...yq53ykyr/AlgoKS/slides/slides06.pdf · Übung zu Algorithmik kontinuierlicher Systeme Übung 6 – Bézierkurven und Interpolation

Baryzentrische Koordinaten — Teilungsverhältnis undVorzeichen

SS 2019 | Florian Frank | FAU | TutAlgoKS – Bézierkurven und Interpolation 6–37