Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
kurse:efcomputergrafik:kw47 [2019/11/04 11:25] Ivo Blöchliger [Grad 2 (wird selten verwendet)] |
kurse:efcomputergrafik:kw47 [2019/11/22 09:09] (current) Ivo Blöchliger [Eindeutigkeiten der Kombinationen] |
||
---|---|---|---|
Line 26: | Line 26: | ||
a) die Menge aller Linearkombinationen von $\vec u$ und $\vec v$? | a) die Menge aller Linearkombinationen von $\vec u$ und $\vec v$? | ||
+ | |||
b) die Menge aller konvexen Kombinationen 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$? | c) die Menge aller Linearkombinationen von $\vec v$? | ||
+ | |||
d) die Menge aller konvexen Kombination von $\vec v$? | d) die Menge aller konvexen Kombination von $\vec v$? | ||
+ | |||
e) die Menge aller konvexen Kombinationen von 3 Vektoren im Raum? | e) die Menge aller konvexen Kombinationen von 3 Vektoren im Raum? | ||
Line 35: | Line 39: | ||
* die Linearkombination von Linearkombinationen eine einfache Linearkombination ist. | * die Linearkombination von Linearkombinationen eine einfache Linearkombination ist. | ||
* die konvexe Kombination von konvexen Kombinationen eine einfache konvexe Kombination 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, | ||
+ | * 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 ====== | ====== Geometrische Definition von Bezierkurven ====== | ||
Line 44: | Line 62: | ||
Bestimmen Sie eine Parametrierung dieser " | Bestimmen Sie eine Parametrierung dieser " | ||
$$ | $$ | ||
- | p(t) = \text{Formel mit $p_0$, $p_1$ und $t$} =: I(t, p_0, p_1) | + | 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]$. | Die Funktion $I$ interpoliert linear zwischen $p_0$ und $p_1$ für $t \in [0,1]$. | ||
Line 51: | Line 69: | ||
Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft. | Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft. | ||
- | Verwenden Sie dazu die bereitgestellte {{ : | + | Verwenden Sie dazu die bereitgestellte {{ : |
+ | |||
+ | Für den Umgang mit der Klasse " | ||
<code python interpolation.py> | <code python interpolation.py> | ||
from gpanel import * | from gpanel import * | ||
from vector import Vector | from vector import Vector | ||
# Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen. | # Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen. | ||
+ | |||
makeGPanel(0, | makeGPanel(0, | ||
- | + | ||
- | # | + | # t in [0,1] |
- | # Hier fehlt die Definition einer oder mehrerer Funktionen | + | # p0, p1, sind Vektoren |
- | # | + | # Liefert die lineare interpolation |
+ | def interpolate(t, | ||
+ | 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 | n = 100 | ||
- | enableRepaint(False) | + | enableRepaint(False) |
- | intpts = [] | + | intpts = [Vector((0.1, |
for i in range(n+1): | for i in range(n+1): | ||
- | t=n/i | + | t=i/n |
- | clear() | + | clear() |
- | # | + | # Ganze Linie |
- | # Punkt p(t) berechnen und Situation schön anzeigen | + | linie(intpts[0], |
- | # | + | # Interpolierter |
- | repaint() | + | |
+ | # Kreiszentrum | ||
+ | kreis(p) | ||
+ | repaint() # Gezeichnetes anzeigen (vermindert flackern) | ||
delay(60) | delay(60) | ||
+ | | ||
</ | </ | ||
Line 90: | Line 124: | ||
Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft. | Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft. | ||
- | ===== Grad 3 (der quasi Standard) ===== | + | ===== Grad 3, kubische Bezierkurve |
Gegeben sind 4 **Kontrollpunkte** $p_i$ mit $i\in\{0, | Gegeben sind 4 **Kontrollpunkte** $p_i$ mit $i\in\{0, | ||
Der Punkt $p(t)$ wird wie folgt berechnet: | Der Punkt $p(t)$ wird wie folgt berechnet: | ||
- | ===== Aufgaben | + | * Man berechne $s_i(t) |
+ | * $q_i(t) | ||
+ | * $p(t) = I(q_0, q_1, t)$ | ||
+ | |||
+ | |||
+ | ==== Aufgaben | ||
=== Animation === | === Animation === | ||
Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft. | Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft. | ||
- | ===== Grad $n$ (wird selten für $n>3$ verwendet) ===== | + | <code python bezierallgemein.py> |
- | Gegeben sind $n+1$ Kontrollpunkte $p_i$ mit $i \in \{0,1,\ldots, n,n+1\}$. | + | from gpanel import * |
+ | from vector import Vector | ||
+ | import math | ||
+ | # Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen. | ||
+ | |||
+ | makeGPanel(0, | ||
+ | |||
+ | # 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) | ||
- | ===== Aufgabe | + | n = 100 |
- | Die entsprechende Animation kann für beliebige $n$ sehr elegant rekursiv programmiert werden. | + | enableRepaint(False) |
+ | #pini = [Vector((0.4, | ||
+ | num = 20; | ||
+ | # Folge von Punkten auf einer Lissajou-Figur | ||
+ | pini = [Vector([math.sin(i/ | ||
+ | kurve=[] | ||
+ | for i in range(n+1): | ||
+ | t=i/n | ||
+ | clear() | ||
+ | p = pini | ||
+ | while len(p)> | ||
+ | # Neue Punkte | ||
+ | q = [] | ||
+ | for j in range(len(p)-1): | ||
+ | linie(p[j], p[j+1]) | ||
+ | q.append(interpolate(t, | ||
+ | kreis(q[j]) | ||
+ | p = q | ||
+ | kurve.append(p[0]) | ||
+ | for k in kurve: | ||
+ | kreis(k, | ||
+ | repaint() | ||
+ | delay(60) | ||
- | ====== Algebraische Form ====== | + | </ |
- | Bestimmen Sie die algebraische Form der Bezierkurven von Grad 1,2,3 (und $n$, wer möchte), und zwar | + | |
- | als konvexe Kombination der Kontrollpunkte mit den Koeffizienten als Polynome in $t$. | + | ===== Grad $n$ (wird selten für $n>3$ verwendet) |
+ | Gegeben sind $n+1$ Kontrollpunkte | ||
+ | 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)$. | ||