Geometric Algorithms for the Visual Exploration of Spatiotemporal Data

Abstract

The visualization of spatial data is an important research field in geoinformation science. Especially nowadays, where positioning sensors are widely spread, many (large) data sets have spatial information. As an example, take a set of bird observations where a data point corresponds to the location of a bird sighting and possibly additional information (timestamp, photo, species specification, etc.). Often, such data sets are large and complex. Visualizations from cartography allow users to explore and analyze the data. This ranges from visualizations that give an overview of the data, to tools that enable a detailed analysis of data patterns. In this thesis, we develop methods that support such visualizations. To be more precise, we apply methods from theoretical computer science to existing visualizations from cartography to improve them, e.g., to decrease the time needed to produce a visualization. <br /> This thesis has two parts. In the first part, we consider the spatiotemporal case where each data point is an event consisting of a point in space and time. For visualizing spatiotemporal data, it is common to use an interactive visualization. Here, we focus on filtering the data for time windows. Then, the data that temporally lies in the time window is visualized on a map. As visualizations, we consider three standard techniques for visualizing point sets. <br /> • A standard visualization is the representation of the events with one or multiple polygons, i.e., we aggregate the points that lie in the time window into one or multiple polygons. In particular, we build on the existing representation technique α-shapes. It is parameterized by a value α. Depending on α the representation ranges from the convex hull of the point set, over multiple, detailed polygons, to no polygons at all. Typically, one chooses an α value that still reflects the point set distribution while at the same time simplifying it. We also discuss a modification of the standard α-shapes which produces schematized α-shapes. <br /> • Another visualization of a point set is the spatial density map. Here, we overlay the map with a grid, and all grid cells that contain more data points than a given threshold are colored. Such a visualization can also color encode the number of points in the grid cells. As output, we receive a simplified and schematized aggregation of the points. <br /> • We also look at the labeling of point sets. Labeling is a standard cartography technique to display additional data information. Therefore, we place an icon (e.g., a symbol) on the map over the data point. To achieve good legibility, only a selection of labels is displayed. To guarantee a pleasant interaction for the user, the visualization must be displayed in real-time. Especially for large data sets this is a challenge. In this work, we develop data structures that guarantee a fast response time. Such data structures are called <em>time-windowed data structures</em>. As a general idea, we break down the visualizations into their atomic geometric elements. Then, we pre-process the set of all time-window queries for which each atomic geometric element is displayed. Furthermore, we also look at consistency criteria between two successive time-window queries. <br /> Especially, when the interaction is implemented in the user interface with a slider (time-window slider), an interaction with the time-window slider should not lead to flickering effects in the visualization. <br /> In the second part of the thesis, we consider a static case where we have a complex spatial geometry without any temporal information as input. While displaying this complex geometry with all its details can be needed for a thorough analysis, it can be unclear and overwhelming for a user who wants a high-level overview. For example, think of a very detailed border of a country. Often, such a border is used as an underlying base map to give the user a spatial orientation. To not distract the reader from the data that lies over the base map, the base map should not be too detailed. Hence, simplifying the border can be necessary for clear and readable visualizations. We simplify polygons by hulls i.e., a polygon that contains the input polygon.

Die Visualisierung räumlicher Daten ist ein wichtiges Forschungsgebiet der Geoinformatik. Eine Vielzahl der heutzutage erzeugten Daten haben einen räumlichen Bezug, da Sensoren zur Positionsbestimmung (z.B. mittels GPS) weit verbreitet sind. Ein Beispiel für räumliche Daten sind Vogelbeobachtungen: ein Datenpunkt entspricht der Position und dem Zeitpunkt des beobachteten Vogels und ggf. zusätzlichen Informationen wie Fotos oder Angaben zur Spezies. Räumliche Datensätze sind oftmals groß und komplex. Die Visualisierung der Daten ermöglicht es, die Daten zu untersuchen und zu analysieren. In dieser Arbeit werden Methoden entwickelt, die solche Visualisierungen unterstützen. Dafür werden Visualisierungstechniken aus der Kartographie mit Methoden aus der theoretischen Informatik kombiniert, um z.B. die Berechnungszeit einer Visualisierung zu verringern. <br /> Diese Arbeit besteht aus zwei Teilen. Im ersten Teil werden raum-zeitliche Daten betrachtet. Hier entspricht jeder Datenpunkt einem Punkt in Raum und Zeit. Für solche raum-zeitliche Daten werden oftmals interaktive Visualisierungen verwendet, wo Nutzer die Daten mittels Zeitfenstern filtern können. Die Daten, welche in dem angefragten Zeitfenster liegen, werden auf einer Karte visualisiert. Da solch eine Visualisierung unübersichtlich werden kann, werden in der Kartographie häufig Techniken verwendet, welche die Übersichtlichkeit erhalten. In dieser Arbeit werden folgende Techniken diskutiert: <br /> • In der Kartographie wird eine Punktmenge häufig durch ein oder mehrere Polygone repräsentiert. Dies kann es erleichtern räumliche Muster zu erkennen und die visuelle Darstellung zu vereinfachen. Ein verbreiteter Ansatz für die Repräsentation mit Polygonen sind α-Shapes. Abhängig von der Wahl des Parameters α entspricht das α-Shape der konvexen Hülle der Punktmenge, oder mehreren detaillierten Polygonen, oder der Eingabepunktmenge. Üblicherweise wählt man einen α Wert, der die Verteilung der Punktmenge widerspiegelt und sie gleichzeitig vereinfacht. In dieser Arbeit wird eine Modifikation der α-Shapes eingeführt, welche schematisierte α-Shapes erzeugt. <br /> • Eine weitere Visualisierung einer Punktmenge ist die Spatial Density Map. Dazu wird die Karte mit einem Gitter überlagert, und alle Gitterzellen, die mehr Datenpunkte enthalten als ein festgelegter Schwellenwert, werden eingefärbt. Eine solche Visualisierung kann auch die Anzahl der Punkte in den Gitterzellen farblich kodieren. Eine Spatial Density Map ist eine vereinfachte und schematisierte Aggregation der Punkte. <br /> • Eine weitere Standardtechnik der Kartographie für die Darstellung von zusätzlichen Dateninformationen basiert darauf, dass Symbole oder Beschriftungen in der Karte über eine Auswahl der Punkte aus der Punktmenge platziert werden. Die Symbole können beispielsweise Icons sein, welche den Typ des Datenpunktes beschreiben oder die Beschriftung kann dem Namen des Datenpunktes entsprechen. Um eine gute Lesbarkeit zu garantieren und überlappende Symbole oder Beschriftungen zu vermeiden, wird nur eine Auswahl der Symbole oder Beschriftungen angezeigt. <br /> Um eine angenehme Interaktion für den Nutzer zu gewährleisten, sollte die Visualisierung in Echtzeit dargestellt werden. Besonders bei großen Datenmengen ist dies eine Herausforderung und on-demand Berechnungen reichen oftmals nicht aus. In dieser Arbeit werden Datenstrukturen entwickelt, die eine schnelle Visualisierung ermöglichen. Solche Datenstrukturen für Zeitfensterfilterung werden in der Literatur als <em>Time-Windowed Data Structures</em> bezeichnet. Für diese Datenstrukturen werden die Visualisierungen in ihre atomaren geometrischen Elemente zerlegt. Für diese atomaren geometrischen Elementen werden alle Zeitfenster bestimmt, für die das Element dargestellt wird. Darüber hinaus betrachten wir auch Konsistenzkriterien zwischen aufeinanderfolgenden Zeitfensterfilterungen. Insbesondere wenn die Interaktion in der Benutzeroberfläche mit einem Schieberegler (Time-Slider) implementiert ist, sollte eine Interaktion nicht zu Flackereffekten in der Visualisierung führen. <br /> Im zweiten Teil der Arbeit wird das Szenario betrachtet, bei dem komplexe räumliche Daten ohne zeitliche Information vorliegen, welche visualisiert werden sollen. Während die Darstellung dieser komplexen Geometrie mit all ihren Details für eine gründliche Analyse erforderlich sein kann, kann sie für Nutzer, welche sich einen Überblick verschaffen möchten, unübersichtlich und überwältigend sein. Ein Beispiel ist eine sehr detaillierte Landesgrenze, welche in Basiskarten verwendet wird, um Nutzern eine räumliche Orientierung zu geben. Um die Nutzer nicht von den dargestellten Daten abzulenken, sollte die Basiskarte nicht zu kleinteilig sein. Daher kann eine Vereinfachung der Grenze notwendig sein, um eine klare und lesbare Visualisierung zu erreichen. In diesem Teil der Arbeit werden polygonale Hüllen diskutiert, welche komplexe Eingabepolygone vereinfachen.