Generating Multi-destination Maps Based-on Map Simplification And Layout Optimization

Multi-destination maps are a kind of navigation maps, aimed to guide visitors to multiple destinations within a region. Multi-destination maps are common in tourist attractions, navigating visitors to multiple spots. They are also usually found in the advertising materials to navigate customers to reach their stores. However, there are some limitations of the current online map service that we use to generate a multi-destination map within a single, consistent visual frame. The main shortcoming of the current online map service is that they do not distinguish between essential and extraneous information. As a result, they provide users too much redundant data and they cannot show users the detail views and the overviews at the same time. To date, such destination maps have always been created manually. Professional mapmakers choose which information is most essential for the users and they use a lot of cartographic generalization techniques including distortion, simplification, and abstraction to emphasize the most important information. However, it is a time-consuming process to create a multi-destination map by hand. Therefore, it is meaningful and challenging to design an automated system for creating such multi-destination maps.In this paper, we present a principle-based algorithm for simplifying map data. First, we exam research in cognitive psychology, on the way people mentally think about and use maps. Based on this analysis we summed up a set of principles for simplifying map data and emphasizing the essential information. Second, we transform these principles into implementable algorithms for selecting the relevant network of roads. We search the visibility rings of highways, major roads and streets around each destination hierarchically and connect the rings to the destination using the optimal path that produced by A*algorithm. The optimal path is defined that contains shortest path, minimum turns and minimal complexity. Finally, we use Douglas-Peucker algorithm to remove redundant points on the road and maintain the topology of the road network.Then, we propose a novel layout model designed especially for the multi-destination maps. We use the ROIs and the connecting edges to represent the layout of multi-destination maps abstractly. First, we use an improved Min-Cut algorithm to segment the map into multiple ROIs and make sure that each ROI contain only one destination, complete traversable routes and minimal overlapping area. Second, we model our layout problem as a graph drawing that satisfies a set of constraints, including spatial efficiency design, limitation of the length and angle of a road segment and maintain the topology of the road network etc. Finally, We propose a perturbation-based simulated annealing algorithm to find an optimal layout that matches the pre-defined constraints in the complex solution space. In addition, our algorithm is a dual-level layout optimization method, which considers the global and the local layout of a multi-destination map. The multi-destination maps generated by our system can show the overview and the detail view of the whole map at the same time.What’s more, we provide a large number of experimental data and comparative results in this paper. In addition, we performed a user study to evaluate the effectiveness of our system. In the end, we summarize the main content of this paper and point out the limitations of our algorithm that give the direction of following research in the future.