diff options
Update markdown syntax to use pandoc's peculiarities
Diffstat (limited to 'articles/2016-05-22_visualisierung_von_metriken_in_voronoi_diagrammen.md')
| -rw-r--r-- | articles/2016-05-22_visualisierung_von_metriken_in_voronoi_diagrammen.md | 84 |
1 files changed, 42 insertions, 42 deletions
diff --git a/articles/2016-05-22_visualisierung_von_metriken_in_voronoi_diagrammen.md b/articles/2016-05-22_visualisierung_von_metriken_in_voronoi_diagrammen.md index 2b05dc9..accb083 100644 --- a/articles/2016-05-22_visualisierung_von_metriken_in_voronoi_diagrammen.md +++ b/articles/2016-05-22_visualisierung_von_metriken_in_voronoi_diagrammen.md @@ -4,16 +4,18 @@ In der Analysis 2 Vorlesung meines Mathematik Studiums beschäftigen wir uns der ## Normen und Metriken in endlichdimensionalen Vektorräumen -In der herkömmlichen Schulmathematik sowie alltäglichen Rechnungen definieren wir Begriffe wie die Größe einer Zahl und den Abstand zwischen zwei Zahlen implizit über deren Betrag beziehungsweise die Differenz $$\vert a-b \vert$$ mit $$a, b \in \mathbb{R}$$ [^1]. Diese implizite, ja _intuitive_ Definition der genannten Begriffe reicht für vieles aus, gelangt aber schnell an ihre Grenzen, wenn wir das Ganze, im Rahmen der mathematischen Arbeit des Beweisens, auf formale Grundlagen stellen und als Fundament für Aussagen in anderen Mengen als den herkömmlichen Zahlen nutzen wollen. +In der herkömmlichen Schulmathematik sowie alltäglichen Rechnungen definieren wir Begriffe wie die Größe einer Zahl und den Abstand zwischen zwei Zahlen implizit über deren Betrag beziehungsweise die Differenz $\vert a-b \vert$ mit $a, b \in \mathbb{R}$ [^1]. Diese implizite, ja _intuitive_ Definition der genannten Begriffe reicht für vieles aus, gelangt aber schnell an ihre Grenzen, wenn wir das Ganze, im Rahmen der mathematischen Arbeit des Beweisens, auf formale Grundlagen stellen und als Fundament für Aussagen in anderen Mengen als den herkömmlichen Zahlen nutzen wollen. -Mit nicht herkömmlichen Zahlen meine ich dabei Elemente aus Vektorräumen[^2] wie $$\mathbb{R}^2$$. Zumindest für diesen, mittels eines Kartesischen Koordinatensystems als zweidimensionale Ebene darstellbaren, Vektorraum, haben wir in der Schule eine Vorstellung bekommen. Dies trifft sich gut, da sich auch die Visualisierung von Metriken mittels Voronoi-Diagrammen in diesem Raum abspielen wird. +Mit nicht herkömmlichen Zahlen meine ich dabei Elemente aus Vektorräumen[^2] wie $\mathbb{R}^2$. Zumindest für diesen, mittels eines Kartesischen Koordinatensystems als zweidimensionale Ebene darstellbaren, Vektorraum, haben wir in der Schule eine Vorstellung bekommen. Dies trifft sich gut, da sich auch die Visualisierung von Metriken mittels Voronoi-Diagrammen in diesem Raum abspielen wird. -Betrachten wir zunächst den Begriff der Größe oder auch des Betrags einer Zahl. Dieser wird für Elemente eines Vektorraums, also Vektoren, über Normen beschrieben. Eine Norm ist dabei formal eine Abbildung $$\| \cdot \| : V \rightarrow \mathbb{R}_{\geq0}$$, also eine Funktion, die Elementen aus einem $$\mathbb{K}$$-Vektorraum $$V$$[^3] einen reellen Wert größer oder gleich Null zuordnet. -Diese Funktion darf dabei nicht vollkommen beliebig definiert sein, sondern muss für $$x, y \in V$$ sowie $$\alpha \in \mathbb{K}$$ die folgenden Bedingungen erfüllen: +Betrachten wir zunächst den Begriff der Größe oder auch des Betrags einer Zahl. Dieser wird für Elemente eines Vektorraums, also Vektoren, über Normen beschrieben. Eine Norm ist dabei formal eine Abbildung $\| \cdot \| : V \rightarrow \mathbb{R}_{\geq0}$, also eine Funktion, die Elementen aus einem $\mathbb{K}$-Vektorraum $V$[^3] einen reellen Wert größer oder gleich Null zuordnet. +Diese Funktion darf dabei nicht vollkommen beliebig definiert sein, sondern muss für $x, y \in V$ sowie $\alpha \in \mathbb{K}$ die folgenden Bedingungen erfüllen: -|Definitheit |$$\|x\|=0 \Leftrightarrow x=0$$ | -|Homogenität |$$\|\alpha * x\|=\alpha * \|x\|$$| -|Dreiecksungleichung|$$\|x+y\| \leq \|x\| + \|y\|$$ | +------------------- ------------------------------- +Definitheit $\|x\|=0 \Leftrightarrow x=0$ +Homogenität $\|\alpha * x\|=\alpha * \|x\|$ +Dreiecksungleichung $\|x+y\| \leq \|x\| + \|y\|$ +------------------- ------------------------------- Diese Anforderungen bedeuten, dass eine Funktion genau dann als Norm gesehen werden kann, wenn sie nur den Nullvektor auf die reelle Null abbildet, Skalare analog zu linearen Ausrücken _herausgezogen_ werden können und ein Umweg zwischen zwei Punkten nie kürzer ist, als der direkte Verbindungsweg. @@ -21,48 +23,50 @@ Betrachten wir an dieser Stelle die Defintion der häufig verwendeten Klasse der $$\|x\|_p := \left(\displaystyle\sum_{i=1}^{n} \vert x_i \vert ^p\right)^\frac{1}{p} \; \text{mit} \; x \in \mathbb{R}^n ,\; p \in \mathbb{R_{\geq1}}$$ -Beachtenswerter Weise geht aus dieser Norm für $$p=1$$ die Betragsnorm, also die Aufsummierung aller Komponentenbeträge des gegebenen Vektors, sowie für $$p=2$$ die sogenannte Euklidische Norm hervor. Durch Verschieben von $$p$$ im Intervall $$[1, \infty]$$ lässt sich dabei die charakteristische Rautenform der Einheitskugel[^4] der Betragsnorm über die tatsächlich kugelförmige Einheitskugel der Euklidischen Norm in die quadratische Form der Maximumsnorm überführen ($$p \rightarrow \infty$$). +Beachtenswerter Weise geht aus dieser Norm für $p=1$ die Betragsnorm, also die Aufsummierung aller Komponentenbeträge des gegebenen Vektors, sowie für $p=2$ die sogenannte Euklidische Norm hervor. Durch Verschieben von $p$ im Intervall $[1, \infty]$ lässt sich dabei die charakteristische Rautenform der Einheitskugel[^4] der Betragsnorm über die tatsächlich kugelförmige Einheitskugel der Euklidischen Norm in die quadratische Form der Maximumsnorm überführen ($p \rightarrow \infty$).  -Kommen wir nun zum Begriff des Abstands zwischen zwei Zahlen, welcher in Form von Metriken auf algebraische Strukturen wie Vektorräume übertragen wird. Wie in der Einführung dieses Abschnits beschrieben, haben wir den Abstand zwischen Zahlen schon in der Schule über den Betrag der Differenz beschrieben. Wir kennen an dieser Stelle in Form des Satz des Pythagoras auch schon eine sinnvolle Definition für den Abstand zwischen Punkten in $$\mathbb{R}^2$$: +Kommen wir nun zum Begriff des Abstands zwischen zwei Zahlen, welcher in Form von Metriken auf algebraische Strukturen wie Vektorräume übertragen wird. Wie in der Einführung dieses Abschnits beschrieben, haben wir den Abstand zwischen Zahlen schon in der Schule über den Betrag der Differenz beschrieben. Wir kennen an dieser Stelle in Form des Satz des Pythagoras auch schon eine sinnvolle Definition für den Abstand zwischen Punkten in $\mathbb{R}^2$: $$d(x,y) := \sqrt{\vert x_1-x_2 \vert ^2 - \vert y_1-y_2 \vert ^2} \; \text{mit} \; x, y \in \mathbb{R}^2$$ -Diese Metrik über dem zweidimensionalen reellen Vektorraum lässt sich, auf folgende naheliegende Art und Weise, in eine Metrik für alle endlich dimensionalen $$\mathbb{R}$$-Vektorräume erweitern: +Diese Metrik über dem zweidimensionalen reellen Vektorraum lässt sich, auf folgende naheliegende Art und Weise, in eine Metrik für alle endlich dimensionalen $\mathbb{R}$-Vektorräume erweitern: $$d(x,y) := \sqrt{\displaystyle\sum_{i=1}^{n} \vert x_i - y_i \vert ^2} \; \text{mit} \; x, y \in \mathbb{R}^n$$ Diese Metrik auf Grundlage des Satz des Pythagoras wird als Euklidische Metrik bezeichnet. Sie ist eine der Metriken, welche wir im weiteren Verlauf dieses Artikels in Voronoi-Diagrammen visualisieren werden. -Die Definition solcher Metriken als Abbildungen der Form $$d(x,y) : V \times V \rightarrow \mathbb{R}_{\geq0}$$ beinhaltet eine Menge von Axiomen, welche von der Metrik-Abbildung erfüllt sein müssen. +Die Definition solcher Metriken als Abbildungen der Form $d(x,y) : V \times V \rightarrow \mathbb{R}_{\geq0}$ beinhaltet eine Menge von Axiomen, welche von der Metrik-Abbildung erfüllt sein müssen. -|Positive Definitheit|$$d(x,y) \geq 0 \land d(x,y)=0 \Leftrightarrow x=y$$| -|Symmetrie |$$d(x,y) = d(y,x)$$| -|Dreiecksungleichung |$$d(x,z) \leq d(x,y) + d(y,z)$$| +-------------------- -------------------------------------------------- +Positive Definitheit $d(x,y) \geq 0 \land d(x,y)=0 \Leftrightarrow x=y$ +Symmetrie $d(x,y) = d(y,x)$ +Dreiecksungleichung $d(x,z) \leq d(x,y) + d(y,z)$ +-------------------- -------------------------------------------------- Wir fordern also, dass der Abstand zwischen beliebigen Punkten immer größer gleich Null sein muss, ein Nullabstand äquivalent zur Gleichheit der Punkte ist, die Reihenfolge der Punkte für den Abstand irrelevant ist und das der direkte Abstand zwischen zwei Punkten kleiner gleich einem Umweg über weitere Punkte ist. -Bei der Betrachtung der Definitionen von p-Norm und Euklidischer Metrik fällt auf, dass diese sich zu ähneln scheinen. Dies ist kein Zufall, denn Metriken können aus Normen _induziert_ werden. So folgt die Euklidische Metrik mit $$d(x,y) := \|x-y\|_2$$ direkt aus der 2-Norm. +Bei der Betrachtung der Definitionen von p-Norm und Euklidischer Metrik fällt auf, dass diese sich zu ähneln scheinen. Dies ist kein Zufall, denn Metriken können aus Normen _induziert_ werden. So folgt die Euklidische Metrik mit $d(x,y) := \|x-y\|_2$ direkt aus der 2-Norm. -Es liegt also Nahe, dass auch aus die Betragsnorm mit $$p=1$$ eine Metrik induziert - die sogenannte Mannheimer-Metrik: +Es liegt also Nahe, dass auch aus die Betragsnorm mit $p=1$ eine Metrik induziert - die sogenannte Mannheimer-Metrik: $$d(x,y) := \displaystyle\sum_{i=1}^{n} \vert x_i - y_i \vert \; \text{mit} \; x, y \in \mathbb{R}^n$$ Die Bezeichnung dieser Metrik als Mannheimer-, Manhattan oder auch Taxi-Metrik wird nachvollziehbar, wenn wir uns bewusst machen, dass sie die Betragsdifferenzen der Punkte aufsummiert und somit den Weg beschreibt, den ein Taxi in einem Straßenraster nachvollziehen müsste, wie es in Mannheim und zahlreichen nordamerikanischen Städten üblich ist, um von A nach B zu gelangen. -Wir haben also nun zwei Metriken kennengelernt, die beide für verschiedene $$p$$ aus der gleichen p-Norm hervorgehen. Die Mathematik charakterisierende Suche nach gemeinsamen Mustern in abstrakten Strukturen legt nahe, dass so, wie die Betragsnorm und die Euklidische Norm Varianten der allgemeineren Klasse der p-Normen sind, auch die Mannheimer und Euklidische Metrik Varianten einer allgemeineren Klasse von Metriken sind. Diese allgemeinere Klasse beschreiben wir in Form der Minkowski-Metrik: +Wir haben also nun zwei Metriken kennengelernt, die beide für verschiedene $p$ aus der gleichen p-Norm hervorgehen. Die Mathematik charakterisierende Suche nach gemeinsamen Mustern in abstrakten Strukturen legt nahe, dass so, wie die Betragsnorm und die Euklidische Norm Varianten der allgemeineren Klasse der p-Normen sind, auch die Mannheimer und Euklidische Metrik Varianten einer allgemeineren Klasse von Metriken sind. Diese allgemeinere Klasse beschreiben wir in Form der Minkowski-Metrik: $$d(x,y) := \left(\displaystyle\sum_{i=1}^{n} \vert x_i - y_i \vert ^p\right)^\frac{1}{p} \; \text{mit} \; x, y \in \mathbb{R}^n ,\; p \in \mathbb{R_+}$$ -Die Beschreibung der Euklidischen und Mannheimer-Metrik als Varianten der Minkowski-Metrik ist damit gerechtfertigt, dass diese für $$p=1$$ beziehungsweise $$p=2$$ aus ihr hervorgehen. +Die Beschreibung der Euklidischen und Mannheimer-Metrik als Varianten der Minkowski-Metrik ist damit gerechtfertigt, dass diese für $p=1$ beziehungsweise $p=2$ aus ihr hervorgehen. -Besonders interessant ist im Kontext der Visualisierung von Metriken, dass die Minkowski-Metrik für $$p \in [1, 2]$$ einen stetigen Übergang von der Mannheimer in die Euklidische Metrik ermöglicht. Dies ergibt schöne, _flüssige_ Voronoi-Diagramme, wie wir im Abschnitt zu bewegten Bildern sehen werden. +Besonders interessant ist im Kontext der Visualisierung von Metriken, dass die Minkowski-Metrik für $p \in [1, 2]$ einen stetigen Übergang von der Mannheimer in die Euklidische Metrik ermöglicht. Dies ergibt schöne, _flüssige_ Voronoi-Diagramme, wie wir im Abschnitt zu bewegten Bildern sehen werden. -[^1]: $$\mathbb{R}$$ könnte an dieser Stelle auch die Menge $$\mathbb{N}$$ der natürlichen Zahlen, die Menge $$\mathbb{C}$$ der komplexen Zahlen oder ein beliebiger anderer Körper sein, für den der Betrag definiert ist. -[^2]: Ein Vektorraum ist eine Menge von Vektoren gleicher Dimension, für welche die Operationen der Vektoraddition und Skalarmultiplikation sinnvoll definiert sind. Eine sinnvolle Definition dieser Operationen schließt neben einigen Rechenregeln mit ein, dass ein unter der Addition neutrales Element, der Nullvektor, sowie ein unter der Skalarmultiplikation neutraler Skalar, das Einselement, existieren. Zusätzlich muss zu jedem Vektor ein bezüglich der Addition inverses Element existieren, d.h. ein $$v \in V$$ mit $$v + -v = 0$$. Zusammenfassend führen diese Anforderungen dazu, dass innerhalb eines Vektorraums in weitgehend gewohnter Art und Weise gerechnet werden kann. -[^3]: Der Begriff $$\mathbb{K}$$-Vektorraum sagt aus, dass alle Komponenten der enthaltenen Vektoren Elemente aus dem Körper $$\mathbb{K}$$ sind. Im Falle eines $$\mathbb{R}$$-Vektorraums sind also beispielsweise alle Komponenten aller Vektoren reelle Zahlen. Der Körper ist dabei auch die Menge, aus der die Skalare für die Skalarmultiplikation gegriffen werden. -[^4]: Die abgeschlossene Einheitskugel ist die Menge $$\overline{B}(1,0) := \{x \in V \vert \|x\| \leq 1 \}$$ - also die Menge aller Vektoren mit Länge kleiner gleich Eins. Die Visualisierung dieser Kugel kann zur Charakterisierung von Normen herangezogen werden. +[^1]: $\mathbb{R}$ könnte an dieser Stelle auch die Menge $\mathbb{N}$ der natürlichen Zahlen, die Menge $\mathbb{C}$ der komplexen Zahlen oder ein beliebiger anderer Körper sein, für den der Betrag definiert ist. +[^2]: Ein Vektorraum ist eine Menge von Vektoren gleicher Dimension, für welche die Operationen der Vektoraddition und Skalarmultiplikation sinnvoll definiert sind. Eine sinnvolle Definition dieser Operationen schließt neben einigen Rechenregeln mit ein, dass ein unter der Addition neutrales Element, der Nullvektor, sowie ein unter der Skalarmultiplikation neutraler Skalar, das Einselement, existieren. Zusätzlich muss zu jedem Vektor ein bezüglich der Addition inverses Element existieren, d.h. ein $v \in V$ mit $v + -v = 0$. Zusammenfassend führen diese Anforderungen dazu, dass innerhalb eines Vektorraums in weitgehend gewohnter Art und Weise gerechnet werden kann. +[^3]: Der Begriff $\mathbb{K}$-Vektorraum sagt aus, dass alle Komponenten der enthaltenen Vektoren Elemente aus dem Körper $\mathbb{K}$ sind. Im Falle eines $\mathbb{R}$-Vektorraums sind also beispielsweise alle Komponenten aller Vektoren reelle Zahlen. Der Körper ist dabei auch die Menge, aus der die Skalare für die Skalarmultiplikation gegriffen werden. +[^4]: Die abgeschlossene Einheitskugel ist die Menge $\overline{B}(1,0) := \{x \in V \vert \|x\| \leq 1 \}$ - also die Menge aller Vektoren mit Länge kleiner gleich Eins. Die Visualisierung dieser Kugel kann zur Charakterisierung von Normen herangezogen werden. ## Voronoi-Diagramme @@ -70,17 +74,17 @@ Nachdem wir uns im vorangehenden Abschnitt einen groben Überblick über Normen Unter Voronoi-Diagrammen verstehen wir die Aufteilung der Euklidischen Ebene in disjunkte Teilflächen abhängig der Distanz zu einer gegebenen Menge von Punkten und gekennzeichnet durch entsprechende Einfärbung entsprechend des jeweils nächsten Punktes. -Im Falle der Euklidischen Metrik, d.h. der Minkowski-Metrik mit $$p=2$$, ergeben sich somit Grafiken wie die folgende: +Im Falle der Euklidischen Metrik, d.h. der Minkowski-Metrik mit $p=2$, ergeben sich somit Grafiken wie die folgende:  -Während wir die Definitionen der Metriken bisher im Speziellen für $$\mathbb{R}^2$$ betrachtet haben, gerät der zugrundeliegende Körper $$\mathbb{R}$$ mit der konkreten Generierung von Voronoi-Diagrammen als Pixelgrafiken in Konflikt, da wir offensichtlich nicht alle Punkte der Teilflächen bzw. Mengen darstellen können. Die naheliegendste Lösung für dieses Problem ist, die Metriken nur auf $$\mathbb{Z}^2$$ zu betrachten. Dies ist einfach möglich, da $$\mathbb{Z}^2$$ eine echte Teilmenge von $$\mathbb{R}^2$$ ist und eine triviale Bijektion zwischen Punkten in $$\mathbb{Z}^2$$ und Pixeln auf einem Bildschirm existiert. +Während wir die Definitionen der Metriken bisher im Speziellen für $\mathbb{R}^2$ betrachtet haben, gerät der zugrundeliegende Körper $\mathbb{R}$ mit der konkreten Generierung von Voronoi-Diagrammen als Pixelgrafiken in Konflikt, da wir offensichtlich nicht alle Punkte der Teilflächen bzw. Mengen darstellen können. Die naheliegendste Lösung für dieses Problem ist, die Metriken nur auf $\mathbb{Z}^2$ zu betrachten. Dies ist einfach möglich, da $\mathbb{Z}^2$ eine echte Teilmenge von $\mathbb{R}^2$ ist und eine triviale Bijektion zwischen Punkten in $\mathbb{Z}^2$ und Pixeln auf einem Bildschirm existiert.  -Die konkrete Generierung von Voronoi-Diagrammen ist dann einfach möglich - es müssen nur die Punkte der, dem gewünschten Sichtbereich entsprechenden, Teilmenge von $$\mathbb{Z}^2$$ durchlaufen und abhängig ihrer Distanz zu den Referenzpunkten unter der gewünschten Metrik eingefärbt werden. +Die konkrete Generierung von Voronoi-Diagrammen ist dann einfach möglich - es müssen nur die Punkte der, dem gewünschten Sichtbereich entsprechenden, Teilmenge von $\mathbb{Z}^2$ durchlaufen und abhängig ihrer Distanz zu den Referenzpunkten unter der gewünschten Metrik eingefärbt werden. -~~~ +```cpp double minkowski_metric( const double p, const imgen::vector& a, @@ -92,14 +96,13 @@ double minkowski_metric( 1.0 / p ); } -~~~ -{:.language-cpp} +``` -Zur Approximation der Bildmenge $$\mathbb{R}_{\geq 0}$$ der Metrik-Funktionen verwenden wir `double` Werte, während die Ursprungsmenge $$\mathbb{R}^2 \times \mathbb{R}^2$$ über zwei Tupel des Typs `std::tuple<std::ptrdiff_t, std::ptrdiff_t>` in unserer Implementierung abgebildet wird. +Zur Approximation der Bildmenge $\mathbb{R}_{\geq 0}$ der Metrik-Funktionen verwenden wir `double` Werte, während die Ursprungsmenge $\mathbb{R}^2 \times \mathbb{R}^2$ über zwei Tupel des Typs `std::tuple<std::ptrdiff_t, std::ptrdiff_t>` in unserer Implementierung abgebildet wird. -Die obige Implementierung der Minkowski Metrik in C++ genügt zusammen mit folgendem, auf einer kleinen PPM _Grafikbibliothek_ basierendem, Listing zur Generierung von Voronoi-Diagrammen über einer fixen `reference_vectors` Punktmenge für beliebige $$p$$. +Die obige Implementierung der Minkowski Metrik in C++ genügt zusammen mit folgendem, auf einer kleinen PPM _Grafikbibliothek_ basierendem, Listing zur Generierung von Voronoi-Diagrammen über einer fixen `reference_vectors` Punktmenge für beliebige $p$. -~~~ +```cpp std::pair<double, imgen::colored_vector> get_distance_to_nearest( const std::function<double(imgen::vector, imgen::vector)>& metric, const imgen::vector a @@ -144,10 +147,9 @@ void generate_minkowski_voronoi(const double p) { } ); } -~~~ -{:.language-cpp} +``` -Die Punktmenge ist dabei die, welche in obigen Beispiel Diagrammen zu betrachten ist. Alles, was wir an dieser Stelle über die zentrale Funktion `imgen::write_ppm` wissen müssen, ist, dass diese formell ein Bild über der Menge $$M := \{(x, y) \in \mathbb{Z}^2 \vert \: x \in [-\frac{w}{2}, \frac{w}{2}] \land y \in [-\frac{h}{2}, \frac{h}{2}]\}$$ mit Höhe $$h$$ und Breite $$w$$ aufspannt und für $$\forall \: (x, y) \in M$$ die gegebene Funktion $$\mathbb{Z} \times \mathbb{Z} \rightarrow [255] \times [255] \times [255]$$ aufruft, wobei die Tupel ihrer Bildmenge als Farben interpretiert werden. +Die Punktmenge ist dabei die, welche in obigen Beispiel Diagrammen zu betrachten ist. Alles, was wir an dieser Stelle über die zentrale Funktion `imgen::write_ppm` wissen müssen, ist, dass diese formell ein Bild über der Menge $M := \{(x, y) \in \mathbb{Z}^2 \vert \: x \in [-\frac{w}{2}, \frac{w}{2}] \land y \in [-\frac{h}{2}, \frac{h}{2}]\}$ mit Höhe $h$ und Breite $w$ aufspannt und für $\forall \: (x, y) \in M$ die gegebene Funktion $\mathbb{Z} \times \mathbb{Z} \rightarrow [255] \times [255] \times [255]$ aufruft, wobei die Tupel ihrer Bildmenge als Farben interpretiert werden. Zur Kennzeichnung der Referenzvektoren wird jeweils eine abgeschlossene Kugel unter der verwendeten Metrik mit Radius 5 gezogen. Dies hat den schönen Nebeneffekt, dass wir anhand der Form der Punktmarkierungen schon Rückschlüsse auf die zur Generierung verwendete Metrik ziehen können, da die Markierungen nur skalierte Versionen der Einheitskugel sind, welche wir im vorangehenden Abschnitt besprochen haben. @@ -159,7 +161,7 @@ Wie bereits angedeutet, basiert der hier gewählte Weg zur Generierung von Voron Eines der wohl einfachsten Dateiformate für Pixelgrafiken ist das **P**ortable **P**ix**M**ap Format, dass nur aus der magischen Zahl `P6` gefolgt von Zeilenumbruch-separierter Breite und Höhe sowie einem Stream der Bildpunkte bestehend aus je drei Bytes für Rot, Grün und Blau in dieser Reihenfolge besteht. Dieses primitive Format führt dazu, dass die im Beispiel verwendete `imgen::write_ppm` Funktion sehr einfach zu implementieren ist: -~~~ +```cpp void write_ppm( const std::string& path, const std::size_t width, @@ -179,8 +181,7 @@ void write_ppm( } } } -~~~ -{:.language-cpp} +``` Den inhärenten Mehraufwand der Verwendung von `std::function` zur Übergabe der Callbacks für Generierung und Metriken und der Ausgabestreams des Standards in `imgen` sowie der eigentlichen Diagram-Generierung akteptiere ich an dieser Stelle der Klarheit und des Vertrauens in den Compiler wegen. Weiterhin lässt sich die Performance von vielen repetiven Generierungen - die ohnehin nicht an der Ein-Ausgabe-Performance sondern an den konkreten Berechnungen hängt - über Multithreading in verkraftbare Schranken weisen. @@ -190,9 +191,9 @@ Das in meinen Augen schönste Resultat dieses Artikels ist die Visualisierung de  -Diese Grafik kann dabei vollautomatisch über das, auf [Imagemagick] basierende, Script [voronoi.sh] rekonstruiert werden. Da die Generierung der für die Animation notwendigen zahlreichen Einzelbilder von Voronoi-Diagrammen mit langsam ansteigendem $$p$$ etwas Zeit kosten kann, lohnt sich die Optimierung durch Aufteilen des Arbeitsaufwands auf mehrere Verarbeitungsstränge. Dies ist einfach möglich, da wir keinerlei veränderliche Daten zwischen einzelnen Voronoi-Diagrammen teilen müssen. Da der Standard mittlerweile schon seit einigen Jahren Unterstützung für Multithreading bietet, gestaltet sich auch die konkrete Umsetzung dieser Optimierung erfreulich kompakt. +Diese Grafik kann dabei vollautomatisch über das, auf [Imagemagick] basierende, Script [voronoi.sh] rekonstruiert werden. Da die Generierung der für die Animation notwendigen zahlreichen Einzelbilder von Voronoi-Diagrammen mit langsam ansteigendem $p$ etwas Zeit kosten kann, lohnt sich die Optimierung durch Aufteilen des Arbeitsaufwands auf mehrere Verarbeitungsstränge. Dies ist einfach möglich, da wir keinerlei veränderliche Daten zwischen einzelnen Voronoi-Diagrammen teilen müssen. Da der Standard mittlerweile schon seit einigen Jahren Unterstützung für Multithreading bietet, gestaltet sich auch die konkrete Umsetzung dieser Optimierung erfreulich kompakt. -~~~ +```cpp void generate_parallel_minkowski_voronoi( const unsigned int thread_count, const double lower, @@ -222,8 +223,7 @@ void generate_parallel_minkowski_voronoi( thread.join(); } } -~~~ -{:.language-cpp} +``` ## Rückblick |