Header

UZH-Logo

Maintenance Infos

Quadtree-based real-time point generalisation for web and mobile mapping


Bereuter, Pia. Quadtree-based real-time point generalisation for web and mobile mapping. 2015, University of Zurich, Faculty of Science.

Abstract

Die Generalisierung von Karten ist ein Kernprozess in der Kartographie und beschreibt wie räumliche Phänomene abstrahiert und lesbar auf Karten dargestellt werden. Die Anforderungen an die Generalisierung sind dabei abhängig vom gewählten Darstellungsmedium und dem Kontext, in dem die Karten angewandt werden. Für webbasierte und mobile Anwendungen gelten hohe Anforderungen an eine Generalisierung, die in Echtzeit zu erfolgen hat. Für Nutzerinnen und Nutzer von online und mobilen Anwendungen ist zudem wichtig, dass der Karteninhalt dabei flexibel angepasst werden kann (Modularität). Durch das Aufkommen neuer Kartentypen, die es erlauben, Inhalte dynamisch aus mehreren Datenquellen zu sogenannten „mash-up“ Karten zusammenzustellen, haben Punktdaten an Wichtigkeit gewonnen. Punktdaten stellen die grundlegendste, aber zugleich auch am stärksten abstrahierte Form räumlicher Daten dar. Obwohl Punktdaten zunehmend auf Karten dargestellt werden, sind Lösungen zu deren Echtzeitgeneraliserung bis heute noch wenig erforscht.
Das Hauptaugenmerk der vorliegenden Arbeit ist deswegen die Analyse und Entwick- lung von automatisierten Algorithmen, die in Echtzeit Punktdaten kartographisch generalisieren. Auf die spezifischen Bedürfnisse für web-basierte und mobile Karten und deren Integration in dynamische Darstellung wird dabei besonderen Wert gelegt. An dieser Arbeit ist speziell hervorzuheben, dass alle darin vorgeschlagenen Verfahren auf dem Quadtree beruhen, einer hierarchischen, räumlichen Datenstruktur. Obwohl der Quadtree für die kartographische Generalisierung interessante Eigenschaften aufweist, wurde diese Datenstruktur allerdings erst wenig für die Generalisierung verwendet.
Der Hauptbeitrag dieser Arbeit ist sowohl die Entwicklung einer umfassenden Methodologie, als auch eines auf dem Quadtree basierenden, modularen Systems von Operatoren und Algorithmen für die Echtzeit-Generalisierung von Punktdaten. Der Quadtree, besser gesagt der Point Region (PR) Quadtree, wird als hierarchischer, räumlicher Index und Hilfsdatenstruktur verwendet. Der PR Quadtree ermöglicht sowohl Echtzeitverhalten als auch Modularität der Algorithmen. Zusätzlich liefert er unterstützende Informationen, welche die Generalisierungsalgorithmen und -regeln unterstützen. Die Verwendung des Quadtrees erlaubt, die Dichotomie bisher aus der Literatur bekannten Ansätze zur Generalisierung in Echtzeit zu überwinden. Bisherige Ansätze zur Echtzeitgeneralisierung können in zwei Hauptansätze unterteilt werden. Dies sind einfache Generalisierungsalgorithmen mit hoher Flexibilität in der Prozessgestaltung, aber limitiert in der kartographischen Qualität und Lösungen basierend auf im Voraus berechneten, hierarchischen Datenstrukturen, von hoher kartographischer Qualität, die aber in der Flexibilität eingeschränkt sind.
Folgende Forschungsfragen waren für die Arbeit leitgebend: Welches sind notwendige Eigenschaften für eine effiziente und flexible Echtzeitgeneralisierung von Punktdaten, welche die Anforderungen von Web- und Mobilkarten erfüllt? Wie können verschiedene Arten von Operatoren zur Punktgeneralisierung in einen modularen Arbeitsablauf integriert werden? Wie kann die Interaktion mit der Kartengeneralisierung erweitert werden, um eine dynamische Erkundung von Information in Webkarten zu ermöglichen? Und schliesslich, welches sind Stärken und Schwächen von auf dem Quadtree basierenden Algorithmen zur Echtzeitgeneralisierung, und wie verhalten sie sich?
Als Erstes erfolgt die Auswahl und Kategorisierung von Methoden zur Echtzeitgeneralisierung, die Entwicklung einer umfassenden Methodologie, als auch eines problemorientierten Arbeitprozesses der Generalisierung. Die Methodologie unterscheidet zwischen zwei Hauptprinzipien in der Punktgeneralisierung: Einerseits die objekt-gerichteten Generalisierungsoperatoren, welche die Kartenobjekte direkt manipulieren und andererseits die raum-gerichtete Operatoren, die den Kartenraum deformieren, um Generalisierungsoperationen durchzuführen. Der in der Arbeit entwickelte Prototyp implementiert sowohl Lösungen für objekt- und für raumgerichtete Generalisierungsoperatoren.
Die wichtigsten objekt-gerichteten Generalisierungsoperatoren von Punktdaten sind Selektion, Vereinfachung, Aggregation und Verdrängung. Für diese Hauptoperatoren der Generalisierung schlägt die Arbeit quadtree-basierte Generalisierungsalgorithmen vor. Für den Fall der raumgerichteten Generalisierung sind zwei Ansätze umgesetzt worden, welche das Konzept des dehnbaren Raumes (’malleable space’) verwenden. Erstens dichtebasierte Kartogramme und zweitens Laplace Glättung. Der Quadtree ist bei beiden Algorithmen ein masstabsabhängiger Dichteschätzer für die räumliche Deformation.

Abstract

Die Generalisierung von Karten ist ein Kernprozess in der Kartographie und beschreibt wie räumliche Phänomene abstrahiert und lesbar auf Karten dargestellt werden. Die Anforderungen an die Generalisierung sind dabei abhängig vom gewählten Darstellungsmedium und dem Kontext, in dem die Karten angewandt werden. Für webbasierte und mobile Anwendungen gelten hohe Anforderungen an eine Generalisierung, die in Echtzeit zu erfolgen hat. Für Nutzerinnen und Nutzer von online und mobilen Anwendungen ist zudem wichtig, dass der Karteninhalt dabei flexibel angepasst werden kann (Modularität). Durch das Aufkommen neuer Kartentypen, die es erlauben, Inhalte dynamisch aus mehreren Datenquellen zu sogenannten „mash-up“ Karten zusammenzustellen, haben Punktdaten an Wichtigkeit gewonnen. Punktdaten stellen die grundlegendste, aber zugleich auch am stärksten abstrahierte Form räumlicher Daten dar. Obwohl Punktdaten zunehmend auf Karten dargestellt werden, sind Lösungen zu deren Echtzeitgeneraliserung bis heute noch wenig erforscht.
Das Hauptaugenmerk der vorliegenden Arbeit ist deswegen die Analyse und Entwick- lung von automatisierten Algorithmen, die in Echtzeit Punktdaten kartographisch generalisieren. Auf die spezifischen Bedürfnisse für web-basierte und mobile Karten und deren Integration in dynamische Darstellung wird dabei besonderen Wert gelegt. An dieser Arbeit ist speziell hervorzuheben, dass alle darin vorgeschlagenen Verfahren auf dem Quadtree beruhen, einer hierarchischen, räumlichen Datenstruktur. Obwohl der Quadtree für die kartographische Generalisierung interessante Eigenschaften aufweist, wurde diese Datenstruktur allerdings erst wenig für die Generalisierung verwendet.
Der Hauptbeitrag dieser Arbeit ist sowohl die Entwicklung einer umfassenden Methodologie, als auch eines auf dem Quadtree basierenden, modularen Systems von Operatoren und Algorithmen für die Echtzeit-Generalisierung von Punktdaten. Der Quadtree, besser gesagt der Point Region (PR) Quadtree, wird als hierarchischer, räumlicher Index und Hilfsdatenstruktur verwendet. Der PR Quadtree ermöglicht sowohl Echtzeitverhalten als auch Modularität der Algorithmen. Zusätzlich liefert er unterstützende Informationen, welche die Generalisierungsalgorithmen und -regeln unterstützen. Die Verwendung des Quadtrees erlaubt, die Dichotomie bisher aus der Literatur bekannten Ansätze zur Generalisierung in Echtzeit zu überwinden. Bisherige Ansätze zur Echtzeitgeneralisierung können in zwei Hauptansätze unterteilt werden. Dies sind einfache Generalisierungsalgorithmen mit hoher Flexibilität in der Prozessgestaltung, aber limitiert in der kartographischen Qualität und Lösungen basierend auf im Voraus berechneten, hierarchischen Datenstrukturen, von hoher kartographischer Qualität, die aber in der Flexibilität eingeschränkt sind.
Folgende Forschungsfragen waren für die Arbeit leitgebend: Welches sind notwendige Eigenschaften für eine effiziente und flexible Echtzeitgeneralisierung von Punktdaten, welche die Anforderungen von Web- und Mobilkarten erfüllt? Wie können verschiedene Arten von Operatoren zur Punktgeneralisierung in einen modularen Arbeitsablauf integriert werden? Wie kann die Interaktion mit der Kartengeneralisierung erweitert werden, um eine dynamische Erkundung von Information in Webkarten zu ermöglichen? Und schliesslich, welches sind Stärken und Schwächen von auf dem Quadtree basierenden Algorithmen zur Echtzeitgeneralisierung, und wie verhalten sie sich?
Als Erstes erfolgt die Auswahl und Kategorisierung von Methoden zur Echtzeitgeneralisierung, die Entwicklung einer umfassenden Methodologie, als auch eines problemorientierten Arbeitprozesses der Generalisierung. Die Methodologie unterscheidet zwischen zwei Hauptprinzipien in der Punktgeneralisierung: Einerseits die objekt-gerichteten Generalisierungsoperatoren, welche die Kartenobjekte direkt manipulieren und andererseits die raum-gerichtete Operatoren, die den Kartenraum deformieren, um Generalisierungsoperationen durchzuführen. Der in der Arbeit entwickelte Prototyp implementiert sowohl Lösungen für objekt- und für raumgerichtete Generalisierungsoperatoren.
Die wichtigsten objekt-gerichteten Generalisierungsoperatoren von Punktdaten sind Selektion, Vereinfachung, Aggregation und Verdrängung. Für diese Hauptoperatoren der Generalisierung schlägt die Arbeit quadtree-basierte Generalisierungsalgorithmen vor. Für den Fall der raumgerichteten Generalisierung sind zwei Ansätze umgesetzt worden, welche das Konzept des dehnbaren Raumes (’malleable space’) verwenden. Erstens dichtebasierte Kartogramme und zweitens Laplace Glättung. Der Quadtree ist bei beiden Algorithmen ein masstabsabhängiger Dichteschätzer für die räumliche Deformation.

Statistics

Downloads

8 downloads since deposited on 28 Jan 2016
4 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Dissertation
Referees:Weibel Robert, Burghardt Dirk, Mackaness William A
Communities & Collections:07 Faculty of Science > Institute of Geography
Dewey Decimal Classification:910 Geography & travel
Language:English
Date:2015
Deposited On:28 Jan 2016 13:43
Last Modified:05 Jul 2016 07:05
Number of Pages:227
Free access at:Official URL. An embargo period may apply.
Official URL:http://www.geo.uzh.ch/fileadmin/files/content/abteilungen/gis/research/phd_theses/Bereuter-2014-PhD_Thesis-Small.pdf

Download

Download PDF  'Quadtree-based real-time point generalisation for web and mobile mapping'.
Preview
Content: Published Version
Filetype: PDF
Size: 15MB