Diplomarbeit€¦ · konstruktive Kritik und für die vielen hilfreichen Anmerkungen. Bedanken möchte ich mich auch bei sehr guten Freunden für eine Uni-nahe Unterkunft und beste

Brandenburgische Technische Universität CottbusInstitut für InformatikLehrstuhl Software-Systemtechnik

Diplomarbeit

Entwurf, Umsetzung und Evaluation einer Metapher zur Visualisierung veränderlicher

Dekompositionsstrukturen

vorgelegt von Michael TauerMatrikel Nr.: 2108649

Abgabedatum: 26. Oktober 2009

Selbstständigkeitserklärung

Ich erkläre hiermit, dass ich die vorliegende Diplomarbeit selbstständig und ohne unerlaubte Hilfe angefertigt habe. Alle verwendeten Hilfsmittel und Quellen sind im Literaturverzeichnis vollständig aufgeführt und die aus den benutzten Quellen wörtlich oder inhaltlich entnommenen Stellen als solche kenntlich gemacht.

Cottbus, Oktober 2009

Danksagung

An dieser Stelle möchte ich mich bei allen Personen bedanken, die mich bei der Er-stellung dieser Arbeit unterstützt haben.Bei Herrn Prof. Dr. C. Lewerentz bedanke ich mich für die Vergabe und Betreuung der Diplomarbeit.Ebenfalls bedanken möchte ich mich bei meinem Betreuer Frank Steinbrückner für die engagierte Betreuung und für viele hilfreiche Diskussionen.Ein besonderer Dank gilt meiner Schwester für das Korrekturlesen dieser Arbeit, für die konstruktive Kritik und für die vielen hilfreichen Anmerkungen.Bedanken möchte ich mich auch bei sehr guten Freunden für eine Uni-nahe Unterkunft und beste Gesellschaft.Nicht zuletzt möchte ich meinen Eltern danken, die mir durch ihre fortwährende Unterstützung das Studium und letztlich diese Arbeit ermöglichten und sie mit Anteil-nahme verfolgt haben.

INHALTSVERZEICHNIS

Inhaltsverzeichnis

1 Einführung..........................................................................................................................................................11.1 Motivation..........................................................................................................................................................11.2 Ziele......................................................................................................................................................................11.3 Gliederung.........................................................................................................................................................22 Relevante Literatur..........................................................................................................................................32.1 Visualisierung veränderlicher Datenstrukturen................................................................................32.1.1 Vergleich von Bäumen.....................................................................................................................32.1.2 Software-Evolution...........................................................................................................................32.2 Stadtmetapher.................................................................................................................................................52.3 Stadt-System.....................................................................................................................................................63 Analyse.................................................................................................................................................................73.1 Definitionen......................................................................................................................................................73.1.1 Graph......................................................................................................................................................73.1.2 Baum......................................................................................................................................................73.1.3 Veränderlicher Baum (CT).............................................................................................................73.1.4 Attributierter Baum (ACT)............................................................................................................83.1.5 Gelevelter Baum (LACT).................................................................................................................83.2 Layout-Anforderungen.................................................................................................................................83.2.1 Stabilität................................................................................................................................................83.2.2 Kompaktheit........................................................................................................................................93.2.3 Skalierbarkeit...................................................................................................................................103.3 Baum-Layouts................................................................................................................................................103.3.1 Level-Layout und Radiales Layout...........................................................................................103.3.2 Kräfte-basiertes Layout................................................................................................................113.3.3 Treemaps...........................................................................................................................................113.3.4 Hyperbolische Bäume...................................................................................................................123.3.5 Weitere Visualisierungen.............................................................................................................133.3.6 Zusammenfassung..........................................................................................................................133.4 Layouts für veränderliche Bäume.........................................................................................................133.4.1 Modellierung von Systemänderungen....................................................................................133.4.2 Abbilden der Baum-Struktur.....................................................................................................143.4.3 Abbilden der Baum-Entwicklung.............................................................................................144 Evolution City-Layout..................................................................................................................................174.1 Layout-Algorithmus....................................................................................................................................174.2 Repräsentation und Layout des Level 1-Knotens............................................................................184.2.1 Repräsentation als zentraler Platz...........................................................................................184.2.2 Repräsentation als Autobahn.....................................................................................................194.3 Repräsentation und Layout der Level 2-Knoten..............................................................................224.3.1 Layout von Level 2-Knoten mit Level 2-Kindern................................................................234.3.2 Layout von Level 2-Knoten mit Level 3-Kindern................................................................254.4 Repräsentation und Layout von Level 3-Knoten.............................................................................264.5 Höhenfeld........................................................................................................................................................274.5.1 Implizite Flächen und Metaballs...............................................................................................274.5.2 Höhenfeld-Funktion.......................................................................................................................28vii

INHALTSVERZEICHNIS

4.5.3 Darstellung des Höhenfeldes.....................................................................................................314.5.4 Entwicklungsrichtung des Geländes.......................................................................................334.6 Evolution Tower...........................................................................................................................................354.7 Abbilden von Knotenattributen auf visuelle Eigenschaften der Repräsentanten..............374.7.1 Farbfunktionen................................................................................................................................384.7.2 Float-Funktionen............................................................................................................................465 Evaluierung......................................................................................................................................................475.1 Bewertung der Stabilität...........................................................................................................................475.1.1 Stabilitätsmaße................................................................................................................................475.1.2 Abhängigkeiten der Stabilität....................................................................................................565.2 Bewertung der Kompaktheit...................................................................................................................665.2.1 Kompaktheitsmaße........................................................................................................................665.2.2 Abhängigkeiten der Kompaktheit............................................................................................705.3 Bewertung der Skalierbarkeit.................................................................................................................815.4 Zusammenfassung.......................................................................................................................................816 Anhang...............................................................................................................................................................836.1 Grundlegende Algorithmen.....................................................................................................................836.1.1 Die konvexe Hülle...........................................................................................................................836.1.2 Der kleinster umschließender Kreis.......................................................................................84 Literaturverzeichnis.......................................................................................................................................85 Abbildungsverzeichnis...................................................................................................................................89

viii

1 EINFÜHRUNG

1 Einführung

1.1 MotivationDie Visualisierung von Graphen und Bäumen spielt in der Informationsdarstellung und besonders bei der Software-Visualisierung eine wichtige Rolle. Obwohl es bereits eine Vielzahl von Techniken und Algorithmen zur Graph-basierten Softwaredarstellung gibt, beruht die Erzeugung fast aller Visualisierungen ausschließlich auf Informationen eines Zeitpunktes. Dies kann zu stark veränderlichen Visualisierungen des selben Software-Systems für unterschied-liche Versionen führen.Innerhalb von Software-Entwicklungsprozessen erfordern variierende Visualisierungen mit jeder neuen Version einen Mehraufwand an Einarbeitungszeit, da sich bereits bekannte Anordnungsmuster von graphischen Objekten ändern und Orientierungspunkte in den Darstellungen verloren gehen. Daher sind viele existierende Ansätze nur bedingt für einen entwicklungsbegleitenden Einsatz geeignet.Unter Ausnutzung von Informationen und Layout-Berechnungen zurückliegender Versionen lassen sich Visualisierungen erzeugen, die für verschiedener Versionen des selben Systems eine hohe Stabilität aufweisen und sich somit gut für die entwicklungsbegleitende Anwendung eignen. Durch eine Erweiterung des zu visualisierenden Datenmodells um die Dimension der Zeit, ist es außerdem möglich, Aspekte darzustellen, die Analysen der Entwicklungsgeschichte sowie Entwicklungsprognosen zulassen.Da die Arbeit durch die Softwareanalyse motiviert ist, liegt ihr Fokus in der Visualisierung der Entwicklungsgeschichte von Softwaresystemen. Dennoch kann die beschriebene Darstellungs-form äquivalent auf zeitlich veränderliche und hierarchisch organisierte Daten aus anderen Bereichen angewandt werden. Beispiele hierfür sind die Entwicklung phylogenetischer Stammbäume und veränderliche hierarchische Organisierungsstrukturen im Kontext von Personal- und Ressourcenmanagement.1.2 ZieleZiel der Arbeit ist es, eine dreidimensionale Stadtvisualisierung zu entwerfen, umzusetzen und zu evaluieren, welche die strukturelle Entwicklung eines Softwaresystems und den Verlauf von Kennzahlen der abgebildeten Systemelemente darstellt.In der Informationsvisualisierung bezeichnen Metaphern Konzepte zur Abbildung komplexer Daten auf einen allgemein bekannten Gegenstandsbereich. Für die Umsetzung der Arbeit wird die Stadtmetapher verwendet, die ein Softwaresystem als „Software-Stadt“ darstellt. Ein hierarchisches Straßennetz bildet hierbei die Dekompositionsstruktur des Systems oberhalb eines Basislevels ab. Die Basiselemente selbst sind als Gebäude entsprechend ihrer De-kompositionsbeziehung entlang der Straßen angeordnet, wobei die Entfernungen der Ge-bäude und abzweigender Straßen zum Straßenursprung der übergeordneten Straße Aussagen über den Entstehungszeitpunkt der Elemente zulassen. Zusätzlich lässt sich der Entstehungs-zeitpunkt der visualisierten Systemelemente in der Stadtszene auf die Höhe der Objekt-Grund-flächen abbilden. Durch ein dargestelltes Geländemodell soll die Lesbarkeit dieser Höhen-

1

KAPITEL 1. EINFÜHRUNG

information verbessert werden. Falls im Laufe der Entwicklung Elemente wieder aus dem System entfernt werden, sind sie durch grafische Markierungen kenntlich gemacht.Ausgehend von den beschriebenen Abbildungsvorschriften implementiert ein Prototyp das konkrete Konzept. Dieser wird als Plugin in die bestehende Werkzeuglandschaft CrocoCosmos [LSS02] integriert.1.3 GliederungEinleitend gibt das Kapitel 2 einen Überblick über Literatur, die in Bezug auf Aufgabenstellung und Ziel der Arbeit von Bedeutung sind und stellt Veröffentlichungen aus den Themen-bereichen Softwarevisualisierung, Visualisierung veränderlicher Datenstrukturen und Stadt-metapher vor. Die restliche Arbeit ist in drei Teile unterteilt: Analyse, Evolution City-Layout und Evaluierung. Das Kapitel 3 definiert zuerst eine veränderliche Baumstruktur und erarbeitet wichtige An-forderungen, die an das zu entwickelnde Layout gestellt werden. Danach untersucht es existierende Layout-Verfahren bezüglich der Anforderungen und analysiert mögliche Layout-Ansätze für die Visualisierung veränderlicher Bäume.Ein konkretes Layout, das einen veränderlichen Baum als Stadtszene visualisiert, ist in Kapitel 4 beschrieben. Es geht dabei ausführlich auf die verschiedenen Repräsentationen der Baum-elemente ein und beschreibt wichtige Teilschritte des entwickelten und umgesetzten Layout-Algorithmus. Kapitel 5 evaluiert das vorgestellte Stadt-Layout bezüglich der definierten Anforderungen Stabilität, Kompaktheit und Skalierbarkeit. Dabei erarbeitet es zuerst Maße zum objektiven Be-stimmen der Stabilität und Kompaktheit und untersucht dann die Abhängigkeit verschiedener Layout-Parameter und Baumeigenschaften auf die Layout-Stabilität und Layout-Kompaktheit.

2

2 RELEVANTE LITERATUR

2 Relevante Literatur

2.1 Visualisierung veränderlicher DatenstrukturenDie Betrachtung der Struktur und Attributausprägungen von Bäumen und Baumelementen über die Zeit ermöglicht es, modellierte Systeme besser einschätzen zu können und Trends in der Systementwicklung vorherzusehen. Für Visualisierungssysteme bedeutet die zusätzliche Dimension der Zeit neue Anforderungen, da sich der Umfang der zu visualisierenden Informationen um den Faktor der Versionenanzahl erhöht.2.1.1 Vergleich von BäumenUm die Informationsmenge zunächst zu begrenzen, gibt es die Möglichkeit, jeweils zwei Versionen einer Baumstruktur vergleichend zu visualisieren. In [MGTZZ03] beschreibt Munzner et al. eine so genannte Focus+Context-Technik zum visuellen Vergleich großer Baumstrukturen. Das vorgestellte Werkzeug TreeJuxtaposer stellt zwei zu vergleichende Bäume nebeneinander dar und hebt Unterschiede farblich hervor. Eine ähnliche Herangehensweise ist in [HW08] von Holten et al. beschrieben. Hier werden die zu vergleichenden Bäume übereinander oder nebeneinander dargestellt und Unterschiede durch gebündelte Kanten visualisiert, die jeweils gleiche Elemente verschiedener Versionen miteinander verbinden. Abbildung 1 zeigt im oberen Bereich (a) eine Darstellung des Werkzeugs TreeJuxtaposer und im untere Bereich (b) ein Beispiel der Arbeit [HW08].Beide Ansätze sind konzeptionell für den Vergleich von genau zwei Versionen ausgelegt und lassen sich nicht für Visuali-sierungen beliebig vieler Versionen erweitern.2.1.2 Software-EvolutionEine Möglichkeit zur Visualisierung der Entwicklungsgeschichte eines Softwaresystems stellt Wettel et al. in [WL08b] als CodeCity vor. Motiviert durch Verbesserungen im Reverse Engineering-Prozess visualisiert der beschriebenen Ansatz die Geschichte eines Softwaresystems bis zu einer bestimmten Version. Die dreidimensionale Visualisierung basiert auf der in Kapitel 2.2 beschriebenen Stadtmetapher. Gebäudequader repräsentieren dabei die Klassen des Softwaresystems. Ineinander verschachtelte Grundflächen bilden die Package-Hierarchie ab. Die Evolution bis zu einem bestimmten Zeitpunkt des Systems kann einerseits durch ein Durchlaufen der Versionen sichtbar gemacht werden. Zum anderen bilden Einfärbungen der Layout-Objekte die Entstehungszeitpunkte der Systemelemente in einzelnen statischen Darstellungen ab.

3

Abbildung 1: Verglei-chende Visualisierung zweier Baumversionen (Bildquellen: [MGTZZ03], [HW08])

KAPITEL 2. RELEVANTE LITERATUR

Die Rückwärtsanalyse der Entwicklungsgeschichte eines Softwaresystems wird mit dem Werkzeug für viele Anwendungsszenarien unterstützt. Bei einem entwicklungsbegleitenden Einsatz dagegen variieren die Visualisierungen sehr stark. Es ist kaum möglich, den Repräsentanten eines bestimmten System-elements über verschiedene Versionen hinweg zu verfolgen, was zu Desorientierungen mit jeder neuen Version führen kann. Einen weiteren Ansatz zur Visualisierung der Software-Evolution stellt die EvolutionMatrix dar, wie sie in [Lan01] beschrieben ist. Sie visualisiert über den Entwicklungszeitraum eines Softwaresystems die Existenz von Klassen sowie die Softwaremetriken NOM (Number of Methods) und NIV (Number of Instance Variables) für jede Klasse in einer zweidimensionalen Rasterdarstellung. Jede Version einer Klasse wird dabei innerhalb einer Zelle des Rasters als Rechteck repräsentiert, wobei die Breite des Rechtecks durch die NOM-Metrik und die Höhe durch die NIV-Metrik bestimmt ist. Die zeitliche Entwicklung der Metriken einer Klasse lässt sich in einer Zeile des Rasters ablesen. Jede Spalte stellt eine Momentaufnahme des Systems für eine Version dar. Dieser Zusammenhang ist schematisch in der oberen Darstellung der Abbildung 3 aufgezeigt. Die untere Darstellung zeigt eine Visualisierung der EvolutionMatrix anhand eines Beispiels. Basierend auf der EvolutionMatrix beschreibt Lanza in [Lan01] außerdem eine Möglichkeit, Klassen durch ihre Entwicklungscharakteristiken zu kategorisieren. Dabei bezeichnet er z.B. Klassen, die im Laufe ihrer Entwicklung immer wieder wachsen und schrumpfen als Pulsar; Klassen, deren Größe plötzlich ansteigt als Supernova und Klassen, die bis auf eine Minimalgröße schrumpfen als White Dwarf (Weißer Zwerg). Weitere beschriebene Klassenkategorien sind: Red Giant (Roter Riese), Stagnant, Dayfly und Persistent. Motiviert ist die Kategorisierung durch eine schnelle Identifikation von Designproblemen, da jede Kategorie auf spezielle Probleme hinweist. Die erzeugten Visualisierungen der EvolutionMatrix sind bei einem entwicklungsbegleitenden Einsatz sehr stabil. Falls viele Klassen des Systems für einen langen Zeitraum in der Entwicklungsgeschichte der Software existieren, sind die grafischen Objekte der Visualisierungen innerhalb des Rasters außerdem effizient und kompakt angeordnet. Allerdings stellt das Layout nur einzelne Klassen eines Softwaresystems dar und lässt die Dekompositionsstruktur und übergeordnete System-elemente unbeachtet.

4

Abbildung 2: Färbung der System-elemente nach ihrer Entstehung im Werkzeug CodeCity. (Bildquelle: [WL08b])

Abbildung 3: Die EvolutionMatrix visualisiert die Entwicklung der Klassen eines Softwaresystems in einem zwei-dimensionalen Raster. (Bildquellen: [Lan01])

2.1 VISUALISIERUNG VERÄNDERLICHER DATENSTRUKTUREN

Eine andere Visualisierung der Evolution von Softwaresystemen stellen Taylor et al. in [TM02] vor. Motiviert durch ein schnelles Programmverständnis speziell für Opensource-Softwareprojekte, die in der Sprache C/C++ geschrieben sind, beschreiben Taylor et al. die Visualisierung Revision Towers. Sie nutzt die Informationen eines Versionskontrollsystems und zeigt für die Paare von Header- und Implemen-tierungsdatei die zeitliche Entwicklung der LOC-Metrik (Lines of Code) vergleichend an. In Abbildung 4 ist ein Beispiel eines Revision Towers dargestellt. Der mittlere Bereich der Visualisierung repräsentiert für die Entwicklung der dargestellten System-elemente eine Zeitachse und besitzt für jedes Release des visualisierten Softwaresystems eine Unter-teilung. Die Zeit kann auf der Achse durch verschiedene Skalen abgetragen werden. Neben einer einheitlichen Unterteilung für jedes Release, wie es in der Abbildung 4 zu sehen ist, gibt es die Möglichkeit, die Zeitpunkte der Versionen und Releases linear auf der Achse abzubilden. Die Rechtecke links bzw. rechts von der Zeitachse repräsentieren Zeitspannen, in denen die LOC-Metrik der Header- bzw. der Implementierungsdatei einen konstanten Wert besitzt und die Datei unverändert bleibt. Die Farben (oder Grauwerte) der Rechtecke repräsentieren den Softwareentwickler, der für die entsprechende Dateiänderung verantwortlich ist.Wie auch beim Ansatz EvolutionMatrix sind Software-Visualisierungen als Revision Towers stabil und relativ kompakt. Sie stellen jedoch nur die Entwicklung einzelner Klassen bzw. Dateien dar. Die Dekompositionsstruktur oder übergeordnete Sys-temelemente werden nicht visualisiert.2.2 StadtmetapherIn der Informationsvisualisierung bezeichnen Metaphern allgemein Konzepte zur Abbildung komplexer und abstrakter Daten auf einen bekannten Gegenstandsbereich. Im Kontext der Softwarevisualisierung bedeutet dies eine Abbildung der Softwareelemente mit ihren Struk-turen auf Elemente eines Metaphern-Konzeptes. Eine bekannte Metapher für die Visualisierung von Softwaresystemen ist die Stadtmetapher. Sie bildet die Elemente einer Software auf unterschiedliche Stadtobjekte ab, wodurch das Softwaresystem als Stadtszene dargestellt wird. Eine ausführliche Erläuterung des Konzeptes der Stadtmetapher zur Softwarevisualisierung ist in [Hag05] gegeben.Ein theoretischer Ansatz, der die Stadtmetapher nutzt, um einen speziellen Aspekt von Softwaresystemen intuitiv zu visualisieren, ist in [PBG03] vorgestellt. Panas et al. beschreiben darin den konkreten Anwendungsfall, die Wartungskosten eines Softwaresystems durch das Markieren der Stadtgebäude intuitiv darzustellen. Zwei umgesetzte Software-Visualisierungs-werkzeuge, die ebenfalls die Stadtmetapher verwenden, sind in [KM00] und [AD07] beschrieben.Eine ähnliche Metapher, die Landschaftsmetapher, ist in [BNDL04] verwendet, um statische Hierarchien von Softwaresystemen darzustellen.

5

Abbildung 4: Die Visualisierung Revision Towers zeigt die Entwicklung der LOC-Metrik für Header- und Implementierungsdateien vergleichend an. (Bildquelle: [TM02])

KAPITEL 2. RELEVANTE LITERATUR

Da das Konzept der Stadtmetapher bereits die Idee der Entstehung und Entwicklung einer Stadt beinhaltet, eignet sich die Metapher neben der statischen Softwarevisualisierung gut, um auch die Evolution eines Softwaresystems zu beschreiben. So nutzt z.B. das bereits erwähnte Werkzeug CodeCity ([WL08b]) die Stadtmetapher zur Visualisierung der historischen Ent-wicklung eines Softwaresystems. Das im nächsten Unterkapitel separat aufgeführte Konzept Stadt-System beruht ebenfalls auf der Stadtmetapher und visualisiert die Entwicklungs-geschichte von Softwaresystemen.2.3 Stadt-SystemDer freie Entwurf Stadt-System von Martin Neubert, der 2008 in Zusammenarbeit mit den Lehrstühlen Städtebau und Entwerfen (Prof. Heinz Nagler), Software-Systemtechnik (Prof.Dr. Claus Lewerentz) und Darstellungslehre (Prof. Dominik Lengyel) an der Brandenburgischen Technischen Universität Cottbus entstand, nutzt die Stadtmetapher und be-schreibt an zwei Beispielen ein Konzept zur Visuali-sierung von Softwaresystemen als Städte. Der folgende Abschnitt stellt das Konzept, durch das die Aufgabenstellung und somit auch diese Arbeit inspiriert ist, zusammenfassend vor.Der Entwurf Stadt-System bildet ein primäres Modell, welches eine veränderliche Dekompo-sitionsstruktur eines Softwaresystems beschreibt, auf eine Basis-Stadtszene, die als Sekundärmodell bezeichnet ist, ab. Die Hierarchie des Softwaresystems (Package-Struktur) ist dabei als hierarchisches Straßennetz dargestellt und Systemmodule (Klassen) sind als Gebäude repräsentiert (siehe Abbildung 5). Die Methoden und Attribute der Klasse sind in den Fassaden der Gebäude abgebildet. Durch eine Verschiebung der Stadtobjekte in der Höhe wird die zeitliche Entwicklung der Software repräsentiert. Hierdurch wächst die Stadt von unten nach oben oder von oben nach unten. Die Abbildung von Kennzahlen der Systemelemente führt zu einem Tertiärmodell und erfolgt durch verschiedene grafische Markierungen der Stadtobjekte.Voraussetzung für die initiale Konstruktion einer „Software-Stadt“ ist die Vorabschätzung der zu erwartenden Größe und Komplexität des zu visualisierenden Systems, nach der ein Grund-Layout sowie die Abmessungen der Gebäudegrundstücke festgelegt werden. Das erläuterte Konzept ist in dem Entwurf theoretisch beschrieben und durch zwei von Hand erstellten Beispielszenen veranschaulicht. Es dient für die vorliegende Arbeit als Beispiel einer möglichen Stadtvisualisierung der Evolution von Softwaresystemen, wobei einige Ideen in die Aufgabenstellung der Arbeit eingegangen sind.

6

Abbildung 5: Entwurf Stadt-System von Martin Neubert.

3 ANALYSE

3 Analyse

Im Rahmen dieser Arbeit soll ein Visualisierungsverfahren entwickelt werden, welches für eine gegebene veränderliche Baumstruktur eine Stadtszene generiert und in den Stadtobjekten verschiedene Kennzahlen der Baumelemente abbildet. Dieses Kapitel analysiert das Ziel der Arbeit und untersucht dabei die Besonderheiten veränderlicher Bäume genauer. Dabei definiert zunächst das Kapitel 3.1 die zu visualisierende Baumstruktur formal. Die Anforderungen, die die Aufgabe an eine Stadt-Visualisierung stellt, werden im Kapitel 3.2 erarbeitet und zu drei Kernanforderungen zusammengefasst. Das Kapitel 3.3 betrachtet die Erweiterbarkeit existierender Layout-Verfahren für unveränderliche Bäume bezüglich der Anforderungen und Kapitel 3.4 befasst sich schließlich genauer mit den speziellen Eigen-schaften veränderlicher Bäume für die Visualisierung als Stadtlandschaft.3.1 Definitionen

3.1.1 GraphEin gerichteter Graph G=V , E besteht aus einer endlichen Knotenmenge V und einer endlichen Kantenmenge E⊆V×V . Die endliche Folge von Knoten w= v1 , , vn heißt Weg in G=V , E , falls gilt: ∀ i∈{1, , n−1} v i , vi1∈E . Von jedem Knoten v∈V aus führt der

leere Weg w=∅ zu sich selbst.3.1.2 BaumEin gewurzelter Baum T=V , E , r ist ein gerichteter Graph mit einem ausgezeichneten Knoten r∈V , wobei jeder Knoten v∈V durch genau einen Weg von r aus erreichbar ist. Der Knoten r heißt Wurzel des Baumes. Es sei für einen gewurzelten Baum T=V , E , r die Funktion ROOT definiert als ROOT T =r . Für eine Kante u , v∈E in einem gewurzelten Baum T=V , E , r , heißt u Elternknoten von v und v Kind von u . Die Funktion CHILDREN :VP V beschreibt zu einem Knoten u die Menge seiner Kindknoten. Es gilt: ∀ v∈V v∈CHILDREN u ⇔ v≠u∧u , v ∈E , mit u∈V .3.1.3 Veränderlicher Baum (CT)Ein veränderlicher Baum CT=V ,E , , , , besteht aus einer endlichen Knotenmenge V , einer endlichen Kantenmenge E⊆V×V , einer endlichen Menge von Zeitpunkten und drei Funktionen , , . Die Funktion :PV gibt für einen Zeitpunkt t∈ die Menge V t⊆V von Knoten zurück, die zum Zeitpunkt t existieren. Die Funktion :PE gibt für einen Zeitpunkt t∈ die Menge E t⊆E von Kanten zurück, die zum Zeitpunkt t existieren. Die Funktion :V gibt die Wurzel des Baumes zum Zeitpunkt t∈ an. Für den veränderlichen Baum C=V , E , , , , muss gelten:1. ∀ t∈T t=t , t ,t ist ein gewurzelter Baum .

7

KAPITEL 3. ANALYSE

3.1.4 Attributierter Baum (ACT)Ein attributierter veränderlicher Baum ACT=CT , A , B ist ein Tripel, bestehend aus einem veränderlichen Baum CT=V , E , , , , und zwei endlichen Attributmengen A , B . Für ein Attribut a∈A , mit a= , M a ordnet die Funktion :V ,M a einem Knoten die Ausprägung des Attributs a zum Zeitpunkt t∈ zu. M a stellt dabei die Menge der Ausprägungen für das Attribut a dar. Für ein Attribut b∈B , mit b= , N b ( N b sei die Menge der Ausprägungen des Attributs b ) ordnet die Funktion : E , N b einer Kante die Ausprägung des Attributs b zum Zeitpunkt t∈ zu.3.1.5 Gelevelter Baum (LACT)Ein gelevelter attributierter veränderlicher Baum LACT=V , E , , , , , A , B ist ein attributierter veränderlicher Baum (ACT) mit einem festen Knotenattribut , L∈A . Die Menge L={l 1 , , l m} ist dabei eine linear geordnete Menge von Knotenleveln. Die Funktion :V , L ordnet jedem Knoten einen Level zu. Es muss gelten:1. ∀ v∈V ∀ t∈v , t ist definiert ,2. ∀ v∈V v , t 1=v , t 2, mit t1∈∧t 2∈ , d.h. der Knotenlevel bleibt über die Zeit konstant,3. v , t =l 1⇔ v=t , mit v∈V , t∈ , d.h. die Wurzel r=t besitzt als einziger Knoten den Level l 1 ,4. Sei t∈ , v∈V und v '∈V mit l=v , t und

l '=v ' , t . Falls v ' Kindknoten von v ist und l≠l ' , muss gelten: l ist in der Ordnung von L Vorgänger von l ' ,5. Für jeden Knoten v∈V besitzen dessen Kinder den selben Knotenlevel l∈L .Die Mengen A und B sind äquivalent zum attibutierten veränderlichen Baum (ACT) definiert. Ein Beispiel für die Zuordnung der Knotenlevel in einem gelevelten attributierten veränderlichen Baum (LACT) ist in Abbildung 6 dargestellt.

3.2 Layout-AnforderungenZiel der Arbeit ist es, eine Visualisierung für veränderliche Baumstrukturen, wie sie im vorigen Kapitel 3.1.5 definiert wurden, zu entwerfen. Sie soll speziell im Kontext der entwicklungs-begleitenden Analyse Anwendung finden, weshalb visualisierte Baumelemente in Dar-stellungen verschiedener Versionen des selben Baumes wiedererkennbar sein sollen. Aus-gehend von diesen Zielen definieren die nächsten Abschnitte die Anforderungen Stabilität, Kompaktheit und Skalierbarkeit für das zu entwickelnde Stadt-Layout.3.2.1 StabilitätEin Problem bei der entwicklungsbegleitenden Nutzung von Visualisierungen, sind stark variierende Darstellungen für verschiedene Versionen des selben abgebildeten Systems. Diese erfordern mit jeder neuen Version einen Mehraufwand an Einarbeitungszeit in die Visuali-8

Abbildung 6: Beispiel für die Zu-ordnung von Knotenleveln in ei-nem LACT.

3.2 LAYOUT-ANFORDERUNGEN

sierung, da Orientierungspunkte in den Darstellungen verloren gehen und sich bereits erlernte Anordungsmuster grundlegend verändern. Um Visualisierungen entwicklungsbe-gleitend effektiv einsetzen zu können, müssen Repräsentanten gleicher Systemelemente in Darstellungen verschiedener Versionen des Systems gut wiedererkennbar sein. Anordnungen von Elementen dürfen sich in den Visualisierungen nicht zu stark ändern.Der folgende Abschnitt beschreibt zwei verschiedene Ansätze einen Stabilitätsbegriff zu definieren, der die Wiedererkennbarkeit von gleichen Elementen in Visualisierungen von Bäumen unterschiedlicher Versionen beschreibt. Die Stabilität bezieht sich dabei auf zwei verschiedene Anordnungen von Objekten, die die selben Baumelemente repräsentieren. Eine solche Anordnung von geometrischen Objekten ist im Folgenden als Layout bezeichnet.Transformationsstabilität: Der erste Ansatz für die Definition eines Stabilitätsbegriffes geht davon aus, dass die menschliche Wahrnehmung eine Anordnung von Objekten in ver-schiedenen Visualisierungen als die selbe erkennt, auch wenn die gesamte Objektanordnung verschoben, gedreht oder skaliert wurde. Hieraus ergibt sich die erste Definition der Stabilität, die für beliebige Layouts angewendet werden kann. Die Transformationsstabilität zweier Layouts bezeichnet die größtmögliche Ähnlichkeit aller Positionen gleicher Objekte, die sich durch Verschieben, Drehen oder Skalieren der gesamten Anordnung der Objekte erzielen lässt. Falls alle Positionen jeweils gleicher Objekte in zwei verschiedenen Layouts durch Verschiebung, Drehung oder Skalierung der Objektanordnung auseinander hervorgehen, heißen diese Layouts vollständig transformationsstabil. Die Ähnlichkeit zwei Positionen kann dabei durch ein beliebiges Distanzmaß, wie z.B. den euklidischen Abstand, bestimmt werden. Ordnungsstabilität: Ein anderer Ansatz geht von der Annahme aus, dass in einem Baum-Layout Ordnungsbeziehungen der Positionen von Repräsentationen von Kindelementen relativ zu ihren Eltern-Repräsentationen für die Wiedererkennbarkeit eine besonders große Rolle spielen. Darstellungen in denen die Reihenfolge von Gebäuden in Bezug auf den Ursprung der übergeordneten Straße gleich ist, werden als stabil wahrgenommen. Dies führt zur zweiten Definition der Stabilität, die sich auf Baum-Layouts beschränkt. Es sei für Knoten in einem Baum eine Ordnungsbeziehung definiert, die die Entfernung von Repräsentanten von Kindknoten relativ zu den Repräsentanten ihrer Elternknoten in Beziehung setzt. Die Ordnungsstabilität zweier Baum-Layouts bezeichnet den Anteil der Ordnungsbeziehungen von je zwei Knoten mit gleichem Elternknoten, die in beiden Versionen erhalten bleiben, in Bezug zur Anzahl aller Ordnungsbeziehungen. Wenn für alle Paare von Knoten mit gleichem Elternknoten die Ordnungsrelationen in zwei Baum-Layouts erhalten, bleiben heißen diese Baum-Layouts vollständig ordnungsstabil.3.2.2 KompaktheitUm eine gute Lesbarkeit der Visualisierungen zu erreichen, ist es von Vorteil, wenn die Stadt-objekte nicht zu weit entfernt von einander positioniert sind. Ein komprimiertes Layout sorgt zudem für eine gute Übersicht, da sich in der Umgebung jedes Objektes weitere Objekte befinden, die eine Einordnung in den Kontext des Systems ermöglichen.Der Begriff der Kompaktheit beschreibt die Informationsdichte in einer Visualisierung und stellt dabei eine weitere wichtige Anforderung an das zu entwickelnde Stadt-Layout dar. Die Kompaktheit eines zweidimensionalen Layouts ist definiert als das Verhältnis der genutzten (informationstragenden) Fläche zur Gesamtfläche des Layouts. Da die konstruierte Stadtszene im Raum sowie ihre Projektion auf die Ebene ohne Begrenzungen auskommt, muss für die Berechnung der Layout-Kompaktheit eine Stadtgrenze definiert werden. Hierfür ist jede Form, die alle Stadtobjekte möglichst eng umschließt geeignet.

9

KAPITEL 3. ANALYSE

3.2.3 SkalierbarkeitMotiviert ist die Entwicklung des Stadt-Layouts durch die Visualisierung von Software-systemen, von denen selbst kleine Systeme sehr komplex sein können und weit gefächerte Dekompositionsstrukturen besitzen. Sie erfordern daher für ein Visualisierungssystem den Umgang mit großen Baumstrukturen und die Darstellung einer Vielzahl von Objekten. Zudem ist die Änderungshäufigkeit für Softwaresysteme hoch, was die zu visualisierende Informa-tionsmenge vervielfacht. Die Skalierbarkeit stellt daher die dritte wichtige Anforderung an den zu entwickelnden Layout-Algorithmus dar. So soll es konkret möglich sein, die Entwicklung eines kleinen bis mittelgroßen Softwaresystems für mehr als zehn Versionen zu visualisieren.3.3 Baum-LayoutsFür die Visualisierung unveränderlicher Bäume gibt es bereits eine Vielzahl von Dar-stellungsmethoden, die sich durch die verschiedenen Herangehensweisen beim Anordnen der geometrischen Repräsentanten der Baumknoten im zweidimensionalen oder dreidimen-sionalen Raum unterscheiden. Einige grundlegende Baum-Layouts werden im Folgenden kurz aufgeführt und in Bezug auf die Anforderungen des zu entwickelnden Layouts bewertet. Obwohl alle vorgestellten Layouts nur unveränderliche Bäume visualisieren, soll dieses Unterkapitel prüfen, in wie weit vorhandene Layout-Algorithmen als Basis für die Darstellung veränderlicher Bäume dienen könnte.3.3.1 Level-Layout und Radiales LayoutEine einfache und bekannte 2D-Visualisierung für Hierarchien ist das Level-Layout. Kinderknoten werden hierbei unterhalb des Elternknotens angeordnet. Die Y-Komponente der Position jedes Knotens errechnet sich aus dem Vielfachen seiner Tiefe im Baum. Für die Bestimmung der X-Komponente gibt es unterschiedliche Ansätze, die im wesentlichen darauf ausgelegt sind, Kantenüberschneidungen zu minimieren und das Layout zu kompaktifizieren [BETT99]. In der Literatur wird das Level-Layout auch als Layering, Hierarchie-Layout oder Rooted-Tree-Layout bezeichnet. Abbildung 7 zeigt ein Beispiel des beschriebenen Layouts.Das Radiale Layout oder Radial Drawing ist eine Variation des Level-Layouts. Die Wurzel des Baumes wird hier im Ursprung dargestellt. Abhängig von der Tiefe im Baum liegen alle anderen Knoten auf konzentrischen Kreisen, deren Mittelpunkte im Ursprung liegen. Ein Beispiel eines Radialen Layouts zeigt Abbildung 8. Beide Visualisierungstechniken eignen sich wenig zur Visualisierung großer Hierarchien, da sie schlecht skalieren. Außerdem kann es, abhängig von dem konkret verwendeten Positionierungs-Algorithmus, zu starken Änderungen des Layouts bei kleinen Strukturänderungen des Baumes kommen.

10

Abbildung 7: Level-Layout.

Abbildung 8: Radiales Layout.

3.3 BAUM-LAYOUTS

3.3.2 Kräfte-basiertes Layout

Kräfte-basierte Layouts verwenden physikalische Modelle, um Visualisierungen zu erzeugen. Die meisten dieser Layouts bestehen aus zwei Komponenten: einem Kräfte- bzw. Energiesystem, welches durch die Knoten und Kanten des Graphen konfiguriert wird und einem Algorithmus zur Bestimmung eines Zustandes, in dem sich das System im Gleichgewicht befindet. Dieser Zustand, in dem die Gesamtenergie des Systems minimal ist, definiert die Darstellung des Graphen [BETT99]. Ein weit verbreitetes Kräfte-basiertes Layout verwendet eine Kombination aus Federkräften und elektrischen Kräften. Im Modell sind die Kanten als Federn zwischen den Knoten und die Knoten als elektrisch gleich-geladene Partikel, welche sich gegenseitig abstoßen, definiert [FR91]. Ein weiteres bekanntes Layout, die Barycenter-Methode, wird von Tutte beschrieben [Tut60], [Tut63]. Abbildung 9 zeigt ein Beispiel des Layouts.Das Kräfte-basierte Layout arbeitet mit allgemeinen Graphen und erzeugt Visualisierungen die vielen ästhetischen Kriterien genügen. Da viele Komponenten im Kräftesystem miteinander wechselwirken können, ist die Komplexität der Optimierungsalgorithmen hoch, was die Skalierbarkeit des Layouts einschränkt. Außerdem können sich bei einer Änderung eines visualisierten Baumes die Positionen der Knoten sprunghaft ändern.3.3.3 TreemapsEine weitere 2D-Visualisierungstechnik speziell für hierarchische Strukturen stellen Treemaps dar. Die Hierarchie wird hier durch ineinander verschachtelte Rechtecke abgebildet. Die Kanten des Baumes werden nicht wie gewöhnlich als Verbindungslinien dargestellt, sondern durch eine Enthaltensein-Beziehung der als Rechtecke gezeichneten Knoten indirekt visualisiert [JS91]. Abbildung 10 zeigt für den oben darstellten Baum im unteren Bereich der Darstellung als Treemap. Knotenattribute der Blätter und deren Größenverhält-nisse können in Treemaps gut veranschaulicht werden, indem die Flächen der Rechtecke proportional zu den Attributwerten skaliert. Hierdurch lassen sich Extrem-werte schnell erkennen. Dagegen ist die Interpretation der verschachtelten Rechtecke als Hierarchiestruktur ungewohnt. Für große Bäume ergibt die Darstellung ein unübersichtliches und teilweise wirres Bild.Um diesem Problem zu begegnen gibt es eine Vielzahl von Verbesserungen und Erweiterungen der Treemap-Darstellung, wie beispielsweise Cushion Treemaps [WW99], Squarified Treemaps [BHW99], Beamtrees [HW02] oder Voronoi Treemaps [BDL05], [BD05] (siehe Abbildung 11). Allen Ansätzen gemeinsam ist, dass sich bei kleinen Änderungen der Hierarchie die Visualisierung grundlegend ändern kann.

11

Abbildung 9: Kräfte-basierte Lay-outs verwenden physikalische Mo-delle, um Graphen zu visualisieren.

Abbildung 10: Treemaps bilden hierarchische Strukturen als inein-ander verschachtelte Rechtecke ab.

KAPITEL 3. ANALYSE

3.3.4 Hyperbolische BäumeEin grundsätzliches Problem bei der Visualisierung großer Baumstrukturen ist das exponentielle Wachstum der Knotenanzahl bei zunehmender Baumtiefe und dem damit verbundenen exponentiell wachsenden Platzbedarf für das Layout-Verfahren. Um diesem Problem zu begeg-nen, beschreiben Lamping et al. in [LRP95] eine Visuali-sierungstechnik, bei der Hierarchien in einer hyperboli-schen Ebene konstruiert werden. Im Gegensatz zur Ebene im Euklidischen Raum steht in der hyperbolischen Ebene mehr „Platz“ für die Darstellung des Baumes zur Verfü-gung. So erfährt beispielsweise der Umfang eines Kreises, dessen Radius linear wächst, im hyperbolischen Raum ein exponentielles Wachstum. Im Euklidischen Raum würde der Umfang desselben Kreises auch linear wachsen. Zum Anzeigen der hyperbolischen Ebene in einem 2-dimensio-nalen Darstellungsbereich verwenden die Autoren das Poincaré-Scheiben-Modell, welches die gesamte hyper-bolische Ebene innerhalb eines Einheitskreises abbildet. Dabei wird ein fokussierter Bereich des Baumes in der Mitte der Scheibe vergrößert dargestellt, nicht-fokussierte Elemente schrumpfen in Richtung der Scheibenperipherie kontinuierlich. Der Fokus ist somit ständig im Kontext des gesamten Baumes sichtbar. Abbildung 12 zeigt die Visualisierung einer Hierarchie als hyperbolischen Baum.In [Mun97] stellt Munzner eine Erweiterung des Ansatzes für 3-dimensionale Visualisierungen als H3-Layout vor. Hierarchische Graphen werden hierbei im hyperbolischen Raum konstruiert und innerhalb einer Kugel im Euklidi-schen Raum abgebildet (siehe Abbildung 13). Hyperbolische Bäume sind als 2D- und auch als 3D-Visua-lisierungen sehr gut skalierbar. Die starke Verzerrung stellt aber Probleme für die Visualisierung veränderlicher Hierarchien dar. So können beispielsweise Strukturände-rungen auf einer hohen Hierarchieebene zu starken Ver-änderungen des Layouts führen, wohingegen Strukturän-derungen in der Nähe der Blätter des Baumes die Darstel-lung kaum beeinflussen. Generell nimmt der Einfluss der Strukturänderung eines Baumes auf das Layout mit 12

Abbildung 12: Ein hyperbo-lischer Baum wird in der hyper-bolischen Ebene konstruiert und auf einer „euklidischen“ Scheibe abgebildet.

Abbildung 13: Das H3-Layout verallgemeinert hyperbolische Bäume für 3D-Visualisierungen. (Bildquelle: [Mun97])

Abbildung 11: a) Cushion Treemaps, b) Squarified Treemaps, c) Beamtreemaps, d) Voronoi Treemaps erweitern die Treemap-Visualisierungstrechnik. (Bildquellen: [WW99], [BHW99], [HW02], [BDL05])

3.3 BAUM-LAYOUTS

steigender Knotenanzahl ab. Eine Veränderung großer Hierarchien ist allein durch die Visualisierung nicht mehr belegbar. 3.3.5 Weitere VisualisierungenNeben den beschriebenen Visualisierungen gibt es eine Vielzahl weiterer Visuali-sierungstechniken für Bäume, wie z.B. Cone Trees [RMC91], Tree Rings (Sunburst) oder Ballon Trees.3.3.6 ZusammenfassungBei der Betrachtung existierender allgemeiner Layout-Verfahren für unveränderliche Bäume wie z.B. Level-Layouts, Radiale Layouts, Kräfte-basierte Layouts, Treemaps oder Hyperbolische Bäume wurde keine Technik gefunden, welche optimal als Grundlage für die Visualisierung großer veränderlicher Bäume dienen könnte. Gründe hierfür sind zum einen die geringe Stabilität der Visualisierungen, was dazu führt, dass sich die Darstellungen der Bäume bei kleinen Strukturänderungen grundlegend ändern können. Zum anderen sind einige Techniken schlecht skalierbar, was sie für die Visualisierung großer Bäume mit vielen Knoten ungeeignet erscheinen lässt.Auf die besonderen Eigenschaften veränderlicher Bäume für ein spezielles Layout-Verfahren geht das nächste Unterkapitel 3.4 näher ein.3.4 Layouts für veränderliche BäumeDas folgende Unterkapitel untersucht veränderliche Bäume genauer. Dabei beschreibt das Kapitel 3.4.1 zuerst, wie sich Änderungen von zu visualisierenden Systemen (speziell von Softwaresystemen) in einem gelevelten attributierten veränderlichen Baum (LACT) modellieren lassen. Eine Abbildung der Hierarchie eines solchen veränderlichen Baumes und mögliche Darstellungen der zeitlichen Informationen des LACT-Baumes erläutern die Kapitel 3.4.2 und 3.4.3.3.4.1 Modellierung von SystemänderungenFür die Visualisierung der Evolution von Softwaresystemen müssen sich die Änderungen des Systems in einem gelevelten attributierten veränderlichen Baum (LACT), wie er in Kapitel 3.1.5 definiert wurde, modellieren lassen. Dabei lassen sich die Systemänderungen in zwei Gruppen unterteilen. Zum einen gibt es in der zeitlichen Entwicklung eines Softwaresystems struk-turelle Änderungen in der Dekomposition des ganzen Systems und zum anderen verändern sich die Eigenschaften und Kennzahlen der einzelnen Systemelemente.Die Änderungen der Dekompositionsstruktur eines Softwaresystems umfassen die Opera-tionen Hinzufügen, Löschen oder Verschieben von Systemelementen. Das Hinzufügen und Löschen eines Elementes lässt sich dabei im gelevelten attributierten veränderlichen Baum (LACT) durch die Existenz oder Nichtexistenz eines Knotens in den verschiedenen System-versionen beschreiben. Das Verschieben eines Softwareelements innerhalb der Dekom-positionsstruktur ist im LACT-Baum durch das Entfernen eines Knotens aus dem Baum sowie das Einfügen eines neuen Knotens an die neue Stelle innerhalb des Baumes modelliert. Verschiebungen als atomare Operationen sind im LACT-Baum nicht abgebildet, weshalb das zu entwickelnde Layout nur das Hinzufügen und Löschen von Knoten in einem Baum

13

KAPITEL 3. ANALYSE

berücksichtigen und in den Stadtszenen abbilden muss.Änderungen von Eigenschaften oder Kennzahlen der Softwareelemente sind im LACT-Baum als Attribute mit unterschiedlichen Ausprägungen für verschiedene Versionen modelliert.3.4.2 Abbilden der Baum-StrukturDie Repräsentation und Darstellung der einzelnen Knoten eines LACT-Baumes in der Stadt-visualisierung ist durch den in Kapitel 2.3 beschriebenen Entwurf Stadt-Systeme inspiriert und durch die Aufgabenstellung der Arbeit in Ansätzen vorgegeben. So werden Knoten eines Basislevels, die im LACT-Baum den Knotenlevel 3 besitzen, als Gebäudeobjekte in der Stadt-szene repräsentiert. Knoten mit dem Knotenlevel 2 sind als Straßen abgebildet, wobei die Hierarchie der Level 2-Knoten durch ein hierarchisches Straßennetz repräsentiert ist. Level 3-Knoten, die die Kinder eines Level 2-Knotens sind, befinden sich in der Stadtvisualisierung an den Straßenrändern des (als Straße visualisierten) Level 2-Elternknotens. 3.4.3 Abbilden der Baum-EntwicklungUm die zeitliche Entwicklung eines LACT-Baumes auf das Layout einer Stadtszene abzubilden, gibt es für die verschiedenen Baumänderungen unterschiedliche Möglichkeiten. Falls beispielsweise Gebäude und abzweigenden Straßen an den Rändern einer überge-ordneten Straße nach den Entstehungszeitpunkten dieser repräsentierten Kinder sortiert sind, spiegelt die Entfernung von den am Straßenrand befindlichen Objekten zum Straßen-ursprung der übergeordneten Straße das Alter der repräsentierten Kind-Knoten wider. Die übergeordnete Straße stellt somit eine ungleichmäßig eingeteilte Zeitachse dar. Eine Variation dieses Ansatzes teilt die Zeitachsen, die sich auf die Straßen projizieren lassen, gleichmäßig ein. Hierdurch verschieben sich die Objekte an den Straßenrändern vom Ursprung der übergeordneten Straße weg, so dass die Entfernung der Objekte zum Straßenursprung den Entstehungszeitpunkt der Objekte relativ zum Entstehungszeitpunkt der Straße linear abbildet. Ein Problem dieser Variante ist jedoch, dass sich die Verschiebung der Objekte negativ auf die Kompaktheit des Stadt-Layouts auswirkt. Außerdem kann es notwendig sein, die Länge der Zeitabschnitte im Laufe der Entwicklung zu vergrößern, was zusätzlich negative Auswirkungen auf die Layout-Stabilität hat. Eine andere Möglichkeit, die zeitliche Entwicklung eines veränderlichen Baumes abzubilden, besteht darin, alle Objekte abhängig von ihrem Entstehungszeitpunkt in der Höhe zu ver-schieben. Somit bildet die Höhe der Grundflächen aller Stadtobjekte über dem Ausgangs-niveau den Entstehungszeitpunkt des jeweils repräsentierten Knotens linear ab. Diese Ab-bildung hat keinen Einfluss auf die Kompaktheit oder die Stabilität des Layouts.Die Information, dass ein Knoten aus dem Baum entfernt wurde, lässt sich durch eine (farbliche) Markierung oder durch das Austauschen der Repräsentation mit einem Platzhalter darstellen, ohne die Position der anderen Stadtobjekte zu verändern und dadurch die Stabilität negativ zu beeinflussen. Durch die visuellen Eigenschaften der Stadtobjekte, wie z.B. die Ausdehnung oder Farben, die die verschiedenen Stadtobjekte besitzen, lassen sich die Änderungen der Attributausprä-gungen abbilden.Die Konstruktion des entwickelten Stadt-Layouts Evolution City beschreibt das nächste Kapitel 4. Es kombiniert zwei der betrachteten Möglichkeiten, die Entstehungszeitpunkte der Knoten 14

3.4 LAYOUTS FÜR VERÄNDERLICHE BÄUME

eines LACT-Baumes abzubilden. Hier stellen die Straßen in den erzeugten Stadtvisualisie-rungen ungleichmäßig unterteilte Zeitachsen dar, während gleichzeitig die Entstehungs-zeitpunkte linear auf die Höhe der Objektgrundflächen abgebildet werden.

15

4 EVOLUTION CITY-LAYOUT

4 Evolution City-Layout

Das folgende Kapitel beschreibt detailliert die Generierung des dreidimensionalen Stadt-Layouts Evolution City für veränderliche Baumstrukturen. Das nächste Unterkapitel 4.1 gibt einen Überblick über das Konzept und die grundsätzliche Funktionsweise des Layout-Algorithmus. Die Unterkapiteln 4.2, 4.3, 4.4 und 4.6 beschreiben für verschiedene Teilbäume und Knotentypen ausführlich dessen Layout und Repräsentation in den Stadtvisualisierungen. Die Generierung eines Geländes, welches die Stadtobjekte miteinander verbindet, stellt das Unterkapitel 4.5 vor. Abschließend sind im Unterkapitel 4.7 verschiedene Möglichkeiten der Abbildung von Knotenattributen auf Eigenschaften der Stadtobjekte aufgeführt.4.1 Layout-AlgorithmusDer Layout-Algorithmus generiert aus einer gegebenen veränderlichen Baumstruktur, die im Kapitel 3.1.5 genauer als gelevelter attributierter veränderlicher Baum (LACT) definiert ist, eine dreidimensionale Stadtszenerie, die die Hierarchie, Attribute der Baumknoten und deren zeitliche Änderungen auf die Anordnung und Gestaltung von Stadtobjekten abbildet. Das Layout basiert grundsätzlich auf einer zweidimensionalen Anordnung von Repräsentationen der Baumknoten in der XZ-Ebene. Die dritte Dimension der Szene wird neben der räumlichen Darstellung der Repräsentanten dazu verwendet, die Grundflächen der Stadtobjekte in der Höhe (in Richtung der Y-Achse) zu verschieden, um somit den Entstehungszeitpunkt der repräsentierten Knoten abzubilden. In der gegebenen Baumstruktur gibt es drei verschiedene Knotentypen bzw. Knotenlevel, von denen die Repräsentation der Knoten abhängt. Der Level 1-Knoten ist in der Stadt als zentraler Platz oder Autobahn abgebildet. Die Dekompositionsstruktur der Level 2-Knoten ist durch ein hierarchisches Straßensystem repräsentiert. Level 3-Knoten sind in der Stadtvisualisierung als Gebäude dargestellt, wobei ihre Hierarchie als Enthaltensein-Beziehung weiterer Gebäude im „Hinterhof“ des Gebäudegrundstücks abgebildet ist. Als Bottom-Up-Verfahren baut das Layout die Stadtszene von den Blättern der gegebenen Baumestruktur bis zur Wurzel rekursiv auf. Für jeden Knoten werden die Repräsentationen untergeordneter Teilbäume möglichst optimal innerhalb einer Begrenzungsform ohne Überschneidungen angeordnet. Sie bilden zusammen mit dem Repräsentanten des betrachteten Knotens die Repräsentation für den gesamten übergeordneten Teilbaum. Das Packing-Verfahren arbeitet dabei mit Parallelogrammen als Begrenzungsform, wobei sich die optimale Positionierung der Repräsentationen innerhalb dieser Form auf die Minimierung des Flächeninhalts eines umschließenden Parallelogramms bezieht.In einigen Teilschritten des Layout-Verfahrens für Knoten unterschiedlicher Knotenlevel werden Repräsentationen von den Kindern eines Baumknotens sortiert und entsprechend dieser Sortierung in der Szene positioniert. Um eine möglichst hohe Stabilität des generierten Layouts zu erreichen, muss der Layout-Algorithmus gewährleisten, dass die Reihenfolge der sortierten Repräsentationen in allen Visualisierungen zukünftigen Versionen erhalten bleibt. Dieses lässt sich durch verschiedene Herangehensweisen erreichen. Zum einen gibt es die Möglichkeit, die Sortierung nach einem unveränderlichen Schlüssel der Wurzel eines darzustellenden Teilbaums durchzuführen. Für die Sortierung nach einer zeitlich veränderlichen Eigenschaft der Repräsentationen, wie z.B. die Größe oder Ausdehnung einer

17

KAPITEL 4. EVOLUTION CITY-LAYOUT

Begrenzungsfläche, gibt es eine zweite Herangehensweise. Für diesen Fall müssen die Repräsentationen der Kinder eines Knotens stets nach den Eigenschaften sortiert werden, wie sie zum Entstehungszeitpunkt des Elternknotens existiert haben.Die nächsten Unterkapitel beschreiben den Layout-Algorithmus und die Repräsentation für Knoten unterschiedlicher Knotenlevel genauer. Anders als der Bottom-Up-Algorithmus selbst beginnen die Beschreibungen des Layouts beim Wurzelknoten des gegebenen Baumes und erläutern erst später das Abbilden von Level 2- und Level 3-Knoten.4.2 Repräsentation und Layout des Level 1-KnotensDer einzige Knoten, der den Knotenlevel 1 besitzt, ist die Wurzel der zu visualisierenden Baumstruktur. Für die Darstellung des Level 1-Knotens oder Level 1-Elementes wurden in der Arbeit zwei verschiedene Konzepte entwickelt und im Prototyp Evolution Viewer umgesetzt. Beide Varianten haben Vor- und Nachteile bezüglich der Lesbarkeit, Stabilität und Kompaktheit der erzeugten Stadtvisualisierungen. Die nächsten Abschnitte stellen beide Varianten näher vor. Den Einfluss der vorgestellten Repräsentationen des Level 1-Knotens auf die Stabilität und Kompaktheit des Layouts untersuchen die Kapitel 5.1.2.1 und 5.2.2.2 genauer. 4.2.1 Repräsentation als zentraler PlatzBei der Repräsentation des Level 1-Elemen-tes als zentralen Platz stellt eine flache runde Scheibe die Wurzel der visualisierten Baum-struktur dar. Alle untergeordneten Level 2-Knoten zweigen, als Straßen repräsentiert, sternförmig vom Mittelpunkt des Platzes ab. Die Repräsentationen untergeordneter Teil-bäume, die jeweils ein Subsystem darstellen, ordnen sich als „Kuchenstücke“ um den zen-tralen Platz herum und bilden in der Visuali-sierung Sektoren oder Fächer einer zentral organisierten Stadt. Abbildung 14 zeigt ein Beispiel einer Stadtvisualisierung, bei der der Level 1-Knoten als Platz repräsentiert ist. Im Laufe der zeitlichen Entwicklung entstehen neue Subsysteme im Uhrzeigersinn um den Platz herum. Die Subsysteme selbst entwi-ckeln sich strahlenförmig vom Platzzentrum weg nach außen.Um für eine hohe Anzahl von Subsystemen oder für besonders große Subsysteme eine Überschneidung der Sektoren im Stadt-Layout zu verhindern, gibt es die Möglichkeit, die Länge l des Anfangsabschnitts einer Straßen, welche das oberste Level 2-Element eines Subsystem-Teilbaums repräsentieren, anzupassen. Große Werte für l führen zu spitzeren Sektoren, von denen mehr in einem Vollkreis Platz finden. Bei einem kurzen Straßenabschnitt l dagegen vergrößert sich der Winkel eines Sektors. Diese Zusammenhänge von Anfangsabschnitt und Sektorenwinkel für ein Subsystem S i verdeutlicht Abbildung 15. Das Element S i der Menge S={S 1 , , S N }, mit N=∣S∣ stellt dabei den i -ten Subsystem-Teilbaums dar, dessen Begren-zungsfläche zusammen mit dem blau markierten Anfangsabschnitt l der Straße den Winkel 18

Abbildung 14: Bei der Repräsentation des Level 1-Knotens als zentralen Platz zweigen Subsys-teme sternförmig vom Mittelpunkt ab.

4.2 REPRÄSENTATION UND LAYOUT DES LEVEL 1-KNOTENS

des Sektors bestimmt. Diese Straße, die die Wurzel des Subsystem-Teilbaums repräsentiert, teilt den Sektor in zwei Teilsektoren, wobei die Funktion :S×ℝℝ den Winkel des Teilsektors links der Straße und die Funktion :S×ℝℝ den Winkel des Teilsektors rechts der Straße definiert. Durch eine Be-schreibung der Begrenzungsfläche von S i durch ein Polygon lässt sich die Funktion als maximaler Winkel zwischen einem Poly-gonpunkt und der Strecke ai definieren, falls der Winkel in einem Bereich zwischen − und bestimmt wird. Die Funktion be-rechnet den Betrag des minimalen Winkels. Für eine gleichmäßige Verteilung der Subsys-tem-Sektoren um den Mittelpunkt des Plat-zes berechnet die Funktion :ℝℝ in Abhängigkeit der Länge des Straßenabschnitts l den Winkel eines ungenutzten Sektors, der sich als Freiraum zwischen jeweils zwei Subsystem-Sektoren einfügen lässt. Bei einem negativen Funktionswert von überschneiden sich die Sektoren der Subsysteme um den Betrag des Winkels l . Die Funktion ist in Gleichung 1 formal definiert.

l =2−∑

i=1

N

S i , l S i , l

N (1)

Liefert für das Stadt-Layout einer Baumstruktur bei einer minimalen Länge des Anfangs-abschnitts der Subsystem-Straßen l min einen positiven Wert oder Null ( l min≥0 ), können die Repräsentationen der Subsysteme mit der Länge lmin des Anfangsabschnitts um den Platz herum positioniert werden, wobei zwischen jeweils zwei Sektoren ein Platzhalter-Sektor mit einem Winkel von lmin eingefügt wird. Für den Fall, dass gilt: l min0 , lässt sich mit Hilfe eines Näherungsverfahrens, wie z.B. Regula Falsi, die Nullstelle der Funktion und somit l 0, mit l 0=0 bestimmen. Anschließend können die Repräsentationen der Subsysteme mit einer Anfangslänge der Subsystem-Straßen von l 0 ohne Zwischenräume und ohne Über-schneidungen um den Platz angeordnet werden.Die Reihenfolge, in der die Subsystem-Repräsentationen um den Platz herum im Uhrzeigersinn positioniert sind, bestimmt sich primär aus dem Entstehungszeitpunkt der Wurzeln der Subsystem-Teilbäume und sekundär aus einem Schlüssel der Wurzeln, wie z.B. einem ein-deutigen Namen oder einer Identifikationsnummer.Der zentrale Platz besitzt als einzige freie visuelle Eigenschaft die Farbe, wodurch sich bis zu drei Attribute der Wurzel in der Stadtvisualisierung abbilden lassen, da sich jede Farbe in einem dreidimensionalen Farbraum, wie z.B. RGB oder HSB, beschreiben lässt. Der Radius des Platzes wird aus der Anzahl der abzweigenden Subsystem-Repräsentanten berechnet und ist somit nicht frei.4.2.2 Repräsentation als AutobahnNeben der Repräsentation als zentralen Platz stellt die Repräsentation als Autobahn eine

19

Abbildung 15: Abhängigkeit des Sektorenwin-kels von der Anfangslänge l der Straße, die das oberste Level 2-Element im Subsystem-Teilbaum repräsentiert.


zweite Möglichkeit dar, das Level 1-Element in den Stadtvisualisierungen abzubilden. Die Repräsentationen der Subsysteme zweigen hierbei orthogonal von einer Autobahn ab, die als zentrale Achse mittig durch die gesamte Stadt verläuft. Durch ein Anfügen der Repräsen-tationen neu entstandener Subsysteme an nur einem Ende der Autobahn wächst die Stadt im Laufe der zeitlichen Entwicklung des Systems in eine Richtung und die Autobahn stellt somit eine Zeitachse mit ungleichmäßiger Einteilung dar. Die Entwicklungsrichungen der Sub-systeme führen zu beiden Seiten der Autobahn senkrecht von dieser weg. Abbildung 16 zeigt in der Darstellung a) ein Beispiel der Repräsentation des Level 1-Elementes als Autobahn. Das Autobahn-Objekt besitzt in den Stadtvisualisierungen die freien Eigenschaften der Breite und der Farbe. Die Farbe ist verschiedene Autobahnabschnitte frei und ermöglicht für jede visualisierte Version das Abbilden von bis zu drei Knotenattributen der Wurzel. Ein viertes Attribut kann für die letzte dargestellte Version auf die Breite der Autobahn abgebildet werden.

Die Anordnung und Positionierung der Repräsentationen untergeordneter Elemente ist für die Autobahn konzeptionell ähnlich der Positionierung untergeordneter Elemente an Straßen, die im Kapitel 4.3 als Repräsentanten der Level 2 Elemente näher beschrieben sind. Speziell die Einteilung in Straßenabschnitte verschiedener Höhen ist für die Autobahn und Straßen gleich. Von jedem dieser Abschnitte zweigen Repräsentationen untergeordneter Teilbäume ab, die in der selben Version im System entstanden sind. Somit gruppieren die Autobahnabschnitte die Subsysteme nach ihren Entstehungszeitpunkten. In jedem Abschnitt der Autobahn erfolgt die Positionierung der Subsystem-Repräsentationen in zwei Schritten. Zuerst bestimmt das Layout die Straßenseitenzuordnung und Reihenfolge der Subsysteme auf Grundlage von Attribut- bzw. Metrikwerten zum Entstehungszeitpunkt der Subsysteme. Danach werden die Repräsentationen entsprechend dieser Reihenfolgen auf Grundlage der Metrikwerte der letzten visualisierten Version an den Rändern der Autobahn überschneidungsfrei positioniert.Es sei zunächst die Menge aller maximalen Teilbäume des gegebenen veränderlichen Baumes als X definiert. Die Untermenge T v⊆X von X enthält alle Teilbäume, deren Wurzelknoten die Kinder eine Baumknotens v darstellen. Eine weitere Untermenge T v ,i⊆T v bezeichnet 20

Abbildung 16: Bei der Repräsentation des Level 1-Elementes als Autobahn zweigen Subsysteme orthogonal von der Autobahn ab. Jeder Abschnitt der unterteilten Autobahn gruppiert die Subsysteme dabei nach ihren Entstehungszeitpunkten: a) 3D-Darstellung, b) schematische Darstellung der An-ordnung der Subsysteme.

4.2 REPRÄSENTATION UND LAYOUT DES LEVEL 1-KNOTENS

diejenigen Teilbäume aus T v , deren Wurzeln zum Zeitpunkt t i entstanden sind. Über der Menge X sei außerdem eine Ordnungsrelation Rb⊆X×X definiert durch:u , v∈Rb⇔b u b v∨b u =b v∧GUIDuGUID v, mit u , v∈ X (2)

Die Funktionen a : X ℝ und b: Xℝ beschreiben die Breite bzw. Tiefe der Grundflächen-begrenzung einer Teilbaum-Repräsentation zum Entstehungszeitpunkt der Teilbaumwurzel. Sie geben somit konstant die Ausdehnungen der Repräsentation eines Teilbaums zurück, die er in der Version, in der die Teilbaumwurzel als Knoten zur Baum hinzugefügt wurden, besessen hat. Die Funktion GUID : X ℝ liefert für einen Teilbaum einen eindeutigen Schlüssel zurück. Mit Hilfe der Ordnungsrelation Rb lassen sich die Elemente einer Menge T v ,i nach der historischen Tiefe der Begrenzungsflächen der Teilbaum-Repräsentationen absteigend sortieren. Eine nach der Relation Rb geordnete Menge T v ,i ist als T v ,i definiert. Für den Wurzelknoten r des gegebenen Baumes bezeichnet somit T r , i die Menge aller Subsystem-Teilbäume, die zum Zeitpunkt t i entstanden sind. T r , i beschreibt die nach der historischen Tiefe der Repräsentationen geordnete Menge von Subsystem-Teilbäumen mit dem Ent-stehungszeitpunkt t i .Zum Bestimmen der Seitenzuordnung und Reihenfolge an einem Abschnitt der Autobahn werden beide Seiten des Abschnitts ausgewogen mit den Elementen der sortierten Menge T r , i in Entwicklungsrichtung der Autobahn „aufgefüllt“. Dabei positioniert der Layout-Algorithmus zuerst die größte Repräsentation eines Subsystems si ,1∈T r , i an eine Seite des Autobahnab-schnitts. Damit ist diese Seite über eine Länge von a s i ,1 , der historischen Breite der Repräsentation von si ,1 , als belegt markiert. Die nächstgrößere Repräsentation eines Sub-systems si ,2∈T r , i wird danach an die Straßenseite mit der kürzeren Seitenmarkierung positioniert und die Markierung an der entsprechenden Seite um a s i ,2 verlängert. Dieses Vorgehen lässt sich für alle weiteren Elemente aus T r , i wiederholen, wobei an beiden Seiten des Autobahnabschnitts Subsystem-Repräsentationen mit immer kleinerer historischer Grundflächen-Tiefe angefügt werden. Für das Layout der Subsystem-Repräsentationen an der Autobahn wechselt die Seite, bei der der Füll-Algorithmus startet, mit jedem Autobahn-abschnitt alternierend. Darstellung b) der Abbildung 16 zeigt schematisch die Anordnung der Subsystem-Repräsentationen an den Seiten einer Autobahn.Mit den zuvor bestimmten Informationen über die Reihenfolge und Straßenseitenzuordnung der Subsysteme eines Autobahnabschnitts kann der Layout-Algorithmus in einem zweiten Schritt die Repräsentationen der Subsystem-Teilbäumen der Menge T r , i mit ihren aktuellen Ausdehnungen an den Rändern des Abschnitts positionieren. Die Ausdehnung und die Form der Subsystem-Repräsentationen ist dabei durch die Metrikwerte der letzten visualisierten Version bestimmt.Durch den beschriebenen Layout-Algorithmus für Subsystem-Repräsentationen an einem Abschnitt der Autobahn ist für Stadtvisualisierungen späterer Baumversionen sichergestellt, dass die Straßenseite, der eine Subsystem-Repräsentation zugewiesen wird, und auch die Reihenfolge der Repräsentationen an jeder Straßenseite konstant bleibt und sich im Laufe der Systementwicklung nicht mehr ändern. Dieses wirkt sich positiv auf die Stabilität des Layouts aus. Untersuchungen verschiedener Variationen des Algorithmus im Prototypen Evolution Viewer haben gezeigt, dass sich die Sortierung der Repräsentationen nach der Größe sowie der Seitenwechsel mit jedem Autobahnabschnitt positiv auf die Übersichtlichkeit und Lesbarkeit der Visualisierung auswirkt, da sich hierdurch die Gruppierung der Subsysteme nach ihren Entstehungszeitpunkten visuell verstärken lässt.

21


Von beiden möglichen Repräsentationen des Level 1-Knotens gehen als Straßen visualisierte untergeordnete Level 2-Knoten ab. Die Repräsentation und das Layout dieser Level 2-Hierarchien beschreibt der nächste Abschnitt.4.3 Repräsentation und Layout der Level 2-KnotenDie Dekompositionsstruktur der Level 2-Knoten des gegebenen Baumes wird durch den Layout-Algorithmus in den Stadtvisualisierungen als hierarchisches Straßennetz abgebildet. Ausgehend vom Repräsentanten der Level 2-Wurzel eines Subsystem-Teilbaums zweigen alle als Straßen dargestellten Level 2-Knoten in einem für das gesamte Stadtlayout einheitlichen Winkel von übergeordneten Straßen ab. Dieser Abzweigungswinkel der Straßen kann Werte zwischen 0° und 90° annehmen ( 0°≤90° ). Je kleiner der Abzweigungswinkel für das Stadt-Layout gewählt wird, desto ähnlicher ist die Entwicklungsrichtung der Kind-Repräsentationen zur Entwicklungsrichtung der Repräsentation des Elternknotens. Bei einem kleinen Abzweigungswinkel kann außerdem das Problem vermieden werden, dass es Repräsentationen gibt, die in Richtung Stadtzentrum wachsen. Ein solches Wachstum zum Zentrum hin kann sich negativ auf die Stabilität des gesamten Layouts auswirken. Genauere Untersuchungen der Abhängigkeit der Stabilität sowie der Abhängigkeit Kompaktheit des Layouts vom Abzweigungswinkel finden sich im Kapitel 5.1.2.2 und 5.2.2.1.Abbildung 17 zeigt als Beispiel drei Darstellungen von Visualisierungen der Level 2-Knoten-Hierarchie als Straßennetz mit einem Abzweigungswinkel der Straßen von 30°, 45° und 90°. Diese drei Abzweigungswinkel stellen spezielle Winkel für die visualisierten Städte dar, da sie die möglichen Orientierungsrichtungen der Straßen begrenzen, falls der Level 1-Knoten als Autobahn repräsentiert ist. Für einen Abzweigungswinkel von =30 ° ist die Anzahl der Straßenorientierungen auf sechs begrenzt. In einer Stadtvisualisierung, in der die Straßen mit einem Winkel von =45° von übergeordneten Straßen abzweigen, gibt es vier mögliche Orientierungen der Straßen und für einen Abzweigungswinkel von =90 ° begrenzt sich die Anzahl der Straßenorientierungen auf zwei. Falls der Level 1-Knoten als Platz repräsentiert ist, gilt die die Begrenzung der Straßenorientierungen nicht für das gesamte Stadt-Layout sondern nur separat für jedes Subsystem.

Um die Evolution eines Level 2-Knotens in den Stadtvisualisierungen darzustellen, ist jede 22

Abbildung 17: Abbildung der Dekompositionsstruktur der Level 2-Knoten als hierarchisch angeord-netes Straßensystem mit unterschiedlichen Abzweigungswinkeln der Straßen: a) 30°, b) 45° und c) 90°.

4.3 REPRÄSENTATION UND LAYOUT DER LEVEL 2-KNOTEN

Straße (ähnlich zur Autobahn) in verschiedene Abschnitte unterteilt. Von jedem der Abschnitte zweigen Repräsentanten von Kinder ab, die in der selben Version entstanden sind. Die Höhe der Abschnitte im Stadt-Layout bildet dabei den gemeinsamen Entstehungszeitpunkt abzweigender Kind-Repräsentationen ab. Somit gruppieren die Straßenabschnitte Reprä-sentationen untergeordneter Knoten nach der Version, in der sie zum System hinzugefügt wurden. Durch ein Anfügen der Repräsentationen neu entstandener Kind-Knoten eines Level 2-Knotens am Ende der Straße, wächst diese im Laufe der Systementwicklung in eine Richtung und bildet einen ungleichmäßig eingeteilten Zeitstrahl ab. Die Entfernungen der Straßenabschnitte zum Ursprung der Straße geben dadurch den Entstehungszeitpunkt der abzweigenden Repräsentationen von Kind-Knoten relativ zum übergeordneten Elternknoten wieder.Da die Anordnung und Positionierung von Repräsentanten der Kinder eines Level 2-Knotens an den Straßenabschnitten vom Knotenlevel dieser Kinder abhängig ist, werden in den nächsten zwei Abschnitten die beiden möglichen Fälle gesondert erläutert. Dabei können die Kinder eines Level 2-Knotens den Knotenlevel 2 oder 3 besitzen.4.3.1 Layout von Level 2-Knoten mit Level 2-KindernDas Layout von Level 2-Knoten beruht auf dem Ansatz die Repräsentationen der Kindknoten möglichst optimal innerhalb eines Parallelogramms anzuordnen, d.h. den Flächeninhalt eines umschließenden Parallelogramms zu minimieren. Die Repräsentationen der Kinder, die von einer Straße abzweigen, sind dabei nach ihren Entstehungszeitpunkten gruppiert an ver-schieden Straßenabschnitten angeordnet.Abbildung 18 zeigt schematisch das Vorgehen beim Positionieren von Repräsentationen von untergeordneten Level 2-Teilbäumen an den Seiten einer Straße, die den übergeordneten Level 2-Elternknoten repräsentiert. Der dargestellte und im weiteren näher beschriebene Layout-Algorithmus ist speziell für eine nach rechts abzweigende Straße eines Level 2-Elternknotens entwickelt. Für nach links abzweigende Straßen muss die vorgestellte Anordnung der Kind-Repräsentationen an der Mittelachse der Straße gespiegelt werden.

Die Positionierung der Kind-Repräsentationen an den Rändern jedes Straßenabschnitts erfolgt, wie beim Layout der Autobahnabschnitte, in zwei Schritten. Zuerst bestimmt der Layout-Algorithmus die Straßenseitenzuordnung und die Reihenfolge der Repräsentationen auf 23

Abbildung 18: Positionierung von untergeordneten Level 2-Teilbäumen an den Seiten einer nach rechts abzweigenden Straße, die den übergeordneten Level 2-Elternknoten p repräsentiert.


Grundlage der Attribut- bzw. Metrikwerte zum Entstehungszeitpunkt der Kinder. Für das Layout von Level 2-Knoten mit Level 2-Kindern ordnet der Algorithmus die Kind-Reprä-sentationen an jedem Abschnitt der Größe nach absteigend im Uhrzeigersinn an. In einem zweiten Schritt werden dann die Repräsentationen entsprechend der Seitenzuordnung und Reihenfolge auf Grundlage der Attributwerte der letzten visualisierten Version an den Straßenseiten positioniert.Es sei zunächst der als Straße repräsentierte Level 2-Knoten als p benannt. Nach den Definitionen der Mengen X , T v , T v ,i und T v ,i , die im Kapitel 4.2.2 beschrieben sind, bezeichnet T p die Menge aller Teilbäume, deren Wurzeln die Kinder des Knotens p sind und deren Repräsentationen der Layout-Algorithmus an den Rändern der Straße anordnet. Die Menge der Teilbäume, deren Repräsentationen von nur einem Abschnitt der Straße abzweigen, lässt sich durch T p , i beschreiben, wobei der betrachtete Straßenabschnitt die Version t i repräsentiert. Die durch die Ordnungsrelation Rb geordnete Menge T p , i ist als T p , i bezeichnet und enthält die Elemente aus T p , i absteigend nach der historischen Tiefe der Teilbaum-Repräsentationen sortiert. Die historische Breite eines Teilbaums, d.h. die Breite, die die Repräsentation eines Teilbaums zum Entstehungszeitpunkt der Teilbaumwurzel besessen hat, berechnet die Funktion a : X ℝ .Um den Repräsentationen eines Straßenabschnitts eine Seite zuzuweisen und ihre Reihenfolge festzulegen, wird die linke Seite des Abschnitts absteigend mit den historisch größten Repräsentationen und die rechte Seite aufsteigend mit den historisch kleinsten Reprä-sentationen ausgewogen aufgefüllt. Der Algorithmus beginnt dabei mit dem ersten und größten Teilbaum e i ,1∈T p , i und positioniert dessen Repräsentation an der linken Seite des Straßenabschnitts. Damit ist die linke Seite um die auf die Straße projizierte historische Breite der Repräsentation a ei ,1⋅sin a −1 markiert und das Element e i ,1 kann aus der Menge T p , i entfernt werden. Solange die Menge T p , i nicht leer ist, führt der Algorithmus dann die folgenden Anweisungen aus: Falls die Markierung der rechten Seite kürzer ist als die der linken Seite, positioniert er das letzte und somit auch das kleinste Element e i , n∈T p , i mit n=∣T p , i∣ an der rechten Seite, verlängert die Markierung der rechten Seite um die projizierte historische Breite a ei , n⋅sin a −1 und entfernt e i , n aus der Menge T p , i . Für den Fall, dass die Markierung der linken Seite die kürzere ist, wird das größte Element e i ,1∈T p , i auf der linken Seite positioniert, die linke Markierung um a ei ,1⋅sin a −1 verlängert und das Element aus T p , i entfernt. Abbildung 18 zeigt schematisch das beschriebene Vorgehen für drei Abschnitte einer nach rechts abzweigenden Straße.Unter der Voraussetzung, dass die untergeordneten Elemente der Repräsentationen der Kind-Teilbäume auch optimal innerhalb von Parallelogrammen angeordnet sind, lassen sich die Begrenzungsflächen der Repräsentationen als Parallelogramme vorstellen. Solche Parallelo-gramme können an der linken Straßenseite wesentlich optimaler in ein umschließendes Parallelogramm gepackt werden als auf der rechten. Der Grund hierfür sind unvermeidliche ungenutzte Flächen auf der rechten Seiten, die in der Abbildung 18 als blaue Flächen hervorgehoben sind. Daher positioniert der Layout-Algorithmus die größten Repräsentationen eines Abschnitts an der linken Straßenseite und die kleineren an der rechten, um die Reprä-sentationen möglichst optimal innerhalb eines umschließenden Parallelogramms anzuordnen.Nachdem die Seitenzuordnung und Reihenfolge der Repräsentationen für einen Straßen-abschnitt bestimmt wurden, können im zweiten Schritt des Layout-Algorithmus die Repräsentationen entsprechend dieser Festlegungen auf Grundlage der Attributwerte der letzten visualisierten Version überschneidungsfrei an den Straßenseiten positioniert werden. 24

4.3 REPRÄSENTATION UND LAYOUT DER LEVEL 2-KNOTEN

4.3.2 Layout von Level 2-Knoten mit Level 3-KindernGrundsätzlich ist das Layout-Verfahren für Level 2-Knoten mit Level 3-Kindern dem im vorigen Abschnitt beschriebenen Layout von Level 2-Knoten mit Level 2-Kindern sehr ähnlich.Der wichtigste Unterschied der beiden Packing-Verfahren ist jedoch die Herangehensweise bei der Bestimmung der Seitenzuordnung und Reihenfolge der Repräsentationen an einem Stra-ßenabschnitt. Während der Layout-Algorithmus für Level 2-Kinder die Repräsentationen im Uhrzeigersinn der Größe nach absteigend anordnet, positioniert der Algorithmus die Reprä-sentationen von untergeordneten Level 3-Teilbäumen an jedem Straßenabschnitt (der Größe nach absteigend) gegen den Uhrzeigersinn. Außerdem wird die erste und größte Teilbaum-Repräsentation auch nicht der linken sondern der rechten Straßenseite zugeordnet. Mit anderen Worten ist die rotierende Anordnung der Repräsentationen für jedem Straßen-abschnitt im Gegensatz zum Layout mit Level 2-Kindern an der Mittelachse der Straße gespiegelt. In Abbildung 19 ist die Anordnung der Repräsentationen untergeordneter Level 3-Teilbäume an drei Straßenabschnitten schematisch dargestellt.

Ein zweiter Unterschied zum zuvor beschriebenen Layout von Level 2-Knoten mit Level 2-Kindern ist die Unterscheidung verschiedener Straßenabschnitte im Layout-Algorithmus. Für den ersten Abschnitt der Straße enthält die linke Markierung der Straßenseite eine veränderliche Anfangskomponente, die die Gesamtmarkierung dieser Seite verlängert. Die Anfangskomponente wird mit jeder neuen Positionierung einer Repräsentation auf der linken Seite so angepasst, dass die Repräsentationen der linken Straßenseite an den Repräsentanten der übergeordneten Straße anstoßen ohne diese zu überschneiden. In der Abbildung 19 ist die Anfangskomponente der linken Seitenmarkierung für den ersten Straßenabschnitt durch eine orange Linie hervorgehoben. Die Änderung der Rotationsrichtung beim Anordnen der Kind-Repräsentationen für das Layout von Level 3-Kindern an einem Straßenabschnitt hat den Vorteil, dass dadurch der ungenutzte Platz, der in der Abbildung 19 als blauer Bereich markiert ist, im ersten Straßen-abschnitt auf der linken Straßenseite minimiert wird und sich letztlich auch der Flächeninhalt eines umschließenden Parallelogrammes verkleinert.Wie der Layout-Algorithmus jeden einzelnen Level 3-Kindknoten und auch Level 3-Knoten-hierarchien in den Stadtvisualisierungen repräsentiert, beschreibt das folgende Kapitel.25

Abbildung 19: Positionierung von untergeordneten Level 3-Teilbäumen an den Seiten einer nach rechts abzweigenden Straße, die den übergeordneten Level 2-Elternknoten repräsentiert.


4.4 Repräsentation und Layout von Level 3-KnotenEine einfache Möglichkeit, einen Level 3-Knoten, der keine Kinder besitzt, in der Stadtvisualisierung darzustellen, ist die Repräsentation als quaderför-miges Gebäude. Ein solcher Quader besitzt die frei-en visuellen Eigenschaften der Breite, Tiefe, Höhe und der Farbe. Hierdurch lassen sich auf die räumli-che Ausdehnung und auf die Farbe, die sich in ei-nem dreidimensionalen Farbraum darstellen lässt (z.B. RGB oder HSB), jeweils drei verschiedene At-tribute bzw. Metriken abbilden. Die abgebildeten Attribute beziehen sich dabei immer auf die letzte Version, die durch die Stadtvisualisierung darge-stellt wird. Abbildung 20 zeigt ein Beispiel dieser Repräsentation, wobei zu erkennen ist, dass sich der Quader auf einer Grundfläche befindet, die als Gebäudegrundstück interpretiert werden kann. Ist das visualisierte Level 3-Element zum letzten Zeitpunkt der Visualisierung nicht mehr im System vorhanden, wird der gesamte Repräsentant dunkelgrau eingefärbt oder ausgeblendet.Für die Visualisierung von Softwaresystemen, durch die diese Arbeit motiviert ist, stellen in der zu visualisierenden Baumstruktur Level 3-Elemente im Allgemeinen Klassen dar. In den Stadtvisualisierungen repräsentieren für einen solchen Anwendungsfall Gebäudequader die Klassen eines Softwaresystems. Innere und anonyme Klassen können dabei als Kinder einer umschließenden Klasse aufgefasst werden und definieren somit eine Hierarchie von Level 3-Knoten. Basierend auf der Metapher eines Hinterhofs lässt sich die Repräsentation einer Level 3-Hierarchie rekursiv konstruieren.

Die untersten Knoten (Blätter) in einem Teilbaum von Level 3-Knoten besitzen keine Kinder und lassen sich, wie oben beschrieben, als Gebäudequader repräsentieren. Ein übergeordneter Level 3-Knoten wird ebenfalls als Quader repräsentiert, wobei die Grundstücksfläche an der von der Straße abgewandten Seite nach hinten erweitert wird, bis alle Gebäude-Reprä-sentanten der untergeordneten Elemente im „Hinterhof“ Platz finden. Die Breite des Grundstücks ergibt sich aus der maximalen Breite der Repräsentanten aller untergeordneter Level 3-Knoten und des Gebäudequaders selbst. Die selbe Konstruktionsvorschrift ist rekursiv 26

Abbildung 20: Quaderförmige Gebäude-Repräsentation eines Level 3-Elementes ohne untergeordnete Elemente.

Abbildung 21: Rekursiv konstruierte Repräsentation einer Level 3-Hierarchie als a) Draufsicht, b) Seitenansicht und c) 3D-Ansicht.

4.4 REPRÄSENTATION UND LAYOUT VON LEVEL 3-KNOTEN

auf weitere übergeordnete Level 3-Knoten anwendbar. Um die zeitliche Entwicklung der Level 3-Hierarchie darzustellen, besteht die Grundfläche (bzw. das Grundstück) eines Gebäudes aus Terrassen. Auf jeder dieser Terrassen befinden sich Repräsentanten untergeordneter Level 3-Knoten, die in der selben Version entstanden sind. Die Höhe der Terrassen-Abschnitte bildet dabei den Entstehungszeitpunkt der enthaltenen Repräsentanten linear ab. Im Laufe der Zeit kann sich dieser stufige „Hinterhof“ von unten nach oben oder von oben nach unten entwickeln. Für den Fall, dass die maximale Baumtiefe einer visualisierten Level 3-Hierarchie höchsten 2 beträgt, stellt der Hinterhof von oben gesehen, wie auch die zuvor beschriebenen Straßen, eine ungleichmäßig unterteilte Zeitachse dar. Abbildung 21 zeigt die Repräsentation einer Hierarchie von Level 3-Knoten als Draufsicht, Seitenansicht und dreidimensionaler Ansicht in den Darstellungen a), b) und c). Der repräsentierte Baum von Level 3-Knoten hat dabei eine maximale Tiefe von 3. Die in den Darstellungen a) und b) orange markierten Objekte repräsentieren zwei Teilbäume der Tiefe 2, die bei der rekursiven Konstruktion zuerst modelliert werden.Auf eine zweite Möglichkeit der Repräsentation von Level 3-Elementen geht das Kapitel 4.6 näher ein. Die darin beschriebenen Evolution Tower stellen eine Level 3-Repräsentation dar, die speziell für die Entwicklungsrichtung des Geländes von unten nach oben Verwendung findet. Daher beschreibt das folgende Kapitel 4.5 zuerst das Gelände als Höhenfeld und stellt verschiedenen Entwicklungsrichtungen gegenüber.Implementierung: Um die Komplexität der Stadtvisualisierungen besonders von sehr großen Systemen zu begrenzen, lässt sich im Prototypen der Aufbau von Level 3-Hierarchien in der zu visualisierenden Baumstruktur verhindern. Diese Option ist als Standardeinstellung festgelegt und stellt alle Level 3-Knoten der obersten Ebene als Gebäudequader ohne „Hinterhof“ dar.4.5 HöhenfeldOhne eine optische Verbindung der einzelnen Stadtobjekte in den Visualisierungen schwebt die Stadtszene mit ihren Objekten in der Luft und das Ablesen der Höhen der Objektgrundflächen, welche Informationen über die Entwicklungsgeschichte der dargestellten Baumstruktur abbilden, ist nur schwer möglich. Eine dreidimensionale Landschaft, in die die Stadt eingebettet ist, unterstützt dagegen eine intuitive Vermittlung der Höheninformation durch die Stadtmetapher und erleichtert damit ein schnelles Wahrnehmen der Evolution des visualisierten Systems. Zusätzlich gibt ein dargestelltes Gelände die Möglichkeit, auch in einer Draufsicht Höheninformationen abzulesen. Freien Flächen zwischen Systemrepräsentanten werden durch ein Höhenfeld als Informationsträger nutzbar gemacht, um Aspekte der Systementwicklung in den Visualisierungen redundant und somit verstärkt darzustellen.Anders als in der Realität, in der sich eine Stadt in einem vorgegebenen Gelände entwickelt, sind für die Konstruktion des Höhenfeldes in dieser Arbeit die Positionen der Stadtobjekte und die Höhen der Grundflächen vorgegeben und das Höhenfeld des Geländes soll nach dem Layout-Verfahren unter diese Objekte generiert werden. Das Höhenfeld ist dabei als zwei-dimensionale Funktion modelliert, die für einen Punkt in der XZ-Ebene die Geländehöhe bestimmt.4.5.1 Implizite Flächen und MetaballsOberflächen dreidimensionaler Objekte im ℝ3 lassen sich entweder explizit durch Funktionen in Parameterform oder implizit darstellen. Implizite Flächen sind als Punktmengen der Form

27


{q∈ℝN | f q=0 } definiert.Metaballs, welche implizite Flächen zur Beschreibung von Objektoberflächen im Raum nutzen, wurden zuerst von Blinn in [Bli82] als Blobs beschrieben und finden u.a. in den Arbeiten [BD07], [LBD07], [YJC98], [DKYON00] sehr unterschiedliche Anwendungen. Eine einführende Erläuterung von Impliziten Flächen und Metaballs ist in [Wat00] aufgeführt.Das Metaball-Konzept beschreibt eine implizite Fläche durch eine Menge von Generator-punkten P , wobei jeder Generatorpunkt pi∈P , mit 1≤i≤∣P∣ einen zugehörigen Einfluss-radius r i besitzt. Den Anteil der Dichte im Raum eines einzelnen Generatorpunktes pi in einem Punkt q∈ℝ3 bestimmt die Dichtefunktion D i :ℝ3ℝ , die in Gleichung 3 definiert ist.

D i q={1−∥q− pi∥r i

22

, falls ∥q− pi∥r i

0 , falls ∥q− pi∥≥r i

(3) F q =∑iD i q− (4)

Die Summe der Dichtefunktionen aller Generatorpunkte aus P minus einem Schwellenwert ≥0 erzeugt das Dichtefeld F . Gleichung 4 definiert die Funktion des Dichtefeldes F :ℝ3ℝ für einen Punkt q formal. Die implizite Fläche, die durch F q =0 beschrieben wird, enthält dabei genau die Punkte des Raumes, für die die Aufsummierung der Werte der Dichtefunktion D aller Generatorpunkte gleich dem Schwellenwert ist. Bei einem hohen Schwellenwert schmiegt sich die implizite Fläche enger an die Generatorpunkte an und trennt diese schneller. Für kleine Werte von findet dagegen eher eine „Verschmelzung“ der Generatorpunkte statt. Abbildung 22 zeigt eine Implizite Fläche im ℝ2 , die durch zwei Generatorpunkte p1 , p2 mit den Einflussradien r1 , r 2 und einem Schwellen-wert von 0,3 definiert ist.4.5.2 Höhenfeld-FunktionAls Basis für die Entwicklung der Höhenfeld-Funktion dient das Dichtefeld F des beschriebenen Metaball-Konzeptes. Für einen Punkt q∈ℝ2 lässt sich der Wert einer für die Ebene angepassten Dichtefeld-Funktion F :ℝ2ℝ mit einem Schwellenwert =0 als Geländehöhe über der XZ-Ebene interpretieren. Jeder Generator-punkt pi∈P definiert dabei im Gelände eine punktförmige Erhöhung mit der Höhe 1. Der Einflussradius r i bestimmt, wie steil das Gelände an den Rändern der Erhöhung abfällt. Ein Schnitt durch ein Gelände, das durch zwei Generator-punkte p1 und p2 definiert wird, ist in Abbildung 23 dargestellt.Um das Höhenfeld für die Nutzung als Geländeform in den Stadtvisualisierungen anzupassen, muss der Ansatz der Funktion erweitert werden. So besitzen Stadtobjekte in den 28

Abbildung 22: Implizite Fläche, die im ℝ2 durch zwei Generatorpunkte und ei-nem Schellenwert =0,3 definiert ist. (Bildquelle: [BD07])

Abbildung 23: Schnitt durch ein Gelände das durch die Dichtefeld-Funktion F und zwei Generatorpunkte definiert ist.

4.5 HÖHENFELD

Visualisierungen ausgedehnte (nicht nur punktfömige) Grundflächen, die auf unter-schiedlichen Höhen liegen. Außerdem muss die Geländesteigung zwischen zwei ungleich hohen Stadtobjekten steiler sein als durch die Einflussradien angegeben, falls diese sich zu dicht beieinander befinden. Für jede Generatorfläche g i muss innerhalb der Fläche der Wert der Höhenfeld-Funktion stets gleich der Flächenhöhe hi sein. Die Funktion sollte dabei keine Knicke haben und die Ableitung weder Sprünge noch undefinierten Bereiche aufweisen.Eine erste Erweiterung der Dichtefeld-Funktion er-setzt die Menge P der Generatorpunkte durch eine Menge G von Generatorflächen, wobei jede Generatorfläche g i eine Abstandsfunktion d i :ℝ

2ℝ besitzt, die für einen Punkt q den kür-zesten Abstand zum Rand der Generatorfläche g i bestimmt. Stellt die Generatorfläche g i einen Punkt p dar, berechnet d i den euklidischen Ab-stand d Punkt q =∥q− p∥ . Ist die Generatorfläche g i als Kreis mit dem Mittelpunkt m und dem Radius a gegeben, ist d i definiert als d Kreis q=∥q−m∥−a, falls q außerhalb des Kreises liegt. Für den Fall, dass g i als Rechteck durch die Punkte A , B , C , D gegeben ist, muss zunächst bestimmt werden, in welchem von neun Bereichen sich der Punkt q befindet. Ist für eine Gerade AB der Normalenvektor n AB mit ∥n AB∥=1 gegeben, kann mit Hilfe des Skalarproduktes q−A⋅n AB der Abstand des Punktes q von der Geraden AB ermittelt werden. Das Vorzeichen des Skalarproduktes zeigt die Seite an, auf der sich q befindet. Hierdurch lässt sich die Ebene durch das Rechteck, wie in Abbildung 24 dargestellt, in neun Bereiche R I bis R IX unterteilen und bestimmen, in welchem sich der Punkt q befindet (beispielsweise gilt: q∈R IV⇔q−D ⋅n AD0∧q−A⋅nAB≤0∧q−C ⋅nCD≤0 ). Gleichung 5 definiert die Abstandsfunktion d Rechteck :ℝ2ℝ für ein beliebig transformiertes Rechteck ABCD in der Ebene.

d Rechteck q={∥q−A∥, falls q∈R I

q−A⋅nAB , falls q∈R II

∥q−B∥, falls q∈R III

q−D⋅n AD , falls q∈R IV

q−B ⋅n BC , falls q∈RVI

∥q−C∥, falls q∈RVII

q−C ⋅nCD , falls q∈RVIII

∥q−D∥, falls q∈R IX

0 , sonst.

(5)

Die um die Abstandsfunktion d i verallgemeinerte Dichtefunktion D i ist in Gleichung 6 definiert. Sie gibt den Einfluss einer beliebigen Generatorfläche g i auf die Geländehöhe an. Der Einflussradius r i setzt sich dabei aus dem Produkt der Höhe hi der Generatorfläche und einem Einflussfaktor zusammen, der die Steigung des Geländes definiert (siehe Gleichung 7).

29

Abbildung 24: Die Abstandsfunktion d iq für ein Rechteck ABCD .


D i q={1− d iq r i

22

, falls d i qr i

0 , falls d i q≥r i∨hi=0

(6) r i=hi⋅ (7)Welche Auswirkungen der Einflussfaktor auf die Steigung des Geländes und somit auf die generierte Geländeform hat, ist in Abbildung 19 vergleichend für die Werte =1,0 , =2,5 und =6,0 gezeigt. Die Werte entsprechen einer durchschnittlichen Steigung von 100%, 40% und 17%.

Um zu erreichen, dass sich das Gelände in der Nähe einer Generatorfläche g i unabhängig von allen anderen Generatorflächen den Rändern von g i annähert, muss eine Gewichtung der Dichte- bzw. Höhenfunktion D i mit abnehmendem Abstand zu g i stark zunehmen. Bei einem minimalen Abstand zum Rand der Generatorfläche g i muss durch die Gewichtung der Anteil der übrigen Höhenfunktionen {D k | 1≤k≤∣G∣∧k≠i } an der Gesamthöhe vernachlässigbar gering sein. Die Gewichtungsfunktion W i , die in Gleichung 8 angegeben ist, besitzt die Eigenschaft, sehr schnell gegen unendlich zu streben, falls der Abstand eines Punktes q zum Rand der Generatorfläche g i gegen Null geht. Dafür sorgt die erste Teilfunktion der Gleichung: r i⋅d i q

2−1 . Durch die Multiplikation mit einer zweiten Teilfunktion d i q −r i2 , der eine in X-Richtung verschobene quadratische Funktion darstellt, strebt die Gewichtungsfunktion W i gegen Null, falls der Abstand des Punktes q gegen den Einflussradius r i strebt. Ist der Abstand des Punktes q größer als der Einflussradius r i , liefert die Gewichtsfunktion W i Null zurück.

W i q={ r i

d i q 2⋅d i q −r i

2 , falls d i qr i

0 , falls d i q≥r i

(8)Durch eine Verknüpfung der Gewichtsfunktion W i mit der um hi skalierten Dichte- bzw. Höhenfunktion D i jeder Generatorfläche lässt sich der Anteil jeder Höhenfunktionen in einer Aufsummierung anpassen. Diese Summe der gewichteten und skalierten Höhenfunktionen kann durch Division durch die Summe aller Gewichte normalisiert werden und bildet somit das Höhenfeld H :ℝ2ℝ . Eine formale Definition der Höhenfeld-Funktion ist in Gleichung 9 angegeben.30

Abbildung 25: Die Auswirkungen des Einflussfaktors auf die Steigung und Form des Geländes.

4.5 HÖHENFELD

H q =∑i=1

N

D i q⋅hi⋅W iq

∑i=1

N

W i q mit N=∣G∣ (9)

Durch die Erweiterung des Dichtefeldes für Metaballs um beliebige Generatorflächen und eine Gewichtung der Dichtefunktionen ist es möglich, die Werte des Dichtefelds als Höhenfeld zu interpretieren und ein Gelände für die visualisierte Stadt zu formen, welches durch die Grundflächen der einzelnen Stadtobjekte definiert wird. Abbildung 26 zeigt einen Schnitt durch ein Gelände, das zwei Generatorflächen g 1 und g 2 der Höhe h1 und h2 definieren. Die starke Nähe der beiden Generatorflächen führt zum gewünschten Verhalten der Höhenfeld-Funktion, dass das Gelände zwischen g 1 und g 2 steiler ist als durch den Einflussfaktor allgemein bestimmt. Die gestichelte Linie in der Abbildung deutet den Abfall des Geländes an der linken Seite von g 2 ohne den Einfluss der Generatorfläche g 1 an.4.5.3 Darstellung des HöhenfeldesUm das durch die Höhenfeld-Funktionen H beschriebene Gelände in den Stadt-Visualisierungen darzustellen, gibt es im entwickelten Prototypen Evolution Viewer drei Möglichkeiten: als Gitternetz, als solide Fläche oder als Höhenlinien. Die unterschiedlichen Darstellungsformen können außerdem als Kombinationen visualisiert werden. Abbildung 27 stellt die Möglichkeiten vergleichend dar, die in den folgenden Abschnitten näher beschrieben sind.Gitternetz: Bei einer Abtastung von Punkten auf der XZ-Ebene in einem Raster, definiert die Höhenfunktionen H q die Y-Komponente der Punkte, wobei für jeden Abtastpunkt p∈ℝ3 auf der XZ-Ebene der Punkte q= px , p z als Eingabe für die Höhenfeld-Funktion dient und ein zugehöriger Höhenpunkt definiert ist durch: P= p x , H p x , p z , pz . Nach dem Verbinden von allen benachbarten Höhenpunktpaaren mit einer Linie entsteht ein Gitternetz des Geländes, bei dem die Y-Komponenten der Höhenpunkte die Werte der Höhenfeld-Funktion widerspiegeln und die Linien lineare Interpolationen zwischen diesen Punkten darstellen. Neben einer Visualisierung der Höhenpunkte selbst ist das Gitternetz die einfachste Darstellungsform des Höhenfeldes, wobei kleine Änderungen der Höhe nur schwer erkennbar sind. Abbildung 27 zeigt in der Darstellung a) ein Beispiel eines Gitternetzes. Solide Fläche: Die solide Fläche zur Darstellung des Höhenfeldes ist eine aus ebenen Teilflächen bestehende angenäherte gekrümmte Fläche. Wie auch für das Gitternetz bilden die im Raster angeordneten Höhenpunkte, deren Y-Komponenten den Werten der Höhenfeld-Funktion entsprechen, die Basis für die Konstruktion. Die gekrümmte Fläche ist durch diese Höhenpunkte in Zellen unterteilt, wobei jeweils vier beieinander liegende Punkte eine Zelle als gekrümmtes Viereck definieren. Jedes dieser Vierecke lässt sich durch eine Diagonale in zwei (ebene) Dreiecke zerlegen. Die Gesamtheit aller Dreieck bestimmt dann ein geometrisches Objekt, welches das Gelände als solide Fläche beschreibt. Um eine Beleuchtung zu ermöglichen ist für jeden Punkt des Geländeobjektes zusätzlich ein Normalenvektor definiert, der senkrecht

31

Abbildung 26: Schnitt durch ein Gelände, das durch die Höhenfeld-Funktion H und zwei Generatorflächen g1 und g2 der Höhe h1 und h2 definiert ist.


auf einer tangentialen Ebene steht. Die dreidimensionale Wirkung des Geländes entsteht in der Visualisierung durch eine lokale Beleuchtung des Objektes.

Mit Hilfe der Darstellungsform des Geländes als solide gekrümmte Fläche lassen sich durch Licht- und Schatteneinwirkungen auch geringe Unebenheiten und Höhenunterschiede gut visualisieren. Da das Geländeobjekt jedoch relativ massiv ist, kann es von der eigentlichen Baumvisualisierung ablenken. Außerdem werden Artefakte, die bei einer groben Abtastung des Höhenfeldes auftreten, verstärkt wahrgenommen. Die Qualität der Geländevisualisierung als solide Fläche hängt daher stark von der Auflösung des Abtastrasters ab. Ein Beispiel für die 32

Abbildung 27: Darstellungen des Höhenfeldes durch ein Gitternetz a), durch eine solide Fläche b) oder durch Höhenlinien c).

4.5 HÖHENFELD

Visualisierung des Höhenfeldes als solide Fläche ist in der Darstellung b) der Abbildung 27 gezeigt. Höhenlinien: Voraussetzung für die Bestimmung der Höhenlinien ist eine Unterteilung der durch die Höhenfeld-Funktion beschriebene gekrümmten Fläche in Dreiecke, wie sie für die Darstellung des Geländes als solide Fläche beschrieben ist. Jedes Dreieck stellt dabei eine ebene Fläche dar, die eine gekrümmte Teilfläche, in die die gesamte Geländefläche durch die Höhenpunkte unterteilt wird, gut annähert. Die Schnittmenge eines Dreiecks mit einer zur XZ-Ebene parallelen Ebene der Höhe h ist für den allgemeinen Fall, dass P≠h , Q≠h und R≠h entweder leer oder sie entspricht der Verbindungsstrecke der Schnittpunkte von zwei Begrenzungs-strecken des Dreiecks. In jedem Dreieck △ PQR , das die Punkte P , Q und R definieren gilt: Falls es auf einer Begrenzungsstrecke eines Dreiecks ein Punkt s der Höhe h gibt, existiert auch auf einer der beiden anderen Strecken ein Punkt t der Höhe h . Die Verbindungsstrecke der beiden Punkte s und t definiert dann ein Liniensegment der Höhenlinie mit der Höhe h . Das Zusammenfügen der existierenden Liniensegmente aller Dreiecke führt zum Linienobjekt der Höhenlinie. Abbildung 28 zeigt schematisch die beschriebene Konstruktion eines Höhen-linien-Segments. In Abbildung 27 in der Darstellung c) ist ein Beispiel für die Visualisierung des Höhenfeldes als Höhenlinien gezeigt. Im Gegensatz zur soliden Fläche lassen sich durch diese Darstellungsform des Höhenfeldes die Höhen von entfernten Geländepunkten durch Abzählen der Höhenlinien mit einander vergleichen. Außerdem ist es möglich, die Höhen-information auch in einer Draufsicht der Stadtszene abzulesen. Durch eine Kombination der soliden Fläche mit Höhenlinien lassen sich die Höheninformationen schnell wahrnehmbar visualisieren, wobei zusätzlich ein Höhenvergleich entfernter Geländepunkte möglich ist (siehe Abbildung 29). 4.5.4 Entwicklungsrichtung des GeländesUm die zeitliche Entwicklung der visualisierten Baumstruktur auf die Basishöhe der Repräsentanten abzubilden, gibt es zunächst die Möglichkeiten, Repräsentanten neu erstellter Knoten entweder höher oder tiefer als die älteren zu positionieren. Die visualisierte Stadt wächst dadurch im Laufe der Systemevolution von unten nach oben oder von oben nach unten. Darüber hinaus gibt es die beiden Möglichkeiten, die Repräsentation der Systemwurzel oder die Repräsentationen der neuesten Systemelemente bzw. Baumknoten auf die Höhe Null zu positionieren. Hieraus ergeben sich vier Entwicklungsrichtungen, die sich in Form und Interpretation des Geländes unterscheiden. Sie sind vergleichend in Abbildung 29 dargestellt und werden im Folgenden näher beschrieben.Vom oben zur Ebene: Bei dieser Entwicklungsrichtung wächst die visualisierte Stadt im Laufe der Systemevolution von oben nach unten. Die Repräsentation der Wurzel befinden sich zusammen mit den ältesten Knoten-Repräsentationen auf dem Gipfel eines Berges und das hierarchische Straßensystem führt zusammen mit angrenzenden Gebäuden den Hang entlang in Richtung Ebene hinab. Je tiefer ein Repräsentant in der Visualisierung positioniert ist, desto

33

Abbildung 28: Konstruktion eines Segments der Höhenlinie.


später ist der dargestellte Knoten im Baum erstellt worden. Auf Höhe Null und somit auf der XZ-Ebene befinden sich alle Repräsentanten von Systemelementen, die erst in der aktuellen bzw. letzten visualisierten Version entstanden sind. Diese Darstellung der zeitlichen System-entwicklung hebt besonders den ältesten Teil des visualisierten Baumes hervor, da sich dieser gut sichtbar auf der Spitze des Berges befindet und in der Darstellung der Stadtszene auf einen zweidimensionalen Anzeigebereich von anderen Szenen-Objekten nur selten überdeckt wird.Vom der Ebene nach oben: Hier wächst die visualisierte Stadt von unten nach oben. Repräsentationen der ältesten Teile des Systems sind dabei im Tal angesiedelt. Umgeben ist das Tal von Bergen, auf denen die Repräsentanten von Systemelementen positioniert sind, die später zum System hinzugefügt wurden. Stadtobjekte auf den höchsten Gipfeln repräsentieren Elemente, die erst in der letzten dargestellten Version entstanden sind. Der Repräsentant der System Wurzel befindet sich auf der XZ-Ebene auf Höhe Null. Durch die Visualisierung der Systementwicklung vom Tal nach oben auf umgrenzende Berge bilden neue Systemelemente Landschaftsmarken in Form von Gipfeln aus, wodurch besonders neue Systemteile, die auf hohen Bergen positioniert sind, hervorgehoben werden.

Von unten zur Ebene: Eine andere Möglichkeit der Visualisierung der Systementwicklung durch die Geländeform stellt die Stadtentwicklung von unten zur Ebene dar. Das Stadtwachstum beginnt mit dem Wurzel-Repräsentanten am Boden eines Canyons bzw. eines Kraters für die Repräsentation der Wurzel als Autobahn bzw. als zentralen Platz. Im Laufe der Systementwicklung führen die Straßen zusammen mit angrenzenden Gebäuden die Krater- 34

Abbildung 29: Für die Abbildung der Systementwicklung auf die Basishöhe der Repräsentanten-Objekte gibt es vier Möglichkeit: a) Vom oben zur Ebene, b) Von der Ebene nach oben, c) Von unten zur Ebene und d) Von der Ebene nach unten.

4.5 HÖHENFELD

oder Canyonwände hinauf bis die Repräsentanten der neuesten Elemente schließlich die Ebene erreichen. Bei der entwicklungsbegleitenden Anwendung dieser Entwicklungsrichtung in den Stadtvisualisierungen versinkt der älteste Teil des Systems im Boden. Repräsentanten älterer Systemelement sind durch Überdeckungen in der Visualisierung immer schlechter erkennbar und treten immer stärker in den Hintergrund.Von der Ebene nach unten: Bei der Entwicklungsrichtung von der Ebene nach unten ist der Repräsentant der Wurzel in der Ebene auf Höhe Null positioniert. Im Laufe der System-entwicklung „graben“ sich Straßen und angrenzende Gebäude immer weiter in die Erde nach unten, wobei für die Repräsentationen der neusten Systemelemente tiefe Schneisen und Krater im Boden entstehen. Die Interpretation des Geländes für die Visualisierung der Entwicklungs-geschichte des Systems ist widersprüchlich. Einerseits sind tiefe Krater mit hohen Böschungs-wänden sehr markant in den Visualisierungen. Sie heben damit Repräsentanten von System-elemente optisch hervor, die erst spät zum System hinzugefügt wurden. Anderseits befinden sich genau diese Repräsentanten tief unter der Ebene, wodurch sie durch Überdeckungen in einer Visualisierung teilweise schlecht erkennbar sind.Speziell für die beiden Entwicklungsrichtungen von der Ebene nach oben und von unten zur Ebene, bei denen die Stadt von unten nach oben wächst, stellt eine alternative Repräsentation für Level 3-Knoten, die Evolution Tower, eine Möglichkeit dar, die Evolution der Level 3-Knoten selbst zu visualisieren. Kapitel 4.6 beschreibt diese Repräsentation näher.4.6 Evolution TowerFür das Level 1-Knoten und die Level 2-Knoten kann die Entwicklung von Attributen in den Stadtvisualisierungen durch die Repräsentation als Autobahn oder Straßen visualisiert werden. Jeder Straßenabschnitt repräsentiert eine Version des dargestellten Level 1- oder Level 2-Knotens und besitzt die freie visuelle Eigenschaft der Farbe, wodurch sich bis zu drei Attribute pro Version abbilden lassen. Im Gegensatz dazu bildet die Repräsentation der Level 3-Knoten als Gebäudequader die Knotenattribute nur für die letzte Version ab. Eine Möglichkeit, die Entwicklunggeschichte von Level 3-Knoten über alle Versionen zu visuali-sieren, stellt der in der Arbeit entwickelte Evolution Tower dar.Die Repräsentation Evolution Tower ist durch die von Lanza vorgestellte EvolutionMatrix inspiriert. Lanza be-schreibt in [Lan01] eine zweidimensionale Rasterdarstel-lung für Softwaresysteme, in der jede Zelle ein Rechteck enthalten kann, welches zwei Metriken einer Klasse für genau eine Version auf die Breite und Höhe abbildet. In je-der Zeile des Rasters lässt sich dadurch die Entwicklung der beiden Metriken einer Klasse über ihren Lebenszeit-raum verfolgen, während die Spalten eine Momentaufnah-me aller Klassen eines Softwaresystems zu einem Zeit-punkt darstellen (siehe Seite 4, Abbildung 3).Ähnlich zu den Zeilen der EvolutionMatrix, bildet ein nach oben wachsender Evolution Tower die Entwicklungsge-schichte eines Level 3-Knoten ab. Mit jeder neuen Version des Knotens erhält der Evolution Tower eine neue Schicht bzw. ein neues Stockwerk. Jede Schicht repräsentiert den Knoten zu einer bestimmten Version. Sie besitzt neben einer festen Höhe die freien visuellen Eigenschaften Breite, Tiefe und Farbe,

35

Abbildung 30: In einem Evolution Tower repräsentiert jedes Stock-werk genau eine Version eines Level 3- Knotens.


wodurch sich bis zu fünf Metriken bzw. Attribute pro Version auf den Evolution Tower abbilden lassen. Von unten nach oben spiegeln die Etagen des Evolution Towers die Entwicklung der Attribute eines Level 3-Knotens über alle Versionen wider. Die Größe der Gebäudegrundfläche orientiert sich an der maximalen Breite und Tiefe aller Schichten. Abbildung 30 zeigt ein Beispiel eines Evolution Towers mit 16 Schichten, bei dem die auf Schichtbreite und -tiefe abgebildete Metrik im Laufe der Entwicklung kontinuierlich wächst.Die Höhe einer Schicht im Evolution Tower zusammen mit einem Schichtzwischenraum ist in der Stadtszene gleich dem Höhenunterschied einer Version für die Straßenabschnitte. Durch diese Festlegung bildet die Position einer Schicht über der XZ-Ebene von jedem Evolution Tower die absolute Version bezüglich der Systementwicklung ab. Somit stellen alle Schichten, die sich auf einer Höhe über der XZ_Ebene befinden, Level 3-Knoten der selben Version dar. In Abbildung 31 ist in Darstellung a) die Visualisierung einer Straße mit angrenzenden Evolution Tower-Gebäuden schematisch als Seitenansicht gezeigt, wobei der Zusammenhang zwischen den Höhen der Gebäudeschichten und der Version bezüglich der Systementwicklung gut zu erkennen ist. Die Schichten sind in der zweidimensionalen Darstellung in einem Raster angeordnet, wobei in einer Zeile alle Gebäudeschichten die selbe Version repräsentieren. Die obersten Schichten aller Evolution Tower von Level 3-Knoten, die in der letzten dargestellten Version existieren, schließen in der gesamten Stadtszene an der oberen Seite bündig ab. Ein Beispiel für die dreidimensionale Visualisierung eines Level 2-Knotens mit Level 3-Kindern als Straße mit angrenzenden Evolution Tower-Gebäuden ist in Darstellung b) der Abbildung 31 gezeigt.

Die Repräsentation von Level 3-Knoten als Evolution Tower hat gegenüber der Repräsentation als Gebäudequader die Vorteile, durch die Darstellung jeder einzelnen Version eines Knotens als Gebäudeschicht die Entwicklungsgeschichte visualisieren zu können. Es lässt sich somit für alle Knoten der zu visualisierenden Baumstruktur unabhängig vom Knotenlevel die Evolution abbilden, wodurch gleichzeitig die Informationsdichte in den Stadtvisualisierungen erhöht wird. Zusätzlich lassen sich für die Visualisierung von Softwaresystemen Klassen, die als Evolution Tower repräsentiert sind, durch eine von Lanza in [Lan01] vorgestellte Kate-gorisierung einer Evolutionsart zuordnen, wodurch sich z.B. Muster und Antimuster für die strukturelle Entwicklung der Software konstruieren lassen.Für die Visualisierung großer Baumstrukturen stellt die hohe Informationsdichte bei der Repräsentation der Level 3-Knoten als Evolution Tower dagegen ein Problem dar. Durch eine zu hohe Komplexität und vielen Überdeckungen der dreidimensionalen Szene in den Visuali-sierungen sind die Darstellungen nur noch schwer lesbar. Auch die Performance wird durch 36

Abbildung 31: Repräsentation der Level 3-Knoten als Evolution Tower in einer von unten nach oben wachsenden Stadt: a) schematische Seitenansicht, b) Visualisierung der Entwicklungsgeschichte eines Level 2-Knotens (Straße) mit Level 3-Kindern (Evolution Tower).

4.6 EVOLUTION TOWER

eine Vervielfachung der geometrischen Szenenobjekte beeinträchtigt. Darüber hinaus geht für die Abbildung von Knotenattributen der Freiheitsgrad der Höhe für die Evolution Tower-Schicht verloren, wodurch sich die Anzahl der Attribute verringert, die auf die Repräsentation abgebildet werden können. Es hängt daher stark von der Struktur und Größe des darzustellenden Systems sowie vom Anwendungsfeld der Visualisierung ab, welche Reprä-sentation der Level 3-Knoten die geeigneste ist.Nachdem in den oberen Kapiteln 4.1 bis 4.6 ein Stadt-Layout zum Visualisieren von veränderlichen Baumstrukturen vorgestellt und verschiedene Repräsentationen für Baum-knoten unterschiedlicher Knotenlevel beschrieben wurden, gibt das nächste Kapitel ab-schließend einen Überblick über verschiedene Möglichkeiten, Knotenattribute in den Stadt-visualisierungen darzustellen.4.7 Abbilden von Knotenattributen auf visuelle

Eigenschaften der RepräsentantenFür die Berechnung der Visualisierung stellt ein gelevelter attributierter veränderlicher Baum LACT=V , E , , , , , A ,B , wie er in Kapitel 3.1.5 definiert ist, die Eingabe des Algorithmus dar. Jeder Baumknoten v∈V wird dabei in der Visualisierung als Stadtobjekt repräsentiert, wobei der Algorithmus Knoten, die in der letzten dargestellten Version nicht mehr existieren, grau färbt oder durch einen Platzhalter ersetzt. Da jeder Knotenrepräsentant freie visuelle Eigenschaften besitzt, können Knotenattibute der Menge A auf diese abgebildet werden, um somit die Informationsdichte in den Visualisierungen zu erhöhen und verschiedene Aspekte des Systems darzustellen bzw. zu verdeutlichen. Die verschiedenen Repräsentanten der Knoten besitzen jeweils unterschiedliche freie visuelle Eigenschaften, die für eine Abbildung der Attribute nutzbar sind. Der Level 1-Knoten kann wahlweise als Autobahn oder zentraler Platz repräsentiert werden. Bei einer Autobahn ist die Farbe und die Breite als visuelle Eigenschaft frei. Der zentrale Platz besitzt dagegen nur die freie Eigenschaft der Farbe. Level 2-Knoten sind durch Straßen repräsentiert, die die freien visuellen Eigenschaften der Breite und Farbe haben. Jeder Abschnitt einer Straße, welcher eine Version des Level 2-Knotens repräsentiert, lässt sich dabei in einer anderen Farbe darstellen. Level 3-Knoten werden entweder durch Gebäudequader oder durch Evolution Tower repräsentiert. Bei Gebäudequadern ist die Ausdehnung in drei Richtungen frei. Außerdem lassen sich auf die Färbung des Quaders, die Farbe des Grundstücks und die Farbe für die Grundstückbegrenzung weitere Knotenattribute abbilden. Für die Repräsentation der Level 3-Knoten als Evolution Tower entfällt die Quaderhöhe als freie Eigenschaft, da die Stockwerke in jedem Evolution Tower gleich hoch sind. Dafür ist es möglich, in einem Stockwerk, welches jeweils eine Version des Knotens repräsentiert, auf die Breite, Tiefe und Farbe des Stockwerkquaders die Ausprägung eines Knotenattributs für die entsprechende Version abzubilden. Somit lässt sich die Entwicklungsgeschichte von Attributen der Level 3-Knoten auf visuelle Eigenschaften der Evolution Tower-Repräsentanten abbilden.Alle freien Eigenschaften der Repräsentanten lassen sich in zwei Gruppen unterteilen: Ausdehnungen und Färbungen von Bereichen der Repräsentanten. Für Knoten, die in der letzten dargestellten Version nicht mehr existieren, sind die Farben durch den Visualisierungs-Algorithmus festgelegt. Sie stellen somit für diese Knoten keine freien visuellen Eigenschaften mehr dar. Die Abbildung der Attributwerte auf die freien visuellen Eigenschaften der Repräsentanten ist durch zwei Gruppen von Funktionen gelöst. Eine Abbildung von Knotenattributen auf Farben der Repräsentanten erfolgt durch Farbfunktionen. Auf die

37


Ausdehnungen der Repräsentanten lassen sich Attributwerte durch Float-Funktionen abbilden. Implementierung: Alle Farb- und Float-Funktionen lassen sich für die beschriebenen visuellen Eigenschaften durch eine grafische Benutzeroberfläche im entwickelten Werkzeug Evolution Viewer konfigurieren. Die Einstellungen können außerdem als XML-Datei gespeichert und wieder geladen werden.4.7.1 FarbfunktionenFarbfunktionen bilden Knotenattribute als Farben auf Bereiche von Repräsentanten der Systemelemente ab. Jede Farbfunktion c : P×Aℝ3 besitzt als Eingabe eine Menge von einstellbaren Parametern P={ p1 , , pn}, mit n=∣P∣∧ pi∈ℝ und eine Menge von Knoten-attributen A={a1 , , am}, mit m=∣A∣∧ai∈ℝ . Die Parameter der Eingabe lassen sich vor der Layout-Berechnung bestimmen und sind beim Generieren der Visualisierung unveränderlich. Für Teile von Repräsentanten, die eine bestimmte Version eines Systemelements reprä-sentieren, dienen die Werte, die ein Attribut des Elements für die entsprechende Version besitzt, als Attribut-Eingabe. Für Teile von Repräsentanten, die nur eine Version eines Systemelements darstellen, dient der Attributwert der aktuellen bzw. letzten dargestellten Version als Eingabe für eine Farbfunktion. Als Ausgabe berechnen Farbfunktionen einen Farbvektor im RGB-Raum, der durch drei Komponenten den Rot-, Grün- und Blauanteil der Farbe definiert. Der folgende Abschnitt beschreibt verschiedene Farbfunktion, die in der Arbeit entwickelt und im Evolution Viewer umgesetzt wurden, zusammen mit Beispielen für mögliche Anwendungen.Konstanter Farbwert (Constant Color Function): Die konstante Farbfunktion färbt einen Bereich aller Repräsentanten einheitlich mit einem Farbwert ein, der durch einen als Farbvektor angebenen Parameter bestimmt ist. Mit Hilfe der Funktion lässt sich z.B. ein einheitlicher Grauwert für alle Straßen festlegen. Farbübergang (Range Color Function): Mit Hilfe der Farbübergangsfunktion lässt sich ein Farbwert für einen Bereich des Repräsentanten zwischen zwei durch Parameter angegebene Farben C1 und C 2 in Abhängigkeit von einem Attribut a des visualisierten Systemknotens berechnen. Ist der Attributwert des Knotens kleiner als eine unteren Schranke S u , bestimmt der Farbvektor C1 die Färbung des Repräsentantenbereichs. Ist er größer als eine oberen Schranke S o , definiert C 2 die Färbung. Falls der Attributwert zwischen der unteren und oberen Schranke liegt, wird der Farbwert für den Bereich des Repräsentanten zwischen den Farben C1 und C 2 linear interpoliert. Die Berechnung des Rotanteils ist formal in Gleichung 10 angegeben. Der Blau- und Grünanteil der gesuchten Farbe kann analog berechnet werden.

cRCF , Ra ={ C 1, R , falls a≤S u

C 2, R , falls a≥S o

a−S u

S o−S u⋅C 2, R1− a−S u

S o−S u ⋅C 1, R , sonst. (10)

Eine mögliche Anwendung der Farbübergangsfunktion ist z.B. die Abbildung des Entstehungszeitpunktes bzw. des Alters eines Systemelementes auf die Farbe der Repräsentanten. Obwohl der Entstehungszeitpunkt bereits auf die Höhe der Objekt-grundflächen linear abgebildet ist und die Anordnung der Repräsentanten an den Rändern einer Straße Rückschlüsse über die relativen Entstehungszeitpunkte der visualisierten Systemelemente zulässt, kann eine zusätzliche Abbildung der Entstehungszeitpunkte auf die 38

4.7 ABBILDEN VON KNOTENATTRIBUTEN AUF VISUELLE EIGENSCHAFTEN DER REPRÄSENTANTEN

Farbe sinnvoll sein, falls diese Information besonders schnell in der Visualisierung wahrgenommen werden soll. In Abbildung 32 ist ein Beispiel für die beschriebene Anwendung angegeben. Dunkelblaue Gebäude und Straßenabschnitte repräsentieren dabei sehr alte Systemelemente. Je später ein Element im System entstanden ist, desto gelber ist sein Repräsentant eingefärbt.

39

Abbildung 32: Anwendung der Farbübergangsfunktion, um den Entstehungszeitpunkt der Systemelemente auf die Farbe der Straßen und Gebäude abzubilden.

Abbildung 33: Anwendung der Farbübergangsfunktion, um die Entwicklung der Softwaremetrik Degree der Klassen eines Systems auf die Farbe der Gebäude (Evolution Tower) abzubilden.


Eine weite Anwendungsmöglichkeit für die Farbübergangsfunktion ist in Abbildung 33 dargestellt. Hier wird die Entwicklung der Softwaremetrik Degree für alle Klassen eines Systems auf die Farben der Stockwerke der Evolution Tower abgebildet. Für einen niedrigen Metrikwert sind die Stockwerte dunkelblau dargestellt. Bei steigendem Wert der Degree-Metrik verfärben sie sich zu einem satten Orange. Bei zwei der vergrößerten Evolution Tower-Gebäude in der Abbildung ist eine Zunahme des Metrikwertes im Laufe der Entwicklung durch eine Farbveränderung der Stockwerke von unten nach oben (von blau zu orange) deutlich zu erkennen.Farbbereiche (Limits Color Function): Die Farbfunktion Farbbereiche färbt Bereiche eines Repräsentanten abhängig vom Wert eines Knotenattributes des visualisierten Systemelements in drei unterschiedlichen Farben C 1 , C 2 und C 3 , die durch Parameter definiert sind. Falls der Attributwert des Knotens innerhalb eines offenen Intervalls ]S u , S o[ liegt, das durch eine untere Schranke S u und eine obere Schranke S o begrenzt wird, bestimmt der Farbvektor C 2 die Farbe des Repräsentantenbereichs. Ist das Knotenattribut kleiner als die untere Schranke S u gibt C 1 die Farbe des Bereichs an, ist das Attribut größer der oberen Schranke bestimmt C 3 die Färbung. Die beschriebene Farbfunktion ist in Gleichung 11 definiert.

cLCF a ={C 1 , falls a≤S u

C 3 , falls a≥S o

C 2 , sonst. (11)

In der Abbildung 34 ist ein Beispiel für eine mögliche Anwendung der Farbfunktion Farbbereiche aufgeführt. Es lassen sich mit Hilfe der Farbfunktion Klassen markieren, die sehr viele Methoden und Attribute besitzen. Durch eine Färbung der Repräsentanten in den Farben einer Ampel kann so eine Visualisierung vor zu großen Klassen warnen, welche in der Softwareentwicklung bedingt durch ihre Komplexität meist einen großen Wartungsaufwand und hohe Entwicklungskosten bedeuten. Zusätzlich lässt sich in der Visualisierung die Komplexitätsentwicklung der Klassen sehr schnell erfassen, da alle Werte auf nur drei Bereiche bzw. Kategorien aufgeteilt sind. Mit den entsprechenden Daten für die einzelnen Systemelemente lassen sich in ähnlicher Art und Weise auch die Ergebnisse einer Diagnosesoftware wie z.B. FindBugs oder Checkstyle visualisieren.

40

Abbildung 34: Anwendung der Farbfunktion Farbbereiche, um Klassen mit zu vielen Methoden und Attributen durch die Färbung in Ampelfarben zu markieren.


Ein anderes Anwendungsbeispiel für die beschriebene Farbfunktion ist in Abbildung 35 dargestellt. Hier werden die Entstehungszeitpunkte der Systemelemente so auf die Färbung der Repräsentanten abgebildet, dass alle Element, die ab der Version 20 entstanden sind, durch eine Rotfärbung markiert sind. Eine solche Visualisierung kann helfen, die seit einer be-stimmten Version neu entstandenen Elemente schnell zu identifizieren und Struktur-änderungen des Systems einfach zu erkennen.

Farbpalette (Palette Color Function): Gegeben sei eine Menge C={C1 , ,Cn} von n Farbvektoren. Die Menge der möglichen Attributwerte sei außerdem in gleichgroße Intervalle unterteilt. Den Intervallen werden nacheinander die Farben der Farbmenge C zugeordnet, wobei nach einer Zuordnung der letzten Farbe Cn∈C dem nächsten Intervall wieder die Farbe C 1 zugewiesen wird. Der Farbwert der Funktion, der einen Teil des Repräsentanten einfärbt, bestimmt sich durch die Farbe ck∈C , die dem Intervall, in dem der Attributwert des Systemelements liegt, zugewiesen wurde. Durch einen als Parameter definierten Faktor p1 und einen Offset p2 lässt sich die Farbzuweisung anpassen. Die Gleichung 12 definiert die beschriebene Farbfunktion formal.

cPCF a =C k , mit C k∈C∧k=⌊ a⋅p1 p2 ⌋MOD n (12)Ein Beispiel einer Anwendungsmöglichkeit der Farbfunktion Farbpalette ist in Abbildung 36 dargestellt. Hier gruppiert die Farbfunktion unterschiedliche Wertebereiche der Methoden- und Attributanzahl der Klassen und unterstützt ein schnelles Erfassen der Komplexität einer Klasse durch die Färbung der Repräsentanten. In der Abbildung 36 sind z.B. viele kleine dunkelblaue Gebäude zu erkennen, die Klassen mit weniger als 25 Methoden und Attributen repräsentieren. Dagegen gibt es nur ein hellblaues Gebäude, welches eine Klasse mit mehr als 125 Methoden und Attribute repräsentiert. Die obere Darstellung a) der Abbildung visualisiert dabei die Anzahl der Methoden und Attribute der Klassen für die aktuelle bzw. für die letzte dargestellte Version. In der unteren Darstellung b) wird zusätzlich die Entwicklung der Komplexität jeder Klasse durch die Färbung der Etagen der Evolution Tower visualisiert.

41

Abbildung 35: Anwendung der Farbfunktion Farbbereiche, um durch Rotfärbung Systemelemente zu markieren, die ab einem bestimmten Zeitpunkt entstanden sind.


Eine andere Möglichkeit der Anwendung der beschriebenen Farbfunktion zeigt Abbildung 37. Um die unterschiedlichen Entstehungszeitpunkte der Systemelemente in der Visualisierung klar erkennbar voneinander zu trennen, kann die Erstellung der Elemente auch mit Hilfe der Farbfunktion Farbpalette auf die Färbung der Repräsentanten abgebildet werden. So ist der Abbildung 37 beispielsweise eindeutig zu entnehmen, dass nur zwei in der letzten Version noch existierende Klassen, die als dunkelblaue Gebäude visualisiert sind, in den Versionen 1 und 2 entstanden sind. Im Gegensatz dazu lässt sich der Entstehungszeitpunkt in den Abbildungen 32 und 39, in denen die Erstellung der Elemente durch die Farbfunkion Farbübergang bzw. durch die HSB-Farbfunktion abgebildet ist, ungenauer aber intuitiver und somit schneller ablesen.Eine weitere Anwendungsmöglichkeit für die Farbfunktion Farbpalette ist die Verdeutlichung der Hierarchie z.B. der Level 2-Knoten durch Einfärben des Straßensystems. Alle Repräsentanten einer Schachtelungstiefe sind einheitlich in einer Farbe visualisiert, die sich von der Färbung der vorigen bzw. nächsten Schachtelungstiefe abgrenzt. In Abbildung 38 ist die Package-Hierarchie eines Softwaresystems durch Abbilden der Schachtelungstiefe auf die Farben der Straßen in der Stadt-Visualisierung verdeutlicht. Es ist beispielsweise schnell 42

Abbildung 36: Anwendung der Farbfunktion Farbpalette um die Werte der Klassenmetrik Anzahl von Methoden und Attributen zu gruppieren und schnell erfassbar zu visualisieren.


erkennbar, dass die maximale Schachtelungstiefe im zweiten Subsystem deutlich höher ist als im ersten.

Visualisierungen können außerdem mit Hilfe der Farbfunktion Farbpalette Systemelemente unterschiedlich einfärben, um anzuzeigen, welche Entwickler für die Erstellung oder Änderung eines Systemelements verantwortlich sind. Hierfür stehen zum jetzigen Zeitpunkt jedoch notwendige Informationen im Systemgraphen noch nicht zur Verfügung.HSB-Farbfunktion (HSB Color Function): Die HSB-Farbfunktion bildet drei Attribute eines Systemelements auf die Farbe eines Bereiches des Repräsentanten ab, wobei die Funktion die

43

Abbildung 37: Anwendung der Farbfunktion Farbpalette um unterschiedliche Entstehungszeitpunkte klar erkennbar voneinander zu trennen.

Abbildung 38: Anwendung der Farbfunktion Farbpalette zum Hervorheben der Schachtelungstiefe der Packages eines Softwaresystems.


Farbe zuerst im HSB-Farbraum definiert und dann in Koordinaten innerhalb des RGB-Farbraums umrechnet. Der Farbvektor im HSB-Farbraum setzt sich dabei jeweils aus einer linearen Kombination der Werte der Knotenattribute a1 , a 2 und a 3 mit den als Parametern festgelegten Faktoren f 1 , f 2 , f 3 und den Konstanten c 1 , c2 und c3 zusammen. Die erste Komponente der Farbe beschreibt dabei den Farbton (hue) der Farbe, die zweite die Sättigung (saturation) und die dritte die absoluten Helligkeit (brightness). Eine formale Definition der Berechnung der HSB-Komponenten ist in Gleichung 13 angegeben. Ein Algorithmus zur Umrechnung eines Farbvektors vom ähnlich definierten HSI-Farbraum in den RGB-Farbraum ist u.a. in [GW07] beschrieben. In der Programmiersprache Java stellt die Klasse java.awt.Color mit der Methode getHSBColor() eine solche Umrechnungsfunktion bereits zur Verfügung.

cHSB a1 , a 2 , a3=a1⋅f 1c2

a2⋅f 2c2

a3⋅ f 3c3 (13)

Eine Anwendung der HSB-Farbfunktion stellt die Heat Map-Visualisierung dar, bei der für jedes Systemelement das Alter auf den Farbton der Repräsentantenfarbe abgebildet wird. Für zuletzt entstandene Elemente bestimmt die Farbfunktion dabei mit einem satten Rot eine sehr warme Farbe. Mit zunehmendem Alter weist sie den Elementen über orange, gelb, grün, cyan und 44

Abbildung 39: Die Heat Map-Visualisierung ist ein Anwendungsbeispiel für die HSB-Farbfunktion, die das Alter der Systemelemente im Laufe der Entwicklung des Systems intuitiv erkennbar darstellt.


dunkelblau immer kältere Farben zu und beschreibt somit eine intuitive Visualisierung des Alters der Systemelemente durch die Verknüpfung der Farbe mit einer Temperatur. Neue Elemente besitzen eine sehr hohe Temperatur und werden „heiß“ in das System eingefügt. Im Laufe der Entwicklung des Systems kühlen sie bis auf eine Minimaltemperatur ab. Abbildung 39 zeigt die Entwicklungsgeschichte des Softwaresystems EvoViewer als Heat Map-Visualisierung. In der oberen Darstellung a) ist die Systementwicklung bis zur letzten Revision 449 visualisiert. Die unteren Darstellungen b), c) und d) zeigen Stadt-Visualisierungen für verschiedene Endversionen des Systems, wie sie bei einem entwicklungsbegleitenden Einsatz des entwickelten Prototypen Evolution Viewer generiert werden würden. Das „Abkühlen“ der Elemente, die bereits in der Darstellung b) existieren, ist in den nachfolgenden Visuali-sierungen c), d) und a) gut zu erkennen.Eine weiter mögliche Anwendung der HSB-Farbfunktion ist die Abbildung eines Clusterings auf die Färbung der Repräsentanten der Systemelemente. Die Werkzeugumgebung Crococosmo, in die der entwickelte Prototyp Evolution Viewer integriert ist, stellt einige Clustering-Funktionalitäten zur Verfügung, die den Systemelementen verschiedene Cluster-Klassen zuweisen. Jede Cluster-Klasse wird dabei durch eine rationale Zahl aus dem Intervall [0,1] dargestellt. Durch ein Knotenattribut ist den Systemelementen ihr Cluster zugeordnet. Dieses Cluster-Attribut lässt sich mit der HSB-Farbfunktion auf den Farbton der Farbe der Elementrepräsentanten abbilden. Abbildung 40 zeigt eine Visualisierung, bei der die Systemelemente entsprechend ihrer Subsytem-Zugehörigkeit einem Cluster zugeordnet sind. Die Repräsentanten der Systemelemente eines Subsystems sind einheitlich in einer Farbe visualisiert. Hierdurch kann die Größe und Struktur der Subsysteme besonders schnell erfasst werden. Außerdem wirkt sich eine Einfärbung der Subsysteme positiv auf die wahrgenommene Stabilität der Visualisierung aus, da Verschiebungen und Verdrehungen ganzer Subsysteme, wie es bei der Repräsentation des Level 1-Knotens als zentralen Platz häufig vorkommt, besser nachvollziehbar sind.

45

Abbildung 40: Anwendung der HSB-Farbfunktion um die Repräsentanten der Systemelemente entsprechend ihrer Subsystem-Zugehörigkeit einzufärben.


4.7.2 Float-FunktionenFloat-Funktionen bilden Attribute der Systemelemente auf rationale Zahlen ab und ermöglichen so eine Abbildung der Attributwerte auf die Ausdehnungen der Repräsentanten in den Stadt-Visualisierungen. Wie auch die Farbfunktionen bekommt jede Float-Funktion f : P×Aℝ als Eingabe eine Menge von Parametern P={p1 , , pn}, mit n=∣P∣, pi∈ℝ und eine Menge von Attributwerten A={a1 , , am}, mit m=∣A∣, ai∈ℝ . Als Ausgabe liefert sie einen rationalen Wert zurück: . Drei einfache und allgemein anwendbare Float-Funktionen sind im

Evolution Viewer umgesetzt.Konstante Float-Funktion (Constant Foat Function): Die konstante Funktion liefert stets einen als Parameter definierten Wert zurück. Sie kann z.B. dazu verwendet werden, der Breite und Tiefe aller Gebäudequader einen festen Wert zuzuweisen, wie es in Abbildung 33 der Fall ist.Lineare Float-Funktion (Linear Float Function): Die lineare Float-Funktion kombiniert den Wert eines Attributes a mit einem als Parameter definierten Faktor p1 und einer Konstanten p2 : f LFF=a⋅p1 p2 . Anwendung findet die Funktion z.B. um die Anzahl der Methoden und Attribute auf die Ausdehnung der Gebäudequader abzubilden. Die Abbildungen 32, 35, 36, 37, 39 und 40 zeigen dieses Anwendungsbeispiel.

Beschränkte lineare Float-Funktion (Limits Linear Float Function): Die beschränkte lineare Float-Funktion erweitert die lineare Float-Funktion um eine obere und untere Schranke S o , S u , die das berechnete Ergebnis begrenzen. Formal ist die Funktion in Gleichung 14 definiert.

f LLFF={ S o , falls a⋅p1 p2S o

S u , falls a⋅p1 p2S u

a⋅p1 p2 , sonst. (14)

Ein Beispiel einer Anwendung dieser Float-Funktion ist die Abbildung der Schachtelungstiefe der Level 2-Knoten auf die Breite der Repräsentanten, den Straßen. Straßen, die sich in der Hierarchie oben befinden werden breiter visualisiert als weit verschachtelte Straßen, wobei ab einer maximalen Schachtelungstiefe alle Straßen mit einer minimalen Breite dargestellt werden. Besonders gut zu erkennen sind die verschiedenen Straßenbreiten in Abbildung 38.

46

5 EVALUIERUNG

5 Evaluierung

Nachdem im vorigen Kapitel ein Layout vorgestellt wurde, welches eine veränderliche Baumstruktur als dreidimensionale Stadtszene visualisiert, soll dieses Kapitel das entwickelte Layout untersuchen und Methoden erarbeiten, um das Ergebnis der Arbeit objektiv bezüglich der in Kapitel 3.2 definierten Anforderungen zu bewerten.5.1 Bewertung der Stabilität

5.1.1 StabilitätsmaßeAusgehend von den in Kapitel 4.1.1 eingeführten Definitionen für die Transformations- und Ordnungsstabilität stellt der folgende Abschnitt verschiedene Maße zur Bestimmung des Grades der Stabilität vor. Hierbei bilden alle beschriebenen Maße den Grad der Änderung zweier Layouts bzw. den Grad der Nichteinhaltung der Stabilitätsdefinitionen ab.5.1.1.1 TransformationsstabilitätUm die zu untersuchende Informationsmenge zu begrenzen, wird ein vereinfachtes Modell der dargestellten Szene verwendet, welches jeden Repräsentanten durch seinen auf die XZ-Ebene projizierten Mittelpunkt erfasst. Die räumliche Ausdehnung der Repräsentanten kann dabei vernachlässigt werden, da sich der Stabilitätsbegriff nicht auf einzelne Objekte, sondern auf die Anordnung aller Objekte bezieht. Die Projektion der Repräsentanten auf die Ebene ist ohne Einschränkungen möglich, da die generierte Szene auf einem zweidimensionalen Layoutverfahren basiert und alle Szenenobjekte überschneidungsfrei auf die Ebene projiziert werden können. Alle vorgestellten Maße beziehen sich auf dieses Modell und messen die Transformationsstabilität durch Bestimmung der Änderungen von je zwei Versionen der selben Punktmenge im zweidimensionalen Raum.Durchschnittliche absolute Positionsänderung (APCAVG): Ein einfaches Maß zur Bestimmung der Layout-Änderung beschreibt die durchschnittliche absolute Positionsänderung (Average of Absolute Position Changes - APCAVG). Sie summiert die vorzeichenlosen Änderungen der X- und Y-Komponente der Positionen aller Punkte auf und teilt die Summe durch die Anzahl der Punkte. Gleichung (15) zeigt die formale Definition der APCAVG-Metrik. Die Variable P i beschreibt dabei die Positionierung eines Punktes in der Anfangsversion und P i die Position des selben Punktes in der Endversion.

APC AVG=∑i=1

N

∣P i x− P i x∣∣Pi y

− P i y∣N

(15)Zur Bestimmung der Transformationsstabilität ist die APCAVG-Metrik wenig geeignet, da sie keine Toleranz gegenüber Verschiebung, Drehung und Skalierung der Punktmenge aufweist, d.h. es wird z.B. eine einheitliche Verschiebung aller Punkte gleich stark gewichtet wie eine in der Summe gleiche zufällige Positionsänderung aller Punkte.Durchschnittliche relative Positionsänderung (RPCAVG): Ein anderes Maß, die

47

KAPITEL 5. EVALUIERUNG

durchschnittliche relative Positionsänderung (Average of Relative Position Changes - RPCAVG), bestimmt die Summe der komponentenweisen, vorzeichenlosen Änderung der Lagebeziehungen zweier verschiedener Punkte relativ zueinander und teilt diese durch die Anzahl möglicher Punktpaare. Mit anderen Worten, je zwei verschiedene Punkte definieren einen Vektor, der die Lagebeziehung der beiden Punkte zueinander darstellt. Die durchschnittliche vorzeichenlose Änderung der X- und Y-Komponente aller Lage-Vektoren in zwei verschiedenen Versionen entspricht der Metrik RPCAVG. Gleichung (16) definiert die RPCAVG-Metrik formal.

RPC AVG=∑i=1

N−1

∑j=i1

N

∣P j x−P i x− P j x

− P i x∣∣ P j y−P i y− P j y

− P i y∣⋅2N⋅N−1

(16)Gegenüber der durchschnittlichen absoluten Positionsänderung (APCAVG) besitzt die RPCAVG-Metrik die Eigenschaft, eine Punktmenge, die sich in zwei Versionen nur durch Verschiebung unterscheidet, mit einem Metrikwert von 0 als sehr ähnlich und somit auch stabil zu bewerten. Eine Drehung oder Skalierung der Punkte wird nahezu gleich stark bestraft, wie durch die APCAVG-Metrik.

Ein anderes Problem der RPCAVG-Metrik als Stabilitätsmaß ist in Abbildung 41 sichtbar gemacht. Für eine gegebene Anfangsversion von drei Punkten im oberen Bereich sind darunter zwei mögliche Varianten einer Anordnungsänderung dargestellt. In der linken Variante A tauschen die Punkte P1 und P2 die Positionen und verändern die Anordnung aller Punkte zueinander erheblich. Ein Layout mit solch starken Änderungen wird als instabil wahrgenommen. In der rechten Variante B verschiebt sich der Punkt P2 acht Einheiten nach rechts. Hierdurch verzerrt sich das Gesamtbild. Die grundsätzliche Anordnung der Punkte zueinander bleibt jedoch erhalten. Der Punkt P2 ist sowohl in der Anfangsversion als auch in der Endversion rechts von den anderen Punkten angeordnet, wodurch das Layout 48

Abbildung 41: Unterschiedlich starke Anordnungsänderungen bei gleichem RPCAVG-Wert.

5.1 BEWERTUNG DER STABILITÄT

weitestgehend stabil bleibt. Trotz der gezeigten unterschiedlichen Änderungsintensitäten beider Varianten liefert die RPCAVG-Metrik in beiden Fällen den Wert 5,333 und lässt somit eine ähnlich starke Änderung vermuten.Durchschnittliche normalisierte relative Positionsänderung (NRPCAVG): Durch eine Normalisierung aller X- und Y-Abstände zweier Punkte in der RPCAVG-Metrik ergibt sich die durchschnittliche normalisierte relative Positionsänderung (Average of Normalized Relative Position Changes - NRPCAVG). Jeder Abstand eines Punktpaares in X- und Y-Richtung wird dabei durch den durchschnittlichen absoluten X- bzw. Y-Abstand aller Punktpaare der jeweiligen Version geteilt. Das arithmetische Mittel aller normalisierten Abstände ist somit 1. Die formalen Definitionen der Abstandsdurchschnitte sind durch die Gleichungen (17) bis (20) gegen. Die Variable RPXAVG beschreibt dabei den durchschnittlichen absoluten Abstand inX-Richtung aller Punktpaare in der Anfangsversion, die Variable RPXAVG den durchschnittlichen absoluten Abstand in X-Richtung der Endversion. Die Variablen RPYAVG und RPYAVG definieren den durchschnittlichen absoluten Abstand der Punktpaare in Y-Richtung in der Anfangs- bzw. Endversion.

RPX AVG=∑i=1

N−1

∑j=i1

N

∣P j x−P i x∣⋅2

N⋅N−1

(17)RPX AVG=

∑i=1

N−1

∑j=i1

N

∣ P j x− P i x∣⋅2

N⋅N−1

(18)RPY AVG=

∑i=1

N−1

∑j=i1

N

∣P j y−P i y∣⋅2

N⋅N−1

(19)RPY AVG=

∑i=1

N−1

∑j=i1

N

∣ P j y− P i y∣⋅2

N⋅N−1

(20)Durch die Gleichung (21) ist eine Formalisierung der NRPCAVG-Metrik angegeben.

NRPC AVG=∑i=1

N−1

∑j= i1

N ∣P j x−P i x

RPX AVG− P j x

− P i x RPX AVG

∣∣P j y−P i y

RPY AVG− P j y

− P i y RPY AVG

∣⋅2

N⋅N−1

(21)Eine Punktmenge, die sich in zwei Versionen durch Verschiebung und beliebige Skalierung unterscheidet, wird durch die NRPCAVG-Metrik mit einem Metrikwert von 0 als sehr ähnlich gemessen. Transformationen wie z.B. Drehung, Spiegelung, Scherung oder auch beliebige Positionsänderungen der Punkte erhöhen dagegen den NRPCAVG-Wert. Für die in Abbildung 41 angegebenen unterschiedlichen Anordnungsänderungen liefert eine Messung mit der NRPCAVG-Metrik Werte mit stärkerer Aussagekraft als die RPCAVG-Metrik. Für die Änderungsvariante A misst sie den Wert 2,666 und für die Variante B den Wert 0,484. Die unterschiedlichen Änderungsintensitäten des Beispiels sind mit der NRPCAVG-Metrik gut messbar. Da die Definition der Transformationsstabilität zusätzlich zur Verschiebung und Skalierung die Drehung als tolerante Transformation einschließt, ist es nicht möglich, den Grad der Transformationsstabilität mit Hilfe des Metrik NRPCAVG zuverlässig zu messen.Durchschnittliche Entfernungsänderung (DCAVG): Eine Möglichkeit um eine gedrehte Punktmenge als ähnlich zu messen, ist die Betrachtung des euklidischen Abstands aller Punktpaare, anstatt, wie durch die bereits beschriebenen Maße, die Abstände komponentenweise zu betrachten. Die durchschnittliche Entfernungsänderung (Average of Distance Changes - DCAVG) summiert die Abstandsänderungen aller Punktpaare vorzeichenlos auf und teilt die Summe durch die Anzahl möglicher Paare verschiedenen Punkte. Formal definiert ist die DCAVG-Metrik in Gleichung (22).

49


DC AVG=∑i=1

N−1

∑j=i1

N

∣ ∣∣P i− P j∣∣−∣∣P i− P j∣∣ ∣⋅2

N⋅N−1

(22)Die Metrik besitzt die Eigenschaft, dass sie die Änderung eine Punktemenge mit einem Wert von 0 als sehr gering misst, falls sich die Punktanordnungen nur durch Verschiebung und Drehung unterscheiden. Sie ist damit tolerant gegenüber den Transformationen Verschiebung und Drehung. Als Maß für die Transformationsstabilität ist die DCAVG-Metrik jedoch nur mit Einschränkungen verwendbar, da eine Skalierung der Anordnung als starke Änderung gewichtet wird. Ein weiteres Problem ist die Toleranz der Metrik gegenüber Spiegelungen. Obwohl ein Layout, welches Objektanordnungen spiegelt, als instabil wahrnehmbar ist, erfasst die DCAVG-Metrik eine Spiegelung der Punkte als geringstmögliche Änderung. Durchschnittliche normalisierte Entfernungsänderung (NDCAVG): Ähnlich der Erweiterung der RPCAVG-Metrik zur NRPCAVG-Metrik kann auch die DCAVG-Metrik durch eine Normalisierung der Entfernungen angepasst werden. Die durchschnittliche normalisierte Entfernungsänderung (Average of Normalized Distance Changes - NDCAVG) normalisiert die betrachteten Entfernungen aller Punktpaare, indem sie jede Entfernung durch die durchschnittliche Entfernung zweier Punkte der Start- bzw. Endversion teilt. Gleichung (23) definiert die durchschnittliche Entfernung der Punktpaare in der Startversion als DAVG . Die Variable DAVG in Gleichung (24) beschreibt die durchschnittliche Entfernung zweier Punkte in der Endversion.

D AVG=∑i=1

N−1

∑j= i1

N

∣∣P i− P j∣∣⋅2N⋅N−1

(23)D AVG=

∑i=1

N−1

∑j= i1

N

∣∣Pi− P j∣∣⋅2N⋅N−1

(24)Gleichung (25) definiert die NDCAVG-Metrik formal.

NDC AVG=∑i=1

N−1

∑j=i1

N ∣ ∣∣P i− P j∣∣D AVG

−∣∣P i− P j∣∣

D AVG∣⋅2

N⋅N−1

(25)Eine Verschiebung, Drehung oder Skalierung der Punktmenge bewertet die NDCAVG-Metrik mit einem Messwert von 0 als sehr geringe Änderung. Die Metrik ist tolerant gegenüber beliebiger Verschiebung, beliebiger Drehung und Proportionen-erhaltender Skalierung der Punkt-anordung, wodurch sie als Maß für den Grad der Transformationsstabilität in der Regel gut geeignet ist. Gegenüber der NRPCAVG-Metrik besitzt die NDCAVG-Metrik jedoch den Nachteil, dass sie Spiegelungen toleriert und eine ungleichmäßige Skalierung als starke Änderung wertet. Falls die Drehung der Punkte vernachlässigbar klein ist, kann daher die NRPCAVG-Metrik besser zum Abbilden der Transformationsstabilität geeignet sein. Validierung der Metriken: Anhand der Opensource-Software JUnit soll im folgenden Abschnitt die Verwendbarkeit der Metriken nachgewiesen werden. Abbildung 44 zeigt in 18 Darstellungen wichtige Meilensteine der Software JUnit von der Version 2.0.0 bis zur Version 4.6.0, wie sie mit dem erarbeiteten Werkzeug EvolutionCity innerhalb eines Software-Entwicklungprozesses generiert werden würden. Jede einzelne Darstellung bildet dabei die strukturelle Entwicklungsgeschichte des Systems von der Initialversion bis zur angegebenen Endversion ab. 50


Bei einem Vergleich der Darstellungen in der Abbildung fallen drei Paare aufeinanderfolgender Darstellungen auf, die instabiler sind als die übrigen. Von der Darstellung 4 zur Darstellung 5 schrumpft das repräsentierende Gebäude der Klasse TestRunner deutlich, was zu einem Heranrücken der benachbarten Gebäude und Straßen führt. Durch die starke Verkleinerung geht das Gebäudeobjekt außerdem als Orientierungspunkt in der Visualisierung verloren, was die Layouts der beiden Darstellungen zusätzlich instabil wirken lässt. In den Paaren der Darstellungen (15,16) und (16,17) führen die neu erstellten Packages org.junit.matchers, org.junit.runners.model, org.junit.internal.runners.model und org.junit.internal.statements, welche zwischen vorhandene Objekte positioniert werden, zu einem Auseinanderschieben der Anordnung und somit zu einer erhöhten Instabilität der Layouts.Für das gezeigte Beispiel fasst Abbildung 42 die Metrikwerte der Stabilitätsmaße APCAVG, RPCAVG und DCAVG von Paaren aufeinanderfolgender Darstellungen zusammen. Dabei berechnet die APCAVG-Metrik, die als blaue Kurve dargestellt ist, im Vergleich zu den anderen beiden Metriken für die Darstellungspaare (2,3), (8,9), (10,11) und (11,12) sehr große Werte und markiert sie somit als instabil. Diese Werte stehen im Widerspruch zu den wahrnehmbaren Änderungen. Speziell für die Darstellungen 10 und 11 ist eine Änderung des Layouts kaum erkennbar. Die, durch die orange und gelbe Kurve abgebildeten Messwerte der RPCAVG- und DCAVG-Metrik korrelieren sehr stark und bemessen beide die Darstellungspaare (16,17) und (4,5) als besonders instabil. Diese Bewertungen entsprechen den zuvor beschriebenen wahrnehmbaren Stabilitäten der Darstellungen.

51

Abbildung 42: Stabilitätsmaße APCAVG, RPCAVG und DCAVG für Paare von 18 Visualisierung der Software JUnit von Version 2.0.0 bis Version 4.6.0.(1,2)

(2,3)(3,4)

(4,5)(5,6)

(6,7)(7,8)

(8,9)(9,10)

(10,11)(11,12)

(12,13)(13,14)

(14,15)(15,16)

(16,17)(17,18)

0

1

2

3

4

5

6

7

APC_AVGRPC_AVGDC_AVG

Abbildung 43: Stabilitätsmaße NRPCAVG und NDCAVG für Paare von 18 Visualisierung der Software JUnit von Version 2.0.0 bis Version 4.6.0.(1,2)

(2,3)(3,4)

(4,5)(5,6)

(6,7)(7,8)

(8,9)(9,10)

(10,11)(11,12)

(12,13)(13,14)

(14,15)(15,16)

(16,17)(17,18)

0

0,02

0,04

0,06

0,08

0,1

0,12

0,14

0,16

NRPC_AVGNDC_AVG


52

Abbildung 44: Stadtvisualisierungen der Entwicklungsgeschichte des Softwaresystems JUnit von Version 2.0.0 bis zur Version 3.8.0.


53

Abbildung 45: Stadtvisualisierungen der Entwicklungsgeschichte des Softwaresystems JUnit von Version 3.8.1 bis zur Version 4.6.0.


Abbildung 43 stellt die Layout-Änderungen der 17 Darstellungspaare durch die NRPCAVG– und NDCAVG-Metrik dar. Die Werte beider Metriken zeigen gleiche Ausprägungen und messen für die Paare (4,5), (16,17) und (15,16) die größten Layout-Abweichungen. Diese Messergebnisse spiegeln somit den wahrnehmbaren Stabilitätsgrad der drei Paare exakt wieder. Dagegen messen die Metriken für die Darstellungspaare (1,2), (2,3) und (8,9) Änderungen, die in den Darstellungen kaum wahrnehmbar sind.Am Beispiel des Softwaresystems JUnit konnte gezeigt werden, dass die vier Metriken RPCAVG, DCAVG, NRPCAVG und NDCAVG stark korrelieren und große Abweichungen zweier Layouts zuverlässig messen. Layouts, die sich durch kleinen Änderungen unterscheiden, werden dagegen in einigen Fällen als zu instabil bewertet. Durch die hohe Sensibilität können die Metriken aber auch kaum sichtbare Instabilitäten aufzeigen. Für das untersuchte Beispiel konnte die NDCAVG-Metrik die Layout-Stabilitäten der Darstellungspaare am besten abbilden.5.1.1.2 OrdnungsstabilitätNach der in Kapitel 4.1.1 angegebenen Definition beschreibt die Ordnungsstabilität für eine Baumstruktur den Grad der Ordnungserhaltung von Kindknoten in Bezug auf ihre Elternknoten. Der folgende Abschnitt definiert zunächst eine Ordnungsrelation basierend auf der Positionierung von Layout-Objekten und beschreibt weiter eine Metrik zum Messen der Unterschiede zweier Ordnungen über der selben Menge. Durch die Bestimmung der Ordnungsrelationen für die Layouts zweier Versionen eines Systems kann eine Metrik konstruiert werden, die den Grad der Ordnungsstabilität misst.Da für die Bestimmung der Ordnungsrelation die Ausdehnung und Position der Repräsentanten in der Höhe bzw. in Richtung der Y-Achse keine Rolle spielt, ist es im Weiteren ausreichend, eine Projektion der Layout-Objekte auf die XZ-Ebene zu betrachten. Jeder Knoten-Repräsentant besitzt im Layout einen Ursprungspunkt und eine Ausrichtung. Somit lässt sich für jeden Repräsentanten ein lokales kartesisches Koordinatensystem konstruieren, in dem die Positionen der anderen Objekte relativ zu seinem eigenen Ursprung und seiner Ausrichtung angegeben sind. Die Funktionen x :V ℝ und y :Vℝ beschreiben für einen Knoten die X- bzw. Y-Koordinaten des Ursprungspunktes seines Repräsentanten im lokalen Koordinatensystem des Elternknotens. Für den Wurzel-knoten sind die Funktionen x und y undefiniert. Abbildung 46 veranschaulicht im oberen Teil die Funktionen für zwei als Straßen visualisierte Kindknoten v und w des Elternknotens u . Im unteren Teil sind die Funktionen x und y für zwei als Gebäude repräsentierte Knoten dargestellt.Mit Hilfe der Abstandsfunktionen x und y lässt sich über der Menge V u=CHILDREN u , mit u∈V , der Menge aller Kinder eines Knotens u , eine Ordnungsrelation R , u⊆V u×V u definiert durch:

v , w∈R , u⇔ x v x w ∨ x v=x w ∧ y v≤ y w , mit v , w∈V u. (26)

54

Abbildung 46: Die Funktionen x und y bestimmen die Posi-tionen der Layout-Objekte relativ zum übergeordneten Layout-Ob-jekt.


Die Ordnung R , u zählt alle Kinder von u nach der Entfernung ihrer Repräsentanten zum Ursprung des Repräsentanten von u auf. Sind zwei Kind-Repräsentationen gleich weit vom Ursprung entfernt, wird der rechte zuerst aufgezählt.Um den Grad der Abweichung zweier Ordnungsrelationen über der selben Menge zu bestimmen, können durch paarweises Aufsummieren einer Vergleichsfunktion unterschied-liche Relationsbeziehungen gezählt werden. Für zwei Ordnungsrelationen Q und R auf der selben Menge M sei die Funktion Q ,R: M×M {0,1 } definiert durch:Q ,Ra ,b ={1 , falls a ,b ∈Q∧a , b ∉R ∨a ,b∉Q∧a ,b ∈R

0 , sonst , mit a , b∈M . (27)

Die Funktion Q , R summiert für alle Paare der Menge M die Werte der Vergleichsfunktion R , R auf. Sie ist definiert durch:

Q , R=∑i=1

N

∑j=1

N

Q , Rv i , v j , mit v i , v j∈M , N=∣M∣ . (28)Mit Hilfe der Funktion Q , R lässt sich die Anzahl unterschiedlicher Relationsbeziehungen zweier Ordnungsrelationen Q und R bestimmen.Anzahl unterschiedlicher Entfernungsbeziehungen (DORCSUM): Für einen Knoten u sind für zwei Layouts unterschiedlicher Baumversionen die Ordungsrelationen R , u und R , u seiner Kind-Knoten gegeben. Die Ordnungen sind durch die, in Gleichung 26 angegebene, Definition bestimmt und zählen in beiden Layouts die Kinder nach der Entfernung ihrer Repräsentanten zum Ursprung des Repräsentanten von u auf. Die Unterschiede der beiden Ordnungen R , u und R , u lassen sich durch die -Funktion bestimmen und sind als Metrik Anzahl unterschiedlicher Entfernungsbeziehungen von Kindknoten (Distance Order Relation Changes of Cildren - DORCC) in Gleichung 29 definiert.

DORCC u =R ,u , R , u, mit u∈V (29)

Durch Aufsummieren der DORCC-Werte aller Knoten eines Baumes kann der Grad der Ordnungsstabilität gemessen werden. Formal ist die Metrik Anzahl unterschiedlicher Entfernungsbeziehungen (Distance Order Relation Changes – DORCSUM) zweier Baum-Layouts in der Gleichung 30 angegeben.

DORC SUM=∑k=1

M

DORCC u k , mit uk∈V (30)Da sich die Ordnungsrelation R , u der Kinder eines Knotens u , der das Levelattribut L3 besitzt und als Gebäude dargestellt wird, nicht ändert, liefert die Funktion DORCC u stets den Wert 0 zurück. Es wäre daher für die Bestimmung der DORCSUM-Metrik ausreichend, ausschließlich die Summe der DORCC-Metrikwerte für Knoten, die mit dem Level L1 oder L2 attributiert sind, zu betrachten.Validierung der Metrik: Am bekannten Beispiel der Entwicklung des Softwaresystems JUnit soll die Verwendbarkeit der DORCSUM-Metrik nachgewiesen werden. In den Abbildungen 44 und

55


45 ist das System in 18 Stadtvisualisierungen für unterschiedliche Versionen dargestellt. Die größten Layout-Instabilitäten zwischen zwei Visualisierungen aufeinanderfolgender Versionen sind darin für die Darstellungspaare (4,5), (15,16) und (16,17) wahrnehmbar. Abbildung 47 visualisiert die Werte der DORCSUM-Metrik für Layouts zweier aufeinander-folgender Versionen des Softwaresystems JUnit. Die größte Layout-Änderung bezüglich der Ordnungsstabilität misst die DORCSUM-Metrik mit einem Wert von 12 für das Darstellungspaar (4,5). Dies entspricht der hohen wahrnehmbaren Instabilität der beiden Darstellungen. Weitere Layout-Änderungen werden für die Darstellungspaare (1,2), (2,3) und (16,17) ge-messen, wobei die Instabilität der ersten beiden Paare in den Visualisierungen nicht in der Stärke erkennbar ist.

Bei einem Vergleich der in Abbildung 43 dargestellten Stabilitätsmaße NRPCAVG und NDCAVG und dem Stabilitätsmaß DORCSUM lassen sich in den Kurven ähnliche Minimal- und Maximalstellen ausmachen. Die Metriken korrelieren daher relativ stark, obwohl ihre Berechnung auf zwei unterschiedlichen Ansätzen beruht. Es kann deshalb im Weiteren davon ausgegangen werden, dass die drei Metriken NRPCAVG, NDCAVG und DORCSUM gut geeignet sind, um die Stabilität zweier Layouts verschiedener Systemversionen zu messen.5.1.2 Abhängigkeiten der StabilitätViele Parameter des Layout-Algorithmus können sich positiv oder negativ auf die Stabilität der Stadt-Visualisierungen auswirken. Dazu gehören genau die Parameter, welche die Position der Knotenrepräsentanten in einem auf die Ebene projizierten Layout verändern. Zwei Parameter, die diese Positionen besonders stark ändern und somit auch einen großen Einfluss auf die Stabilität haben, stellt der Winkel, in dem untergeordnete Straßen ab der zweiten Hierarchieebene von übergeordneten Straßen abzweigen (Straßenwinkel), sowie die Repräsentation des Level 1-Knotens dar. Ihre Auswirkungen auf die Stabilität sollen im Weiteren genauer untersucht werden. Der Begriff der Stabilität und auch die Stabilitätsmaße sind durch den Vergleich zweier Stadt-Layouts definiert, die die Systementwicklung für zwei unterschiedlichen Endversionen darstellen. Da die Qualität der Stabilität für Paare aufeinanderfolgender Versionen für eine praktische Anwendung des Layout-Algorithmus besonders wichtig ist, sollen sich die Abhängigkeitsuntersuchungen der Stabilität auf aufeinanderfolgende Versionspaare beschränken.56

Abbildung 47: Stabilitätsmaß DORCSUM für Paare von 18 Visualisierung der Software JUnit von Version 2.0.0 bis Version 4.6.0.(1,2)

(2,3)(3,4)

(4,5)(5,6)

(6,7)(7,8)

(8,9)(9,10)

(10,11)(11,12)

(12,13)(13,14)

(14,15)(15,16)

(16,17)(17,18)

0

2

4

6

8

10

12

14

DORC


5.1.2.1 Abhängigkeit von der Repräsentation des Level 1-KnotensDer Level 1-Knoten kann als Autobahn oder als zentraler Platz in den Stadtvisualisierungen dargestellt werden. Bei der Darstellung als Autobahn zweigen die Repräsentationen untergeordneter Teilbäumen im rechten Winkel von verschiedenen Seiten der Autobahn ab. Kommen im Laufe der Systementwicklung neue Untersysteme hinzu, kann die Autobahn in genau eine Richtung weitergeführt werden, um Anschlusspunkte für die Repräsentationen der neuen Untersysteme bereitzustellen. Bei der Darstellung des Level 1-Knotens als zentralen Platz ordnen sich die Repräsentanten sternförmig um einen runden Platz herum an. Falls im Verlauf der Systemevolution neue Subsysteme entstehen, schieben sich alle vorhandenen Subsystem-Repräsentationen zusammen und gegebenenfalls auch nach außen, um Platz für die Repräsentation der neuen Subsysteme zu schaffen.Um die Abhängigkeit der beiden möglichen Repräsentationen des Level 1-Knotens auf die Stabilität des Layouts zu untersuchen, werden nur die NDCAVG-Mertikwerte für Paare aufeinanderfolgender Versionen für die Repräsentation des Level 1-Knotens als Autobahn und für die Repräsentation als zentralen Platz gemessen und verglichen. Die Metrik NRPCAVG stellt für die Untersuchungen kein geeignetes Stabilitätsmaß dar, da die Metrik nicht rotationsinvariant ist. Für den Fall, dass der Level 1-Knoten als Platz repräsentiert ist und neu entstandene Subsysteme die alten zusammenschieben (was einer Rotation der Subsysteme um den Mittelpunkt des Platzes entspricht), berechnet die NRPCAVG-Metrik im Gegensatz zur NDCAVG-Metrik wesentlich höhere Werte, die den wahrgenommenen Ähnlichkeiten der Visuali-sierungen nicht mehr entsprechen. Auch die DORCSUM-Metrik ist für die Untersuchungen ungeeignet, da sich alle Repräsentanten innerhalb der Teilsysteme jeweils relativ zu den übergeordneten Elementen gleich verschieben. Bei der Änderung der Repräsentation des Level 1-Knotens werden die Teilsysteme als Ganzes gedreht und verschoben. Die Positionen der Layout-Objekte eines einzelnen Teilsystems bleibt relativ zum Teilsystem gesehen erhalten. Somit bleibt die Ordnungsstabilität der Objekte gleich und die DORCSUM-Metrik berechnet unabhängig von der Repräsentation des Level 1-Knotens gleiche Werte.

Für die Untersuchungen der Abhängigkeit der Stabilität und Kompaktheit werden in dieser Arbeit die Softwaresysteme Analyz-E-Bay, JUnit, EvoViewer, Ant, JHotDraw und ArgoUML als Beispielsysteme verwendet. Es handelt sich bei ihnen um Java-Softwaresyteme, die sich in ihrer Große und Komplexität deutlich unterscheiden. Alle Systeme bilden die Package-Hierarchie auf Knoten mit dem Knotenlevel 2 und Klassen ohne ihre inneren oder anonymen Klassen auf Level 3-Knoten in der zu visualisierenden Baumstruktur ab, die als Eingabe für den Layout-Algorithmus dient. Abbildung 48 listet die Beispielsysteme mit der Anzahl der Versionen, zu denen Daten über die Systeme existieren, und mit der Anzahl der visualisierten Level 2- und Level 3-Knoten für die Darstellung der ersten Versionen (min.-Werte) sowie für die Visualisierung der Entwicklungsgeschichte von der ersten bis zur letzten Version (max.-Werte) auf. Da für das System Analyz-E-Bay nur Daten für drei Versionen vorhanden sind und die Stabilität durch den Vergleich von Layouts verschiedener Versionen definiert ist, ist das Beispielsystem für die Untersuchung der Abhängigkeit der Stabilität nicht geeignet.57

Abbildung 48: Auflistung von Größe und Versionsanzahl der untersuchten Beispielsysteme.

Softwaresystem Versionen visualisierte Knotenmin. Level 2 min. Level 3 min. gesamt max. Level 2 max. Level 3 max. gesamt

Analyz-E-Bay 3 10 74 84 11 95 106JUnit 18 9 38 47 46 216 262EvoViewer 24 4 7 11 34 271 305Ant 11 70 546 616 91 841 932JHotDraw 10 17 171 188 149 1731 1880ArgoUML 12 96 876 972 167 2808 2975


58

Abbildung 49: Vergleich der NDCAVG-Metrik verschiedener Versionspaare in Abhängigkeit der Repräsentation des Level 1-Knotens für das Softwaresystem JUnit.(1,2)

(2,3)(3,4)

(4,5)(5,6)

(6,7)(7,8)

(8,9)(9,10)

(10,11)(11,12)

(12,13)(13,14)

(14,15)(15,16)

(16,17)(17,18)

0

0,01

0,02

0,03

0,04

0,05

0,06

0,07

JUnit

L1 als Autobahn (NDC_AVG)L1 als zentraler Platz (NDC_AVG)

Versionspaare

Abbildung 50: Vergleich der NDCAVG-Metrik verschiedener Versionspaare in Abhängigkeit der Repräsentation des Level 1-Knotens für das Softwaresystem EvoViewer.(1,2)

(3,4)(5,6)

(7,8)(9,10)

(11,12)(13,14)

(15,16)(17,18)

(19,20)(21,22)

(23,24)0

0,02

0,04

0,06

0,08

0,1

0,12

0,14

EvoViewer


Versionspaare

Abbildung 51: Vergleich der NDCAVG-Metrik verschiedener Versionspaare in Abhängigkeit der Repräsentation des Level 1-Knotens für das Softwaresystem Ant.(1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8) (8,9) (9,10) (10,11)

0,000,010,020,030,040,050,060,070,080,09

Ant


Versionspaare


Die Messergebnisse der NDCAVG-Metrik für die Visualisierungen der Softwaresysteme JUnit, EvoViewer, Ant, JHotDraw und ArgoUML sind in den Abbildungen 49 bis 53 angegeben. Die Metrik misst den Durchschnitt der normalisierten Entfernungsänderung zweier Layout-Objekte von paarweise aufeinanderfolgenden Versionen. Der blaue Graph stellt dabei jeweils die Metrikwerte für Visualisierungen dar, in denen der Level 1-Knoten als Autobahn repräsentiert ist. Für die Repräsentation des Level 1-Knotens als zentralen Platz gibt die orange Kurve die NDCAVG-Metrikwerte an. Allgemein ist in den Abbildungen zu erkennen, dass die Repräsentation des Level 1-Knotens für die untersuchten Beispielsysteme keinen großen Einfluss auf die Stabilität hat. Für das System JUnit ist die Stabilität bei einer Repräsentation des Level 1-Knotens als Autobahn oder als zentralen Platz kaum verändert und im Mittel für alle aufeinanderfolgenden Versionspaare nahezu identisch (siehe Abbildung 49). Die Stabilität der Visualisierungen für die Softwaresysteme EvoViewer und Ant ist bei der Repräsentation des Level 1-Knotens als Autobahn durchschnittlich leicht erhöht, da die NDCAVG-Metrik hierfür leicht niedrigere Werte misst (siehe Abbildung 50, 51). Für Visualisierungen der Systeme JHotDraw und ArgoUML ist die Layout-Stabilität bei der Repräsentation des Level 1-Knotens als zentraler Platz leicht höher (siehe Abbildung 52, 53).59

Abbildung 52: Vergleich der NDCAVG-Metrik verschiedener Versionspaare in Abhängigkeit der Repräsentation des Level 1-Knotens für das Softwaresystem JHotDraw.(1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8) (8,9) (9,10)

00,02

0,040,060,08

0,10,12

0,140,16

JHotDraw


Versionspaare

Abbildung 53: Vergleich der NDCAVG-Metrik verschiedener Versionspaare in Abhängigkeit der Repräsentation des Level 1-Knotens für das Softwaresystem ArgoUML.(1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8) (8,9) (9,10) (10,11) (11,12)

0

0,01

0,020,03

0,04

0,050,06

0,070,08

ArgoUML


Versionspaare


Die Auswertungen der NDCAVG-Metrikwerte für die Beispielsysteme zeigen, dass die Stabilität in geringem Maße von der Repräsentation des Level 1-Knotens abhängig ist. Diese Abhängigkeit ist jedoch durch die spezielle Beschaffenheit des visualisierten Systems gegeben. Eine einfache und allgemein gültige Regel, welche Repräsentation des Level 1-Knotens zu einer höheren Stabilität führt, ist nicht erkennbar. Für den speziellen Fall, dass der Level 1-Knoten als Platz repräsentiert ist und zu wenigen existierenden großen Subsystemen neue Subsysteme hinzukommen, verschieben sich die bestehenden Subsysteme-Repräsentanten relativ stark und das Layout wird instabiler als bei der Repräsentation des Level 1-Knotens als Straße. Gemessen wurde dieser Stabilitätsunterschied in den Visualisierungen des Softwaresystems JHotDraw für das Versionspaar (5,6) (siehe Abbildung 52) und für das System ArgoUML für das Versionspaar (1,2) (siehe Abbildung 53). Die Visualisierungen des Beispielsystems JHotDraw für die Version 6.0.b1, die in den Diagrammen und Abbildungen mit dem Index 5 bezeichnet sind, und Visualisierungen für die Version 7.0.7 (Versionsindex 6) sind vergleichend in der Abbildung 54 für die Repräsentation des Level 1-Knotens als Autobahn und als zentralen Platz dargestellt.

60

Abbildung 54: Visualisierung der Software JHotDraw für die Version 5 (6.0.b1) und 6 (7.0.7) bei der Repräsentation des Level 1-Knotens als Autobahn und zentralen Platz.


5.1.2.2 Abhängigkeit vom StraßenwinkelIn den Stadt-Visualisierungen repräsentiert ein hierarchisches Straßennetz die Level 2-Knoten der zu visualisierenden Baumstruktur. Mit dem Straßenwinkel lässt sich im Layout einheitlich der Winkel einstellen, in dem Straßen ab der zweiten Hierarchieebene von übergeordneten Straßen abzweigen. Ist der Level 1-Knoten als Autobahn repräsentiert, zweigen alle Straßen der ersten Hierarchieebene unabhängig vom eingestellten Straßenwinkel im rechten Winkel von der Autobahn ab, bei einer Repräsentation des Level 1-Knotens als zentralen Platz gehen die Straßen der ersten Hierarchieebene strahlenförmig von Mittelpunkt des Platzes aus. Der Parameter Straßenwinkel kann Werte zwischen 0° und 90° (einschließlich 90°) annehmen.Um die Abhängigkeit der Stabilität vom Straßenwinkel zu bestimmen, werden die Maße für die Transfomationsstabilität NRPCAVG, NDCAVG und das Maß für die Ordnungsstabilität DORCSUM als Durchschnittswerte von allen aufeinanderfolgenden Versionspaaren für verschiedene Straßenwinkel untersucht. Für Visualisierungen der Softwaresysteme JUnit, EvoViewer, Ant, JHotDraw und ArgoUML sind die Durchschnittswerte (von aufeinanderfolgenden Versionspaaren) der NRPCAVG- und NDCAVG-Metrik bei einem Straßenwinkel von 5° bis 90° in 1°-Schritten in den Abbildungen 55, 57, 59, 61 und 63 als blaue und orange Kurve vergleichend dargestellt. Die Durchschnittswerte der DORCSUM-Metrik für Visualisierungen der fünf Beispielsysteme und einem Straßenwinkel von 5° bis 90° sind in den Abbildungen 56, 58, 60, 62 und 64 als grüne Kurve angegeben.Für alle untersuchten Beispielsysteme ändert sich der durchschnittliche Wert der NDCAVG-Metrik (orange Kurve) für verschiedene Straßenwinkel kaum. Die Abhängigkeit der Stabilitätsmetrik NDCAVG vom Straßenwinkel ist daher vernachlässigbar gering. Im Gegensatz dazu wirkt sich die Einstellung des Straßenwinkels auf die NRPCAVG-Metrik deutlicher aus. Es gibt jedoch keine einfache Regel, die diese Abhängigkeit beschreibt. Die Abbildungen 55 und 59 zeigen für die Visualisierungen der Beispielsysteme JUnit und Ant eine Zunahme der NRPCAVG-Metrikwerte mit steigendem Abzweigungswinkel der Straßen. Für die Systeme JHotDraw und ArgoUML verringert sich der Metrikwert mit steigendem Straßenwinkel (siehe Abbildung 61, 63) und für die Visualisierung des Beispielsystems EvoViewer steigt der NRPCAVG-Metrikwert bis zu einem Straßenwinkel von 9° kurz an, fällt dann bis zu einem Winkel von 68° ab und erhöht sich mit steigendem Straßenwinkel wieder. Eine einfache Gesetzmäßgkeit ist nicht erkennbar.

61

Abbildung 55: Auswirkungen des Straßenwinkels auf die Metriken NRPCAVG und NDCAVG für Visualisierungen des Softwaresystems JUnit.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,01

0,02

0,03

0,04

0,05

0,06

0,07

JUnit

NRPC_AVGNDC_AVG

Straßenw inkel


62

Abbildung 57: Auswirkungen des Straßenwinkels auf die Metriken NRPCAVG und NDCAVG für Visualisierungen des Softwaresystems EvoViewer.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,05

0,1

0,15

0,2

0,25

0,3

0,35

EvoViewer

NRPC_AVGNDC_AVG

Straßenw inkel

Abbildung 56: Auswirkungen des Straßenwinkels auf die Metrik DORCSUM für Visualisierungen des Softwaresystems JUnit.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,5

1

1,5

2

2,5

3

JUnit

DORC_SUM

Straßenw inkel

Abbildung 58: Auswirkungen des Straßenwinkels auf die Metrik DORCSUM für Visualisierungen des Softwaresystems EvoViewer.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,2

0,4

0,6

0,8

1

1,2

EvoViewer

DORC_SUM

Straßenw inkel


63

Abbildung 59: Auswirkungen des Straßenwinkels auf die Metriken NRPCAVG und NDCAVG für Visualisierungen des Softwaresystems Ant.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,01

0,02

0,03

0,04

0,05

0,06

Ant

NRPC_AVGNDC_AVG

Straßenw inkel

Abbildung 60: Auswirkungen des Straßenwinkels auf die Metrik DORCSUM für Visualisierungen des Softwaresystems Ant.5

1015

2025

3035

4045

5055

6065

7075

8085

9005

1015202530354045

Ant

DORC_SUM

Straßenw inkel

Abbildung 61: Auswirkungen des Straßenwinkels auf die Metriken NRPCAVG und NDCAVG für Visualisierungen des Softwaresystems JHotDraw.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,050,1

0,150,2

0,250,3

0,350,4

JHotDraw

NRPC_AVGNDC_AVG

Straßenw inkel


64

Abbildung 62: Auswirkungen des Straßenwinkels auf die Metrik DORCSUM für Visualisierungen des Softwaresystems JHotDraw.5

1015

2025

3035

4045

5055

6065

7075

8085

900

10

20

30

40

50

60

70

JHotDraw

DORC_SUM

Straßenw inkel

Abbildung 64: Auswirkungen des Straßenwinkels auf die Metrik DORCSUM für Visualisierungen des Softwaresystems ArgoUML.5

1015

2025

3035

4045

5055

6065

7075

8085

90140

150

160

170

180

190

200

ArgoUML

DORC_SUM

Straßenw inkel

Abbildung 63: Auswirkungen des Straßenwinkels auf die Metriken NRPCAVG und NDCAVG für Visualisierungen des Softwaresystems ArgoUML.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,1

0,2

0,3

0,4

0,5

0,6

ArgoUML

NRPC_AVGNDC_AVG

Straßenw inkel


Eindeutiger als die NDCAVG- oder NRPCAVG-Metrik verhält sich die DORCSUM-Metrik bei einer Änderung des Straßenwinkels. Von wenigen Ausnahmen abgesehen erhöht sich in den Visualisierungen aller Beispielsysteme bei steigendem Straßenwinkel auch der Wert der DORCSUM-Metrik (siehe Abbildung 56, 58, 60, 62 und 64). Es kann daher ein monotoner Zusammenhang zwischen Straßenwinkel und Ordnungsstabilität vermutet werden. Je kleiner der Straßenwinkel gewählt wird, desto stabiler ist das generierte Layout bezüglich der Ordnungsstabilität.Für die Abhängigkeit der Transformationsstabilität vom Straßenwinkel kann keine einfache Regel angegeben werden. Ein möglicher Grund dafür ist, dass sich die Änderung des Straßenwinkels sowohl positiv als auch negativ auf die Transformationsstabilität der Layouts auswirken kann. Bei einem kleinen Abzweigungswinkel der Straßen ist die Ausdehnung der meisten Teilbaum-Repräsentationen sehr groß. Verschiebungen wirken sich hier stärker aus als in Layouts mit höherem Straßenwinkel. Andererseits führt ein großer Straßenwinkel dazu, dass mehr Straßen nach innen zum Zentrum der Visualisierung gerichtet sind. Entstehen an diese Straßen im Laufe der Systementwicklung neue Unterelemente, müssen mehr Elemente nach außen verschoben werden als in Layouts mit kleinerem Straßenwinkel. Da sich die Transformationsstabilität aus einer Überlagerung der beiden beschriebenen Auswirkungen ergibt, kann keine einfache Abhängigkeit zwischen Straßenwinkel und Transformations-stabilität angegeben werden.5.1.2.3 Abhängigkeit von der Repräsentation der Level 3-KnotenNeben weiteren Parametern ist die Stabilität der Stadt-Layouts auch von der Repräsentation der Level 3-Knoten abhängig. Level 3-Knoten können in den Visualisierungen als Gebäude-quader repräsentiert werden, wobei die Ausdehnung des Quaders durch drei verschiedene Attribute des Knotens gegeben ist. Falls sich die Attribute im Laufe der Entwicklung des visualisierten Systems ändern, vergrößert oder verkleinert sich auch das Gebäude. Die resultierende Größenänderung der Gebäudegrundfläche kann die Stabilität des Stadt-Layouts negativ beeinflussen. Eine andere Möglichkeit, Level 3-Knoten in den Visualisierungen darzustellen, ist die Repräsentation der Knoten als Evolution Tower. Für jede Version, in der der Knoten existiert, enthält das Gebäude eine Schicht mit fester Höhe. Die Ausdehnung einer Schicht in X- und Z-Richtung (Breite und Tiefe der Schicht) bestimmen die Werte zweier Attribute des Knotens für die jeweiligen Version. Die Grundfläche des Gebäudes ist durch die Maximalwerte der beiden Knotenattribute über dem visualisierten Entwicklungszeitraum bestimmt. Falls sich die Attributwerte im Laufe der Entwicklung verkleinern, bleibt die Ausdehnung der Grundfläche des Evolution Tower-Gebäudes erhalten und das Layout somit stabil. Nur bei einer Vergrößerung der Attributwerte im Entwicklungsverlauf vergrößert sich die Grundfläche, was sich negativ auf die Stabilität auswirken kann. Daher ist die Stabilität der Stadtvisualisierungen für die Repräsentation der Level 3-Knoten als Evolution Tower gleich hoch oder höher als für die Repräsentation der Knoten als Gebäudequader.

65


5.2 Bewertung der Kompaktheit

5.2.1 KompaktheitsmaßeWie auch schon für die Stabilitätsmaße ist es für das Messen der Kompaktheit, wie sie in Kapitel 4.1.2 definiert ist, ausreichend und sogar notwendig eine Projektion der Stadt-visualisierung auf die Ebene zu betrachten. Das dreidimensionale Layout der Stadt wird durch eine Parallelprojektion in Richtung der Y-Achse auf ein zweidimensionales Layout in der XZ-Ebene abgebildet. Falls der Wurzelknoten (Level 1-Knoten) als Autobahn repräsentiert ist, erscheint er im zweidimensionalen Layout als Rechteck, für eine Repräsentation als zentralen Platz ist er als Kreis abgebildet. Als Straßen und Gebäude repräsentierte Level 2- und Level 3-Knoten sind in der Ebene als Rechtecke dargestellt. Die Achsen im Koordinatensystem des projizierten zweidimensionalen Layouts sind im Weiteren als X- und Y-Achse bezeichnet.Um die Kompaktheit graduell zu messen, soll das Verhältnis der Flächen aller Knoten-Repräsentanten zur Fläche einer, die Stadt umschließenden, Begrenzungsform berechnet werden. Die Begrenzungsform soll eine möglichst einfache geometrische Figur beschreiben, die bei minimalem Flächeninhalt alle Layout-Objekte einschließt. Drei Formen einer Stadtbegrenzung werden im Weiteren genauer untersucht: ein zur X- und Y-Achse orthogonales Rechteck, das kleinste umschließende konvexe Polygon und der kleinste umschließende Kreis.Da die meisten Ausgabegeräte und auch die meisten Benutzerschnittstellen rechteckige Darstellungsbereiche besitzen, stellt das Rechteck eine sinnvolle und einfache Form einer Stadtbegrenzung dar. Bei einer optimierten Kompaktheit in Bezug auf ein umschließendes Rechteck kann eine Stadtvisualisierung als Draufsicht effizient auf einem Ausgabemedium dargestellt werden. Ein konvexes, die Stadt umschließendes, Polygon kommt dagegen einer natürlichen Stadt-begrenzung sehr viel näher. Es stellt die kleinste konvexe Form dar, von der sich die Stadt umschließen lässt.Die maximale Entfernung der Objekte zu einem Stadtzentrum bietet eine weite Möglichkeit die Kompaktheit eines Layouts zu charakterisieren. Je kleiner ein umschließender Kreis ist, in dem alle Stadtobjekte positioniert sind, desto kleiner ist auch die maximale Entfernung der Objekte zum Kreismittelpunkt. Ein Layout, welches innerhalb einer kreisförmigen Begrenzung alle Objekte sehr dicht anordnet und somit kompakt im Sinne des kleinsten umschließenden Kreises ist, besitzt außerdem die Eigenschaft, dass der maximale Abstand zweier Layout-Objekte höchstens dem Durchmesser des Kreises entspricht.Für alle beschriebenen Kompaktheitsmaße wird zur Bestimmung der Begrenzungsform des Stadtlayouts das zweidimensionale Layout auf die Punktmenge P im ℝ2 reduziert. Die Menge P enthält dabei die Eckpunkte aller zweidimensionalen Layout-Objekte. Für jedes Rechteck besitzt P vier Eckpunkte und für jeden Kreis die Eckpunkte eines regelmäßigen n-Ecks mit gleichen Umkreis. Andere Grundformen kommen im zweidimensionalen Layout nicht vor.

Kompaktheit im kleinsten umschließenden Rechteck: Es sei zunächst der Begriff Kompaktheit eines zweidimensionalen Layouts als das Verhältnis der Flächensumme aller Layout-Objekte zu einer Bezugsfläche definiert. Die Metrik Kompaktheit im kleinsten umschließenden Rechteck (Smallest Enclosing Rectangle Compactness - SERC) beschreibt die Kompaktheit eines Stadtlayouts bezüglich des kleinsten achsenparallelen Rechtecks, das alle Layout-Objekte enthält. Es ist für die Konstruktion eines solchen Rechtecks ausreichend, ein 66

5.2 BEWERTUNG DER KOMPAKTHEIT

minimales Rechteck zu finden, dass alle Punkte der Layout-Eckpunktmenge P enthält. Die minimale und maximale X-Komponente der Punkte aus P bestimmen dann die zur Y-Achse parallelen Seiten des Rechtecks. Zur X-Achse parallele Seiten sind durch die minimale und maximale Y-Komponente vorgegeben. Das kleinste umschließende Rechteck wird in der Literatur auch als Minimum Bounding Box, Axis Aligned Bounding Box oder Minimum Bounding Rectangle bezeichnet ([CM04], [BB05]).Eine formale Definition der SERC-Metrik ist in Gleichung 31 angegeben. Die Variable ASER beschreibt dabei den Flächeninhalt des kleinsten umschließenden Rechtecks und die Funktion A :Oℝ gibt für ein Element aus der Menge zweidimensionaler Layout-Objekte O={o1 , o2 , , on} den Flächeninhalt an.

SERC=∑i=1

N

Aoi

ASER ,mit N=∣O∣

(31)Da die Metrik das Verhältnis der Objektflächen zur Fläche eines umschließenden Rechtecks berechnet, kann sie nur Werte zwischen 0 und 1 annehmen. Für ein Treemap-Layout berechnet die SERC-Metrik beispielsweise den Wert 1, da hier die Konstruktion des Layouts auf einer Unterteilung eines Rechtecks beruht und die Summe der Flächen aller Layout-Objekte somit gleich dem Flächeninhalt des umschließenden Rechtecks ist.Kompaktheit im kleinsten umschließenden Polygon: Die Metrik Kompaktheit im kleinsten umschließenden Polygon (Smallest Enclosing Polygon Compactness – SEPC) wird analog zur SERC-Metrik definiert. Die Bezugsform ist hier jedoch durch das konvexe Polygon gegeben, dass alle Punkte der Punktmenge P enthält und eine minimale Fläche besitzt. Die Eckpunkte eines solchen Polygons sind durch die konvexe Hülle CH P der Punktmenge P beschreibbar. Ein einfacher und effizienter Algorithmus zu Berechnung der konvexen Hülle ist in Kapitel 8.1.1 näher beschrieben. Der Flächeninhalt ASEP für ein so konstruiertes umschließendes Polygon lässt sich mit Hilfe der gaußschen Trapezformel bestimmen, die in Gleichung 32 angegeben ist.

ASEP=∑j=1

M

p j , x⋅ p j1 mod M , y− p j−1mod M , y

2 , mit p j∈CH P , M=∣CH P ∣

(32)SEPC=

∑i=1

N

Aoi

ASEP ,mit N=∣O∣ (33)

Gleichung 33 zeigt die formale Definition der SEPC-Metrik. Auch sie liefert nur Werte, die zwischen 0 und 1 liegen.Kompaktheit im kleinsten umschließenden Kreis: Die Metrik Kompaktheit im kleinsten umschließenden Kreis (Smallest Enclosing Circle Compactness – SECC) berechnet die Kompaktheit eines Stadtlayouts bezüglich des kleinsten Kreises, der alle Layout-Objekte umschließt. Dieser Layout umschließende Kreis kann durch einen kleinsten Kreis, der alle Punkte der Layout-Punktmenge P enthält, approximiert werden. Der kleinste umschließende Kreis (Smallest Enclosing Circle - SEC) ist für eine Menge S={p1 , p2 , , p n} mit n≥2 von Punkten in der Ebene definiert als kleinster Kreis, der alle

67


Punkte aus S enthält. Eine Methode zur Bestimmung des SEC, die auf der zuvor bestimmten konvexen Hülle der Punktmenge beruht, beschreibt Skyum in [Sky91]. Der Algorithmus ist im Kapitel 8.1.2 zusammenfassend beschrieben.SECC=

∑i=1

N

Aoi

ASEC ,mit N=∣O∣

(34)In Gleichung 34 ist die Metrik SECC formal definiert. Die Variable ASEC beschreibt dabei den Flächeninhalt des kleinsten umschließenden Kreises der Punktmenge P . Beziehungen der Metriken: Bei den drei aufgeführten Layout-Begrenzungen für die Metriken SERC, SEPC und SECC handelt es sich um konvexe geometrische Formen oder allgemein um konvexe Teilmengen der euklidischen Ebene. Dabei ist eine Teilmenge des ℝn als konvex definiert, falls sie für je zwei Punkte a und b auch die Verbindungsstrecke S={t⋅a1−t ⋅b} mit 0≤t≤1 enthält. Die konvexe Hülle einer Menge bezeichnet ihre kleinste Obermenge. Daher ist das kleinste umschließenden Polygon der Punktmenge P , welches durch die konvexe Hülle CH P konstruiert wird, die kleinstmögliche konvexe Form, die P enthält. Für die Flächeninhalte der begrenzenden Formen gilt also ASEP≤ASER und ASEP≤ASEC , woraus direkt die beiden Ungleichungen und für die Kompaktheitsmaße folgen.

SEPC≥SERC (35)SEPC≥SECC (36)

Validierung der Metriken: An fünf unterschiedlichen Beispielvisualisierungen soll die Verwendbarkeit der Metriken SERC, SEPC und SECC zum Messen der Layout-Kompaktheit nachgewiesen werden. Abbildung 65 zeigt die Stadt-Visualisierungen von fünf Softwaresystemen, die sich in Größe und Komplexität deutlich unterscheiden. Dabei sind die einzelnen Visualisierungen mit unterschiedlichen Layout-Parametern generiert, um die Kompaktheitsmaße für verschiedene Layouts zu validieren. Die Darstellung a) der Abbildung zeigt eine sehr kompakte Stadt-Visualisierung der Software Analyz-E-Bay, die mit einem Straßenwinkel von 90° und der Repräsentation der Level 1-Knotens als Autobahn erstellt wurde. Zwei aufgelockerte aber immer noch kompakte Visualisierungen sind in den Abbildungen b) und c) gezeigt. Sie bilden die Softwaresysteme JUnit und EvoViewer mit einem Straßenwinkel von 90° und der Repräsentation des Systemelements als Autobahn bzw. zentralen Platz ab. Die Darstellung c) wird dabei als etwas kompakter wahrgenommen, da sie eine Einheit mit einem zentralen Kern bildet. Im Gegensatz dazu teilt in Darstellung b) die Autobahn das Layout in zwei Teile, was sich negativ auf die wahrnehmbare Kompaktheit auswirkt. Die in den Darstellungen d) und e) gezeigten Visualisierungen der größeren Softwaresysteme Ant und ArgoUML sind weitläufiger und wenig Kompakt. Beide Layouts sind mit einem Straßenwinkel von 30° und der Repräsentation des Level 1-Knotens als zentralen Platz erstellt. Ein Unterschied in der Kompaktheit der letzten beiden Darstellungen ist nicht erkennbar.

68


69

Abbildung 65: Stadt-Visualisierungen der Softwaresysteme Analyz-E-Bay, JUnit, EvoViewer, Ant und ArgoUML, die mit unterschiedlichen Layout-Parametern generiert wurden.


Die für die fünf Visualisierungen der Abbildung 65 gemessenen Werte der Metriken SERC, SEPC und SECC sind in Abbildung 66 vergleichend dargestellt. Es zeigt sich, dass die Messwerte die wahrgenommene Kompaktheit der verschiedenen Darstellungen in hohem Maße widerspiegeln. So wird für die Kompaktheit des in a) dargestellten Layouts ein für alle Metriken hohen Wert gemessen. Für die Visualisierungen b) und c) messen die Metriken einen deutlich kleineren Wert für die Kompaktheit, wobei für die Darstellung c) leicht höhere Werte speziell mit der SECC-Metrik gemessen werden. Die geringste Kompaktheit messen die Metriken für Visualisierungen der Darstellungen d) und e).Es kann somit gezeigt werden, dass ein Messen der Kompaktheit mit Hilfe der vorgestellten Metriken möglich ist. Da die Metriken stark miteinander korreliert sind, stellen sie alle drei zuverlässiges Maße dar, um die Kompaktheit zu messen. Die Metriken SEPC und SECC besitzen jedoch gegenüber der SERC-Metrik den Vorteil, dass sie rotationsinvariant sind. Sie messen für Layouts, die sich nur durch eine Rotation aller Elemente um einem Punkt unterscheiden, stets gleiche Werte der Kompaktheit. Die Messwerte der SERC-Metrik können sich dagegen bei einer Drehung des Layouts deutlich unterscheiden. 5.2.2 Abhängigkeiten der KompaktheitDie folgenden Abschnitte untersuchen die Auswirkungen der Änderung des Straßenwinkels, den Einfluss der Repräsentation des Level 1-Knotens (als Autobahn oder als zentraler Platz) und die Abhängigkeit der Kompaktheit von der Größe des visualisierten Systems. Der Grad der Kompaktheit wird in allen Messungen durch die zuvor beschriebenen Metriken SEPC und SECC bestimmt.5.2.2.1 Abhängigkeit vom StraßenwinkelAlle Straßen des Stadt-Layouts repräsentieren Level 2-Knoten der zu visualisierenden Baumstruktur. Der Winkel in dem untergeordnete Straßen von übergeordneten abzweigen, ist im Layout einheitlich für Straßen ab der zweiten Hierarchieebene frei zwischen 0° und 90° einstellbar. Ein kleiner, sehr spitzer Winkel führt zu einer Verschiebung der an den Straßenseiten positionierten Objekten (Gebäude und untergeordnete Straßen) nach außen, da sich die nicht nutzbare Fläche an der Abzweigungsecke zwischen übergeordneter und untergeordneter Straße mit abnehmendem Winkel stark verlängert. Das Layout dehnt sich dabei aus und die Kompaktheit verringert sich.70

Abbildung 66: Vergleich der Kompaktheitsmaße SERC, SEPC und SECC für unterschiedliche Beispielvisualisierungen.a) b) c) d) e)

0

0,1

0,2

0,3

0,4

0,5

0,6

SERC-MetrikSEPC-MetrikSECC-Metrik


71

Abbildung 67: Kompaktheit des Stadt-Layouts für die Softwaresysteme Analyz-E-Bay, JUnit, EvoViewer und Ant in Abhängigkeit eines Straßenwinkels von 30°, 45° und 90°.


Der vermutete Zusammenhang zwischen Straßenwinkel und Kompaktheit, dass sich die Kompaktheit mit zunehmendem Abzweigungswinkel auch erhöht, kann für kleine Systeme an Beispielen belegt werden. Für große Systeme dagegen lässt sich kein einfacher Zusammenhang nachweisen.Die bereits bekannten Softwaresysteme Analyz-E-Bay, JUnit, EvoViewer, Ant, JHotDraw und ArgoUML dienen als Beispielsysteme für die Kompaktheitsmessungen bei verschiedenen Abzweigungswinkeln der Straßen. Die Abbildungen 67 und 68 zeigen Stadt-Visualisierungen der Systeme für die Straßenwinkel 30°, 45° und 90°. Ein blaues umschließendes Polygon und ein oranger Umkreis in den Darstellungen veranschaulichen die Bezugsformen für die Berechnung der beiden Kompaktheitsmaße SEPC und SECC.Um die Abhängigkeit der Kompaktheit vom Layout-Parameter Straßenwinkel zu untersuchen, ist in den sechs Beispielsystemen die SEPC- und SECC-Metrik für Winkel von 5° bis 90° in Schritten von 0,5° gemessen worden. Die Messergebnisse sind in Liniendiagrammen in den Abbildungen 69 bis 74 zusammengefasst. Der Straßenwinkel ist dabei auf die X-Achse abgetragen und die Metrikwerte auf die Y-Achse. Die beiden Kompaktheitsmaße SEPC und SECC sind jeweils als blaue und orange Kurve dargestellt.Das kleinste Softwaresystem Analyz-E-Bay, für welches die Abhängigkeit von Kompaktheit und Abzweigungswinkel der Straßen in Abbildung 69 dargestellt ist, zeigt einen monotonen Zusammenhang zwischen Straßenwinkel und Kompaktheit auf. Bis auf wenige Ausnahmen lässt sich durch Erhöhen des Straßenwinkel auch immer die Kompaktheit bezüglich des 72

Abbildung 68: Kompaktheit des Stadt-Layouts für die Softwaresysteme JHotDraw und ArgoUML in Abhängigkeit eines Straßenwinkels von 30°, 45° und 90°.


kleinsten umschließenden Polygons (gemessen durch die SEPC-Metrik) und bezüglich des kleinsten umschließenden Kreises (gemessen durch die SECC-Metrik) erhöhen. Auftretende Sprünge in den Kurven der SEPC- und SECC-Metrik, die für alle Systeme mehr oder weniger stark erkennbar sind, lassen sich durch mögliche Neuordnungen von untergeordneten Elementen an Straßenrändern erklären. Im Stadt-Layout ist an den Rändern einer Straße die Reihenfolge und Seitenzuordnung von Repräsentationen untergeordneter Teilbäume, die in der selben Version entstanden sind, durch die Ausmaße der Begrenzungsflächen der Teilbaum-Repräsentationen bestimmt. Durch die Änderung des Straßenwinkels kann sich die Begrenzungsfläche einiger Repräsentationen ändern. Somit ist es auch möglich, dass sich die Reihenfolge und Seitenzuordnung von Repräsentationen untergeordneter Teilbäume am Rand einer Straße ändert, was zu einer sprunghaften Änderung der Begrenzungsform des gesamten Stadt-Layouts führen kann. Da sich das kleinste umschließende Polygon enger um ein Stadt-Layout herum legt als der kleinste umschließende Kreis, wirken sich Neuordnungen von untergeordneter Elementen an Straßenrändern stärker auf die Polygon-Begrenzungsform als auf den Umkreis aus. Die SECC-Metrik ist daher gegenüber der SEPC-Metrik geglättet und ihre Kurve in den Abbildungen enthält weniger Sprünge.

Für die Visualisierungen der Softwaresysteme JUnit, EvoViewer, Ant und JHotDraw besteht ebenfalls ein monotoner Zusammenhang zwischen Straßenwinkel und Kompaktheit, der sich in den Abbildungen 69 bis 72 aufzeigen lässt. Eine Vergrößerung des Straßenwinkels bewirkt fast immer eine Kompaktifizierung des Layouts. Ausnahmen bilden zum einen Neuordnungen untergeordneter Elemente an den Straßenseiten, die sich durch Sprünge in den Kurven zeigen. Zum anderen verhält sich die SECC-Kompaktheit für Visualisierung der Software EvoViewer ab einem Winkel von 36° umgekehrt, so dass sich die Kompaktheit bezüglich des kleinsten Umkreises mit zunehmendem Straßenwinkel verringert (siehe Abbildung 71). Dies lässt sich dadurch erklären, dass bei steigendem Straßenwinkel das Layout in die Länge gezogen wird und sich der Flächeninhalt des Umkreises somit erhöht. In Abbildung 67 ist zum Vergleich die Layout-Änderung der Software EvoViewer für die Winkel 30°, 45° und 90° veranschaulicht.

73

Abbildung 69: Abhängigkeit der Kompaktheit vom Straßenwinkel für die Software Analyz-E-Bay.5

1015

2025

3035

4045

5055

6065

7075

8085

900

0,1

0,2

0,3

0,4

0,5

0,6

0,7Analyz-E-Bay

SEPC-MetrikSECC-Metrik

Straßenw inkel in °


74

Abbildung 70: Abhängigkeit der Kompaktheit vom Straßenwinkel für die Software JUnit.

Abbildung 71: Abhängigkeit der Kompaktheit vom Straßenwinkel für die Software EvoViewer.

Abbildung 72: Abhängigkeit der Kompaktheit vom Straßenwinkel für die Software Ant.

510

1520

2530

3540

4550

5560

6570

7580

8590

0

0,05

0,1

0,15

0,2

0,25

JUnit



510

1520

2530

3540

4550

5560

6570

7580

8590

0

0,05

0,1

0,15

0,2

0,25

EvoViewer



510

1520

2530

3540

4550

5560

6570

7580

8590

0

0,02

0,04

0,06

0,08

0,1

0,12

0,14Ant




Die Abhängigkeit der Layout-Kompaktheit vom Straßenwinkel ist für das größte untersuchte Softwaresystem ArgoUML in Abbildung 74 dargestellt. Bedingt durch Größe und Komplexität des Systems lässt sich kein einfach beschreibbarer Zusammenhang zwischen dem Abzweigungswinkel der Straßen und der Kompaktheit der Stadt-Visualisierung erkennen. Vielmehr ändert sich die SEPC- und SECC-Kompaktheit bei steigendem Straßenwinkel sprunghaft und scheinbar zufällig. Ein monotoner Zusammenhang zwischen Straßenwinkel und Kompaktheit ist für die Visualisierung der Software AgroUML nicht gegeben.

5.2.2.2 Abhängigkeit von der Repräsentation des Level 1-KnotensDer Level 1-Knoten (System- oder auch Wurzelknoten) kann in den Stadt-Visualisierungen als Autobahn oder als zentraler Platz repräsentiert werden. Bei einer Repräsentation als Autobahn zweigen alle Repräsentanten untergeordneter Teilbäume des zu visualisierenden Baumes im rechten Winkel von unterschiedlichen Seiten der Autobahn ab. Mit fortschreitender Entwicklung des visualisierten Systems kann die Autobahn in genau eine Richtung „wachsen“, falls neue Teilsysteme entstehen. Bei der Repräsentation als zentralen Platz sind alle Repräsentationen untergeordneter Teilbäume sternförmig um einen Punkt angeordnet, der als Platz visualisiert ist. Kommen im Verlauf der Systemevolution neue Subsysteme hinzu, schieben sich alle anderen Teilsystem-Repräsentationen zusammen und gegebenenfalls auch nach außen, um Platz für das neue Teilsystem zu machen. Welche Auswirkungen die beiden 75

Abbildung 73: Abhängigkeit der Kompaktheit vom Straßenwinkel für die Software JHotDraw.

Abbildung 74: Abhängigkeit der Kompaktheit vom Straßenwinkel für die Software ArgoUML.

510

1520

2530

3540

4550

5560

6570

7580

8590

0

0,01

0,02

0,03

0,04

0,05

0,06

0,07JHotDraw



510

1520

2530

3540

4550

5560

6570

7580

8590

00,010,020,030,040,050,060,070,080,09

ArgoUML




möglichen Repräsentationen des Level 1-Knotens auf die Kompaktheit des Stadt-Layouts haben, untersucht der folgende Abschnitt für die Visualisierung der Softwaresysteme Analyz-E-Bay, JUnit, EvoViewer, Ant, JHotDraw und ArgoUML.

In den Abbildungen 76 und 77 sind die sechs Beispielsysteme als Stadt-Visualisierungen dargestellt, wobei der Level 1-Knoten einmal als Autobahn und einmal als zentraler Platz repräsentiert ist. Eine blaue Begrenzungslinie stellt dabei für das Kompaktheitsmaß SEPC die Bezugsform des kleinsten umschließenden Polygons dar und ein oranger Kreis zeigt für das Layout den kleinsten Umkreis, der für die Berechnung der SECC-Metrik als Bezugsform dient. Die Metrikwerte der SEPC- und SECC-Metrik für die dargestellten Stadt-Layouts sind vergleichend in Abbildung 75 dargestellt. Es ist zu erkennen, dass die Softwaresysteme EvoViewer und ArgoUML kompakter visualisiert werden, falls der Level 1-Knoten als zentraler Platz repräsentiert ist. Für die Systeme Analyz-E-Bay und JUnit ist das Layout bei einer Repräsentation des Level 1-Knotens als Autobahn kompakter. Nahezu keinen Einfluß auf die Kompaktheit des Layouts hat eine Änderung der L1-Repräsentation für das System JHotDraw. Widersprüchliche Messergebnisse liefern die Metriken SEPC und SECC für das Softwaresystem Ant.Es zeigt sich somit, dass die Auswirkungen der Repräsentation des Level 1-Knotens auf die Kompaktheit von der konkreten Struktur des zu visualisierenden Baumes abhängt. In den untersuchten Beispielvisualisierungen war die Kompaktheit vom Aufbau der Package-Hierarchien der Softwaresysteme abhängig. Ein einfacher und allgemein gültiger Zusammenhang zwischen Repräsentation des Level 1-Knotens und der Layout-Kompaktheit wurde nicht gefunden. Es gibt jedoch Faktoren, die die Kompaktheit in einem Layout, in dem der Level 1-Knoten als zentraler Platz repräsentiert ist, begünstigen. Hierzu gehören eine ausgewogene Größenverteilung der Teilsysteme sowie eine Mindestanzahl von Teilsystemen, wie es z.B. im Softwaresystem EvoViewer der Fall ist.

76

Abbildung 75: Abhängigkeit der Kompaktheit von der Repräsentation des Level 1-Knotens.Analyz-E-Bay JUnit EvoView er Ant JHotDraw AgroUML0

0,1

0,2

0,3

0,4

0,5

0,6

L1-Knoten als Auto-bahn (SEPC-Metrik)L1-Knoten als Auto-bahn (SECC-Metrik)L1-Knoten als zentraler Platz (SEPC-Metrik)L1-Knoten als zentraler Platz (SECC-Metrik)


77

Abbildung 76: Kompaktheit des Stadt-Layouts für die Softwaresysteme Analyz-E-Bay, JUnit und EvoViewer in Abhängigkeit der Repräsentation des Level 1-Knotens.


78

Abbildung 77: Kompaktheit des Stadt-Layouts für die Softwaresysteme Ant, JHotDraw und ArgoUML in Abhängigkeit der Repräsentation des Level 1-Knotens.


5.2.2.3 Abhängigkeit von der SystemgrößeIn den vorangegangenen Untersuchungen über die Abhängigkeiten der Kompaktheit in den Unterkapiteln 5.2.2.1 und 5.2.2.2 sind für kleine Systeme höhere Werte für die SEPC- und SECC-Metrik gemessen worden als für große Systeme. Es liegt daher die Vermutung nahe, dass die Kompaktheit einer Stadt-Visualisierung nicht nur von Parametern des Layout-Algorithmus abhängt, sondern auch von der Größe und Komplexität der visualisierten Baumstruktur.

Um die Abhängigkeit der Kompaktheit einer Stadt-Visualisierung von der Größe des visualisierten Systems zu messen, sei zunächst die Systemgröße als die Anzahl dargestellter Repräsentanten von Baumknoten definiert. Für die Softwaresysteme Analyz-E-Bay, JUnit, EvoViewer, Ant, JHotDraw und ArgoUML wird die Kompaktheit der Stadt-Layouts ihrer Entwicklungsgeschichte für unterschiedliche Spannen von Versionen und somit für unterschiedlichen Systemgrößen gemessen. Die Darstellung der Messwertpaare von SEPC-Metrik und Systemgröße in einem Koordinatensystem lässt einen klaren Zusammenhang zwischen Kompaktheit und Systemgröße erkennen (siehe Abbildung 78). Bei einem maximalen SEPC-Wert von 0,75 für Layouts von weniger als 100 visualisierten Systemelementen nimmt mit steigender Systemgröße die Kompaktheit ab. Der Betrag, um den sich die Kompaktheit verringert, nimmt mit zunehmender Systemgröße ebenfalls ab. Bei einer Anzahl von ca. 1500 visualisierten Elementen schwankt die SEPC-Kompaktheit dann nur noch um einem Wert von 0,05. Für die Untersuchung der SECC-Kompaktheit sind die Messwertpaare in Abbildung 79 dargestellt. Es ist hier ein ähnlicher Zusammenhang erkennbar.

79

Abbildung 78: Abhängigkeit der SEPC-Kompaktheit von der Systemgröße.0 500 1000 1500 2000 2500 3000 3500

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

Analyz-E-BayJUnitEvoView erAntJHotDrawArgoUML

Systemgröße (Anzahl visualisierter Elemente)

SEPC

-Met

rik

Abbildung 79: Abhängigkeit der SECC-Kompaktheit von der Systemgröße.0 500 1000 1500 2000 2500 3000 3500

0

0,1

0,2

0,3

0,4

0,5

Analyz-E-BayJUnitEvoView erAntJHotDrawArgoUML

Systemgröße (Anzahl visualisierter Elemente)

SECC

-Met

rik


Die Kompaktheit der Stadt-Layouts ist daher klar von der Größe des visualisierten Systems abhängig. Mit steigender Anzahl der visualisierten Systemelemente nimmt die Kompaktheit eines Layouts erst stark und bis zu einer Systemgröße von ca. 1500 dargestellten Elementen immer schwächer ab. Für größere Systeme schwankt sie um einen minimalen Wert. Gründe für die Abnahme der Kompaktheit in großen Systemen sind die stark variierende Anzahl untergeordneter Kindknoten in der gegebenen Baumstruktur sowie eine teilweise sehr hohe Anzahl der Kindknoten. Hierdurch dehnen sich einzelne Bereiche im Layout stärker aus als andere und es können große ungenutzte Flächen beim Packen dieser Bereiche entstehen.5.3 Bewertung der SkalierbarkeitDa die Konstruktion des entwickelten Stadt-Layouts Evolution City auf einem zweidimen-sionalen Layout-Algorithmus basiert, ist die für das Layout verfügbare Fläche in der Ebene auf ein quadratisches Wachstum beschränkt. Dagegen wachsen Baumstrukturen exponentiell schnell. Insofern ist der entwickelte Ansatz theoretisch nicht auf Visualisierungen beliebig großer (veränderlicher) Bäume skalierbar, selbst wenn es das Laufzeitverhalten des Algorith-mus zuließe.Praktisch ist der umgesetzte Prototyp Evolution Viewer für die Visualisierung kleiner bis mittlerer Softwaresysteme geeignet. Die genaue Größe der darstellbaren Systeme ist stark von der Prozessorleistung, dem Arbeitsspeicher sowie der Leistungsfähigkeit der Grafikkarte des Systems abhängig, auf dem der Prototyp ausgeführt wird. In einer Umgebung mit einem Prozessor von 2,00 GHz, einem Arbeitsspeicher von 2 GB und einer NVIDIA GeForce 8400M GS-Grafikkarte stößt die Umsetzung bei der Visualisierung der Entwicklungsgeschichte des Opensource Softwaresystems ArgoUML an seine Grenzen, was sich durch eine niedrige Bildwiederholungsrate und einen hohen Verbrauch des Arbeitsspeichers bemerkbar macht. Für die Darstellung der Entwicklung von 12 Versionen enthält der abgebildete LACT-Baum insgesamt 2975 Knoten. Die generierte Stadtszene besteht dabei aus einer Autobahn, 166 Straßen, und 2808 Gebäuden.5.4 ZusammenfassungMit Hilfe von entwickelten und validierten Stabilitäts- und Kompaktheitsmaßen hat das Kapitel die Abhängigkeit von verschiedenen Layout-Parametern und Baumeigenschaften auf die Stabilität und Kompaktheit des Layouts untersucht, wobei Visualisierungen von sechs unter-schiedlich komplexen Softwaresystemen betrachtet wurden.Für die Stabilität des entwickelten Stadt-Layouts konnte gezeigt werden, dass die Reprä-sentation des Level 1-Knotens als Autobahn oder zentralen Platz keinen großen Einfluss be-sitzt. Der Zusammenhang zwischen dem Abzweigungswinkel der Straßen und der Ordnungs-stabilität ist monoton. Bis auf wenige Ausnahmen führte ein kleinerer Straßenwinkel stets zu einer höheren Ordnungsstabilität. Für die Transformationsstabilität ist Abhängigkeit vom Abzweigungswinkel nicht einfach beschreibbar. Es wurde außerdem bewiesen, dass die Reprä-sentation der Level 3-Knoten als Evolution Tower im Gegensatz zur Repräsentation als einfache Gebäudequader zu stabileren Layouts führt.Für die Kompaktheit des Layouts konnte gezeigt werden, dass für die Visualisierung kleiner Softwaresysteme die Erhöhung des Abzweigungswinkels der Straßen zu einer geringeren Kompaktheit führt. Für große Systeme ergibt sich dagegen ein komplexer, nicht einfach be-schreibbarer Zusammenhang. Bei der Repräsentation des Level 1-Knotens als Autobahn ist das 80

5.4 ZUSAMMENFASSUNG

Layout für kleine Softwaresysteme kompakter. Große Systeme lassen sich dagegen für die Repräsentation des Level 1-Knotens als zentralen Platz kompakter visualisieren. Allgemein wurde gezeigt, dass die Größe des darzustellenden Softwaresystems einen großen Einfluss auf die Kompaktheit besitzt. Bis zu einer Systemgröße von 1000 Elementen nimmt die Layout-Kompaktheit ab und bleibt für größere Systeme nahezu konstant.Die Umsetzung des Stadt-Layout ist auf die Visualisierungen kleiner bis mittelgroßer Software-systeme, wie z.B. JHotDraw oder ArgoUML, skalierbar.

81

6 ANHANG

6 Anhang

6.1 Grundlegende Algorithmen

6.1.1 Die konvexe HülleDer Jarvis's March-Algorithmus ist eine einfache Methode, um die konvexe Hülle einer Punktmenge Q im ℝ2 zu bestimmen ([Jar73], [CLRS01]). Jarvis geht dabei von der Vorüberlegung aus, dass in einer Punktmenge Q ein durch zwei Punkte p und q definiertes Liniensegment l pq= pq nur dann eine Kante der konvexen Hülle von Q bildet, wenn alle anderen Punkte der Menge entweder auf l pq liegen oder auf einer Seite davon. Ein Segment l rs=rs , welches die Punktmenge Q separiert, kann keine Kante der komplexen Hülle sein. Abbildung 80 veranschaulicht diese Idee.Für eine Punktmenge Q startet der Algorithmus mit dem Punkt c 1∈Q , der einen minimalem Y-Wert besitzt. Gibt es mehrere Punkte mit minimalem Y-Wert, wird von ihnen der Punkt mit kleinstem X-Wert ausgewählt. Der so bestimmte Punkt c1 gehört immer zur konvexen Hülle. Der nächster Eckpunkt c2 besitzt nun bezüglich des Punktes c 1 den kleinsten polaren Winkel. Haben mehrere Punkte den gleichen Winkel, wird der Punkt mit der größten Entfernung zu c 1 gewählt. Der neue Punkt c2 ist jetzt Ausgangspunkt für die Bestimmung des nachfolgenden Eckpunktes der konvexen Hülle. Dies wird solange iteriert, bis das Verfahren erneut den Startpunkt c 1 erreicht. Ab dem Punkt c k , der einen maximalen Y-Wert besitzt, werden alle polaren Winkel bezüglich der negativen X-Achse bestimmt (siehe Abbildung 81). Der Algorithmus hat eine Laufzeit von O nh , wobei h für die Anzahl der Eckpunkte der konvexen Hülle steht.Ein leicht abgewandelter Ansatz orientiert sich stärker an den zuvor beschriebenen Vorüberlegungen. Wie auch in der ersten Variante startet das Verfahren mit einem Punkt c1 , der nachweislich zur konvexen Hülle gehört. Ein zweiter Punkt c2 wird jetzt so gewählt, dass alle übrigen Punkte links des Segments l 1=c1 c2 oder darauf liegen. Der neue Punkt c 2 ist Ausgangspunkt für das nachfolgende Segment. Dies wird solange wiederholt, bis der Startpunkt c1 erneut erreicht ist.Beide Varianten liefern als Ergebnis eine Folge von Eckpunkten H={c 1 , c2 , , ch} der konvexen Hülle CH Q im entgegengesetzten Uhrzeigersinn.

83

Abbildung 81: Der Jarvis's March-Algorithmus bestimmt den jeweils nächsten Punkt der konvexen Hülle als Punkt mit kleinstem Winkel bezüglich des Vorgängers.

Abbildung 80: pq ist Kante der konvexen Hülle, da alle anderen Punkte auf einer Seite liegen. Die Kante rs separiert dagegen die Menge.

KAPITEL 6. ANHANG

6.1.2 Der kleinster umschließender KreisEinen iterativen Algorithmus zur Berechnung des kleinsten umschließenden Kreises einer Punktmenge in der euklidischen Ebene beschreibt Skyum in [Sky91]. Er nutzt zunächst die Eigenschaft aus, dass der kleinste umschließende Kreis SEC S der Punktmenge S gleich dem kleinsten umschließenden Kreis SEC H der Menge H⊆S ist, falls H durch die Eckpunkte der konvexen Hülle CH S von S gebildet wird ( SEC S =SEC CH S ).Es sei also eine Punktmenge H={ p1 , p2 , , pn}, mit n≥2 in der Ebene gegeben, welche die Eckpunkte eines konvexen Polygons im Uhrzeigersinn beschreibt ( H=CH S ). Die Funktion BEFORE pi liefert dann für einen Punkt pi seinen Vorgänger pi−1nmod n aus H , NEXT pi bestimmt den Nachfolger pi1mod n . Für drei Punkte p , q und r mit p≠q∧q≠r definiert die Funktion RADIUS p ,q , r den Radius des Kreises p , q , r , der durch alle drei Punkte geht, falls p≠r . Für den Fall, dass p=r gilt, sei RADIUS p ,q , r die Hälfte der Distanz von p nach q . Die Funktion ∡ p ,q , r bezeichnet den Winkel zwischen den Liniensegmenten pq und qr . Außerdem sei folgende Ordnung für Umkreise definiert: p , q , r s , t , u ⇔ RADIUS p ,q , rRADIUS s , t , u ∨

RADIUS p , q , r =RADIUS s , t , u ∧∡ p , q , r∡ s , t , u. (37)

Iterativ entfernt der Algorithmus von Skyum aus der gegebenen Menge H Punkte, die für die Konstruktion des kleinsten umschließenden Kreises nicht relevant sind.Algorithmus von Skyumfinish := false;

repeat(1) Finde den Punkt pmax in H für das Maximum max BEFORE p , p , NEXT p , mit p∈H .(2) if ∡BEFORE p , p , NEXT p ≤

2 thenfinish := true;else entferne pmax aus H ;fi

until finish;return BEFORE pmax , pmax , NEXT pmax ;

Der Algorithmus berechnet den kleinsten umschließenden Kreis für ein konvexes Polygon mit einem Zeitaufwand von O n log n .

84

LITERATURVERZEICHNIS

Literaturverzeichnis

[AD07] Sazzadul Alam und Philippe Dugerdil, EvoSpaces: 3D Visualization of Software Architecture, SEKE, , 2007.[BB05] Michael Bender und Manfred Brill, Computergrafik: Ein anwendungsorientiertes Lehrbuch, Hanser Verlag, 2005[BD05] Michael Balzer und Oliver Deussen, Voronoi Treemaps, INFOVIS '05: Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization, IEEE Computer Society, 2005.[BD07] Michael Balzer and Oliver Deussen, Level-of-detail visualization of clustered graph layouts, Asia-Pacific Symposium on Visualisation 2007, IEEE Computer Society, 2007.[BDL05] Michael Balzer, Oliver Deussen und Claus Lewerentz, Voronoi treemaps for the visualization of software metrics, SoftVis '05: Proceedings of the 2005 ACM symposium on Software visualization, ACM, 2005.[BETT99] Giuseppe Di Battista, Peter Eades, Roberto Tamassia und Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999[BHW99] Mark Bruls, Kees Huizing und Jarke van Wijk, Squarified Treemaps, In Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization, Press, 1999.[Bli82] James F. Blinn, A Generalization of Algebraic Surface Drawing, ACM Trans. Graph., 1, S. 235-256, ACM, 1982.[BNDL04] Michael Balzer, Andreas Noack, Oliver Deussen und Claus Lewerentz, Software Landscapes: Visualizing the Structure of Large Software Systems, VisSym, , 2004.[CLRS01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein, Introduction to Algorithms, The MIT Press, 2001[CM04] Bhabatosh Chanda und D. Dutta Majumder, Digital image processing and analysis, PHI, 2004[DKYON00] Yoshinori Dobashi, Kazufumi Kaneda, Hideo Yamashita, Tsuyoshi Okita und Tomoyuki Nishita, A simple, efficient method for realistic animation of clouds, SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 2000.[FR91] Thomas M. J. Fruchterman und Edward M. Reingold, Graph drawing by force-directed placement, Softw. Pract. Exper., 21, S. 1129-1164, John Wiley \& Sons, Inc., 1991.[GW07] Rafael C. Gonzalez und Richard E. Woods, Color Image Processing, Digital Image Processing (3rd Edition), S. 411-413, Prentice Hall, 2007.[Hag05] Benjamin Hagedorn, Landschafts- und Stadtmetaphern zur Softwarevisualisierung, Konzepte der Softwarevisualisierung für komplexe, objektorientierte Softwaresysteme, S. 59-72, Universitätsverlag Potsdam, 2005.[HW02] Frank van Ham und Jarke J. van Wijk, Beamtrees : Compact Visualization of Large Hierarchies, Information Visualization, IEEE Symposium on, 0, S. 93, IEEE Computer Society, 2002.

85


[HW08] Danny Holten und Jarke J. van Wijk, Visual Comparison of Hierarchically Organized Data, 10th Eurographics/IEEE-VGTC Symposium on Visualization (Computer Graphics Forum; Proceedings of EuroVis 2008), , 2008.[Jar73] R.A. Jarvis, On the Identification of the Convex Hull of a Finite Set of Points in the Plane, #IPL#, 2, S. 18-21, , 1973.[JS91] Brian Johnson und Ben Shneiderman, Tree-Maps: a space-filling approach to the visualization of hierarchical information structures, VIS '91: Proceedings of the 2nd conference on Visualization '91, IEEE Computer Society Press, 1991.[KM00] Claire Knight und Malcolm Munro, Virtual but Visible Software, IV '00: Proceedings of the International Conference on Information Visualisation, IEEE Computer Society, 2000.[Lan01] Michele Lanza, The evolution matrix: recovering software evolution using software visualization techniques, IWPSE '01: Proceedings of the 4th International Workshop on Principles of Software Evolution, ACM, 2001.[LBD07] T. Luft, M. Balzer und O. Deussen, Expressive illumination of foliage based on implicit surfaces, Natural Phenomena 2007 (Proc. of the Eurographics Workshop on Natural Phenomena), , 2007.[LRP95] John Lamping, Ramana Rao und Peter Pirolli, A focus+context technique based on hyperbolic geometry for visualizing large hierarchies, CHI '95: Proceedings of the SIGCHI conference on Human factors in computing systems, ACM Press/Addison-Wesley Publishing Co., 1995.[LSS02] Claus Lewerentz, Frank Simon und Frank Steinbrückner, CrocoCosmos, Graph Drawing, Springer Berlin / Heidelberg, 2002.[MGTZZ03] Tamara Munzner, François Guimbretière, Serdar Tasiran, Li Zhang und Yunhong Zhou, TreeJuxtaposer: scalable tree comparison using Focus+Context with guaranteed visibility, SIGGRAPH '03: ACM SIGGRAPH 2003 Papers, ACM, 2003.[Mun97] Tamara Munzner, H3: laying out large directed graphs in 3D hyperbolic space, IEEE Symposium on Information Visualization, 0, S. 2-10, IEEE Computer Society, 1997.[PBG03] Thomas Panas, Rebecca Berrigan und John Grundy, A 3D Metaphor for Software Production Visualization, IV '03: Proceedings of the Seventh International Conference on Information Visualization, IEEE Computer Society, 2003.[RMC91] George G. Robertson, Jock D. Mackinlay und Stuart K. Card, Cone Trees: animated 3D visualizations of hierarchical information, CHI '91: Proceedings of the SIGCHI conference on Human factors in computing systems, ACM, 1991.[Sky91] Sven Skyum, A simple algorithm for computing the smallest enclosing circle, Inf. Process. Lett., 37, S. 121-125, Elsevier North-Holland, Inc., 1991.[TM02] Christopher M. B. Taylor und Malcolm Munro, Revision Towers, VISSOFT '02: Proceedings of the 1st International Workshop on Visualizing Software for Understanding and Analysis, IEEE Computer Society, 2002.[Tut60] W. T. Tutte, Convex representations of graphs, Proceedings of the London Mathematical Society, 10, S. 304-320, , 1960.[Tut63] W. T. Tutte, How to draw a graph, Proceedings of the London Mathematical Society, 13, S. 743-768, , 1963.[Wat00] Alan Watt, 3D Computer Graphics, Addison-Wesley, 2000

86


[WL08b] Richard Wettel und Michele Lanza, Visual Exploration of Large-Scale System Evolution, WCRE '08: Proceedings of the 2008 15th Working Conference on Reverse Engineering, IEEE Computer Society, 2008.[WW99] Jarke J. van Wijk und Huub van de Wetering, Cushion Treemaps: Visualization of Hierarchical Information, INFOVIS, , 1999.[YJC98] YJ. Yu, H.Y. Jung und H.G. Cho, A new rendering technique for water droplet using metaball in the gravitation force, Proceedings of the 6th International Conference in Central Europe on Computer Graphics and Visualization (WSCG'98), , 1998.

87

ABBILDUNGSVERZEICHNIS

Abbildungsverzeichnis

Abbildung 0 - Logo der BTU Cottus (Quelle: http://www.tu-cottbus.de)........................................................1Abbildung 1 - Vergleichende Visualisierung zweier Baumversionen................................................................3Abbildung 2 - CodeCity - Färbung der Systemelemente nach ihrer Entstehung............................................4Abbildung 3 - EvolutionMatrix..........................................................................................................................................4Abbildung 4 - Revision Towers..........................................................................................................................................5Abbildung 5 - Entwurf Stadt-System...............................................................................................................................6Abbildung 6 - Zuordnung von Knotenleveln in einem LACT.................................................................................8Abbildung 7 - Level-Layout..............................................................................................................................................10Abbildung 8 - Radiales Layout........................................................................................................................................10Abbildung 9 - Kräfte-basiertes Layout.........................................................................................................................11Abbildung 10 - Treemaps.................................................................................................................................................11Abbildung 11 - Treemap Erweiterungen....................................................................................................................12Abbildung 12 - hyperbolischer Baum..........................................................................................................................12Abbildung 13 - H3-Layout................................................................................................................................................12Abbildung 14 - Repräsentation des Level 1-Elementes als zentraler Platz...................................................18Abbildung 15 - Abhängigkeit des Sektorenwinkels von der Anfangslänge der Subsystem-Straße.....19Abbildung 16 - Repräsentation des Level 1-Elementes als Autobahn.............................................................20Abbildung 17 - Abbildung der Dekompositionsstruktur der Level 2-Knoten als hierarchisches Straßensystem.......................................................................................................................................22Abbildung 18 - Layout von Level 2-Knoten mit Level 2-Kindern......................................................................23Abbildung 19 - Layout von Level 2-Knoten mit Level 3-Kindern......................................................................25Abbildung 20 - Repräsentation eines Level 3-Elementes ohne Kinder..........................................................26Abbildung 21 - Rekursiv konstruierte Repräsentation einer Level 3-Hierarchie.......................................26Abbildung 22 - Durch zwei Generatorpunkte definierte implizite Fäche......................................................28Abbildung 23 - Schnitt durch ein Gelände der Dichtefeld-Funktion F............................................................28Abbildung 24 - Die Abstandsfunktion d_i(q) für ein Rechteck...........................................................................29Abbildung 25 - Die Auswirkungen des Einflussfaktors w auf das Gelände...................................................30Abbildung 26 - Schnitt durch ein Gelände der Höhenfeld-Funktion H...........................................................31Abbildung 27 - Darstellungsmöglichkeiten des Höhenfelds...............................................................................32Abbildung 28 - Konstruktion eines Segments der Höhenlinie...........................................................................33Abbildung 29 - Abbildungen der Systementwicklung auf die Basishöhe der Objekte..............................34Abbildung 30 - Repräsentation der Level 3-Elemente als Evolution Tower (1)..........................................35Abbildung 31 - Repräsentation der Level 3-Elemente als Evolution Tower (2)..........................................36Abbildung 32 - Anwendung der Farbübergangsfunktion (Entstehungszeitpunkte).................................39Abbildung 33 - Anwendung der Farbübergangsfunktion (Softwaremetrik Degree).................................39Abbildung 34 - Anwendung der Farbfunktion Farbbereiche (Methoden- und Attributanzahl)...........40Abbildung 35 - Anwendung der Farbfunktion Farbbereiche (Entstehungszeitpunkte)..........................41Abbildung 36 - Anwendung der Farbfunktion Farbpalette (Methoden- und Attributanzahl)...............42Abbildung 37 - Anwendung der Farbfunktion Farbpalette (Entstehungszeitpunkt)................................43Abbildung 38 - Anwendung der Farbfunktion Farbpalette (Packages-Schachtelungstiefe)..................43Abbildung 39 - Anwendung der HSB-Farbfunktion (Heat Map).......................................................................44Abbildung 40 - Anwendung der HSB-Farbfunktion (Subsystem-Zugehörigkeit).......................................45Abbildung 41 - Stabilitätsmaße NRPCAVG und NDCAVG für Paare von 18 Visualisierung der Software JUnit.......................................................................................................................................48Abbildung 42 - Stabilitätsmaße APC_AVG, RPC_AVG, DC_AVG für Paare von 18 Visualisierung der Software JUnit........................................................................................................................................5189

ABBILDUNGSVERZEICHNIS

Abbildung 43 - Stabilitätsmaße NRPC_AVG, NDC_AVG für die Software JUnit.............................................51Abbildung 44 - Stadtvisualisierungen der Entwicklungsgeschichte des Softwaresystems JUnit (1). 52Abbildung 45 - Stadtvisualisierungen der Entwicklungsgeschichte des Softwaresystems JUnit (2). 53Abbildung 46 - Positionsbestimmung der Layout-Objekte relativ zum übergeordneten Objekt.........54Abbildung 47 - Stabilitätsmaß DORC_SUM für Paare von 18 Visualisierung der Software JUnit........56Abbildung 48 - Auflistung von Größe und Versionsanzahl der untersuchten Beispielsysteme............57Abbildung 49 - Auswirkungen der Repräsentation des Level 1-Knotens auf die Metrik NDC_AVG (JUnit)........................................................................................................................................................58Abbildung 50 - Auswirkungen der Repräsentation des Level 1-Knotens auf die Metrik NDC_AVG (EvoViewer)............................................................................................................................................58Abbildung 51 - Auswirkungen der Repräsentation des Level 1-Knotens auf die Metrik NDC_AVG (Ant)...........................................................................................................................................................58Abbildung 52 - Auswirkungen der Repräsentation des Level 1-Knotens auf die Metrik NDC_AVG (JHotDraw)..............................................................................................................................................59Abbildung 53 - Auswirkungen der Repräsentation des Level 1-Knotens auf die Metrik NDC_AVG (ArgoUML)...............................................................................................................................................59Abbildung 54 - Visualisierung der Software JHotDraw in Abhängigkeit der Repräsentation des Level 1-Knotens.................................................................................................................................................60Abbildung 55 - Auswirkungen des Straßenwinkels auf die Metriken NRPC_AVG, NDC_AVG (JUnit). .61Abbildung 56 - Auswirkungen des Straßenwinkels auf die Metrik DORC_SUM (JUnit)...........................62Abbildung 57 - Auswirkungen des Straßenwinkels auf die Metriken NRPC_AVG, NDC_AVG (EvoViewer)............................................................................................................................................62Abbildung 58 - Auswirkungen des Straßenwinkels auf die Metrik DORC_SUM (EvoViewer)...............62Abbildung 59 - Auswirkungen des Straßenwinkels auf die Metriken NRPC_AVG, NDC_AVG (Ant).....63Abbildung 60 - Auswirkungen des Straßenwinkels auf die Metrik DORC_SUM (Ant)..............................63Abbildung 61 - Auswirkungen des Straßenwinkels auf die Metriken NRPC_AVG, NDC_AVG (JHotDraw)..............................................................................................................................................63Abbildung 62 - Auswirkungen des Straßenwinkels auf die Metrik DORC_SUM (JHotDraw).................64Abbildung 63 - Auswirkungen des Straßenwinkels auf die Metriken NRPC_AVG, NDC_AVG (ArgoUML)...............................................................................................................................................64Abbildung 64 - Auswirkungen des Straßenwinkels auf die Metrik DORC_SUM (ArgoUML)..................64Abbildung 65 - Stadt-Visualisierungen mit unterschiedlichen Layout-Parametern.................................69Abbildung 66 - Vergleich der Kompaktheitsmaße SERC, SEPC und SECC.....................................................70Abbildung 67 - Kompaktheit des Stadt-Layouts in Abhängigkeit des Straßenwinkels (1).....................71Abbildung 68 - Kompaktheit des Stadt-Layouts in Abhängigkeit des Straßenwinkels (2).....................72Abbildung 69 - Abhängigkeit der Kompaktheit vom Straßenwinkel (Analyz-E-Bay)...............................73Abbildung 70 - Abhängigkeit der Kompaktheit vom Straßenwinkel (JUnit)................................................74Abbildung 71 - Abhängigkeit der Kompaktheit vom Straßenwinkel (EvoViewer)....................................74Abbildung 72 - Abhängigkeit der Kompaktheit vom Straßenwinkel (Ant)...................................................74Abbildung 73 - Abhängigkeit der Kompaktheit vom Straßenwinkel (JHotDraw)......................................75Abbildung 74 - Abhängigkeit der Kompaktheit vom Straßenwinkel (ArgoUML).......................................75Abbildung 75 - Abhängigkeit der Kompaktheit von der Repräsentation des Level 1-Knotens.............76Abbildung 76 - Kompaktheit in Abhängigkeit der Repräsentation des Level 1-Knotens (1).................77Abbildung 77 - Kompaktheit in Abhängigkeit der Repräsentation des Level 1-Knotens (2).................78Abbildung 78 - Abhängigkeit der SEPC-Kompaktheit von der Systemgröße...............................................79Abbildung 79 - Abhängigkeit der SECC-Kompaktheit von der Systemgröße...............................................79Abbildung 80 - Vorüberlegungen zur Konstruktion der konvexen Hülle.......................................................83Abbildung 81 - Bestimmung der konvexen Hülle nach dem Jarvis's March-Algorithmus.......................83

90

Documents

Diplomarbeit€¦ · konstruktive Kritik und für die vielen hilfreichen Anmerkungen. Bedanken möchte ich mich auch bei sehr guten Freunden für eine Uni-nahe Unterkunft und beste