Space-filling Geographic Treemap Layouts

Space-filling Geographic Treemap Layouts

Often, especially when visualizing relationships between multitudes of geographic locations, the traditional map is stretched to its limits. In cases where the exact location is not as important as the legible visualization of relationships or e.g. concurrent attribute visualizations more abstract geographic representations can be a useful tool to overcome some limitations.

One alternative for abstract geographic representations are treemaps. Each Treemap node represents one geographic location or region. While many treemap algorithms use hierarchical visualization algorithms to keep nodes with the same parent node close to each other, geographic treemaps try to maintain the spatial distribution of points and thereby keep the distortion between original geographic position and treemap position as small as possible.

Comparing an optimized treemap layout with the actual geographic distribution.

Comparing an optimized treemap layout with the actual geographic distribution.

Most existing algorithms take a space-filling treemap approach, e.g. NMAP by Duarte et al [1] or Jo Wood’s solution [3]. This approach creates two limitations. If the treemap should result in equally sized nodes, the amount of nodes needs to be  , otherwise the system needs to fill in blank nodes. As a second constraint the idea of space-filling creates the problem that the actual geographic space might not be close to a rectangle or square.

To overcome this problem I converted the NMAP algorithm to javascript as an initial starting point. From there on I tried to optimize the algorithm, to allow any number of nodes as an input and on the other hand trying to let the final shape of the treemap be closer to the actual geographic extent and shape. As a first step we take the target area into account and modify it, to match the ratio of the original geographic extent. To allow for any number of nodes and a better matching of the actual shape of the geographic space we add empty nodes. I implemented to experimental modes to do this. The first is making use of a quadtree, to find empty areas and the second approach is simply placing new nodes on the border by repetitively calculating distances to the original dataset and the newly added points.

Bildschirmfoto 2015-11-02 um 11.11.54

Black points: original data set, red points: border approach, green points: quadtree approach.

A major limitation of this approach is, that the whole system is just using the centroids of each region, and especially when looking for empty areas, we don’t take into account that those areas might actually not be empty, but instead large regions. Further more its quite obvious, as the border approach delivers, due to the area-fact, the better results, this approach is limited to datasets, that does not require empty cells to be added in central areas, like e.g. an island dataset.

Similar attempts with more sophisticated approaches have for example been conducted by the research group around Bettina Speckmann at the TU Eindhoven, specifically the work by Eppstein et al [2], which makes use of linear programming approaches, to solve the problem. While their approach delivers better results, it is a lot more computing intensive. While the experimental approach presented here, at least on small node-sets, can be computed on the fly, and in javascript, while linear programming so far requires linear programming solvers, mostly implemented in Java.

The code can be found on GitHub.

References

[1] Duarte, F.S.L.G.; Sikansi, F.; Fatore, F.M.; Fadel, S.G.; Paulovich, F.V., “Nmap: A Novel Neighborhood Preservation Space-filling Algorithm,” Visualization and Computer Graphics, IEEE Transactions on , vol.20, no.12, pp.2063,2071, Dec. 31 2014; doi: 10.1109/TVCG.2014.2346276

[2] Eppstein, D.; van Kreveld, M.; Speckmann, B.; Staals, F., “Improved grid map layout by point set matching,” in Visualization Symposium (PacificVis), 2013 IEEE Pacific , vol., no., pp.25-32, Feb. 27 2013-March 1 2013
doi: 10.1109/PacificVis.2013.6596124

[3] Wood, J. & Dykes, J. (2008). Spatially Ordered Treemaps. IEEE Transactions on Visualization and Computer Graphics, 14(6), pp. 1348-1355. doi: 10.1109/TVCG.2008.165