IOException.de » visualisierung http://www.ioexception.de Ausgewählter Nerdkram von Informatikstudenten der Uni Ulm Wed, 19 Mar 2014 22:01:00 +0000 de-DE hourly 1 http://wordpress.org/?v=3.9.1 Einfache Visualisierung von Geodaten – Teil 2: Leaflet & jquery.couch.js http://www.ioexception.de/2011/08/30/einfache-visualisierung-von-geodaten-%e2%80%93-teil-2-leaflet-jquery-couch-js/ http://www.ioexception.de/2011/08/30/einfache-visualisierung-von-geodaten-%e2%80%93-teil-2-leaflet-jquery-couch-js/#comments Tue, 30 Aug 2011 09:48:49 +0000 http://www.ioexception.de/?p=1119 Im vorherigen Teil haben wir gesehen, wie man Geodaten mithilfe von CouchDB abspeichern kann. Da diese Datenbank zugleich ein Webserver ist und die Daten im JSON-Format gespeichert werden, eignet sie CouchDB auch gut für AJAX-Abfragen. Hierfür gibt es eine auf jQuery aufbauende Library namens jquery.couch.js, die von den AJAX-Requests abstrahiert und direkt browser-seitige Interaktionen mit der Datenbank ermöglicht.

Im diesem Beitrag soll gezeigt werden, wie man mit der offenen Karten-Library Leaflet und jquery.couch.js geographische Daten aus CouchDB heraus auf einer Karten anzeigen kann.

Beispiel-Visualisierung von ulmapi.de, ebenfalls basierend auf CouchDB und Leaflet.

Wir verwenden die CouchApp aus dem ersten Teil weiter, und fügen zu den bisherigen Map/Reduce Views noch statische HTML- und Javascript-Dateien hinzu (im _attachments Ordner), die dann im Browser abgerufen werden können. Beim Aufruf dieser Webseite wird ein HTML-Grundgerüst übertragen, sowie eine JavaScript-Datei, die beim Aufruf die eigentlichen Datensätze via jquery.couch.js aus der CouchDB nachlädt.

Als Mapping-Library verwenden wir Leaflet, eine Open-Source Bibliothek für Kartendarstellungen im Browser. Leaflet abstrahiert von verschiedenen Kartenprovidern und erlaubt es somit, unterschiedliche Datenquellen zu verwenden, wie zum Beispiel auch Bing Maps oder Cloudmade. Letzteres ist ein Service, der auf Basis der Open Street Map Daten Kartenkacheln mit individuellen Stilen rendert und hostet – für Visualisierungen oft sehr hilfreich, da reguläre Karten meist zu viele Karteninformationen enthalten oder farblich überladen sind. In unserem Fall haben wir einen einfach Graustufenkarte gewählt. Leaflet selbst lässt sich relativ leicht verwenden, es muss eine CSS-Datei sowie eine JavaScript-Datei importiert werden, und ein div-Block im HTML enthalten sein, worin später die Karte gerendert werden soll. Somit sieht unser HTML-Gerüst zu Beginn so aus:

<!doctype html>
<html>
<head>
	<link rel="stylesheet" href="style/leaflet.css" />
	<script type="text/javascript" src="js/jquery.min.js"></script>
	<script type="text/javascript" src="js/jquery.couch.js"></script>
	<script type="text/javascript" src="js/leaflet.js"></script>
	<script type="text/javascript" src="js/maploader.js"></script>
</head>
<body>
	<div id="map"></div>
</body>
</html>

Es werden jQuery, jquery.couch.js und die Leaflet-Libs geladen, und die letzte importierte JavaScript-Datei soll nun unseren Code zum initialisieren der Karte und dem Laden der Daten aus der CouchDB enthalten. Zunächst erstellen wir eine Karte und rendern sie, sobald die Seite vollständig geladen wurde (jQuery Callback für document.ready):

$(document).ready(function(){

		var cloudmadeUrl = 'http://{s}.tile.cloudmade.com/[YOUR_API_KEY]/33481/256/{z}/{x}/{y}.png';
		var cloudmadeAttribution = 'UlmApi.de / Shape Files: Stadt Ulm (cc-by-sa), Map data &copy; 2011 OpenStreetMap contributors, Imagery &copy; 2011 CloudMade';
		var cloudmade = new L.TileLayer(
			cloudmadeUrl, {
				maxZoom : 18,
				attribution : cloudmadeAttribution
		});

		var map = new L.Map('map', {
			center : new L.LatLng(48.399976,9.995399),
			zoom : 12,
			layers : [ cloudmade ],
			zoomControl : false
		});
});

In der cloudmadeUrl muss für Cloudmade Karte ein korrekter API-Key angegeben werden, der nächste Parameter im Pfad identifiziert den Kartentyp. Beim Initialisieren der Karte wird dann die ID des divs angeben, bei uns ‘map’. Nun sollte unsere Karte bereits dargestellt werden, nachdem wir die CouchApp neu deployen (außerhalb des Fokus dieses Artikels, mehr dazu auf couchapp.org).

Was nun noch fehlt, ist das Nachladen der Geodaten aus der CouchDB und die Anzeige auf der Karte. Hierfür verwenden wir jquery.couch.js als Wrapper für die AJAX-Requests gegen CouchDB und die GeoJSON-Funktionalität von Leaflet:

$.couch.db('database_name').view('design_doc_name/view_name', {

	success: function(data){
		if(data && data.rows && data.rows.length){

			var geoJsonLayer = new L.GeoJSON();

			for(var i = 0;i<data.rows.length;i++){
				geoJsonLayer.addGeoJSON(data.rows[i].value.geometry);
			}

			map.addLayer(geoJsonLayer);
		}
	}
});

Das obige Snippet sollte im vorherigen Code hinter der Erzeugung der Karte eingefügt werden. Es ruft von der Datenbank ‘database_name’ den View ‘view_name’ des Design-Dokuments ‘design_doc_name’ auf, und iteriert bei erfolgreicher Abfrage über alle Zeilen. Von jeder Zeile wird dabei die geometry-Property zu einem GeoJSON-Layer hinzugefügt, der am Ende an die Karte übergeben wird. Da unser View aus Teil 1 bereits GeoJSON generiert, und Leaflet nativ GeoJSON lesen und darstellen kann, ist das Hinzufügen von Geodaten auf die Karte sehr einfach.

Hier noch ein paar weiterführende Links mit vertiefenden Inhalten zu den einzelnen Themen:

]]>
http://www.ioexception.de/2011/08/30/einfache-visualisierung-von-geodaten-%e2%80%93-teil-2-leaflet-jquery-couch-js/feed/ 3
OpenStreetMap-Rendering mit Mapnik http://www.ioexception.de/2010/02/16/openstreetmap-rendering-mit-mapnik/ http://www.ioexception.de/2010/02/16/openstreetmap-rendering-mit-mapnik/#comments Tue, 16 Feb 2010 17:21:01 +0000 http://www.ioexception.de/?p=464 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
]]>
http://www.ioexception.de/2010/02/16/openstreetmap-rendering-mit-mapnik/feed/ 2
Typotisch http://www.ioexception.de/2009/09/18/typotisch/ http://www.ioexception.de/2009/09/18/typotisch/#comments Fri, 18 Sep 2009 15:08:20 +0000 http://www.ioexception.de/?p=306

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

typotisch2 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

typotisch3 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

typotisch_qr 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/
]]>
http://www.ioexception.de/2009/09/18/typotisch/feed/ 0
Vektorfeldvisualisierung durch Flow Streams http://www.ioexception.de/2009/07/28/vektorfeldvisualisierung-durch-flow-streams/ http://www.ioexception.de/2009/07/28/vektorfeldvisualisierung-durch-flow-streams/#comments Tue, 28 Jul 2009 15:45:49 +0000 http://www.ioexception.de/?p=278 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

]]>
http://www.ioexception.de/2009/07/28/vektorfeldvisualisierung-durch-flow-streams/feed/ 0
Die VTK Renderpipeline am Beispiel eines Oktaeders http://www.ioexception.de/2009/07/03/vtk_renderpipeline/ http://www.ioexception.de/2009/07/03/vtk_renderpipeline/#comments Fri, 03 Jul 2009 21:31:05 +0000 http://www.ioexception.de/?p=199 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

]]>
http://www.ioexception.de/2009/07/03/vtk_renderpipeline/feed/ 0
Videoexport aus VTK mittels vtkAVIWriter http://www.ioexception.de/2009/06/23/videoexport-aus-vtk-mittels-vtkaviwriter/ http://www.ioexception.de/2009/06/23/videoexport-aus-vtk-mittels-vtkaviwriter/#comments Tue, 23 Jun 2009 20:55:44 +0000 http://www.ioexception.de/?p=169 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”.

]]>
http://www.ioexception.de/2009/06/23/videoexport-aus-vtk-mittels-vtkaviwriter/feed/ 0
Visualisierung Heap / Heap Sort http://www.ioexception.de/2009/06/21/visualisierung-heap-heap-sort/ http://www.ioexception.de/2009/06/21/visualisierung-heap-heap-sort/#comments Sun, 21 Jun 2009 21:12:34 +0000 http://www.ioexception.de/?p=83 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

]]>
http://www.ioexception.de/2009/06/21/visualisierung-heap-heap-sort/feed/ 0
Visualisierung von Winkelgeschwindigkeiten in Vektorfeldern http://www.ioexception.de/2009/06/21/visualisierung-von-winkelgeschwindigkeiten-in-vektorfeldern/ http://www.ioexception.de/2009/06/21/visualisierung-von-winkelgeschwindigkeiten-in-vektorfeldern/#comments Sun, 21 Jun 2009 21:11:10 +0000 http://www.ioexception.de/?p=45 Um für ein gegebenes Beschleunigungsfeld die Winkelgeschwindigkeiten zu visualisieren bietet es sich an, an äquidistant gestreuten Stützstellen Würfel zu visualisieren die um die Beschleunigungsachse rotiert. Ein mögliches Beispielfeld ist:

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

Für die Umsetzung wurde VTK mit den Tcl Bindings verwendet. Zu Beginn benötigen wir zwei vtkPoints, eines für die geglyphten Würfel und eins für die eigentlichen Punkte im Raum. Im folgenden können wir gridPoints, glyPoints als gegeben vorraussetzen. Des weiteren können wir 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 müssen die Würfel Glyphs initialisiert werden und zu jedem cube_$i ein Mapper und Filter definiert werden.

#iterate thru all glyph points
for {set i 0} {$i < [eval glyPoints GetNumberOfPoints]} {incr i} {  
  
  #create cubes
  vtkCubeSource cube_$i
    set pt [glyPoints GetPoint $i]
    
  #get nearest pnt
  set ref [eval loc FindClosestPoint [lindex $pt 0] [lindex $pt 1] [lindex $pt 2] ] 
  set vl [velocity GetTuple3 $ref]
      
      
  #turn and translate
  vtkTransform cubeTransform_$i
    cubeTransform_$i PostMultiply
    cubeTransform_$i Translate 0 0 0
    set n [eval norm [lindex $vl 0] [lindex $vl 1] [lindex $vl 2]]
    cubeTransform_$i RotateWXYZ $n [lindex $vl 0] [lindex $vl 1] [lindex $vl 2]
    cubeTransform_$i Translate [lindex $pt 0] [lindex $pt 1] [lindex $pt 2]
  
  #create filter for transformation
  vtkTransformPolyDataFilter cubeTransformFilter_$i
    cubeTransformFilter_$i SetInput [cube_$i GetOutput ]
    cubeTransformFilter_$i SetTransform cubeTransform_$i
  
  #create mapper
  vtkPolyDataMapper   cubeMapper_$i
      cubeMapper_$i SetInput [cubeTransformFilter_$i GetOutput]
}

Im letzten Schritt folgt die Animation mit der Kameradrehung.

#render 900 frames
for {set k 0} {$k<900} {incr k} {
    
    
  #rotate all glyphs    
  for {set i 0} {$i<[eval glyPoints GetNumberOfPoints]} {incr i} {
    set pt [glyPoints GetPoint $i]
    
    #find velocity to point
    set ref [eval loc FindClosestPoint [lindex $pt 0] [lindex $pt 1] [lindex $pt 2] ] 
    set vl [velocity GetTuple3 $ref]
    
    #transform every cube
    cubeTransform_$i Identity
    cubeTransform_$i Translate 0 0 0
  
    set n [eval norm [lindex $vl 0] [lindex $vl 1] [lindex $vl 2]]
    cubeTransform_$i RotateWXYZ [expr $k * $n/1000] [lindex $vl 0] [lindex $vl 1] [lindex $vl 2]
    cubeTransform_$i Translate [lindex $pt 0] [lindex $pt 1] [lindex $pt 2]
  
  
  }

  #move camera & render frame
  [ren1 GetActiveCamera] Azimuth 0.1
  renWin Render
 
}

Mit zusätzlicher Einblendung der Beschleunigungvektoren sieht das Ergebnis dann so aus:


]]>
http://www.ioexception.de/2009/06/21/visualisierung-von-winkelgeschwindigkeiten-in-vektorfeldern/feed/ 1