Einleitende Theorie
Wir werden im folgenden Punkte im Raum mit deren Ortsvektoren gleichsetzen und als mathematische Objekte nicht mehr unterscheiden, sondern einfach als Elemente von $\mathbb{R}^3$, die Menge aller geordneten Tripel von reellen Zahlen betrachten.
Linearkombination
Gegeben ist eine Menge $V$ von (abstrakten) “Vektoren”, d.h. Dinge, die man addieren und skalieren (mit einer reellen Zahl multiplizieren) kann. Typische Beispiele:
- Vektoren (aus der Vektorgeometrie)
- Funktionen (z.B. Polynome)
Eine Linearkombination von “Vektoren” ist eine Summe von reellen Vielfachen dieser “Vektoren”: $$ r_1 v_1 + r_2 v_2 + \ldots r_n v_n \qquad \qquad \text{mit } r_i \in \mathbb{R} \text{ und } v_i \in V $$
Beispiele:
- Die Menge aller Linearkombinationen der Einheitsvektoren ergibt alle möglichen Vektoren. Man sagt, die Einheitsvektoren bilden eine Basis.
- Die Menge aller Linearkombinationen der Polynome $1,\, x,\, x^2$ ist die Menge aller möglichen Polynome bis und mit 2. Grades.
Konvexe Kombinationen
Ein konvexe Kombination ist eine Linearkombination mit der zusätzlichen Bedingung, dass die Koeffizienten $r_i$ die Bedingungen $\sum_i r_i =1$ und $r_i \in [0,1]$ erfüllen.
Aufgaben
Geometrische Interpretation
Seien $\vec u$ und $\vec v$ Vektoren im Raum. Welchen Punktemengen entspricht
a) die Menge aller Linearkombinationen von $\vec u$ und $\vec v$?
b) die Menge aller konvexen Kombinationen von $\vec u$ und $\vec v$?
c) die Menge aller Linearkombinationen von $\vec v$?
d) die Menge aller konvexen Kombination von $\vec v$?
e) die Menge aller konvexen Kombinationen von 3 Vektoren im Raum?
Wiederholte Kombinationen
Beweisen Sie dass
- die Linearkombination von Linearkombinationen eine einfache Linearkombination ist.
- die konvexe Kombination von konvexen Kombinationen eine einfache konvexe Kombination ist.
Eindeutigkeiten der Kombinationen
Gegeben ist ein Ortsvektor $\vec p$ und eine Menge von $n$ Vektoren $\vec v_i$. Angenommen $\vec p$ ist als Kombination (linear oder konvex) der Vektoren $\vec v_i$ darzustellen, dann
- ist die Linearkombination eindeutig, wenn die Vektoren linear unabhängig sind und damit einen $n$-dimensionalen Unterraum aufspannen.
- ist die konvexe Kombination eindeutig, wenn die Dimension der konvexen Hülle $n-1$ ist.
Surafel hat einen sehr eleganten Beweis geliefert. Die Idee ist, dass man die verschobenen Vektoren $\vec u_i=\vec v_i - \vec v_1$ betrachtet.
Sei $\vec p = \sum r_i \vec v_i$, mit $\sum r_i = 1$, $r_i \in [0,1]$.
Die entsprechende konvexe Kombination der Vektoren $\vec u_i$ liefert $\sum r_i(\vec v_i - \vec v_1) = \sum r_i\vec v_i - \sum r_i \vec v_1 = \vec p-\vec v_1$. Die Vektoren $\vec u_i$ für $i \geq 2$ spannen einen $n-1$-dimensionalen Unterraum auf, womit die Linearkombination $\sum_{i=2}^n r_i \vec u_i = \vec p - \vec v_1$ eindeutig ist. Damit ist der Koeffizient für $r_1$ (über die Bedingung $\sum r_i =1$) ebenfalls eindeutig.
Geometrische Definition von Bezierkurven
Eine Bezierkurve $n$-ten Grades ist definiert durch $n+1$ Kontrollpunkte. Die einzelnen Punkte auf der Kurve lassen sich durch einen Parameter $t \in [0,1]$ parametrieren.
Grad 1
Die Bezierkurve vom Grad 1 mit den Kontrollpunkten $p_0$ und $p_1$ entspricht der Menge aller konvexen Kombinationen der beiden Punkte.
Bestimmen Sie eine Parametrierung dieser “Kurve”: $$ p(t) = (1-t) \cdot p_0 + t \cdot p_1 =: I(t, p_0, p_1) $$ Die Funktion $I$ interpoliert linear zwischen $p_0$ und $p_1$ für $t \in [0,1]$.
Aufgaben
Animation
Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft.
Verwenden Sie dazu die bereitgestellte Vector-Bibliothek (die die gleichen Methoden wie die entsprechende Bibliothek in Blender zur Verfügung stellt). Starten Sie mit folgendem Code unten.
Für den Umgang mit der Klasse “Vector” studieren Sie bitten den Code am Ende der Datei vector.py (der nur dann ausgeführt wird, wenn die Datei vector.py direkt ausgeführt wird, nicht aber wenn die Datei mit “import” eingebunden wird.)
- interpolation.py
from gpanel import * from vector import Vector # Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen. makeGPanel(0,2,0,2) # t in [0,1] # p0, p1, sind Vektoren # Liefert die lineare interpolation def interpolate(t, p0, p1): return (1-t)*p0+t*p1 def linie(p0, p1): line(p0[0], p0[1], p1[0], p1[1]) def kreis(p): move(p[0], p[1]) fillCircle(0.02) n = 100 enableRepaint(False) #Waehrend dem Zeichnen nichts anzeigen intpts = [Vector((0.1,0.3,0)), Vector((1.8,1.4,0))] # Liste der zu interpolierenden 3D-Vektoren for i in range(n+1): t=i/n clear() # Bild löschen # Ganze Linie linie(intpts[0], intpts[1]) # Interpolierter Punkt p = interpolate(t,intpts[0], intpts[1]) # Kreiszentrum kreis(p) repaint() # Gezeichnetes anzeigen (vermindert flackern) delay(60)
Grad 2, quadratische Bezierkurve (habe ich selten angetroffen)
Gegeben sind 3 Kontrollpunkte $p_0$, $p_1$, $p_2$. Der Kuvenpunkt $p(t)$ wird wie folgt berechnet:
- Man berechne $q_i(t) = I(p_i, p_{i+1},t)$ für $i\in \{0,1\}$. Und daraus
- $p(t) = I(q_0, q_1, t)$
Aufgaben
Konvexe Hülle
Zeigen Sie, dass $p(t)$ immer im Dreieck $p_0$, $p_1$, $p_2$ liegt.
Tangenten
Begründen Sie plausibel, wie die Tangenten in den Punkten $p(0)$, $p(0.5)$ und $p(1)$ liegen.
Animation
Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft.
Grad 3, kubische Bezierkurve (treffe ich häufig an)
Gegeben sind 4 Kontrollpunkte $p_i$ mit $i\in\{0,1,2,3\}$. Der Punkt $p(t)$ wird wie folgt berechnet:
- Man berechne $s_i(t) = I(p_i, p_{i+1},t)$ für $i\in \{0,1,2\}$. Und daraus
- $q_i(t) = I(s_i, s_{i+1},t)$ für $i\in \{0,1\}$. Und daraus
- $p(t) = I(q_0, q_1, t)$
Aufgaben
Animation
Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft.
- bezierallgemein.py
from gpanel import * from vector import Vector import math # Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen. makeGPanel(0,2,0,2) # t in [0,1] # p0, p1, sind Vektoren # Liefert die lineare interpolation def interpolate(t, p0, p1): return (1-t)*p0+t*p1 def linie(p0, p1): line(p0[0], p0[1], p1[0], p1[1]) def kreis(p, typ=0): move(p[0], p[1]) if typ==0: circle(0.04) else: fillCircle(0.02) n = 100 enableRepaint(False) #Waehrend dem Zeichnen nichts anzeigen #pini = [Vector((0.4,0.3,0)), Vector((1.8,1.9,0)), Vector((0.2,1.8,0)), Vector((1.8,0.2,0))] # Liste der zu interpolierenden 3D-Vektoren num = 20; # Folge von Punkten auf einer Lissajou-Figur pini = [Vector([math.sin(i/num*4*math.pi)+1, math.cos(i/num*6*math.pi)+1,0]) for i in range(num)] kurve=[] for i in range(n+1): t=i/n clear() # Bild löschen p = pini while len(p)>1: # Neue Punkte q = [] for j in range(len(p)-1): linie(p[j], p[j+1]) q.append(interpolate(t, p[j], p[j+1])) kreis(q[j]) p = q kurve.append(p[0]) for k in kurve: kreis(k,1) repaint() # Gezeichnetes anzeigen (vermindert flackern) delay(60)
Grad $n$ (wird selten für $n>3$ verwendet)
Gegeben sind $n+1$ Kontrollpunkte $p_i$ mit $i \in \{0,1,\ldots, n,n+1\}$.
Man interpoliert aufeinanderfolgende Punktepaare linear und bekommt so eine Liste von $n-1$ Punkten. Mit dieser Liste verfährt man gleich, bis nur noch 1 Punkt übrig bleibt. Das ist Punkt $p(t)$.