Flow-Map Viewer
Christoph Bösch (0226079)
Reinhold Preiner (0430380)
VO InfoVis, SS 2008, TU Wien
Dokumentation
Einführung
Mit dem Flow-Map Viewer stellen wir ein Tool zur
Verfügung, dass aus einem geeigneten Datenset automatisch eine Flow-Map
generiert und diese am Bildschirm darstellt.
Flow Map Layouts sind ein geeignetes Mittel zur
Visualisierung von quantitativen Objektbewegungen in einem geographischen
Kontext (meist Landkarten). Sie werden verwendet zur Darstellung von
Statistiken wie Warenexporte, Migrationen u.a. Charakteristischerweise
visualisieren solche Graphen eine gegebene Menge von Bewegungsvektoren mit
einem einheitlichem Ursprung, sowie unterschiedlichen Zielen und Gewichtungen.
Der Nachteil von simplen computergestützten Visualisierungsverfahren, in denen
diese Vektoren als geradlinige Pfeile dargestellt werden, die radial vom
Ursprungspunkt ausgehen, ist die visuelle Überladung, die durch eng beieinander
liegende Pfeile entsteht. Vor allem bei großen Datenmengen geht aufgrund dieses
Effektes die Anschaulichkeit einer Grafik schnell verloren.
D. Phan et al
beschreiben in ihrem Paper „Flow Map Layout“ [1] einen Weg, durch geeignete
Zusammenfassung geographisch benachbarter Vektoren die einzelnen Pfeile
herkömmlicher Visualisierungssysteme durch eine anschauliche Baumstruktur zu
ersetzen (hierarchisches Clustering), welche eine allumfassende
Verzweigungsgrafik in der Massenbewegung zu erhalten.
Anschließend eine detaillierte
Beschreibung der Umsetzung der Rendering-Pipeline sowie die Handhabung des
Tools.
Dateneingabe
Für das Einlesen von Datenfiles ist ein CSVReader zuständig.
Folgendes Datenformat wurde spezifiziert:
Eine Zeile steht für einen Knoten im Graph. Als Trennzeichen dient der Beistrich.
In einer Zeile stehen die x-Koordinate, die y-Koordinate und das Knotengewicht
als double-Wert, mit dem Punkt um die Nachkommastellen abzugrenzen. Als vierter
Wert in der Zeile steht der Labeltext für den Knoten als String. Die Werte
müssen in der eben verwendeten Reihenfolge stehen. Der Root-Knoten zeichnet
sich durch ein Gewicht von -1 aus.
Bsp: Input-CSV-File
Diese Werte werden in einem FMPoint-Objekt gespeichert. Nach dem
Einlesevorgang liegt ein java.util.Vector-Objekt gefüllt mit FMPoint-Objekten
vor. Dieser wird nun in sechs Schritten zu einem übersichtlichen Baum
umgestaltet, der für die Darstellung als Flow Map geeignet ist. Diese Schritte
werden nun näher beschrieben.
Layout-Adjustment
Zuerst gilt
es die Abstände der Knoten soweit zu erhöhen, dass sowohl für Labels als auch
für Kanten zwischen diesen Labels genügend Platz vorhanden ist. Dafür verwenden
wir, dem Paper folgend, den Force Scan Algorithmus, wie von Kazuo Misue et al.
1995 im Paper „Layoutadjustment and the Mental Map“ beschrieben. Der
Punkt-Vector wird zuerst nach aufsteigendem x-Wert sortiert, dann wird die
Abstände der Knoten untereinander verglichen. Falls ein Abstand zu gering ist,
wird eine Force für die beiden betroffenen Knoten errechnet und der Knoten mit
dem höheren x Wert, sowie alle ihm nachfolgenden Knoten um diese Force
verschoben. Dasselbe geschieht für die y-Dimension.
Primary-Hierarchical-Clustering
Im zweiten
Schritt werden jeweils die zwei nächsten Punkte bzw. Cluster zu einem neuen
Cluster zusammengefasst. So entsteht ein binärer Baum dessen Blätter die
ursprünglichen Knoten darstellen. Je mehr Kanten zwischen zwei Blättern liegen,
desto größer auch ihr realer Abstand.
Rooted-Hierarchical-Clustering
In diesem
Schritt wird der als Wurzelknoten gekennzeichnete Knoten wirklich an die Wurzel
des Baumes gebracht. Dies geschieht mit dem Hierarchical-Clustering
Algorithmus. Der angestrebte Root Knoten wird Ebene für Ebene im Baum nach oben
geschoben, die Lücken die er auf höheren Ebenen hinterlässt, werden automatisch
aufgefüllt.
Weight-Calculation
Dieser
Schritt wird in [1] eigentlich zusammen mit dem Vorschritt erwähnt. Aufgrund
unserer individuellen Implementierung (siehe Abschnitt 'Edge-Uncrossing') wurde
er jedoch separat herausgenommen, um ihn später evtl. erneut aufzurufen.
Die
Weight-Calculation ist dafür verantwortlich rekursiv die Gewichte aller
Endknoten des Baumes aufzusummieren, und die Zwischensummen der Gewichte in den
Verzweigungsknoten des Baumes zu speichern (bottom-up: von den Endknoten bis
zum Rootknoten). Diese Informationen werden später im Rendering für die
Berechnung der Kanten-Dicke herangezogen.
Spatial Layout
Hierbei
müssen an den Punkten an denen sich der Baum aufspaltet um zwei Subcluster zu
erreichen Verzweigungsknoten erstellt werden. Die Verzweigungsknoten werden
rekursiv erzeugt, und zwar immer auf einer direkten Linie zwischen dem
aktuellen Ausgangsknoten und dem schwereren Kind bzw. Subcluster. Diese neuen
Knoten besitzen keine Label.
Edge-Routing
Der
Edge-Routing-Schritt im Algorithmus dient dem Auffinden von Kanten, die durch
den Bereich des Graphen verläuft, die dem Ast einer Schwesterkante angehört.
Für solche Fälle soll das Edge-Routing den durchkreuzenden Ast um diesen
Bereich "herumleiten". Im Allgemeinen wurde der Edge-Routing
Algorithmus so umgesetzt, wie er in [1] beschrieben wurde.
Edge-Uncrossing
D. Phan et al
verweisen in ihrem Paper bereits auf das Problem, dass trotz des Edge-Routings
im Vorschritt es im Ergebnis-Graphen zu sich überkreuzenden Kanten kommen kann
[1]. Da auch wir mit dieser Problematik konfrontiert wurden, haben wir einen
neuen Rendering-Schritt eingeführt, das "Edge-Uncrossing".
In diesem Schritt werden restliche, sich
überkreuzende Kanten aufgesucht und die Überkreuzungen aufgelöst. Dies
geschieht durch einen Algorithmus, das iterativ folgende Schritte durchführt:
·
Suche zwei sich überkreuzende
Kanten im Graphen
·
Wurden zwei Kanten a und b
gefunden, deren Liniensegmente sich überkreuzen, unterscheide:
o Ist der Root-Knoten des Graphen der einzige gemeinsame
Vorfahre der beiden Vaterknoten von a und b, dann löse die Überkreuzung, indem
die Vaterknoten von a und b getauscht werden.
o Ist der Kindknoten von b in der Hierarchie ein Vorfahre
des Vaterknotens von a, so wird am Schnittpunkt c zwischen a und b ein neuer
Knoten eingefügt, der die Kante b in zwei neue Kanten aufteilt, und der neue
Vaterknoten von a ist.
·
Diese Schritte werden solange ausgeführt, bis der Graph
frei von Überkreuzungen ist
·
Da aufgrund des Relinks der Teiläste der Graphen jedoch
wieder neue Überkreuzungen entstehen können, besteht die Gefahr einer
Endlosschleife. Daher wird der Vorgang nach einer gewissen Anzahl von
Iterationen beendet.
Hinweis: Da nach einem Neu-Verlinken des Baumes die im Schritt
"Weight-Calculation" berechnete Gewicht-Hierarchie zerstört wird,
wird nach einem eventuellen Edge-Uncrossing die Weight-Calculation erneut
durchgeführt.
Rendering
Das
Rendering wird grundsätzlich vom prefuse Framework übernommen, bzw. kann durch
bestehende Komponenten realisiert werden. Wichtige Funktionen wie das Zoomen
sind so schnell umsetzbar. Der Flow-Map Layout Ansatz, den wir verfolgen,
erfordert allerdings eine Erweiterung der prefuse-Standartfunktionalität.
LabelRenderer
Um den Text
für ein Label aus einer FMPoint Variablen auszulesen ist es nötig die getText(VisualItem
item) Methode der LabelRenderer Klasse zu überschreiben. Diese neue
Methode holt zuerst das FMPoint Objekt aus dem VisualItem und
gibt anschließend den label String zurück. Für diesen Zweck haben wir die
Klasse FMPointRenderer erstellt, die von prefuse.renderer.LabelRenderer
abgeleitet ist.
TreeLayout
Für die
Positionierung der Knoten der Flow Map sollen auch die Koordinaten aus dem FMPoint
des VisualItem Objekts verwendet werden. Dafür musste die Klasse FixedPositionTreeLayout von prefuse.action.layout.graph.TreeLayout
abgeleitet werden. Um die richtigen Koordinaten zu erhalten haben wir die
Funktion getLayoutAnchor() so überschrieben, dass sie auf die Daten des FMPoint
Objekts zugreift.
EdgeRenderer
Um dem Baum
ein möglichst organisches Aussehen zu geben wird im Paper die Darstellung der
Kanten als Catmull-Rom Splines vorgeschlagen. Auch diese Splines werden von
prefuse nicht standartmäßig unterstützt. Um diesen Mangel auszugleichen haben
wir einen eigenen CatmullRomSplineEdgeRenderer geschrieben, der eine
Unterklasse von prefuse.renderer.EdgeRenderer ist. In dieser Klasse ist
die getRawShape(VisualItem item)
Methode
dafür zuständig, eine visuelle Repräsentation einer Kante als java.awt.Shape
Objekt zu liefern.
Der Start-
und Endpunkt des Splines und der Kante sind identisch, der Spline benötigt aber
an jedem Ende noch einen Kontrollpunkt. Dafür wird der Vaterknoten des
Startpunktes und ein gewichteter Mittelwert aus den Kindknoten des Endknotens
verwendet. Gewichtet wird mit dem Knotengewicht das ohnehin jeder Knoten im
angehängten FMPoint gespeichert hat.
Durch diese
Wahl der Kontrollpunkte entsteht ein fließender Übergang zwischen aufeinander
folgenden Kanten.
Interface
Das
Interface besteht aus einem großzügigen Fenster, durch das der Baum betrachtet
werden kann. Der Baum kann hier mit der Maus verschoben werden. As kann mit dem
Mausrad hin oder weg gezoomt werden.
In einer Leiste unterhalb dieses Fensters können einige Einstellungen
gemacht werden. Hier lassen sich die Punkte
·
Layout-Adjustment,
·
Edge-Routing und
·
Edge-Uncrossing
durch eine
Checkbox optional ein- und ausschalten. Werden sie nicht durchführt, generiert
das Programm trotzdem einen Baum der die Kriterien einer Flow-Map erfüllt, die
Übersichtlichkeit und Lesbarkeit sind allerdings unter Umständen stark
eingeschränkt. (Primary- und Rooted-Hierarchical-Clustering sowie Spatial-Layout sind
obligatorische Schritte. Sie überführen die Ausgangsdaten in die für eine Flow-Map nötige
Baumstruktur.) Über einen FileChooser kann auch eine neue Datenquelle in Form
eines CSV-Files ausgewählt werden.
Screenshots
Links: Flow Map-Datensatz ohne Edge-Routing und ohne
Edge-Uncrossing.
Mitte: Derselbe Datensatz mit Edge-Routing. Baumzweige werden bereits um andere
Punktcluster herumgeführt, einzelne Kanten-Überkreuzungen tretten jedoch immer
noch auf.
Rechts: Derselbe Datensatz mit Edge-Routing und Edge-Uncrossing. Wie man sieht,
wurden alle restlichen Kantenkreuzungen entfernt.
Download
Referenzen
[1] D. Phan, L. Xiao, R. Yeh, P. Hanrahan, T. Winograd, "Flow Map Layout",
INFOVIS '05: Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization (2005), IEEE Computer Society, p. 29,