IOException.de

Icon

Ausgewählter Nerdkram von Informatikstudenten der Uni Ulm

Graphen & Plots erzeugen mit GLE

Nicht unerheblich für eine erfolgreiche Veröffentlichung ist eine ansprechende Präsentation der Ergebnisse. Jeder schaut sich lieber schöne Plots mit den zum Latex Template passenden Schriftarten an. Eine Möglichkeit solche Plots zu erzeugen ist über die Skriptsprache GLE die auch gleich eine eingebaute Preview Komponente mitbringt.

Ein möglicher Beispielplot ist rechts gezeigt, das dazugehörige GLE Skript unten. Gelesen werden die Daten einfach aus CSV-Dateien.


size 9 6

set font pstr !meine Paper Vorlage verwendet diesen Font. 

set texlabels 0 !keine Tex-Fonts in den Labels

!eine Funktion für einen Scatterplot
sub draw_scatter dataset$ mu sigma dt dst letter$
  begin graph
     size 5 5
     !Achsen in mu+-sigma
     xaxis min mu-sigma max mu+sigma  dticks dt dsubticks dst
     yaxis min mu-sigma max mu+sigma dticks dt  dsubticks dst
     xtitle " x-axis " 
     ytitle "noisy x-axis"
     !Buchstabe als Alternative zu subplots
     title letter$

     !CSV files lesen & plotten
     data dataset$+"_4.csv" d1
     d1 marker dot msize 0.2 color navy

     data dataset$+"_3.csv" d2
     d2 marker dot msize 0.2 color cyan 
     
     data dataset$+"_2.csv" d3
     d3 marker dot msize 0.2 color lime
     
     data dataset$+"_1.csv" d4
     d4 marker dot msize 0.2 color magenta 
     

  end graph
end sub

!Zeichnet einen Linienplot
sub draw_line dataset$ mu sigma dt dst letter$
  begin graph
    xaxis min mu-1/3*sigma max mu+1/3*sigma  dticks dt dsubticks dst
    yaxis min mu-sigma max mu+sigma dticks dt  dsubticks dst
    size 1/3*5 5


    data "lines-"+dataset$+"-1.csv" d1
    d1 line color magenta 
    
    title letter$
  end graph
end sub

!die plots an die richtigen Positionen zeichnen
amove 1 1.2
draw_scatter "csvdata1" 29 200 100 50 "(a)"
amove 6.3  1.2
draw_line "csvdata1" 29 200 100 50 "(b)"



Für einen Preview die .gle Datei im mitgelieferten Tool qgle öffnen, die .gle Datei kann on-the-fly geändert und gespeichert werden. Die qgle Komponente aktualisiert sich automatisch neu. Für eine Veröffentlichung muss nur die .eps Datei exportiert werden, die Schriftart mittels eps2pdf eingebettet werden.

Globale Verteilung der WikiLeaks Mirror visualisieren

Am 2. Dezember 2010 haben verschiedene große DNS Anbieter, nach dem Release der US-Botschaftsdepeschen, aufgehört die wikileaks Domains aufzulösen. Daraufhin wurde der Inhalt der WikiLeaks-Website auf knapp 2.200 Servern gespiegelt. Die Server wurden von Freiwilligen auf der ganzen Welt zur Verfügung gestellt.

Dieser Vorfall zeigt eindrucksvoll, wie die dezentralen Strukturen des Internets genutzt werden können um Zensur zu umgehen und Informationsunterdrückung zu verhindern.

Nachdem ich im vorigen Beitrag die Ausgabe des traceroute Utilities visualisiert habe wollte ich hier noch etwas weiter machen. Dieses Mal war mein Ziel die Domains der verschiedenen Mirrors herauszubekommen, diese erst zu einer IP, dann zu WGS84 aufzulösen. Die WGS84 Koordinaten kann ich dann auf einer Erdkugel abbilden.

Die Domains herauszubekommen war einfach, es gibt verschiedene Seiten die die Adressen der Spiegelserver auf einer HTML-Seite auflisten. Diese Liste lässt sich bequem parsen. Das Auflösen zu einer WGS84-Koordinate habe ich wieder über eine freie GeoIP-Datenbank vorgenommen. Von da an konnte ich große Teile des traceroute Projekts wiederverwenden um die Domains auf eine Weltkugel zu mappen.

Ganz interessant ist, dass die Server tatsächlich auf der ganzen Welt verteilt sind. Die meisten Server stehen — jetzt nicht besonders überraschend — in Mitteleuropra. Es sind wohl aber auch einige wenige in China. Natürlich geben die Ergebnisse der GeoIP Datenbank keine sicher bestimmten Standorte wieder, aber ich finde der Trend ist doch schön erkennbar.

Ich habe ein kleines Video zu der globalen Verteilung zusammengestellt:

Der Direktlink: vimeo.

Ein graphisches Frontend für traceroute

Um mich näher mit Processing und OpenGL auseinanderzusetzen habe ich ein Frontend für das Unix Programm traceroute geschrieben. Die Ausgabe von traceroute ist eine Liste mit Stationen die ein Paket auf seinem Weg durch das Netzwerk passiert. Dies kann etwa für das Debuggen einer Netzwerkverbindung genutzt werden.

Technisch wird dies über das “Time-To-Live”-Feld im Header von IP-Paketen realisiert. Der TTL-Eintrag gibt an, nach wie vielen Stationen ein Paket verworfen werden soll. Jeder Router, den das Paket passiert, dekrementiert dieses Feld. Ist die TTL bei 0 angelangt wird das Paket verworfen und der Absender mittels einer ICMP-Nachricht TIME_EXCEEDED benachrichtigt.

traceroute macht sich diesen Umstand zunutze indem immer wieder Pakete an den Zielhost gesendet werden. Die TTL wird dabei schrittweise erhöht bis das Ziel erreicht ist. Die Hosts auf dem Weg werden sich nach und nach mit ICMP-Nachrichten melden, so dass wir dann Informationen über den Absender gewinnen und somit (hoffentlich) die einzelnen Stationen auf unserer Route identifizieren können. Diese Route muss hierbei nicht zwangsläufig korrekt sein. Es können sich aus verschiedenen Gründen Abweichungen ergeben, etwa durch Firewalls die aus Sicherheitsgründen ICMP gleich komplett deaktivieren.

Für die Visualisierung habe ich traceroute, wie im letzten Beitrag beschrieben, als externes Programm an Processing angebunden. Das Frontend liest dabei die Ausgabe des Kommandoaufrufs traceroute domain.org bis EOF. Jede Zeile wird geparsed, dabei werden die einzelnen Hosts der Route nach IP-Adressen aufgelöst und anschließend die Koordinate bestimmt. Die Koordinaten können anschließend mit etwas sin/cos Grübeln auf einer Erdkugel abgebildet werden. Das Auflösen nach Geolocations habe ich mittels einer GeoIP-Datenbank realisiert. GeoIP-Datenbanken stellen eine Zuordnung IP zu Koordinate dar. Natürlich nur mit einer bestimmten Wahrscheinlichkeit und auch nicht völlig exakt, aber für unsere Zwecke reicht das. Es gibt hier einige freie und natürlich jede Menge kommerzielle Anbieter. Ich habe mich dabei für die freie GeoLite City von Maxmind entschieden. Im Endeffekt löse ich so jetzt eine IP-Adresse zu einer WGS84-Koordinate auf.

Für das Frontend habe ich in Java mithilfe der Processing API eine Visualisierung geschrieben. Die Textur der Weltkugel wird mittels eines in GLSL geschriebenen Shaders weiter verändert. Bibliotheken, die ich verwendet habe: GLGraphics (OpenGL Rendering Engine für Processing), controlP5 (Button, Slider, Textfield) und toxiclibs (Interpolation & andere numerische Methoden).

Den Sourcecode habe ich unter MIT auf GitHub veröffentlicht: visual-traceroute.

Ein bisschen Eye Candy gibts in dem Video unter diesem Beitrag bzw. hier als Direktlink auf Vimeo.

Processing als Frontend: Anbindung an andere Programmiersprachen

Processing ist eine Programmiersprache, die entwickelt wurde um es möglichst einfach zu machen Visualisierungen zu erstellen und grafische Arbeiten am Computer erstellen zu können. Der Sprachumfang (bzw. die API) ist sehr übersichtlich und ist hier auf einer Seite zusammengefasst.

Für Processing existieren heute enorm viele Bibliotheken und die Sprache wurde u.a. nach Javascript portiert bzw. wird aktuell nach Android portiert. Somit wird Processing 2.0 auch das Ausführen im Browser und auf einem Android-Gerät unterstützen (bzw. trunk unterstützt es schon :) ).

Toll ist, dass sich die Processing-Bestandteile als externe Java Bibliotheken referenzieren lassen. Wir können also in unserem Java-Projekt sehr bequem die Processing-Möglichkeiten ausschöpfen. Wir können außerdem jede Menge Processing-Bibliotheken referenzieren, etwa für Physik, Typographie, etc..

Dieser Beitrag soll zeigen wie einfach es ist in Java mit den Processing Bibliotheken ein reines Frontend zu schreiben. Bei vielen Aufgaben bietet es sich an eine Sprache zu verwenden, die sich speziell für diese Aufgabe eignet. In manchen Fällen wollen wir also das Frontend in Processing schreiben, das Backend aber in einer anderen Sprache.

Wir haben also zwei verschiedene Programme. Wie verbinden wir die Beiden jetzt?

Unser Processing-Programm startet einen Thread der wiederum das externe Programm startet und konstant die Ausgabe des externen Programmes liest (bis EOL). Diese Ausgabe wird konstant geparset und in einem Objekt, beispielsweise einer Liste, abgelegt.

Das Hauptprogramm hat die Aufgabe unsere “Zeichenfläche” darzustellen. Processing sieht dazu eine Methode draw() vor, die entsprechend der Framerate oft aufgerufen wird. In der draw() Methode lesen wir das Objekt des Threads ein und berücksichtigen dies für unsere Darstellung.

In Processing sieht das Ganze dann so aus:

/*
 * Aufgabe des Threads:
 * Die Ausgabe unseres "Backend"-Programmes zu lesen und zu parsen.
 */
public class Stream extends Thread { 
  /* Für jede Zeile der Ausgabe erstellen wir einen Eintrag in der Liste */
  Vector <StreamEntry > entries = new Vector <StreamEntry >();

  public void run() { 
    String line; 

    try {
      Process p = Runtime.getRuntime().exec("ping uni-ulm.de");
      BufferedReader input = new BufferedReader(
         new InputStreamReader(p.getInputStream()));

      while ((line = input.readLine()) != null) 
        entries.add(new StreamEntry(line));

      input.close(); 
    } catch (Exception err) {
      err.printStackTrace();
    }
}

public class StreamEntry {
  public int time;

  public StreamEntry(String line) {
    /* Parsing action ... */
    this.time = ...;
  }
}

Unser Hauptprogramm zur Darstellung:

public class Main extends PApplet {
  /* Unser Thread, der die Ausgabe des Backends liest */
  private Stream stream;

  public void setup() {
    size(1024, 768);

    stream = new Stream();
    stream.start();
  }

  /* draw() wird entsprechend der Bildwiederholrate oft aufgerufen */
  public void draw() {
    background(BLACK);

    /* Wir geben alle Einträge der Ausgabe aus */
    for (StreamEntry s : stream.entries)
      text(s.time, 10, y+=15);
  }
}

Der zweite Thread verarbeitet also kontinuierlich die Ausgabe des Backend. Unser Hauptprogramm aktualisiert bei jedem Aufruf von draw() die Zeichenfläche und berücksichtigt hierbei die Ausgabe des Backends.

OpenStreetMap-Rendering mit Mapnik

Mit Hilfe des Kartenmaterials von www.openstreetmap.org (OSM) wird einem die Möglichkeit gegeben, zum Teil qualitativ sehr hochwertiges und offenes Kartenmaterial für eigene Anwendungen zu verwenden. Die Vielzahl der Verwendungsmöglichkeiten muss hier nicht weiter erläutert werden.
Allerdings ist die Verwendung der Daten selbst nicht unbedingt trivial. Mittlerweile gibt es zwar in der weiten Welt des Netzes auch ein paar Blogs und Wikis, die einem helfen, dennoch möchte ich an dieser Stelle für eine voraussichtlich mehrteilige Serie den Grundstein legen. Der besteht daraus, aus dem frei verfügbarem Material einen kleinen einzelnen Ausschnitt zu rendern. Zu späteren Zeitpunkten werde ich hoffentlich noch zeigen können, inwiefern das durchaus umfangreiche Material auf die eigenen Bedürfnisse angepasst werden kann. Natürlich ist das ganze kein Hexenwerk und ich möchte auch nicht so tun als ob es eins wäre, weswegen wir am besten mal loslegen.

Da ich selbst in erster Linie Ubuntu benutze und an manchen Stellen der Einsatz von Windows die Angelegenheit nicht unbedingt erleichtert, ist die nachfolgende Anleitung für Ubuntu 9.10 geschrieben. Grundsätzlich sollte sie aber auch für ältere Ubuntu Versionen funktionieren. Unter http://wiki.openstreetmap.org/index.php/Mapnik gibt es weitere Infos, auch für andere Betriebssysteme.

# Subversion-Installation
sudo apt-get install subversion

# der Einfachheit halber arbeitet man am besten direkt im Homeverzeichnis
cd ~

# Mapnik-Installation (Renderer):
sudo apt-get install python-mapnik

# Postgres-Installation (Datenbank)
sudo apt-get install postgresql-8.3-postgis

# Datenbank-Konfiguration
sudo -u postgres -i
createuser username # ja für superuser, username sollte normaler username sein
createdb -E UTF8 -O username gis
createlang plpgsql gis
exit

psql -d gis -f /usr/share/postgresql-8.3-postgis/lwpostgis.sql

echo "ALTER TABLE geometry_columns OWNER TO username; ALTER TABLE spatial_ref_sys OWNER TO username;" | psql -d gis

# Mapnik-Dateien-Checkout für das Rendern:
svn checkout http://svn.openstreetmap.org/applications/rendering/mapnik mapnik/

cd mapnik
mv archive/* ~/mapnik

svn co http://svn.openstreetmap.org/applications/utils/export/osm2pgsql/

cd osm2pgsql
make

psql -f 900913.sql -d gis

cd ..

# Herunterladen und Entpacken des Kartenmaterials
wget http://tile.openstreetmap.org/world_boundaries-spherical.tgz # ca 50MB

cd world_boundaries
wget http://tile.openstreetmap.org/processed_p.tar.bz2 # ca 227MB
tar xvf processed_p.tar.bz2
wget http://tile.openstreetmap.org/shoreline_300.tar.bz2 # ca 46MB
tar xvjf shoreline_300.tar.bz2

# Weitere Datenbankspeisung und Konfiguration:
shp2pgsql -s 900913 -I -g way processed_p shoreline_a | psql -q gis

# Mapnik-Einrichtung
cd ..
vi set-mapnik-env
# Ändern der unteren beiden Werte
export MAPNIK_DBNAME='gis'
export MAPNIK_DBUSER='username' # username von oben und achtet auf die richtigen Anfuehrungszeichen

# osm.xml-Generierung:
source ./set-mapnik-env
./customize-mapnik-map -> $MAPNIK_MAP_FILE

# erstes Rendering
python generate_image.py

Typotisch

Typotisch – 1 from David L on Vimeo.

Dieses Projekt wurde im Rahmen des Praktikums “Aesthetic Computing” geplant und umgesetzt von Nora von Egloffstein und mir. Nachfolgend mehr Informationen (siehe auch hier).
Kompletten Beitrag lesen »

Vektorfeldvisualisierung durch Flow Streams

In einem vorherigen Artikel hatte ich bereits über Visualisierungen von Vektorfeldern geschrieben, hier werden wir ein identisches Vektorfeld nutzen. Unser Beispielfeld ist wieder:

 V = x^2*y* e_1  + 2 * x * y^2 * z * e_2 + y* z^3 * e_3

Wir setzen wieder gridPoints, glyPoints als gegeben vorraus. Des weiteren können wir auch wieder ein Magnituden-Array mag und ein Beschleunigungs-3Tupel-Array velocity als gegeben vorraussetzen:

vtkPoints gridPoints
vtkPoints glyPoints

vtkFloatArray velocity
  velocity SetNumberOfComponents 3
  velocity SetNumberOfValues [expr $x_extend*$y_extend*$z_extend]


vtkFloatArray mag
  mag SetNumberOfComponents 1
  mag SetNumberOfValues [expr $x_extend*$y_extend*$z_extend]

Im nächsten Schritt erzeugen wir wieder aus den Punkten und den zwei Arrays ein strukturiertes Gitter.

vtkStructuredGrid sgrid
  sgrid SetDimensions $x_extend $y_extend $z_extend
  sgrid SetPoints gridPoints
  [sgrid GetPointData] SetVectors velocity
  [sgrid GetPointData] SetScalars mag

Damit wäre die Definition des Feldes abgeschlossen, als erstes müssen die die Streams einen Startpunkt bekommen. In unserem Fall nehmen wir eine Linie auf der die Streams starten sollen.


vtkLineSource rake
  rake SetPoint1 1 9 9
  rake SetPoint2 9 9  9  
  rake SetResolution 200

Der vtkStreamTracer wird im nächsten Schritt die Stromlinien erzeugen die dann mit einem vtkTubeFilter dargestellt werden.

vtkRungeKutta4 integ
vtkStreamTracer streamer
    streamer SetInput sgrid
    streamer SetSourceConnection [rake GetOutputPort]
    streamer SetMaximumPropagation 5000
    streamer SetMaximumPropagationUnitToTimeUnit
    streamer SetInitialIntegrationStep 0.005
    streamer SetInitialIntegrationStepUnitToCellLengthUnit
    streamer SetIntegrationDirectionToBoth
    streamer SetIntegrator integ

vtkTubeFilter streamTube
    streamTube SetInputConnection [streamer GetOutputPort]
    streamTube SetRadius 0.1
    streamTube SetNumberOfSides 12

Im letzten Schritt muss nurnoch alles in Mapper und Aktoren gepackt werden (siehe frühere Posts) und wir bekommen das folgende Bild:

flow

Die VTK Renderpipeline am Beispiel eines Oktaeders

Die VTK Renderpipeline ist im Gegensatz zu traditionellen Grafikpipelines weniger auf Rasterung, Beleuchtung, Clipping, … fokussiert sondern setzt den Schwerpunkt auf das Aufbereiten, Verändern und Repräsentieren von Eingabedaten. Die traditionelle Renderpipeline wird von dem Benutzer soweit wie möglich versteckt. Zu beachten ist dass die Pipeline von der Senke zur Quelle getriggert wird, falls jedoch in einem vorherigen Modul eine Eingabedatenänderung vorgenommen wird, muss für eine aktuelle Darstellung das jeweilige Modul manuell mittels Update getriggert werden.


 \begin{bmatrix} \text{ \textbf{Quelle} }  \\ \text{Datenbasis f\

Dieser Teil der Pipeline bearbeitet und repräsentiert die Eingabedaten. In unserem Fall repräsentieren wir den Oktaeder aus Punkten, Flächen zwischen den Punkten und Farbangaben für jeden Punkt. In den VTK Tcl Bindings sieht das wie folgt aus:

#holds all points
vtkPoints points

points SetNumberOfPoints 6

#insert all points
points InsertPoint 0 1.0 0.0 0.0
#[...]
points InsertPoint 5 0.0 0.0 -1.0

#holds all faces
vtkCellArray polys

polys InsertNextCell 3
   polys InsertCellPoint 0
   polys InsertCellPoint 3
   polys InsertCellPoint 4
#[...]
polys InsertNextCell 3
   polys InsertCellPoint 2
   polys InsertCellPoint 0
   polys InsertCellPoint 5

#set color to i for each face
vtkFloatArray vertexScalars
   for { set i 0 } { $i < 6 } { incr i } {
vertexScalars InsertTuple1 $i $i
}



 \begin{bmatrix} \text{ \textbf{Quelle} }  \\ \text{Datenbasis f\

In unserem Fall besteht der Filter daraus dass alle Eingabedaten (Punkte, Flächen, …) zusammengesetzt werden müssen.

vtkPolyData octahedron
   octahedron SetPoints points
   octahedron SetPolys polys
   [octahedron GetPointData] SetScalars vertexScalars



 \begin{bmatrix} \text{ \textbf{Filter} }  \\ \text{Daten- und Datenstrommodifikation}  \end{bmatrix} \rightarrow\begin{bmatrix} \text{ \textbf{Mapper} }  \\ \text{Erzeugen der Grafikobjekte}  \end{bmatrix}

Im Mapper wird die eigentlich Repräsentation erzeugt, in unserem Fall ist nurnoch eine Bereichsangabe für die Skalare notwendig.

vtkPolyDataMapper octahedronMapper
   octahedronMapper SetInput octahedron
   octahedronMapper SetScalarRange 0 7



 \begin{bmatrix} \text{ \textbf{Mapper} }  \\ \text{Erzeugen der Grafikobjekte}  \end{bmatrix} \rightarrow  \begin{bmatrix} \text{ \textbf{Actor} }  \\ \text{Repr\

Im Actor werden die Parameter der Datenrepräsentation spezifiziert, meist sind das klassische Computergraphikparameter wie Beleuchtung, Transparenz, …

vtkActor octahedronActor
   octahedronActor SetMapper octahedronMapper



 \begin{bmatrix} \text{ \textbf{Actor} }  \\ \text{Repraesentationsparameter}  \end{bmatrix}   \rightarrow \begin{bmatrix} \text{ \textbf{Renderer \&Fenster} }  \\ \text{Zeigt alle Actoren an}  \end{bmatrix}

In diesem Teil werden alle Actors einen Renderer zugewiesen und über ein Fenster gezeichnet.

vtkRenderer ren1 
   ren1 AddActor octahedronActor
   ren1 SetBackground 0.1 0.2 0.4

vtkRenderWindow renWin
   renWin AddRenderer ren1
   renWin SetSize 300 300

vtkRenderWindowInteractor iren
   iren SetRenderWindow renWin

vtkInteractorStyleTrackballCamera style
   iren SetInteractorStyle style

iren AddObserver UserEvent {wm deiconify .vtkInteract}

iren Initialize

wm withdraw .

Die Interaktionskomponenten die noch initialisiert werden sind nicht direkt Teil der Pipeline sondern nebenläufige Module.


Die komplette VTK Pipeline sieht am Ende wie folgt aus:

 \begin{bmatrix} \text{ \textbf{Quelle} }  \end{bmatrix}   \rightarrow \begin{bmatrix} \text{ \textbf{Filter} }  \end{bmatrix}   \rightarrow \begin{bmatrix} \text{ \textbf{Mapper} }  \end{bmatrix}   \rightarrow \begin{bmatrix} \text{ \textbf{Actor} }  \end{bmatrix}   \rightarrow \begin{bmatrix} \text{ \textbf{Renderer \& Fenster} }  \end{bmatrix}

und das Ergebnis in den Tcl Bindings:

okt

Videoexport aus VTK mittels vtkAVIWriter

Um eine interessante Animation in VTK als Video zu exportieren bietet sich der vtkAVIWriter an. Dieser Filter kann Animation als .avi Datei rausschreiben. Wieder kommt hier VTK in den Tcl Bindings zum Einsatz, die Übertragung auf andere Bindings sollte aber 1:1 möglich sein. An das Ende der Filterkette hängen wir mit dem vtkWindowToImageFilter, einen Filter der das Bild eines vtkRenderWindow aus der momentanen Fensterdarstellung extrahiert.

vtkRenderWindow renderW

#[ ... ]

vtkWindowToImageFilter imageF
  imageF SetInput renderW

Im nächsten Schritt kommt der vtkAVIWriter zum Einsatz, nach der Initialisierung wird nach jedem Frame die Filterkette aktualisiert und der aktuelle Frame rausgeschrieben. Nach dem letzten Frame wird der vtkAVIWriter gestoppt.

vtkAVIWriter aviW
  aviW SetFileName "animation.avi"
  aviW SetInputConnection [imageF GetOutputPort]
  aviW Start

for {set k 0} {$k<$frames} {incr k} {
   
  #do computation
   
  #render window
  renderW Render
  #call modified at filter
  imageF Modified
  #write frame
  aviW Write

}
#end of animation
aviW End

Für ein Beispiel siehe “Visualisierung von Winkelgeschwindigkeiten in Vektorfeldern”.

Visualisierung Heap / Heap Sort

Unter einem Heap (im Deutschen gelegentlich auch als Halde bezeichnet) versteht man eine baumartige Datenstrukur mir einer besonderen Eigenschaft: Die Nachfolgeknoten jedes Knotens besitzen immer kleinere (oder immere größere) Schlüsselwerte als der Knoten selbst. Somit entsteht ein partiell geordneter Baum. Ein Heap wird vor allem für zwei Dinge eingesetzt: Zur Realisierung von gewichteten Prioritätswarteschlangen und zur Sortierung (Heap Sort).

Bei der Sortierung wird eine nicht geordnete Liste in einen binären Heap eingelesen und dabei entsprechend der Heapeigenschaft umstrukturiert. Danach ist die Wurzel genau der Knoten mit dem maximalen Wert, und alle Knoten jeweils kleiner als ihre Elternknoten, aber größer als ihre Kindknoten. Nun beginnt der eigentliche Sortierschritt. Iterativ wird immer der aktuelle Wurzelknoten aus dem Heap entnommen und an den sortieren Bereich angefügt. Danach wird der Heap wieder erneuert und ein neuer Knoten mit dem Maximalwert der übrigen Knoten wandert an die Stelle der Wurzel. Meistens wird diese Datenstruktur auf einem Array realisiert. Das Array wird zunächst in eine gültige Heap-Ordnung überführt. Danach wird jeweils der erste Werte als verbliebenes Maximun in den hinteren Bereich des Arrays einsortiert, wo schrittweise die Ordnung aufgebaut wird. Dabei wird einfach das Wurzelelement mit dem Element an der richtigen Stelle am Ende des Arrays getauscht. Nun wird erneuert der Heap korrigiert.

In der Visualisierung ist der binäre Heap als sogenannter Sunburst Tree dargestellt. Die Wurzel entspricht dem inneren Kreis, die Kindknoten jeweils den konzentrisch abstehenden Kreisbogensegmenten. Die Ordnung entspricht der farblichen Sortierung von Schwarz zu Rot. Im Video sind die einzelnen Phasen gut sichtbar. Zunächst wird die chaotische Ordnung durch eine Ordnung entsprechend des Heaps angepasst. Hier wandern die dunklen Felder nach innen und die roten Felder nach außen. Anschließend beginnt die Sortierung. Im Falle des ersten Elements bedeutet dies das Tauschen des dunkelsten schwarzen Feldes (Kreismitte) mit dem Ende des Arrays. Anschließend wird wieder die Heapstruktur hergestellt. Somit ensteht schrittweise die Ordnung – im Uhrzeigersinn und von außen nach innen.

Realisiert habe ich die animierte Visualisierung mithilfe von Java (zur Grafikgenerierung) und mencoder (Stopmotion). Auf vimeo gibt es außerdem das Video in hoher Qualität.

Originalartikel: Visualisierung Heap / Heap Sort

ioexception.de

Benjamin Erb [] studiert seit 2006 Medieninformatik und interessiert sich insbesondere für Java, Web-Technologien, Ubiquitous Computing, Cloud Computing, verteilte Systeme und Informationsdesign.


Raimar Wagner studiert seit 2005 Informatik mit Anwendungsfach Medizin und interessiert sich für C++ stl, boost & Qt Programmierung, Scientific Visualization, Computer Vision und parallele Rechenkonzepte.


David Langer studiert seit 2006 Medieninformatik und interessiert sich für Web-Entwicklung, jQuery, Business Process Management und Java.


Sebastian Schimmel studiert seit 2006 Informatik mit Anwendungsfach Medizin und interessiert sich für hardwarenahe Aspekte, Robotik, webOs, C/C++ und UNIX/Linux.


Timo Müller studiert seit 2006 Medieninformatik. Er interessiert sich allen voran für Mobile and Ubiquitous Computing, systemnahe Enwticklung und verteilte Systeme, sowie Computer Vision.


Achim Strauß studiert seit 2006 Medieninformatik. Seine Interessen liegen in Themen der Mensch-Computer Interaktion sowie Webentwicklung und UNIX/Linux.


Tobias Schlecht studiert seit 2006 Medieninformatik und interessiert sich vor allem für Software Engineering, Model Driven Architecture, Requirements Engineering, Usability Engineering, Web-Technologien, UML2 und Java.


Fabian Groh studiert seit 2006 Medieninformatik. Seine Interessengebiete sind Computer Graphics, Computer Vision, Computational Photography sowie Ubiquitos Computing.


Matthias Matousek studiert seit 2007 Medieninformatik und interessiert sich besonders für Skriptsprachen, Echtzeitsysteme und Kommunikation.


Michael Müller [] studiert seit 2009 Medieninformatik. Er interessiert sich vor allem für Web-Technologien, Ubiquitous Computing, User-Interfaces, UNIX und Creative Coding.


Falco Nogatz [] studiert seit 2010 Informatik mit Anwendungsfach Mathematik. Er interessiert sich für Web-Technologien, Programmierparadigmen und theoretische Grundlagen.

Archiv

Februar 2015
M D M D F S S
« Mrz    
 1
2345678
9101112131415
16171819202122
232425262728