A spatial one-to-many flow layout algorithm using triangulation, approximate Steiner trees, and path smoothing

ABSTRACT

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 algorithm triangulates the mapped space and builds 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.

KEYWORDS:

• Spatial one-to-many flow
• automated map layout
• flow visualization

Acknowledgments

I would like to thank the Editor, Dr Nick Chrisman, for his patience, constructive comments, and editorial help. This article has benefited significantly from the detailed and thoughtful comments from three anonymous reviewers. The author also wants to thank Dr Dudley Bonsal for his help on writing and Yalong Yang for sharing his JavaScript code. As usual, I am solely responsible for all mistakes and shortcomings.

Disclosure statement

No potential conflict of interest was reported by the author.