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.

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.

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.

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.

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 – 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).

Der Typotisch ist eine weiße Box, etwa so hoch wie eine Arbeitsplatte. Die Oberseite besteht aus einer Milchglasscheibe, auf die der Benutzer Wortplättchen legen kann. Auf einer großen Leinwand oder einem Bildschirm wird dann eine Animation der gelegten Worte gezeigt, wie wenn die Milchglasscheibe mit einer Kamera abgefahren würden. Je nachdem in welchem Winkel die Wortplättchen zueinander liegen, macht die Kamera eine entsprechende Drehung, auf 90° gerundet. Manche Wörter haben in der Animation einen fest zugeordneten Effekt. Der Typotisch soll eine Verknüpfung von Kinetischer Typographie und einer besonderen Interaktionsmöglichkeit sein.

Material

Die Box ist aus 12mm dicken MDF-Platten gebaut. Oben ist ein 30cm*30cm große Aussparung für die Milchglassplatte die dann auf Ausfräsungen am Rand der Aussparung gelegt werden kann. Im Inneren der Box sind zwei Bretter angebracht.

Die Wortplättchen sind aus Magnetgummi. Auf der vorderen Seite eines solchen Plättchens steht das Wort geschrieben und auf der Rückseite ist das Wort als QR-Code dargestellt.

So funktioniert´s

Auf dem oberen inneren Brett wird eine Digitalkamera, bei uns eine Canon Powershot A620, mit Objektiv nach oben, angebracht. Auf dem unteren Brett steht ein mit der Kamera verbundener Laptop. Durch die Fernsteuerungssoftware von Canon wird alle zehn Sekunden ein Foto von der Milchglasscheibe gemacht und in einen Ordner abgelegt. Dieser Ordner ist für den zweiten Laptop im lokalen Netzwerk freigegeben. Die Software die auf diesem Laptop läuft, greift auf die Fotos zu und generiert die Animation.

Software & Libraries

Die Analyse des Fotos wurde mit Processing (1) realisiert. Das Foto wird gelesen, potentielle Plättchen erkannt, dank einer Bibliothek für OpenCV für Processing (2) Dann wird deren Lage bestimmt und ihre Drehung auf 0°, 90°, 180° oder 270° gerundet. Anschließend wird die Reihenfolge der Plättchen ausgelesen, angefangen an der linken oberen Ecke der Milchglasscheibe. Dabei werden auch die QR-Codes (3) dekodiert.

1. http://processing.org
2. http://ubaa.net/shared/processing/opencv/
3. http://qrcode.sourceforge.jp/

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:

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
}

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

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

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

vtkActor octahedronActor
   octahedronActor SetMapper octahedronMapper

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:

und das Ergebnis in den Tcl Bindings:

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

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