» Notes on BlackBerry OS 10 development in 2017

October 3, 2017 | cpp development english | Adrian Kummerländer

I recently broke my seven-year streak of only using smartphones in the tradition of Nokia's fabled N900. The reason for this change was the growing age of my Jolla phone combined with my continued desire for a working physical keyboard1. In today's market overflowing with faceless, exchangeable, uninspired and uniform touch-only devices this left me no choice but to opt for the last true BlackBerry: The Passport.

Thoughts on OS 10

The BlackBerry Passport is the last device that was both manufactured by RIM and runs their QNX based OS 10 operating system. OS 10 offers everything you can expect from a state of the art smartphone operating system. Furthermore its communication stack is beyond comparison and renders any third-party mail, calendar, task and contact applications redundant - as one would expect of a device built by the erstwhile mobile handset pioneer. The system integrates perfectly with the hardware and features true multitasking that is exposed to the user in a Maemo-like fashion. One very nice feature is the keyboard's touch capability that allows for text-navigation and scroll movements without touching and thus obscuring the actual screen. Although the native app catalog obviously doesn't feature as many applications as are available on the big platforms I don't miss anything2.

QNX is a unixoid real-time operating system that is very interesting in its own right. A nice side benefit of this is the ability to run a native terminal emulator and execute cross-compiled UNIX tools in the way I got used to during my time with Maemo and Sailfish OS. Sadly BlackBerry OS 10 is deprecated and won't receive future support as the whole platform has been discontinued3.

Luckily I found the system to be very stable and feature complete. Thus I don't see any immediate problems requiring continued support - as long as I can compile and install my own code.

OS 10 application development is based mostly on C++ and Qt/QML which suits my preferences quite nicely. Additionally the default stack includes a Python 3.2 interpreter as well as the ability to install and run arbitrary APKs.

Momentics IDE

BlackBerry offers a native SDK which bundles a Eclipse-based IDE called Momentics in addition to a full set of CLI utilities spanning the full development process. Installing and running it on my preferred distribution was straight forward. The only issue I encountered was the need to manually pass the path to an older XUL runner instance:

./qde -Dorg.eclipse.swt.browser.XULRunnerPath=~/tmp/xul/xulrunner/

~/tmp/xul/xulrunner contains the extracted contents of a matching XUL runtime version 10.0 archive.

While enabling the development mode in the device's settings menu is just a toggle flick away and only requires a device password to be defined actually installing a program archive generated by Momentics requires one to register with RIM in order to be able to sign the archive. Fortunately enough this process is completely free and devoid of any further organisatory hurdles.

When I first tried to connect to my Passport via the IDE I encountered an SSL authentication error. All my attempts at solving this by temporarily disabling authentication via JVM flags failed. This issue also extended to browser based device access using e.g. BB10 App Manager which failed due to a invalid server response. In fact the only thing that worked was the SSH connection initiated via the SDK's CLI utilities:

./blackberry-connect $device_ip -password $device_password -sshPublicKey ~/.
rim/bbt_id_rsa.pub

After some investigation I was able to trace this issue to some custom system update trickery I performed during the first days of setting up the device4. Luckily this was easily solved by resetting the device to the latest OS 10 version via the official autoloader.

Momentics IDE

After solving this issue Momentics turned out to be a workable IDE that seems to be enough for most purposes. Should this turn out to be a premature assessment it will be worthwhile to check out older versions of Qt Creator which include BlackBerry 10 support. And if everything visual fails there are still the SDK's CLI utilities that allow for fully text driven packaging, signing and deployment of applications:

λ ~/t/m/b/h/l/x/u/bin ● ls | grep blackberry
blackberry-airpackager
blackberry-barchecker
blackberry-connect
blackberry-custompackager
blackberry-debugtokenrequest
blackberry-deploy
blackberry-keytool
blackberry-nativepackager
blackberry-signer
blackberry-uripackager

Device-local development

As the alert reader might have noticed everything described in the last section hinges on the continued willingness of BlackBerry to generate and distribute development certificates without which one cannot deploy applications to physical devices. This is probably one of the primary tradeoffs one makes when leaving the world of open mobile systems behind.

Luckily there is a way to cross compile, install and run arbitrary CLI programs without even enabling the development mode: mordak/playbook-dev-tools.

This set of scripts developed by the same person that wrote the premier native terminal emulator for OS 10 offers a fully automated systems that compiles and installs GCC 4.6.3 amongst further development and system utilities.

Term48

It remains to be investigated if this entry point can be expanded to device-local development of full Cascades-based UI applications.

  1. i.e. something better than the TOHKBDv2

  2. Especially since it offers an Android runtime analogously to what I am used to on Sailfish OS

  3. I am not convinced by RIM's externally manufactured Android smartphone. Neither the build quality nor the software are anywhere near to what they offered with the Passport. I fear that they will further degrade the keyboard quality in future devices and expect them to fully disappear from the market within the next couple of years.

  4. Namely impatiently forcing an OS upgrade using Sachesi

» Tinkering with meta tools

January 20, 2017 | english linux opinion | Adrian Kummerländer

If the contents of this website are of interest to you chances are that you also know how easy it is to spend large parts of one's leisure time tinkering with computer systems and improving workflows while losing sight of what one actually wants to accomplish. I am going to use this article to document parts of my current personal computing setup in an attempt to summarize and refocus my efforts in this direction in addition to articulating some of my thoughts in this context.

Working with computers is my job to the extend that computers are the machines that my software developing self instructs to - hopefully - solve actual problems in the real world™. This means that configuring and optimizing my personal computing environments is not only a leisure time activity but can be considered a productive activity within certain boundaries1. If I think of time consuming optimization-activties that are definitely yielding payoff in my day to day work a few things come to mind: Learning and mastering a single powerful text editor2, switching to an open operating system and using open source software wherever possible, using a tiling window manager, version control everything, maintaining a private internet archive, frequently experimenting with new programming languages and paradigms as well as studying mathematics. I am going to use the following sections to further explore some of these activities.

Text editing

Plain text is still the most used format for expressing and storing program instructions for all common and nearly all uncommon languages out there. Although the simplicity and thus flexibility of plain text continues to cause distracting discussions around topics such as tabs-vs-spaces3 there sadly are no usable alternative in the vein of e.g. generalized tree encodings available at this point in time. S-Expressions could probably be used as a foundation for such an alternative but alas we don't live in the alternative time line where the adoption of a LISP as the internet's scripting language instead of the quickly hacked together thing that is JavaScript caused a widespread rise of LISP-like languages culminating in all common languages being LISP-dialects and thus being expressible in sexprs.

To return the topic at hand: plain text it is and will continue to be for the foreseeable future. If one looks for powerful, widely available and extensible text editors the choice will in most cases come down to the still reigning giants Vim and Emacs 4.
When I stood before this decision nearly half a lifetime ago5 my choice fell on Vim. If one only considers the default editing interface this definitely was the right choice for me as I would not trade Vim's modal text manipulation language for overly long default Emacs key chords. But I have to admit that I regularly take wistful looks at some of the applications available inside Emacs such as Org-mode. Had I already discovered the joys of LISP when I was trying to decide between the two editors I probably would have chosen Emacs. Luckily one can always alter such decisions - sooner or later I will probably settle on some kind of Evil based setup just to be able to use the text based operating system that is Emacs.

a Vim session in its natural environment

Altough the 122 lines including comments that currently make up most of my Vim configuration are not much by most standards I have invested quite some time in setting the editor up to my taste - not the least by writing my very own color scheme to match the rest of my primary desktop environment.

Over time I have grown so accustomed to Vim's keybindings that I now use them wherever possible including but not restricted to: my web browser, PDF reader, various IDEs, image viewer and window manager of choice.

Operating system and desktop environment

ArchLinux continues to be the Linux distribution of choice for most of my computing devices. It offers most of the flexibility of Gentoo if one needs it while preserving fast installation and frequent updates of most of the software I require. The only feature I currently miss and that will probably lead me switch distributions sooner or later is declarative package management as offered by NixOS or GuixSD. A fully declarative configuration of my Linux installation in a plain-text and thus easily version controllable file would be the logical conclusion of my current efforts in managing system configurations: /etc is tracked using etckeeper, various dotfiles are tracked using plain git and GNU stow for symlink management.

Example of a basic i3 session

My choice of desktop environment has converged on a custom setup built around the i3 tiling window manager over the last couple of years. I have adopted the tiling concept to such a degree that I struggle to think of a single advantage a common - purely floating - window manager might hold over tiling window managers. This holds especially true if your workflow is similar to mine, i.e. you have lots and lots of terminals and a few full screen applications running at most times as well as a fondness for using the keyboard instead of shoving around a mouse.

More complex unstaged example of a i3 session

What I like about i3 in particular is that it doesn't enforce a set of layouts to toggle between like some other tiling WMs but allows you full control over the tree structure representing its layout. Another nice feature is that it lends itself to Vim-style keybindings as well as offering good support for multi monitor setups.

Compared to a desktop environment such as KDE a custom setup built around a window manager obviously requires much more configuration. In exchange for that I gained full control over my workflow in addition to basically instantaneous interaction with the system and its applications.

I find it very useful to have a certain set of information available at all times. Examples for such information are dictionary definitions, language and framework documentation, login credentials and notes. For this purpose I wrote a set of scripts that enable me to query a local dict daemon6, note folders and passman entries using the dmenu-replacement Rofi. In addition to that i3's scratchpad feature is very useful for keeping Zeal and Vim instances running in the background while preserving accessability in every context by displaying them in a floating window overlaying the current workspace.

Archiving, web browsing and note taking

An important purpose of the tool we call Computer is accessing information on the Internet. This task is achieved primarily using a web browser - in fact there is an argument to be made that web browsers are some of the most complex applications the average users comes into contact with.
I sometimes frown at the wasteful complexity many of today's websites contain even if their actual contents still consist of mostly plaintext and some pictures. It is no longer the exception but the rule that a single load of common websites pulls more data over the wire than would be required to encode a whole book while often containing far less content. These are the moments where I wish that Gopher had gained wider usage or that something in the vein of ipfs will grow to encompass most of the sources I commonly use7.

Current Pentadactyl, TreeStyleTabs and ScrapBook X augmented Firefox setup

As one can see in the screeshot above the current browser setup I use to deal with this rather unsatisfying state of things is a quite customized version of Firefox. This is achieved using Pentadactyl, TreeStyleTabs and ScrapBook X.

Pentadactyl transforms Firefox into a fully keyboard driven browser with Vim-like keybindings and looks as well as the possibility of configuring the browser using a single dotfile .pentadactylrc.

TreeStyleTabs allows me to better manage my workflow of keeping all tabs related to my current projects and interests opened as well as grouped in a tree structure. While Vim-like keybindings can be configured in other browsers, usable TreeStyleTabs like tab management is currently only available on Firefox.

ScrapBook X is my current answer to a question I have spent quite some time thinking about: How to best archive and organize interesting documents on the web. ScrapBook allows reasonably good offline archival of websites, organizing archived pages in a folder structure and exporting a HTML version of itself for hosting a private Internet Archive. It doesn't work perfectly on all websites and uses plain file mirroring instad of the more suitable WARC format but it is the best solution I was able to find short of investing most of my time into attemting to develop something more to my taste.
For now it is good enough and fullfills my primary use cases: Having access to most of my sources independent of network availability8, preventing the unpleasant situation of wanting to consult a vaguely remembered source only to find that it is not available anymore as well as full text search over all interesting pages I visited.

Archiving the web ties into the last section of this article: note taking. While I write all my lecture notes and excercise sheet solutions using pen input on one of Microsoft's Surface9 devices I like to capture project and research notes as well as general thoughts using a keyboard on my normal computer.
When taking notes as plain text I preferably want to do so using Vim which rules out most of the already relatively limited selection of open source desktop wiki software. After quite some time using VimWiki I currently use markdown files stored in a flat directory structure. Desktop integration is solved using a background Vim instance running in a i3 scratchpad as well as a Rofi based note selection dialog that communicates with Vim using remote commands. Advanced markdown features, syntax highlighting and conversion is based on pandoc integration plugins.
In addition to that I also now and then play around with Emacs' Org-mode which can probably fulfill most of my requirements but requires considerable upfront configuration efforts to make it work consistently with Evil for Vim-style usage.

Vision

While the setup outlined above is workable I definitely do not consider it a permanent solution. Even more so I feel that there is much unexplored potential in augmenting not just note taking but formal and exploratory thinking in general using computers. What I mean by that are systems as they were envisioned in the form of the Memex or as described by Engelbart in Augmenting Human Intellect10.

Such a system would not only encompass note taking and knowledge management but form an intergral part of the user facing operating system. Everything you see on a screen should be explorable in the vein of Lisp Machines or Smalltalk instances, annotatable in a fully interlinkable and version controlled knowledge base that transparently integrates information from the Internet in a uniform fashion as well as shareable with other beings where required.
Formal verification software could look over the figurative shoulder of the user and point out possible fallacies and formal errors. Even a single component of such a system like for example a math environment that pulls up appropriate definitions, theorems and examples depending on the current context or a literate development environment that automatically pulls up documentation, stackexchange threads and debugging output would be of great help.
Usage tracking similar to Gnome Zeitgeist in conjunction with full text archival of all visited websites and fully reproducible tracking of the desktop state would also complement such a system.

In conclusion: My current setup doesn't even scratch the surface of what should be possible. Tinkering with my computing systems and workflow-optimization will continue to be an unbounded but at least somewhat productive leisure time sink.

  1. ...that I have probably crossed frequently

  2. Section 16, Power Editing, The Pragmatic Programmer.

  3. Tabs for indentation, spaces for alignment it is for me - this is probably the reason for my dislike of whitespace-dependent languages that tend to interfere with this personal preference of mine.

  4. Desktop-only text editors - especially those Electron based ones written in HTML and JavaScript of all things - are not an alternative for my use cases. Although at least VSCode is developing nicely into a usable cross platform IDE.

  5. Luckily not that long in my case :-)

  6. Serving a collection of freely available dictionaries such as Webster's 1913 and Wordnet

  7. Note to self: Make the raw markdown sources (?) of this blog available on ipfs

  8. e.g. when riding the black forest train from Karlsruhe to my home village in the Hegau.

  9. The only non-Linux device I regularly use. Pen input on tablet devices has reached a point of general viability (concerning power usage and form factor) in recent years. I am actually very satisfied with my Surface 4 and Windows 10 as both a note taking and tablet device. For tinkering and security reasons I still hope to one day be able to use an open operating system and open note taking software on such a device but for now it is a workable solution for my use case of studying (mostly) paperless.

  10. AUGMENTING HUMAN INTELLECT : A Conceptual Framework., October 1962, D. C. Engelbart

» Visualisierung von Metriken in Voronoi-Diagrammen

May 22, 2016 | cpp development german math | Adrian Kummerländer

In der Analysis 2 Vorlesung meines Mathematik Studiums beschäftigen wir uns derzeit mit Normen und Metriken in endlich dimensionalen Vektorräumen, welche wiederum die Grundlage für die Übertragung der, aus Analysis 1 bekannten, Konvergenz und Stetigkeitsbegriffe in höhere Dimensionen schaffen. Während der Bearbeitung der entsprechenden Übungsblätter habe ich dabei nach Visualisierungsmöglichkeiten recherchiert, um eine bessere Intuition für diese Begriffe zu erlangen. Voronoi-Diagramme sind eine solche Möglichkeit, deren Grundlagen und Generierung ich in diesem Artikel zwischen Theorie und Praxis näher erläutern möchte.

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 ab\vert a-b \vert mit a,bRa, 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äumen2 wie R2\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 :VR0\| \cdot \| : V \rightarrow \mathbb{R}_{\geq0}, also eine Funktion, die Elementen aus einem K\mathbb{K}-Vektorraum VV3 einen reellen Wert größer oder gleich Null zuordnet.
Diese Funktion darf dabei nicht vollkommen beliebig definiert sein, sondern muss für x,yVx, y \in V sowie αK\alpha \in \mathbb{K} die folgenden Bedingungen erfüllen:

Definitheit x=0x=0\|x\|=0 \Leftrightarrow x=0
Homogenität αx=αx\|\alpha * x\|=\alpha * \|x\|
Dreiecksungleichung x+yx+y\|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.

Betrachten wir an dieser Stelle die Defintion der häufig verwendeten Klasse der p-Normen:

xp:=(i=1nxip)1pmitxRn,pR1\displaystyle \|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=1p=1 die Betragsnorm, also die Aufsummierung aller Komponentenbeträge des gegebenen Vektors, sowie für p=2p=2 die sogenannte Euklidische Norm hervor. Durch Verschieben von pp im Intervall [1,][1, \infty] lässt sich dabei die charakteristische Rautenform der Einheitskugel4 der Betragsnorm über die tatsächlich kugelförmige Einheitskugel der Euklidischen Norm in die quadratische Form der Maximumsnorm überführen (pp \rightarrow \infty).

Veränderung der abgeschlossenen Einheitskugel unter der p-Norm für p zwischen 1 und 3

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 R2\mathbb{R}^2:

d(x,y):=x1x22y1y22mitx,yR2\displaystyle 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 R\mathbb{R}-Vektorräume erweitern:

d(x,y):=i=1nxiyi2mitx,yRn\displaystyle 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×VR0d(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)0d(x,y)=0x=yd(x,y) \geq 0 \land d(x,y)=0 \Leftrightarrow x=y
Symmetrie d(x,y)=d(y,x)d(x,y) = d(y,x)
Dreiecksungleichung d(x,z)d(x,y)+d(y,z)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):=xy2d(x,y) := \|x-y\|_2 direkt aus der 2-Norm.

Es liegt also Nahe, dass auch aus die Betragsnorm mit p=1p=1 eine Metrik induziert - die sogenannte Mannheimer-Metrik:

d(x,y):=i=1nxiyimitx,yRn\displaystyle 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 pp 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):=(i=1nxiyip)1pmitx,yRn,pR+\displaystyle 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=1p=1 beziehungsweise p=2p=2 aus ihr hervorgehen.

Besonders interessant ist im Kontext der Visualisierung von Metriken, dass die Minkowski-Metrik für p[1,2]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.

Voronoi-Diagramme

Nachdem wir uns im vorangehenden Abschnitt einen groben Überblick über Normen und Metriken in endlich dimensionalen reellen Vektorräumen gemacht haben, können wir uns nun dem eigentlichen Thema dieses Artikels zuwenden: der Visualisierung von Metriken in Voronoi-Diagrammen.

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=2p=2, ergeben sich somit Grafiken wie die folgende:

Voronoi-Diagramm der Minkowski-Metrik mit p=2

Während wir die Definitionen der Metriken bisher im Speziellen für R2\mathbb{R}^2 betrachtet haben, gerät der zugrundeliegende Körper R\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 Z2\mathbb{Z}^2 zu betrachten. Dies ist einfach möglich, da Z2\mathbb{Z}^2 eine echte Teilmenge von R2\mathbb{R}^2 ist und eine triviale Bijektion zwischen Punkten in Z2\mathbb{Z}^2 und Pixeln auf einem Bildschirm existiert.

Voronoi-Diagramm der Minkowski-Metrik mit p=1

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 Z2\mathbb{Z}^2 durchlaufen und abhängig ihrer Distanz zu den Referenzpunkten unter der gewünschten Metrik eingefärbt werden.

double minkowski_metric(
    const double         p,
    const imgen::vector& a,
    const imgen::vector& b
) {
    return std::pow(
          std::pow(std::abs(std::get<0>(a) - std::get<0>(b)), p)
        + std::pow(std::abs(std::get<1>(a) - std::get<1>(b)), p),
        1.0 / p
    );
}

Zur Approximation der Bildmenge R0\mathbb{R}_{\geq 0} der Metrik-Funktionen verwenden wir double Werte, während die Ursprungsmenge R2×R2\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 pp.

std::pair<double, imgen::colored_vector> get_distance_to_nearest(
    const std::function<double(imgen::vector, imgen::vector)>& metric,
    const imgen::vector a
) {
    constexpr std::array<imgen::colored_vector, 9> reference_vectors{
        imgen::colored_vector{   0,    0, imgen::red()                },
        imgen::colored_vector{ 240,  200, imgen::color{220, 220, 220} },
        imgen::colored_vector{-100,  230, imgen::color{ 94, 113, 106} },
        imgen::colored_vector{ 120, -100, imgen::color{140, 146, 172} },
        imgen::colored_vector{ -42, -200, imgen::color{128, 128, 128} },
        imgen::colored_vector{ 120,   40, imgen::color{ 16,  20,  22} },
        imgen::colored_vector{-150,   50, imgen::color{192, 192, 192} },
        imgen::colored_vector{  60, -128, imgen::color{178, 190, 181} },
        imgen::colored_vector{-240,  -20, imgen::color{ 54,  69,  79} }
    };

    // [...] Bestimmung des nächsten Referenzvektors unter der gegebenen Metrik

    return std::make_pair(*minimal_distance, nearest);
}

void generate_minkowski_voronoi(const double p) {
    const auto metric{[p](const imgen::vector a, const imgen::vector b) -> 
    double {
        return minkowski_metric(p, a, b);
    }};

    imgen::write_ppm(
        "voronoi_" + std::to_string(p) + ".ppm",
        512,
        512,
        [&metric](std::ptrdiff_t x, std::ptrdiff_t y) -> imgen::color {
            const auto& nearest = get_distance_to_nearest(
                metric,
                imgen::vector{x, y}
            );

            if ( nearest.first <= 5.0 ) {
                return imgen::black();
            } else {
                return std::get<2>(nearest.second);
            }
        }
    );
}

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)Z2x[w2,w2]y[h2,h2]}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 hh und Breite ww aufspannt und für (x,y)M\forall \: (x, y) \in M die gegebene Funktion Z×Z[255]×[255]×[255]\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.

Der komplette Quellcode der aufgeführten Beispiele ist auf Github und cgit unter der MIT Lizenz frei verfügbar und kann so zur Generierung eigener Voronoi Diagramme herangezogen werden.

Minimalistische Generierung von Pixelgrafiken in C++

Wie bereits angedeutet, basiert der hier gewählte Weg zur Generierung von Voronoi-Diagrammen auf einer minimalistischen C++ Grafikbibliothek, welche im Rahmen meiner Experimente zu diesem Thema entstanden ist. Die Ursache dafür war, dass ich von vornherein nur einfache Pixelgrafiken generieren wollte und keinerlei Bedarf für die Vielfalt an Funktionalität hatte, wie sie von Grafikbibliotheken wie Cairo dargeboten wird. In solchen Situationen empfielt es sich, dass entstehende Program nicht mit Abhängigkeiten zu großen Frameworks zu überfrachten, sondern das Problem auf das Essenzielle zu reduzieren. In unserem Fall also die Iteration über eine gegebene Bildmenge und die Zuweisung von Farben zu Punkten. Andere Probleme wie Kompression und Animation in GIF Grafiken sind dann besser spezialisierten Werkzeugen wie Imagemagick überlassen.

Eines der wohl einfachsten Dateiformate für Pixelgrafiken ist das Portable PixMap 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:

void write_ppm(
    const std::string&                                   path,
    const std::size_t                                    width,
    const std::size_t                                    height,
    std::function<color(std::ptrdiff_t, std::ptrdiff_t)> generator
) {
    ppm_pixel_stream file(path, width, height);

    const std::ptrdiff_t min_y = height / 2 * -1;
    const std::ptrdiff_t max_y = height / 2;
    const std::ptrdiff_t min_x = width  / 2 * -1;
    const std::ptrdiff_t max_x = width  / 2;

    for ( std::ptrdiff_t posY = max_y; posY > min_y; --posY ) {
        for ( std::ptrdiff_t posX = min_x; posX < max_x; ++posX ) {
            file << generator(posX, posY);
        }
    }
}

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.

Bewegte Bilder

Das in meinen Augen schönste Resultat dieses Artikels ist die Visualisierung der Transformation von der Mannheimer in die Euklidische Metrik in Form der folgenden GIF Animation:

Übergang von der Mannheimer in die Euklidische Metrik und zurück

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 pp 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.

void generate_parallel_minkowski_voronoi(
    const unsigned int thread_count,
    const double       lower,
    const double       upper,
    const double       epsilon
) {
    std::vector<std::thread> threads;

    const double step = ( upper - lower ) / thread_count;
    double offset     = lower;

    while ( threads.size() < thread_count ) {
        threads.emplace_back([offset, step, epsilon]{
            generate_minkowski_voronoi(
                offset,
                offset + step,
                epsilon
            );
        });

        offset += step;
    }

    generate_minkowski_voronoi(upper);

    for ( auto& thread : threads ) {
        thread.join();
    }
}

Rückblick

Hiermit sind wir am Ende meines ersten textuellen Ausflugs an die Schnittstelle zwischen Mathematik und Software angelangt. Ich hoffe an dieser Stelle, dass die Ausführungen und Beispiele verständlich waren und ich mich, am Anfang meines Studiums der Mathematik stehend, nicht in formelle Fehler verstrickt habe.

Grundsätzlich finde ich Voronoi-Diagramme hilfreich, um eine visuelle Intuition für die Auswirkungen verschiedener Metriken zu gewinnen - gleichwohl diese in höheren Dimensionen schnell in ihrem Nutzen schwindet. Aber auch abgesehen vom praktischen Aspekten sind diese Diagramme eine schöne Möglichkeit in etwas anschaulicherem Kontext mit Mathematik zu spielen und schöne Bilder zu erzeugen.

Ansätze zum Ausbau der im Rahmen dieses Artikels entstandenen Programme - an dieser Stelle noch einmal der Hinweis auf die Quellen bei Github und cgit - sind verschiedene Metriken in einem Diagramm zu mischen oder zu gewichten sowie sich praktische Einsatzszenarien für Voronoi-Diagramme anzuschauen. Wenn die Grafiken beispielweise bei dem ein oder anderen meiner Leser die Erinnerung an Strukturen in der Natur wie Bienenwaben oder aufeinandertreffende Seifenblasen geweckt haben, dann liegt das daran, dass sich Prozesse dieser Art tatsächlich über Voronoi-Diagramme betrachten lassen. Der entsprechende Wikipedia-Artikel liefert hier als Abschluss eine Auflistung zahlreicher Anwendungsbeispiele.

  1. R\mathbb{R} könnte an dieser Stelle auch die Menge N\mathbb{N} der natürlichen Zahlen, die Menge C\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 vVv \in V mit v+v=0v + -v = 0. Zusammenfassend führen diese Anforderungen dazu, dass innerhalb eines Vektorraums in weitgehend gewohnter Art und Weise gerechnet werden kann.

  3. Der Begriff K\mathbb{K}-Vektorraum sagt aus, dass alle Komponenten der enthaltenen Vektoren Elemente aus dem Körper K\mathbb{K} sind. Im Falle eines R\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 B(1,0):={xVx1}\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.