Maps are the main tool to represent geographical information. Geographical information is usually scale-dependent, so users need to have access to maps at different scales. In our digital age, the access is realized by zooming. As discrete changes during the zooming tend to distract users, smooth changes are preferred. This is why some digital maps are trying to make the zooming as continuous as they can. The process of producing maps at different scales with smooth changes is called continuous map generalization. In order to produce maps of high quality, cartographers often take into account additional requirements. These requirements are transferred to models in map generalization. Optimization for map generalization is important not only because it finds optimal solutions in the sense of the models, but also because it helps us to evaluate the quality of the models. Optimization, however, becomes more delicate when we deal with continuous map generalization. In this area, there are requirements not only for a specific map but also for relations between maps at difference scales. This thesis is about continuous map generalization based on optimization. First, we show the background of our research topics. Second, we find optimal sequences for aggregating land-cover areas. We compare the A$^{\!\star}$\xspace algorithm and integer linear programming in completing this task. Third, we continuously generalize county boundaries to provincial boundaries based on compatible triangulations. We morph between the two sets of boundaries, using dynamic programming to compute the correspondence. Fourth, we continuously generalize buildings to built-up areas by aggregating and growing. In this work, we group buildings with the help of a minimum spanning tree. Fifth, we define vertex trajectories that allow us to morph between polylines. We require that both the angles and the edge lengths change linearly over time. As it is impossible to fulfill all of these requirements simultaneously, we mediate between them using least-squares adjustment. Sixth, we discuss the performance of some commonly used data structures for a specific spatial problem. Seventh, we conclude this thesis and present open problems. / Maps are the main tool to represent geographical information. Users often zoom in and out to access maps at different scales. Continuous map generalization tries to make the changes between different scales smooth, which is essential to provide users with comfortable zooming experience. In order to achieve continuous map generalization with high quality, we optimize some important aspects of maps. In this book, we have used optimization in the generalization of land-cover areas, administrative boundaries, buildings, and coastlines. According to our experiments, continuous map generalization indeed benefits from optimization. / Landkarten sind das wichtigste Werkzeug zur Repräsentation geografischer Information. Unter der Generalisierung von Landkarten versteht man die Aufbereitung von geografischen Informationen aus detaillierten Daten zur Generierung von kleinmaßstäbigen Karten. Nutzer von Online-Karten zoomen oft in eine Karte hinein oder aus einer Karte heraus, um mehr Details bzw. mehr Überblick zu bekommen. Die kontinuierliche Generalisierung von Landkarten versucht die Änderungen zwischen verschiedenen Maßstäben stetig zu machen. Dies ist wichtig, um Nutzern eine angenehme Zoom-Erfahrung zu bieten. Um eine qualitativ hochwertige kontinuierliche Generalisierung zu erreichen, kann man wichtige Aspekte bei der Generierung von Online-Karten optimieren. In diesem Buch haben wir Optimierung bei der Generalisierung von Landnutzungskarten, von administrativen Grenzen, Gebäuden und Küstenlinien eingesetzt. Unsere Experimente zeigen, dass die kontinuierliche Generalisierung von Landkarten in der Tat von Optimierung profitiert.

The process of performing cartographic generalization in an automatic way applied on geographic information is of highly interest in the field of cartography, both in academia and industry. Many research e↵orts have been done to implement di↵erent automatic generalization approaches. Being able to answer the research question on automatic generalization, another interesting question opens up: ”Is it possible to retrieve and visualize geographic information in any arbitrary scale?” This is the question in the field of vario-scale geoinformation. Potential research works should answer this question with solutions which provide valid and efficient representation of geoinformation in any on-demand scale. More brilliant solutions will also provide smooth transitions between these on-demand arbitrary scales. Space-Scale-Cube (Meijers and Van Oosterom 2011) is a reactive tree (Van Oosterom 1991) data structure which shows positive potential for achieving smooth automatic vario-scale generalization of area features. The topic of this research work is investigation of adaptation of this approach on an interesting class of geographic information: road networks datasets. Firstly theoretical background will be introduced and discussed and afterwards, implementing the adaptation would be described. This research work includes development of a hierarchical data structure based on road network datasets and the potential use of this data structure in vario-scale geoinformation retrieval and visualization.

Die Region Mestia liegt abgeschieden im Norden Georgiens im Großen Kaukasus. Markant für die Region Mestia ist der Doppelgipfel der Ushba. Dieser zieht Touristen an, welche Wandertouren und Erkundungen durchführen möchten. Um diese sicher gewährleisten zu können, ist eine Alpenvereinskarte dringend erforderlich. In dieser Arbeit wird eine Generalisierung des Gebäudedatenbestand der Region Mestia mit Hilfe der Geoinformationssoftware ArcGIS Pro für eine ebensolche Alpenvereinskarte erstellt. Als Ausgangsdaten werden OpenStreetMap-Datensätze verwendet. Es werden die für den Zweck dieser Karte relevanten Daten herausgefiltert und alle unwichtigen Elemente entfernt. Zudem werden alle Stützpunkte der Gebäude gebildet und deren Abstand zueinander mittels eines dichte basierten Clustering bestimmt. Im Anschluss werden die Stützpunkte den Gebäude-Polygonen zugewiesen. Anhand der Abstandsbestimmung kann im Folgenden eine Unterscheidung der Gebäude in zwei Kategorien vorgenommen werden. Einzelnstehende Gebäude bzw. Gebäude mit einer sehr geringen Anzahl an Gebäuden in der unmittelbaren Nachbarschaft werden der Kategorie „Einzelgebäude“ zugeordnet. Alle anderen Gebäude werden in die Kategorie „Siedlung“ eingegliedert, da diese Gebäude sehr zahlreich und dicht beieinanderstehen. Die beiden Kategorien werden unterschiedlich generalisiert. Die Gebäude, die der Kategorie „Einzelgebäude“ zugeordnet sind, werden vereinfacht und als Punktsignaturen dargestellt. Alle anderen Gebäude werden aggregiert und Polygone mit einem geringen Flächeninhalt eliminiert. Zudem werden die Außenkanten der Polygone geglättet, damit ein vereinfachter Grundriss der Gebäude vorliegt. In einer Evaluierung wird die erstellte Generalisierung des Gebäudebestandes mit einer weiteren Gebäudegeneralisierung, welche mit dem Programm QGIS erstellt ist, gegenübergestellt. Den Expert*innen werden zudem Bilder von den Gebäuden der Region und zwei Beispielkarten, auf denen die generalisierten Gebäude dargestellt sind, gezeigt. Es ist zu entscheiden, welche Karte die Gebäude auf dem Bild abbildet. In dieser Arbeit wird die unterschiedliche Generalisierung der Einzelgebäude und der Siedlungen betrachtet. Die Unterschiede dieser beiden Kategorien wird herausgearbeitet. Mittels der Evaluierung wird das Ergebnis von Expert*innen überprüft. / The Mestia region is in the north of Georgia in the Great Caucasus. A distinctive feature of the Mestia region is the double peak of the Ushba. It attracts tourists who want to go hiking and exploring. To be able to guarantee this safely, an alpine association map is urgently needed. In this work, a generalisation of the building data stock of the Mestia region is created with the help of the geoinformation software ArcGIS Pro for a similar alpine association map. OpenStreetMap datasets are used as source data. The data relevant for the purpose of this map are filtered out and all unimportant elements are removed. In addition, all support points of the buildings are formed and their distance to each other is determined using density based clustering. Subsequently, the support points are assigned to the building polygons. Based on the distance determination, the buildings can be divided into two categories. Single buildings or buildings with a very small number of buildings in the immediate vicinity are assigned to the category 'single building'. All other buildings are placed in the category 'Settlement', as these buildings are very numerous and close together. The two categories are generalised differently. The buildings assigned to the category 'single building' are simplified and represented as point signatures. All other buildings are aggregated and polygons with a small area are eliminated. In addition, the outer edges of the polygons are smoothed so that a simplified ground plan of the buildings is available. In an evaluation, the created generalisation of the building stock is compared with another building generalisation created with the QGIS programme. The experts are also shown pictures of the buildings in the region and two sample maps showing the generalised buildings. It must be decided which map depicts the buildings on the picture. In this paper, the different generalisation of individual buildings and settlements is considered. The differences between these two categories will be worked out. By means of evaluation, the result is checked by experts.

The process of performing cartographic generalization in an automatic way applied on geographic information is of highly interest in the field of cartography, both in academia and industry. Many research e↵orts have been done to implement di↵erent automatic generalization approaches. Being able to answer the research question on automatic generalization, another interesting question opens up: ”Is it possible to retrieve and visualize geographic information in any arbitrary scale?” This is the question in the field of vario-scale geoinformation. Potential research works should answer this question with solutions which provide valid and efficient representation of geoinformation in any on-demand scale. More brilliant solutions will also provide smooth transitions between these on-demand arbitrary scales. Space-Scale-Cube (Meijers and Van Oosterom 2011) is a reactive tree (Van Oosterom 1991) data structure which shows positive potential for achieving smooth automatic vario-scale generalization of area features. The topic of this research work is investigation of adaptation of this approach on an interesting class of geographic information: road networks datasets. Firstly theoretical background will be introduced and discussed and afterwards, implementing the adaptation would be described. This research work includes development of a hierarchical data structure based on road network datasets and the potential use of this data structure in vario-scale geoinformation retrieval and visualization.:Declaration of Authorship i Abstract iii Acknowledgements iv List of Figures vii Abbreviations viii 1 Introduction 1 1.1 Problem Definition 2 1.1.1 Research Questions 2 1.1.2 Objectives 3 1.2 Proposed Solution 3 1.3 Structure of the Thesis 4 1.4 Notes on Terminology 4 2 Cartographic Generalization 6 2.1 Cartographic Generalization: Definitions and Classifications 6 2.2 Generalization Operators 9 2.3 Efforts on Vario-Scale Visualization of Geoinformation 10 2.4 Efforts on Generalization of Road Networks and Similar Other Networks 16 2.4.1 Geometric Generalization of Networks 17 2.4.2 Model Generalization of Networks 18 2.5 Clarification of Interest 20 3 Theory of Road Network SSC 21 3.1 Background of an SSC 21 3.1.1 tGAP 21 3.1.2 Smoothing tGAP 23 3.2 Road Network as a ’Network’ 24 3.2.1 Short Background on Graph Theory 5 3.3 Formation of Road Network SSC 26 3.3.1 Geometry 26 3.3.2 Network Topology 27 3.3.3 Building up tGAP on The Road Network 28 3.3.4 Smoothing of Road Network SSC 31 3.3.4.1 Smoothing Elimination 32 3.3.4.2 Smoothing Simplification 32 3.4 Reading from a road network SSC 34 3.4.1 Discussion on Scale 34 3.4.2 Iterating Over The Forest 35 3.4.3 Planar Slices 35 3.4.4 Non-Planar Slices 36 4 Implementation of Road Network SSC 37 4.1 General Information Regarding The Implementation 37 4.1.1 Programming Language 37 4.1.2 RDBMS 38 4.1.3 Geometry Library 39 4.1.4 Graph Library 39 4.2 Data Structure 40 4.2.1 Node 40 4.2.2 Edge 41 4.2.3 Edge-Node-Relation 41 4.3 Software Architecture 42 4.3.1 More Detail on Building The SSC 42 4.3.1.1 Initial Data Processing 42 4.3.1.2 Network Processing 43 4.3.2 More Detail on Querying The SSC 46 4.3.2.1 Database Query 46 4.3.2.2 Building Geometry 46 4.3.2.3 Interface and Visualization 47 4.4 Results 48 5 Conclusions and Outlook 49 Bibliography 51

Die mapChart GmbH bietet einen Softwaredienst an, der es ermöglicht, auf der Grundlage von teilweise kundenspezifischen Basisgeometrien vektorbasierte Karten zu erstellen. Primäres Ausgabemedium ist dabei die Bildschirmkarte des JAVA-Clients im Webbrowser. PDF-Export und Druck sind ebenso möglich. Bei der Kartenerstellung ist der Anwender nicht an vorgegebene Maßstäbe gebunden, sondern kann frei wählen, welches Gebiet in welcher Größe dargestellt werden soll. Hierdurch ergeben sich komplexe Aufgabenstellungen für die kartografische Generalisierung. Diese Probleme und deren bisherige Lösungen durch das Unternehmen werden im ersten Teil der Arbeit diskutiert, wobei verschiedene wissenschaftliche Arbeiten für spezielle Teilaufgaben der Generalisierung kurz vorgestellt werden. Selektion und Formvereinfachung gelten als die wichtigsten Generalisierungsschritte. Während die Selektion mit den vorhandenen Methoden von Geodatenbanken relativ problemlos realisiert werden kann, stellt die Formvereinfachung ein umfangreiches Problem dar. Das Hauptaugenmerk der Arbeit richtet sich deswegen auf die rechnergestützte Liniengeneralisierung verbunden mit dem Ziel, überflüssige Stützpunkte mit Hilfe von Algorithmen zur Linienvereinfachung einzusparen. Ergebnis sind schnellere Übertragungszeiten der Kartenvektordaten zum Anwender sowie eine Beschleunigung raumbezogener Analysen, wie z. B. Flächenverschneidungen. Des weiteren werden Verbesserungen in der Darstellung angestrebt. Ein geeigneter Algorithmus zeichnet sich durch eine geringe Beanspruchung der Ressourcen Zeit und Speicherbedarf aus. Weiterhin spielt der erreichbare Grad der Verringerung der Stützpunktmenge bei akzeptabler Kartenqualität eine entscheidende Rolle. Nicht zuletzt sind topologische Aspekte und der Implementierungsaufwand zu beachten. Die Arbeit gibt einen umfassenden Überblick über vorhandene Ansätze zur Liniengeneralisierung und leitet aus der Diskussion der Vor- und Nachteile zwei geeignete Algorithmen für die Implementierung mit der Programmiersprache JAVA ab. Die Ergebnisse der Verfahren nach Douglas-Peucker und Visvalingam werden hinsichtlich der Laufzeiten, des Grades der Verringerung der Stützpunktmenge sowie der Qualität der Kartendarstellung verglichen, wobei sich für die Visvalingam-Variante leichte Vorteile ergeben. Eine Parameterkonfiguration für den konkreten Einsatz der Vereinfachungsmethode in das GIS der mapChart GmbH wird vorgeschlagen. Die Vereinfachung von Polygonnetzen stellt eine Erweiterung des Problems der Liniengeneralisierung dar. Hierbei müssen topologische Aspekte beachtet werden, was besonders schwierig ist, wenn die Ausgangsdaten nicht topologisch strukturiert vorliegen. Für diese Aufgabe wurde ein neuer Algorithmus entwickelt und ebenfalls in JAVA implementiert. Die Implementierung dieses Algorithmus und damit erreichbaren Ergebnisse werden anhand von zwei Testdatensätzen vorgestellt, jedoch zeigt sich, dass die wichtige Bedingung der Echtzeitfähigkeit nicht erfüllt wird. Damit ergibt sich, dass der Algorithmus zur Netzvereinfachung nur offline benutzt werden sollte. / MapChart GmbH offers a software service, which allows users to create customized, vector-based maps using vendor as well as customer geometric and attributive data. Target delivery media is the on-screen map of the JAVA client within the web browser. PDF export and print are also supported. Map production is not limited to specific scales. The user can choose which area at which scale is shown. This triggers complex tasks for cartographic generalization. Current solutions by the company are discussed and scientific work for selected tasks will be presented shortly. Selection and Simplification are known as the most important steps of generalization. While selection can be managed sufficiently by geo databases, simplification poses considerably problems. The main focus of the thesis is the computational line generalization aiming on reducing the amount of points by simplification. Results are an increased speed of server to client communication and better performance of spatial analysis, such as intersection. Furthermore enhancements for the portrayal of maps are highlighted. An appropriate algorithm minimizes the demands for the resources time and memory. Furthermore the obtainable level of simplification by still producing acceptable map quality plays an important role. Last but not least efforts for the implementation of the algorithm and topology are important. The thesis discusses a broad overview of existing approaches to line simplification. Two appropriate algorithms for the implementation using the programming language JAVA will be proposed. The results of the methods of Visvalingam and Douglas-Peucker will be discussed with regards to performance, level of point reduction and map quality. Recommended parameters for the implementation in the software of MapChart GmbH are derived. The simplification of polygon meshes will be an extension of the line generalization. Topological constraints need to be considered. This task needs a sophisticated approach as the raw data is not stored in a topological structure. For this task a new algorithm was developed. It was also implemented using JAVA. The results of the testing scenario show that the constraint of real-time performance cannot be fulfilled. Hence it is recommended to use the algorithm for the polygon mesh simplification offline only.

Die mapChart GmbH bietet einen Softwaredienst an, der es ermöglicht, auf der Grundlage von teilweise kundenspezifischen Basisgeometrien vektorbasierte Karten zu erstellen. Primäres Ausgabemedium ist dabei die Bildschirmkarte des JAVA-Clients im Webbrowser. PDF-Export und Druck sind ebenso möglich. Bei der Kartenerstellung ist der Anwender nicht an vorgegebene Maßstäbe gebunden, sondern kann frei wählen, welches Gebiet in welcher Größe dargestellt werden soll. Hierdurch ergeben sich komplexe Aufgabenstellungen für die kartografische Generalisierung. Diese Probleme und deren bisherige Lösungen durch das Unternehmen werden im ersten Teil der Arbeit diskutiert, wobei verschiedene wissenschaftliche Arbeiten für spezielle Teilaufgaben der Generalisierung kurz vorgestellt werden. Selektion und Formvereinfachung gelten als die wichtigsten Generalisierungsschritte. Während die Selektion mit den vorhandenen Methoden von Geodatenbanken relativ problemlos realisiert werden kann, stellt die Formvereinfachung ein umfangreiches Problem dar. Das Hauptaugenmerk der Arbeit richtet sich deswegen auf die rechnergestützte Liniengeneralisierung verbunden mit dem Ziel, überflüssige Stützpunkte mit Hilfe von Algorithmen zur Linienvereinfachung einzusparen. Ergebnis sind schnellere Übertragungszeiten der Kartenvektordaten zum Anwender sowie eine Beschleunigung raumbezogener Analysen, wie z. B. Flächenverschneidungen. Des weiteren werden Verbesserungen in der Darstellung angestrebt. Ein geeigneter Algorithmus zeichnet sich durch eine geringe Beanspruchung der Ressourcen Zeit und Speicherbedarf aus. Weiterhin spielt der erreichbare Grad der Verringerung der Stützpunktmenge bei akzeptabler Kartenqualität eine entscheidende Rolle. Nicht zuletzt sind topologische Aspekte und der Implementierungsaufwand zu beachten. Die Arbeit gibt einen umfassenden Überblick über vorhandene Ansätze zur Liniengeneralisierung und leitet aus der Diskussion der Vor- und Nachteile zwei geeignete Algorithmen für die Implementierung mit der Programmiersprache JAVA ab. Die Ergebnisse der Verfahren nach Douglas-Peucker und Visvalingam werden hinsichtlich der Laufzeiten, des Grades der Verringerung der Stützpunktmenge sowie der Qualität der Kartendarstellung verglichen, wobei sich für die Visvalingam-Variante leichte Vorteile ergeben. Eine Parameterkonfiguration für den konkreten Einsatz der Vereinfachungsmethode in das GIS der mapChart GmbH wird vorgeschlagen. Die Vereinfachung von Polygonnetzen stellt eine Erweiterung des Problems der Liniengeneralisierung dar. Hierbei müssen topologische Aspekte beachtet werden, was besonders schwierig ist, wenn die Ausgangsdaten nicht topologisch strukturiert vorliegen. Für diese Aufgabe wurde ein neuer Algorithmus entwickelt und ebenfalls in JAVA implementiert. Die Implementierung dieses Algorithmus und damit erreichbaren Ergebnisse werden anhand von zwei Testdatensätzen vorgestellt, jedoch zeigt sich, dass die wichtige Bedingung der Echtzeitfähigkeit nicht erfüllt wird. Damit ergibt sich, dass der Algorithmus zur Netzvereinfachung nur offline benutzt werden sollte. / MapChart GmbH offers a software service, which allows users to create customized, vector-based maps using vendor as well as customer geometric and attributive data. Target delivery media is the on-screen map of the JAVA client within the web browser. PDF export and print are also supported. Map production is not limited to specific scales. The user can choose which area at which scale is shown. This triggers complex tasks for cartographic generalization. Current solutions by the company are discussed and scientific work for selected tasks will be presented shortly. Selection and Simplification are known as the most important steps of generalization. While selection can be managed sufficiently by geo databases, simplification poses considerably problems. The main focus of the thesis is the computational line generalization aiming on reducing the amount of points by simplification. Results are an increased speed of server to client communication and better performance of spatial analysis, such as intersection. Furthermore enhancements for the portrayal of maps are highlighted. An appropriate algorithm minimizes the demands for the resources time and memory. Furthermore the obtainable level of simplification by still producing acceptable map quality plays an important role. Last but not least efforts for the implementation of the algorithm and topology are important. The thesis discusses a broad overview of existing approaches to line simplification. Two appropriate algorithms for the implementation using the programming language JAVA will be proposed. The results of the methods of Visvalingam and Douglas-Peucker will be discussed with regards to performance, level of point reduction and map quality. Recommended parameters for the implementation in the software of MapChart GmbH are derived. The simplification of polygon meshes will be an extension of the line generalization. Topological constraints need to be considered. This task needs a sophisticated approach as the raw data is not stored in a topological structure. For this task a new algorithm was developed. It was also implemented using JAVA. The results of the testing scenario show that the constraint of real-time performance cannot be fulfilled. Hence it is recommended to use the algorithm for the polygon mesh simplification offline only.

Zugl.: Hannover, Universiẗat, Diss., 2004.

Die mapChart GmbH bietet einen Softwaredienst an, der es ermöglicht, auf der Grundlage von teilweise kundenspezifischen Basisgeometrien vektorbasierte Karten zu erstellen. Primäres Ausgabemedium ist dabei die Bildschirmkarte des JAVA-Clients im Webbrowser. PDF-Export und Druck sind ebenso möglich. Bei der Kartenerstellung ist der Anwender nicht an vorgegebene Maßstäbe gebunden, sondern kann frei wählen, welches Gebiet in welcher Größe dargestellt werden soll. Hierdurch ergeben sich komplexe Aufgabenstellungen für die kartografische Generalisierung. Diese Probleme und deren bisherige Lösungen durch das Unternehmen werden im ersten Teil der Arbeit diskutiert, wobei verschiedene wissenschaftliche Arbeiten für spezielle Teilaufgaben der Generalisierung kurz vorgestellt werden. Selektion und Formvereinfachung gelten als die wichtigsten Generalisierungsschritte. Während die Selektion mit den vorhandenen Methoden von Geodatenbanken relativ problemlos realisiert werden kann, stellt die Formvereinfachung ein umfangreiches Problem dar. Das Hauptaugenmerk der Arbeit richtet sich deswegen auf die rechnergestützte Liniengeneralisierung verbunden mit dem Ziel, überflüssige Stützpunkte mit Hilfe von Algorithmen zur Linienvereinfachung einzusparen. Ergebnis sind schnellere Übertragungszeiten der Kartenvektordaten zum Anwender sowie eine Beschleunigung raumbezogener Analysen, wie z. B. Flächenverschneidungen. Des weiteren werden Verbesserungen in der Darstellung angestrebt. Ein geeigneter Algorithmus zeichnet sich durch eine geringe Beanspruchung der Ressourcen Zeit und Speicherbedarf aus. Weiterhin spielt der erreichbare Grad der Verringerung der Stützpunktmenge bei akzeptabler Kartenqualität eine entscheidende Rolle. Nicht zuletzt sind topologische Aspekte und der Implementierungsaufwand zu beachten. Die Arbeit gibt einen umfassenden Überblick über vorhandene Ansätze zur Liniengeneralisierung und leitet aus der Diskussion der Vor- und Nachteile zwei geeignete Algorithmen für die Implementierung mit der Programmiersprache JAVA ab. Die Ergebnisse der Verfahren nach Douglas-Peucker und Visvalingam werden hinsichtlich der Laufzeiten, des Grades der Verringerung der Stützpunktmenge sowie der Qualität der Kartendarstellung verglichen, wobei sich für die Visvalingam-Variante leichte Vorteile ergeben. Eine Parameterkonfiguration für den konkreten Einsatz der Vereinfachungsmethode in das GIS der mapChart GmbH wird vorgeschlagen. Die Vereinfachung von Polygonnetzen stellt eine Erweiterung des Problems der Liniengeneralisierung dar. Hierbei müssen topologische Aspekte beachtet werden, was besonders schwierig ist, wenn die Ausgangsdaten nicht topologisch strukturiert vorliegen. Für diese Aufgabe wurde ein neuer Algorithmus entwickelt und ebenfalls in JAVA implementiert. Die Implementierung dieses Algorithmus und damit erreichbaren Ergebnisse werden anhand von zwei Testdatensätzen vorgestellt, jedoch zeigt sich, dass die wichtige Bedingung der Echtzeitfähigkeit nicht erfüllt wird. Damit ergibt sich, dass der Algorithmus zur Netzvereinfachung nur offline benutzt werden sollte.:1 Einleitung 2 Kartografische Generalisierung 3 Algorithmen zur Liniengeneralisierung 4 Implementierung 5 Ergebnisse 6 Ausblick 7 Zusammenfassung / MapChart GmbH offers a software service, which allows users to create customized, vector-based maps using vendor as well as customer geometric and attributive data. Target delivery media is the on-screen map of the JAVA client within the web browser. PDF export and print are also supported. Map production is not limited to specific scales. The user can choose which area at which scale is shown. This triggers complex tasks for cartographic generalization. Current solutions by the company are discussed and scientific work for selected tasks will be presented shortly. Selection and Simplification are known as the most important steps of generalization. While selection can be managed sufficiently by geo databases, simplification poses considerably problems. The main focus of the thesis is the computational line generalization aiming on reducing the amount of points by simplification. Results are an increased speed of server to client communication and better performance of spatial analysis, such as intersection. Furthermore enhancements for the portrayal of maps are highlighted. An appropriate algorithm minimizes the demands for the resources time and memory. Furthermore the obtainable level of simplification by still producing acceptable map quality plays an important role. Last but not least efforts for the implementation of the algorithm and topology are important. The thesis discusses a broad overview of existing approaches to line simplification. Two appropriate algorithms for the implementation using the programming language JAVA will be proposed. The results of the methods of Visvalingam and Douglas-Peucker will be discussed with regards to performance, level of point reduction and map quality. Recommended parameters for the implementation in the software of MapChart GmbH are derived. The simplification of polygon meshes will be an extension of the line generalization. Topological constraints need to be considered. This task needs a sophisticated approach as the raw data is not stored in a topological structure. For this task a new algorithm was developed. It was also implemented using JAVA. The results of the testing scenario show that the constraint of real-time performance cannot be fulfilled. Hence it is recommended to use the algorithm for the polygon mesh simplification offline only.:1 Einleitung 2 Kartografische Generalisierung 3 Algorithmen zur Liniengeneralisierung 4 Implementierung 5 Ergebnisse 6 Ausblick 7 Zusammenfassung

Die mapChart GmbH bietet einen Softwaredienst an, der es ermöglicht, auf der Grundlage von teilweise kundenspezifischen Basisgeometrien vektorbasierte Karten zu erstellen. Primäres Ausgabemedium ist dabei die Bildschirmkarte des JAVA-Clients im Webbrowser. PDF-Export und Druck sind ebenso möglich. Bei der Kartenerstellung ist der Anwender nicht an vorgegebene Maßstäbe gebunden, sondern kann frei wählen, welches Gebiet in welcher Größe dargestellt werden soll. Hierdurch ergeben sich komplexe Aufgabenstellungen für die kartografische Generalisierung. Diese Probleme und deren bisherige Lösungen durch das Unternehmen werden im ersten Teil der Arbeit diskutiert, wobei verschiedene wissenschaftliche Arbeiten für spezielle Teilaufgaben der Generalisierung kurz vorgestellt werden. Selektion und Formvereinfachung gelten als die wichtigsten Generalisierungsschritte. Während die Selektion mit den vorhandenen Methoden von Geodatenbanken relativ problemlos realisiert werden kann, stellt die Formvereinfachung ein umfangreiches Problem dar. Das Hauptaugenmerk der Arbeit richtet sich deswegen auf die rechnergestützte Liniengeneralisierung verbunden mit dem Ziel, überflüssige Stützpunkte mit Hilfe von Algorithmen zur Linienvereinfachung einzusparen. Ergebnis sind schnellere Übertragungszeiten der Kartenvektordaten zum Anwender sowie eine Beschleunigung raumbezogener Analysen, wie z. B. Flächenverschneidungen. Des weiteren werden Verbesserungen in der Darstellung angestrebt. Ein geeigneter Algorithmus zeichnet sich durch eine geringe Beanspruchung der Ressourcen Zeit und Speicherbedarf aus. Weiterhin spielt der erreichbare Grad der Verringerung der Stützpunktmenge bei akzeptabler Kartenqualität eine entscheidende Rolle. Nicht zuletzt sind topologische Aspekte und der Implementierungsaufwand zu beachten. Die Arbeit gibt einen umfassenden Überblick über vorhandene Ansätze zur Liniengeneralisierung und leitet aus der Diskussion der Vor- und Nachteile zwei geeignete Algorithmen für die Implementierung mit der Programmiersprache JAVA ab. Die Ergebnisse der Verfahren nach Douglas-Peucker und Visvalingam werden hinsichtlich der Laufzeiten, des Grades der Verringerung der Stützpunktmenge sowie der Qualität der Kartendarstellung verglichen, wobei sich für die Visvalingam-Variante leichte Vorteile ergeben. Eine Parameterkonfiguration für den konkreten Einsatz der Vereinfachungsmethode in das GIS der mapChart GmbH wird vorgeschlagen. Die Vereinfachung von Polygonnetzen stellt eine Erweiterung des Problems der Liniengeneralisierung dar. Hierbei müssen topologische Aspekte beachtet werden, was besonders schwierig ist, wenn die Ausgangsdaten nicht topologisch strukturiert vorliegen. Für diese Aufgabe wurde ein neuer Algorithmus entwickelt und ebenfalls in JAVA implementiert. Die Implementierung dieses Algorithmus und damit erreichbaren Ergebnisse werden anhand von zwei Testdatensätzen vorgestellt, jedoch zeigt sich, dass die wichtige Bedingung der Echtzeitfähigkeit nicht erfüllt wird. Damit ergibt sich, dass der Algorithmus zur Netzvereinfachung nur offline benutzt werden sollte.:1 Einleitung 2 Kartografische Generalisierung 3 Algorithmen zur Liniengeneralisierung 4 Implementierung 5 Ergebnisse 6 Ausblick 7 Zusammenfassung / MapChart GmbH offers a software service, which allows users to create customized, vector-based maps using vendor as well as customer geometric and attributive data. Target delivery media is the on-screen map of the JAVA client within the web browser. PDF export and print are also supported. Map production is not limited to specific scales. The user can choose which area at which scale is shown. This triggers complex tasks for cartographic generalization. Current solutions by the company are discussed and scientific work for selected tasks will be presented shortly. Selection and Simplification are known as the most important steps of generalization. While selection can be managed sufficiently by geo databases, simplification poses considerably problems. The main focus of the thesis is the computational line generalization aiming on reducing the amount of points by simplification. Results are an increased speed of server to client communication and better performance of spatial analysis, such as intersection. Furthermore enhancements for the portrayal of maps are highlighted. An appropriate algorithm minimizes the demands for the resources time and memory. Furthermore the obtainable level of simplification by still producing acceptable map quality plays an important role. Last but not least efforts for the implementation of the algorithm and topology are important. The thesis discusses a broad overview of existing approaches to line simplification. Two appropriate algorithms for the implementation using the programming language JAVA will be proposed. The results of the methods of Visvalingam and Douglas-Peucker will be discussed with regards to performance, level of point reduction and map quality. Recommended parameters for the implementation in the software of MapChart GmbH are derived. The simplification of polygon meshes will be an extension of the line generalization. Topological constraints need to be considered. This task needs a sophisticated approach as the raw data is not stored in a topological structure. For this task a new algorithm was developed. It was also implemented using JAVA. The results of the testing scenario show that the constraint of real-time performance cannot be fulfilled. Hence it is recommended to use the algorithm for the polygon mesh simplification offline only.:1 Einleitung 2 Kartografische Generalisierung 3 Algorithmen zur Liniengeneralisierung 4 Implementierung 5 Ergebnisse 6 Ausblick 7 Zusammenfassung

OpenStreetMap (OSM) konnte sich seit der Gründung 2004 sehr schnell etablieren und stellt mittlerweile eine konkrete Alternative gegenüber vergleichbaren kommerziellen Anwendungen dar. Dieser Erfolg ist eindeutig auf das revolutionäre Grundkonzept des Projektes zurückzuführen. Weltweit werden räumliche Daten durch Mitglieder erhoben und dem Projekt OSM zur Verfügung gestellt. Über die zugrunde liegenden Lizenzbestimmungen wird sichergestellt, dass OSM-Daten frei verfügbar und kostenfrei weiter verwendbar sind. Vor allem die Vorstellung der Unabhängigkeit von proprietären Daten hat zu starker, weiterhin zunehmender globaler Beteiligung geführt. Resultierend daraus erreichen die verfügbaren Daten inzwischen hohe Dichte sowie Genauigkeit. Visualisierungen in Form von interaktiven, frei skalierbaren Weltkarten, welche über die vollständig automatisierten Softwarelösungen Mapnik und Osmarender erstellt werden, sind am weitesten verbreitet. Infolgedessen müssen kartographische Grundsätze und Regeln formalisiert und implementiert werden. Insbesondere in Bezug auf kartographische Generalisierung treten teils erhebliche Mängel in den entsprechenden Umsetzungen auf. Dies bildet den Ausgangspunkt der Untersuchung. Ausgehend von einer Ist-Analyse werden vorhandene Defizite identifiziert und anschließend Möglichkeiten zur Integration von Generalisierungsfunktionalitäten untersucht. Aktuelle Entwicklungen streben die Anwendung interoperabler Systeme im Kontext kartographischer Generalisierung an, mit dem Ziel Generalisierungsfunktionalitäten über das Internet bereitzustellen. Grundlage hierfür bilden die vom Open Geospatial Consortium (OGC) spezifizierten Web Processing Services (WPS). Sie ermöglichen die Analyse und Verarbeitung räumlicher Daten. In diesem Zusammenhang werden Web Generalization Services (WebGen-WPS) auf mögliche Integration in die Softwarelösungen untersucht und bilden somit einen zentralen Untersuchungsgegenstand der vorliegenden Arbeit. Mapnik stellt, nicht zuletzt durch dessen offengelegten Quelltext („Open Source“), optimale Voraussetzungen für jene Implementierungen zur Verfügung. Zur Verarbeitung von OSM-Daten verwendet Mapnik die freie Geodatenbank PostGIS, welche ebenfalls Funktionalitäten zur Analyse und Verarbeitung räumlicher Daten liefert. In diesem Kontext wird zusätzlich untersucht, inwiefern PostGIS-Funktionen Potential zur Anwendung kartographischer Generalisierung aufweisen. / OpenStreetMap (OSM) has established very quickly since its founding in 2004 and has become a suitable alternative to similar commercial applications. This success is clearly due to the revolutionary concept of the project. Spatial data is collected by members world-wide and is provided to the project OSM. The underlying license aggreement ensures that OSM-Data is freely available and can be used free of charge. Primarily, the idea of independence from proprietary data has led to strong, still growing, global participation. Resulting from that, the available data is now achieving high density and accuracy. Visualizations in form of interactive, freely scalable maps of the world, which are constructed by the fully automated software solutions Mapnik and Osmarender are most common. In consequence cartographic principles and rules must be formalized and implemented. Particularly with respect to cartographic generalization, some serious faults appear in the corresponding implementations. This is the starting point of this diploma thesis. Based on an analysis of the current state, actual existing deficiencies are identified and then examined for possibilities to integrate generalization functionalities. Recent developments aim at the deployment of interoperable systems in the context of cartographic generalization, with the intention of providing generalization functionalities over the Internet. This is based on Web Processing Services (WPS) that where developed by the Open Geospatial Consortium (OGC). They enable the analysis and processing of spatial data. In this context, Web Generalization Services (Webgen-WPS) are examined for possible integration into the software solutions and represent therefore a central object of investigation within that examination. Mapnik provides, not least through its “open source” code, ideal conditions for those implementations. Mapnik uses the “open source” spatial database PostGIS for the processing of OSM-Data, which also provides capabilities to analyze and process spatial data. In this context is examined in addition, to what extent the features have potential for implementation of cartographic generalization.