Gestelltes Problem
Da ich zum Ausmalen (siehe Computergrafik) gerne Bitmaps mit möglichst vielen Einzelflächen als Ausgangsbasis nehme, dachte ich daran, dass doch zur Abwechslung einmal 3-dimensionale Objekte interessant wären. Solche Programme hab’ ich schon früher geschrieben, allerdings in Turbo-Pascal, einer Sprache die damals auf IBM-kompatiblem PC’s mit MS-DOS wirklich unschlagbar war, den Sprung zu Windows aber nicht geschafft hat. Mitte der 80er war das für mich an der Uni als Darstellung von Elektronenorbitalen (Kugelfunktionen) eine Übungsaufgabe in theoretischer Physik. Entweder die Darstellung der Kugelfunktionen am PC oder eine “schriftliche Aufgabe”. Damals hab’ ich mich in drei Millisekunden für die Programmieraufgabe entschieden. Der Professor meinte dann übrigens zu meinen Ausdrucken “Das ist die beste Darstellung der Kugelfunktionen, die ich jemals gesehen habe. Wie haben Sie das gemacht?”
Es ging jetzt also darum, diese Darstellung in C++ zu implementieren.

Algorithmus
Die Koordinaten der Fläche werden durch drei Funktionen X(s,t), Y(s,t), Z(s,t) berechnet. Die Intervalle für s und t werden vom Benutzer gewählt, ebenso eine Anzahl Schritte, in die die Intervalle eingeteilt werden. Das Programm durchläuft das Intervall und ermittelt für je drei Punkte aus dem Intervall drei Punkte im Raum, die dann ein Dreieck ergeben. Diese Dreiecke werden in einer Liste abgelegt. Nach der Berechnung wird die Dreiecksliste so sortiert, dass die vom Betrachter am weitesten entfernten Flächen an den Anfang der Liste kommen. Dann wird die Liste gezeichnet, wobei jedes Dreieck mit der Hintergrundfarbe gefüllt wird. Dadurch verdecken die vorderen Flächen die hinteren.

Screenshot (20.000 Flächen):

Gestelltes Problem
Hier eine Platte, da eine Platte, Datensicherungen vom Arbeits-PC. Diverse Rechnerwechsel. Irgendwann waren meine Datenbestände wirklich komplett durcheinander, alles mehrfach irgendwo abgelegt. Deshalb brauchte ich mal wieder ein Programm zum Auffinden von Duplikaten. Es sucht in einem Verzeichnisbaum rekursiv nach identischen Dateien. Die gefundenen Gruppen von Dateien gleichen Inhaltes werden dann in einem Tree-Control angezeigt und können gelöscht werden.

Algorithmus
Zunächst alle Dateien auffinden. Dabei prüfen, ob es Dateien mit identischer Länge gibt. Für diese eine Checksumme bilden. Dateien mit gleicher Länge und gleicher Checksumme werden gruppenweise verglichen. Es ergibt sich also eine Liste mit Gruppen von identischen Dateien.

Screenshot:

Gestelltes Problem
Meine Kumpels und ich digitalisieren unsere CDs. Wir tauschen nur zu Backupzwecken und völlig unkommerziell. Bei einer MP3-Sammlung stellt sich ab einer gewissen Grösse die Frage, ob man ein bestimmtes Lied nicht schon irgendwo hat. Manuelle Abgleiche sind zeitaufwendig.

Algorithmus
Das Programm scannt einen Verzeichnisbaum auf MP3-Dateien, liest diese ein, und erzeugt eine Informationsdatei mit einem Extrakt aus den ersten 15 Musiksekunden sowie anderen Dateiinformationen. Diese Dateien werden in einem zweiten Schritt wieder eingelesen und dem Anwender in Form einer Liste präsentiert. In dieser Liste werden Dateien mit gemeinsamen Merkmalen zusammengefasst. Die Liste wird zunächst sortiert und dann Dateien mit gemeinsamen Merkmalen markiert. Folgende Sortierkriterien sind bis jetzt implementiert:
Dateiname (ohne Verzeichnis), Dateiname “tolerant” (Ziffern und Sonderzeichen entfernt), Dateigrösse, Dateigrösse “tolerant” (Dateilängen, die sich um maximal 100 Byte unterscheiden, gelten als identisch), Bitrate der MP3-Datei (alles unter 160 kBit/s ist schlecht), Samplingfrequenz (normal 44 kHz) und die Position des Lautstärkemaximums der ersten 15 Musiksekunden.
Damit kann man schon viele Doppelte erkennen, trotzdem muss bei der Verarbeitung der eigentlichen Musikdaten noch etwas getan werden.

Screenshot:

Gestelltes Problem
An meinem Notebook sind zwei USB-Laufwerke angeschlossen. Auf dem Ersten befinden sich meine MP3-Dateien. Das Zweite wird zu Backupzwecken genutzt. Nun brauchte ich ein Programm, mit dem man zwei grosse Verzeichnisse mitsamt Unterverzeichnissen synchron halten kann. Mit dem Windows Explorer kam ich nämlich nicht weiter weil dieser beim Kopieren die schon vorhandenen Dateien erneut kopiert was bei grossen Dateianzahlen einfach zu lange dauert.

Algorithmus
Da ist nicht viel Algorithmus dabei, es wird ein Quellverzeichnis rekursiv durchsucht und geprüft, ob die dort liegenden Dateien im Zielverzeichnis mit gleicher Länge vorliegen. Falls nicht, werden sie kopiert. Nach dem Kopieren wird für jede Datei im Zielverzeichnisbaum geprüft, ob sie im Quellverzeichnisbaum vorhanden ist (sie könnte ja seit dem letzten Lauf gelöscht oder umbenannt worden sein). Falls sie dabei nicht gefunden wird, wird sie gelöscht.

Screenshot:

Gestelltes Problem
Angenommen, man hat ca. 10.000 Jpeg-Dateien unter denen sich viele Doppelte befinden. Diese Dubletten können sich in der Bildgrösse, in den Bildproportionen, der Helligkeit und auch der Farbverteilung unterscheiden.

Algorithmus
Das einfachste ist ein Vergleich der Dateigrössen. Damit hab’ ich viele Dubletten gefunden, aber natürlich meine Anforderungen noch nicht erfüllen können. Die eine Hälfte des Algorithmus ist dadurch aber schon entstanden und zwar ist das eine Sortierung und eine anschliessende Anzeige von Dateien mit gleichem “Kennwert”, zunächst eben der Dateigrösse. Ich habe mir den Quelltext für das Einlesen von Jpeg-Dateien von der “Independent JPEG Group” downgeloaded (wenn jemand mal erschreckend guten Quelltext sehen will, da ist er richtig) und somit Zugriff auf die Bilddaten. Zur Einbeziehung des Bildinhaltes werden die Jpeg-Dateien auf eine wahnsinnig schlechte Auflösung heruntergerechnet (8×8 Pixel). Dann werden sie in schwarz-weiss konvertiert, wobei ein Punkt dann schwarz ist, wenn er dunkler ist als die Durchschnittshelligkeit des Originalbildes, ansonsten weiss. Es ergibt sich also eine 64bit-Ganzzahl und nach diesem Wert werden die Bilder sortiert und dann Dateien mit gleichem Kennwert angezeigt. Dann kann der Anwender sich beide Versionen angucken und entscheiden ob die Bilder wirklich identisch sind.

Screenshot: