One to Many Flow Layout
One to Many Flow Layout
Abstract from the publication
Mapping spatial flow remains a challenge despite noticeable progress in recent years. This article presents a new, automated layout algorithm for spatial flow from one origin to multiple destinations. The algorithmtriangulates themapped space andbuilds a network from the triangles. It then simulates the formation of the dendritic drainage pattern of natural river systems and constructs an approximate Steiner tree by sequentially computing the shortest paths from the origin to the destinations using dynamically decreasing edge costs. A series of automatic cartographic operations, including edge simplification, straightening, smoothing, and rendering, then follow to improve the esthetics of the tree and to produce flow layouts that feature natural clusters and smooth edges. An experimental evaluation using four examples illustrates the effectiveness and adaptability of the algorithm with various spatial and parameter configurations. A quantitative comparison with existing methods on esthetics shows that the new algorithm generally renders destinations farther away from tree edges, which helps improve map readability but at the cost of longer total tree length. Evaluated with a smoothness index that rewards gradual tree splitting and smooth, natural, and straight edges, the proposed algorithm can achieve higher average edge smoothness and avoid the least smooth edges under various parameter settings.
References
Sun, S. (2018). A spatial one-to-many flow layout algorithm using triangulation, approximate Steiner trees, and path smoothing. Cartography and Geographic Information Science, 1-17. https://doi.org/10.1080/15230406.2018.1437359
Sun, S. (2016, September 14-16). An Automated Spatial Flow Layout Algorithm using Triangulation, Approximate Steiner Tree, and Path Smoothing. AutoCarto 2016: The 21st International Research Symposium on Computer-based Cartography and GIScience, Albuquerque, NM.