Coordinated Schematization for Visualizing Mobility Patterns on Networks

Authors Bram Custers , Wouter Meulemans , Bettina Speckmann , Kevin Verbeek



PDF
Thumbnail PDF

File

LIPIcs.GIScience.2021.II.7.pdf
  • Filesize: 5.94 MB
  • 16 pages

Document Identifiers

Author Details

Bram Custers
  • Eindhoven University of Technology, The Netherlands
Wouter Meulemans
  • Eindhoven University of Technology, The Netherlands
Bettina Speckmann
  • Eindhoven University of Technology, The Netherlands
Kevin Verbeek
  • Eindhoven University of Technology, The Netherlands

Acknowledgements

We would like to thank HERE Technologies for providing the HR dataset.

Cite AsGet BibTex

Bram Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek. Coordinated Schematization for Visualizing Mobility Patterns on Networks. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.GIScience.2021.II.7

Abstract

GPS trajectories of vehicles moving on a road network are a valuable source of traffic information. However, the sheer volume of available data makes it challenging to identify and visualize salient patterns. Meaningful visual summaries of trajectory collections require that both the trajectories and the underlying network are aggregated and simplified in a coherent manner. In this paper we propose a coordinated fully-automated pipeline for computing a schematic overview of mobility patterns from a collection of trajectories on a street network. Our pipeline utilizes well-known building blocks from GIS, automated cartography, and trajectory analysis: map matching, road selection, schematization, movement patterns, and metro-map style rendering. We showcase the results of our pipeline on two real-world trajectory collections around The Hague and Beijing.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Trajectories
  • Visualization
  • Schematization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. N. Adrienko and G. Adrienko. Spatial generalization and aggregation of massive movement data. IEEE TVCG, 17(2):205-219, 2010. URL: https://doi.org/10.1109/TVCG.2010.44.
  2. H. Alt, A. Efrat, G. Rote, and C. Wenk. Matching planar maps. Journal of Algorithms, 49(2):262-283, 2003. URL: https://doi.org/10.1016/S0196-6774(03)00085-3.
  3. G. Andrienko, N. Andrienko, W. Chen, R. Maciejewski, and Y. Zhao. Visual Analytics of Mobility and Transportation: State of the Art and Further Research Directions. IEEE Transactions on Intelligent Transportation Systems, 18(8):2232-2249, 2017. URL: https://doi.org/10.1109/TITS.2017.2683539.
  4. M. Arnold and E. Ohlebusch. Linear time algorithms for generalizations of the longest common substring problem. Algorithmica, 60(4):806-818, 2011. URL: https://doi.org/10.1007/s00453-009-9369-1.
  5. K. Buchin, M. Buchin, M. van Kreveld, B. Speckmann, and F. Staals. Trajectory grouping structure. In WADS, pages 219-230, 2013. URL: https://doi.org/10.1007/978-3-642-40104-6_19.
  6. K. Buchin, A. Driemel, J. Gudmundsson, M. Horton, I. Kostitsyna, M. Löffler, and M. Struijs. Approximating (k, l)-center clustering for curves. In Proc. SODA, pages 2922-2938, 2019. URL: https://doi.org/10.1137/1.9781611975482.181.
  7. S. Cabello, M. de Berg, and M. van Kreveld. Schematization of networks. Computational Geometry, 30(3):223-238, 2005. URL: https://doi.org/10.1016/j.comgeo.2004.11.002.
  8. P. Chao, Y. Xu, W. Hua, and X. Zhou. A survey on map-matching algorithms. In ADC, pages 121-133, 2020. URL: https://doi.org/10.1007/978-3-030-39469-1_10.
  9. J. Chen, Y. Hu, Z. Li, R. Zhao, and L. Meng. Selective omission of road features based on mesh density for automatic map generalization. IJGIS, 23(8):1013-1032, 2009. URL: https://doi.org/10.1080/13658810802070730.
  10. W. Chen, F. Guo, and F.-Y. Wang. A survey of traffic data visualization. IEEE Transactions on Intelligent Transportation Systems, 16(6):2970-2984, 2015. URL: https://doi.org/10.1109/TITS.2015.2436897.
  11. M. Garey, D. Johnson, G. Miller, and C. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM Journal on Algebraic Discrete Methods, 1(2):216-227, 1980. URL: https://doi.org/10.1137/0601025.
  12. H. Imai and M. Iri. Computational-geometric methods for polygonal approximations of a curve. Computer Vision, Graphics, and Image Processing, 36(1):31-41, 1986. Google Scholar
  13. M.-J. Kraak. The Space-Time cube revisited from a Geovisualization perspective. In Proc. ICC, pages 1988-1996, 2003. Google Scholar
  14. L. Kulik, M. Duckham, and M. Egenhofer. Ontology-driven map generalization. Journal of Visual Languages & Computing, 16(3):245-267, 2005. URL: https://doi.org/10.1016/j.jvlc.2005.02.001.
  15. O. Lampe and H. Hauser. Interactive visualization of streaming data with kernel density estimation. In Proc. IEEE PacificVis, pages 171-178, 2011. URL: https://doi.org/10.1109/PACIFICVIS.2011.5742387.
  16. J.-G. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: a partition-and-group framework. In Proc. 2007 ACM SIGMOD, pages 593-604, 2007. URL: https://doi.org/10.1145/1247480.1247546.
  17. W. Meulemans. Similarity Measures and Algorithms for Cartographic Schematization. PhD thesis, TU Eindhoven, 2014. URL: https://doi.org/10.6100/ir777493.
  18. A. Nath and E. Taylor. k-Median clustering under discrete Fréchet and Hausdorff distances, 2020. URL: http://arxiv.org/abs/2004.00722.
  19. R. Scheepens, N. Willems, H. van de Wetering, and J. van Wijk. Interactive visualization of multivariate trajectory data with density maps. In IEEE PacificVis, pages 147-154, 2011. URL: https://doi.org/10.1109/PACIFICVIS.2011.5742384.
  20. R. Šuba, M. Meijers, and P. van Oosterom. Continuous road network generalization throughout all scales. ISPRS Journal of Geo-Information, 5(8):145, 2016. URL: https://doi.org/10.3390/ijgi5080145.
  21. R. Thomson. The ’stroke’ concept in geographic network generalization and analysis. In Progress in Spatial Data Handling, pages 681-697. Springer, 2006. URL: https://doi.org/10.1007/3-540-35589-8_43.
  22. C. Tominski, H. Schumann, G. Andrienko, and N. Andrienko. Stacking-based visualization of trajectory attribute data. IEEE TVCG, 18(12):2565-2574, 2012. URL: https://doi.org/10.1109/TVCG.2012.265.
  23. M. van de Kerkhof, I. Kostitsyna, M. van Kreveld, M. Löffler, and T. Ophelders. Route-preserving road network generalization. In Proc. ACM SIGSPATIAL, pages 381-384, 2020. URL: https://doi.org/10.1145/3397536.3422234.
  24. S. van den Elzen and J. van Wijk. Multivariate network exploration and presentation: From detail to overview via selections and aggregations. IEEE TVCG, 20(12):2310-2319, 2014. URL: https://doi.org/10.1109/TVCG.2014.2346441.
  25. T. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann. Map schematization with circular arcs. In GIScience, pages 1-17, 2014. URL: https://doi.org/10.1007/978-3-319-11593-1_1.
  26. A. van Goethem, W. Meulemans, A. Reimer, H. Haverkort, and B. Speckmann. Topologically safe curved schematisation. The Cartographic Journal, 50(3):276-285, 2013. URL: https://doi.org/10.1179/1743277413Y.0000000066.
  27. M. van Kreveld. Smooth generalization for continuous zooming. In IGU, pages 2180-2185, 2001. URL: https://icaci.org/files/documents/ICC_proceedings/ICC2001/icc2001/file/f13042.pdf.
  28. P. van Oosterom. Variable-scale topological data structures suitable for progressive data transfer: The GAP-face tree and GAP-edge forest. Cartography and Geographic Information Science, 32(4):331-346, 2005. URL: https://doi.org/10.1559/152304005775194782.
  29. R. Weiss and R. Weibel. Road network selection for small-scale maps using an improved centrality-based algorithm. Journal of Spatial Information Science, 2014(9):71-99, 2014. URL: https://doi.org/10.5311/JOSIS.2014.9.166.
  30. A. Wolff. Drawing subway maps: A survey. Informatik-Forschung und Entwicklung, 22(1):23-44, 2007. URL: https://doi.org/10.1007/s00450-007-0036-y.
  31. J. Wood, J. Dykes, and A. Slingsby. Visualisation of Origins, Destinations and Flows with OD maps. The Cartographic Journal, 47(2):117-129, 2010. URL: https://doi.org/10.1179/000870410X12658023467367.
  32. H.-Y. Wu, B. Niedermann, S. Takahashi, and M. Nöllenburg. A survey on computing schematic network maps: The challenge to interactivity. In Proc. Schematic Mapping Workshop, 2019. URL: https://www.cg.tuwien.ac.at/research/publications/2019/wu-2019-smw/.
  33. B. Yang, X. Luan, and Q. Li. Generating hierarchical strokes from urban street networks based on spatial pattern recognition. IJGIS, 25(12):2025-2050, 2011. URL: https://doi.org/10.1080/13658816.2011.570270.
  34. Y. Yang, T. Dwyer, S. Goodwin, and K. Marriott. Many-to-many geographically-embedded flow visualisation: An evaluation. IEEE TVCG, 23(1):411-420, 2016. URL: https://doi.org/10.1109/TVCG.2016.2598885.
  35. W. Yu, Y. Zhang, T. Ai, Q. Guan, Z. Chen, and H. Li. Road network generalization considering traffic flow patterns. IJGIS, 34(1):119-149, 2020. URL: https://doi.org/10.1080/13658816.2019.1650936.
  36. G. Yuan, P. Sun, J. Zhao, D. Li, and C. Wang. A review of moving object trajectory clustering algorithms. Artificial Intelligence Review, 47(1):123-144, 2017. URL: https://doi.org/10.1007/s10462-016-9477-7.
  37. Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from GPS trajectories. In Proc. WWW, pages 791-800, 2009. URL: https://doi.org/10.1145/1526709.1526816.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail