Benutzer:Georg-Johann/Von Punkt zu Punkt

Für eine Anzahl vorgegebener Punkte $P_{1}$ , ... $P_{n}$ soll eine geschlossene Kurve gefunden werden, welche die Punkte in der gegebenen Reihenfolge approximiert. Vom letzten Punkt $P_{n}$ soll eine Linie zum Anfangspunkt $P_{1}$ zurückführen, und zwischen den Punkten soll die Kurve einen möglichst "natürlichen" Verlauf zeigen.

Das Bild zeigt 17 Punkte, die wie bei einem Punkt-zu-Punkt-Bild miteinander zu verbinden sind, wobei der Linienschluß durch einen weiteren Punkt $P_{18}$ = $P_{1}$ zustande käme.

Interpolation

Für ein gegebenes $n$ -Tupel von Punkten $(P_{k})_{n}\in \mathbb {R} ^{d}$ soll eine geschlossene Kurve gefunden werden, welche die Punkte in der gegebenen Reihenfolge approximiert. Dazu bestimmen wir zunächst eine Interpolation $I:S_{1}\to \mathbb {R} ^{d}$ durch die $n$ Vorgabepunkte:

I(t_{k})=P_{k}\quad \mathrm {f{\ddot {u}}r} \quad k=1\ldots n

Als Interpolationsverfahren zur Berechnung von $I$ bieten sich mehrere Standardverfahren an wie lineare Interpolation oder kubische Splines mit periodischer Anschlussbedingung. Das gewählte Interpolationsverfahren verwenden wir komponentenweise.

Tatsächlich hängt $I$ nicht nur von dem gewählten Interpolationsverfahren und dem Parameter $t$ ab, sondern auch von der Wahl der "Zeitpunkte" $t_{k}$ an denen $I$ die Werte $P_{k}$ annehmen soll:

{\begin{aligned}I:\,S_{1}\times S_{1}^{n}&\to \mathbb {R} ^{d}\\(t,(t_{k})_{n})&\mapsto I(t;t_{1}\ldots t_{n})\end{aligned}}

Die Reihenfolge, in der die Zielpunkte durchlaufen werden, ergibt sich durch die Nebenbedingungen

t_{k}>t_{k-1}\quad \mathrm {f{\ddot {u}}r} \quad k=2\ldots n

Vorbesetzung der Zeitpunkte

Eine erste Belegung für die Zeitpunkte $(t_{k})_{n}$ erhalten wir durch

t_{k}={\frac {\sum _{j=1}^{k}\delta (j)}{\sum _{j=1}^{n}\delta (j)}}\quad \mathrm {f{\ddot {u}}r} \quad k=1\ldots n

etwa mit $\delta _{\infty }={\tfrac {1}{n}}$ und damit $t_{k}={\tfrac {k}{n}}$ . Die Zeitpunkte werden dadurch in gleichen Abständen auf der Zeitachse angeordnet.

Eine weitere Vorbelegung ergibt sich mittels $\delta _{0}(j)=\|P_{j}-P_{j-1}\|$ mit $P_{0}$ := $P_{n}$ , d.h. die Zeitabstände entsprechen den Abständen der Zielpunkte im Raum. Diese beiden Belegungen lassen sich auch kombinieren, indem wir die $d$ -dimensionalen Startpunkte in $S_{1}\times \mathbb {R} ^{d}$ einbetten und ihre (gleichen) Zeitabstände mit berücksichtigen. Dies ergibt schliesslich die Wahl

\delta _{\sigma }(j)=\|({\tfrac {\sigma }{n}},P_{j}-P_{j-1})\|

mit einem Skalierungsfaktor $\sigma$ . Die ersten beiden Wahlen für $\delta$ ergeben sich daraus für die Grenzfälle $\sigma \to \infty$ bzw. $\sigma =0$ .

Die Galerie zeigt den Einfluß des gewählten Interpolationsverfahrens und der Wahl der Startbelegung auf $I$ .

Unterschiedliche Interpolationsverfahren und Startbelegungen
Linear und $\delta =\delta _{\infty }$
Spline und $\delta =\delta _{\infty }$
Spline und $\delta =\delta _{0}\,$

Approximation

Bei der Wahl der Interpolation $I$ bleibt uns – unter Beachtung der Reihenfolge der Zeitpunkte – die freie Wahl der Zeitpunkte $t_{k}$ . Da immer gilt $t_{n}=1$ , bleiben also $n-1$ Parameter, um die eingangs geforderte Eigenschaft der "natürlichen" Approximation zu erfüllen. Wie oben zu sehen hat neben der Wahl des Interpolationsverfahrens auch die Wahl der Zeitpunkte einen starken Einfluß auf das Erscheinungsbild der erhaltenen Kurve.

Durch Variation der Zeitpunkte soll nun eine Approximation berechnet werden. Die Idee ist, die diskrete Fourier-Transformation (DFT) der Interpolierten als Bewertungskriterium zu verwenden. Dazu verwenden wir $m$ Stützstellen $\tau _{m}$ mit

\tau _{j}={\tfrac {j}{m}}\quad \mathrm {f{\ddot {u}}r} \quad j=1\ldots m\quad {\text{und}}\quad m\geqslant n

Das durch die Fourier-Transformation erhaltene trigonometrische Polynom $F\{I\}$ hat dann die Eigenschaft

F\{I\}(\tau _{j})=I(\tau _{j})\quad \mathrm {f{\ddot {u}}r} \quad j=1\ldots m

und liefert damit eine Approximation der Vorgabepunkte:

F\{I\}(t_{k})\approx P_{k}\quad \mathrm {f{\ddot {u}}r} \quad k=1\ldots n

Die Fourier-Transformierte berechnen wir komponentenweise für die $d$ Koordinaten

F\{I\}={(F_{i}\{I\})}_{d}\quad {\text{mit}}\quad F_{i}\{I\}=A_{i,0}+\sum _{k=1}^{m/2}A_{i,k}\cdot \cos \,(2\pi kt+\phi _{i,k})

und mit einer Zweierpotenz für $m$ . Durch die Wahl einer Zweierpotenz für $m$ lässt sich die diskrete Fourier-Transformierte effizient durch das Verfahren der schnellen Fourier-Transformation (FFT) bestimmen.

Bewertung

Eine Approximation bewerten wir mit einer Bewertungsfunktion anhand der Amplituden in den DFTs ihrer $d$ Komponenten:

{\begin{aligned}\mu :\quad S_{1}^{n}&\to \mathbb {R} ^{\geqslant 0}\\(t_{k})_{n}&\mapsto \sum _{i}\sum _{k}A_{i,k}^{\alpha }k^{\beta }\end{aligned}}

mit zwei Parametern α und $\beta$ . Gute Ergebnisse ergeben sich mit α ≈ 0.9 und $\beta =1$ . Durch die Wahl $\alpha <1$ erhält der $A$ -Terme eine Rechtskrümmung, so daß Amplituden, die ohnehin schon klein sind, zu Null tendieren. Für große Amplituden hingegen fällt eine Änderung weniger stark ins Gewicht. Zusammen mit dem $k$ -Term, der zur Verteurung hoher Frequenzen führt, tendiert die Bewertung zu niedrigfrequenten Approximationen.