Hochschule Karlsruhe – Technik und Wirtschaft

Diploma Thesis

Algorithms for Automated Generalisation by Merging Line Strings in OpenStreetMap

for specific special cases

Algorithmen zur automatisierten Generalisierung durch Zusammenfassung von Linienzügen in OpenStreetMap

für konkrete Spezialfälle

Dipl-.Ing. (FH) Arne Johannessen

Advisors

Summary

The goal of the OpenStreetMap project (OSM) is the creation of a free spatial database using volunteered geographic information. Further processing and visualisation of OSM data almost always takes place fully automated. This is impeded by the in parts very high amount of detail, the resulting fragmentation of line strings as well as incomplete linkage of spatial data belonging together by means of relations in the data model.

So far, cartographic generalisation of OSM data only happens to the most limited extent. Among other situations this is noticeable at dual carriageways, whose centreline is not included in OSM and cannot yet be automatically derived in a satisfactory manner. Approaches for the automatic generalisation of line strings exist, but are not well suited for OSM data. In particular, they are often unable to find solutions for junctions without special attributes.

This thesis presents a method for the detection of parallel line strings on the basis of a geometric comparison. Line strings from OSM are fragmented further until vertices on parallels exist opposite to each other such that verifying the parallelism is simple. The subsequent merging of the detected parallels is then easy to solve. The computational complexity of the developed algorithms grows linear with the number of vertices.

An executable implementation of the algorithms demonstrates their operability and allows for testing with real world data from OSM. Due to some technical difficulties, development was more time-consuming than expected. The software (“Combiner”) has considerable potential for optimisation.

The approach developed in this thesis leads to a good generalisation result in many cases. However, this approach has significant problems at junctions as well. Developing a viable solution for these problems was not possible due to time constraints.

There are also reports of similar problems at junctions for other approaches that were developed in parallel to this thesis. An obvious solution with general applicability for the problem of merging parallel line strings is not currently apparent. It can however be expected that a reliable automated junction detection would turn the merging into a simple problem. This thesis lists several distinct potential approaches to this end.