Untangling Origin-Destination Flows in Geographic Information Systems

Origin-destination flow maps are a popular option to visualize connections between different spatial locations, where specific routes between the origin and destination are unknown or irrelevant. Visualizing origin- destination flows is challenging mainly due to visual clutter which appears quickly as data sets grow. Clutter reduction techniques are intensively explored in the information visualization and cartography domains. However, current automatic techniques for origin-destination flow visualization, such as edge bundling, are not available in geographic information systems which are widely used to visualize spatial data, such as origin-destination flows. In this article, we explore the applicability of edge bundling to spatial data sets and necessary adaptations under the constraints inherent to platform-independent geographic information system scripting environments. We propose (1) a new clustering technique for origin-destination flows that provides within-cluster consistency to speed up computations, (2) an edge bundling approach based on force-directed edge bundling employing matrix computations, (3) a new technique to determine the local strength of a bundle leveraging spatial indexes, and (4) a geographic information system-based technique to spatially offset bundles describing different flow directions. Finally, we evaluate our method by applying it to origin-destination flow data sets with a wide variety of different data characteristics.