Unified routing and map rendering

Abstract

Two major areas worth improving in route planning and the maps accompanying it are customization and routing with limited connectivity. This thesis will tackle both while unifying the mapping and routing aspects in a single always consistent scheme. For this we created an extensible framework based on the Contraction Hierarchy scheme originally developed to speed up routing.

This scheme combined with data structures from computational geometry allows us to identify which road segments within a view are most important for routing with a given cost function. Additionally it provides us with a simple yet powerful way to refine roads for rendering at different resolutions and pixel densities. Leading to maps that automatically adapt to both the individual routing scenario and required level of detail.

To allow routing under limited connectivity the identified road segments are packaged as self-contained subgraphs. These subgraphs may then be encoded for transfer to the client where they can be combined into larger graphs that can be rendered as a map and routed on.