Geovisualization of complex origin-destination flow maps using Discrete Global Grid Systems

Abstract. Flow maps, where counts of people or things are shown travelling between origin-destination pairs with paths or arrows, are difficult to draw well, mostly because they rapidly get cluttered as more and more paths are added. Researchers in cartographic and information visualization fields have sought to mitigate these problems in various ways, including cluster detection and edge bundling (Buchin, Speckmann, & Verbeek, 2011; Guo, 2009), force-directed path placement (Holten & van Wijk, 2009; Jenny et al., 2017), use of network topological space instead of planimetric space (Xiao & Chun, 2009), interactive spatial filtering of flows (Vrotsou, Fuchs, Andrienko, & Andrienko, 2017), and by changing the drawing medium to accommodate flows that arc through 3D space (Raposo, 2017; Yang et al., 2019; Zhang, Zhang, Li, & Li, 2018). Other geovisualization techniques recently developed involve and use of matrixes or grids to store and visualize flows; Wood, Dykes, & Slingsby (2010) use spatial tessellation and a set of small multiples of the same tessellation representing origin and destination spaces, respectively, creating a sort of travel heat map when tiles are colored as a choropleth. A comparable approach is taken by Yang et al. (2017) in a system that combines an abstract matrix of flow records with inflow and outflow maps.

This early-stage project builds on previous matrix-based flow visualization methods while leveraging the power of Discrete Global Grid Systems (DGGS), which present a naturally Earth-oriented hierarchical tessellation upon which a matrix of origins and destinations can be stored and visualized. DGGS (Sahr, White, & Kimerling, 2003; Raposo, Robinson, & Brown, in press) partition the round Earth into nested tiles in a manner similar to quad-trees, and have the desirable properties of covering the whole spherical globe in equal-area (or near equal-area) tiles, and of being hierarchical to an arbitrary number of levels. The hierarchical quality allows flows in a DGGS to be naturally bundled by origin and destination points as a function of grid size; greater or lesser detail (i.e., more or less bundling) in the overall pattern of flows is effected by descending or ascending DGGS levels. As DGGS are becoming increasingly popular for geospatial data computation and collection in movement analysis (Brodsky, 2018), the present work provides a natural bridge to the visualization of such data when it pertains to movement phenomena.

The present research will develop a suite of flow visualization techniques upon an existing open-source DGGS rendering platform (Raposo, Robinson, & Brown, in press): 1) grid facet coloring in a choropleth scheme to indicate magnitudes of flow into or out of a particular facet; 2) vertical-space cubic spline flow arcs, and 3) tabular representation of the flow data. All three visualization techniques will function across multiple spatial resolutions, corresponding to each of the hierarchical levels of our chosen DGGS, so that users can interact both with each of the three visualizations of the data as well as the spatial granularity to which the data are displayed. All views will be interactive and linked.

We use Dutton’s (1999) quaternary triangular mesh (QTM), being a DGGS based on recursively subdividing the faces of an octahedron over the globe (Figure 1). Our method begins by finding, at many nested QTM levels, the facets of the QTM with which each origin and destination point intersects; in practice, we use up to 16 levels, as the triangles at that level in the QTM are small enough to address typical individual buildings. Importantly, point-in-polygon intersection is calculated geodetically, and not in 2D projected space, since failing to do this can cause topological errors (Raposo, Robinson, Brown, in press). At each QTM facet and at each level, we build two lists: one of all the other facets at that level that contain an origin point for a flow that arrives at this facet, and another of those that contain a destination point for flows originating in this facet. These lists are stored to each facet as polygon attributes. A flow path curving through vertical space via a cubic spline is also derived for each origin-destination pair and stored as a renderable 3D solid.

The QTM is then plotted in our software on a virtual globe using NASA’s World Wind application programming interface. As users select any one QTM facet, its attributes are read to find all the other facets either contributing or receiving flows to or from the selected facet; these are then colored according to a choropleth scheme to visualize magnitudes of flow (Figure 2). Coloration is controlled for various descriptive statistics on the flows (e.g., total, mean, maximum, etc.). Linear paths curving up and around the globe (Figure 3) will also be available to be toggled on or off, giving users multiple redundant symbolizations of travel paths.