Skip to main content
Springer Nature Link
Log in

Fast overlap removal for location-related representation elements

  • Special Issue on Multi-modal Information Learning and Analytics on Big Data
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

In order to resolve the issues with overlapping elements in location-related applications, an element adjustment method is proposed. This adjustment method can be implemented using a non-iterative algorithm which can significantly improve the processing efficiency of overlap removal. The method first sorts out all the elements according to the distance from the preset Starting Point. Repulsive offset adjustment is used for circular elements. It can be validated through theoretical derivation. Finally, the influencing factors of algorithm parameters are analyzed. Suggestions are given to further optimization of the algorithm. Experimental results show that it can effectively remove overlapping. The relative positional relationship among elements can be preserved to the greatest extent. User’s verifications and expert’s evaluation show that it can also achieve high recognition rate between the geographic region and its representation element.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Liu Huide, Yang Dabing (2004) Research on the geographic spatio-temporal information visualization on web [C]. IEEE Int Geosci Remote Sens Symp, Anchorage, AK, SEP 20–24(2004):2941–2944. https://doi.org/10.1109/IGARSS.2004.1370311

    Article  Google Scholar 

  2. Riccardo Albertoni, Alessio Bertone, Monica De Martino, M. De Martino. (2003) A visualization-based approach to explore geographic metadata [C]. 11th International Conference on Computer Graphics, Visualization and Computer Vision 2003, Plzen, Czech Republic, February 3-7 pp 9-12.

  3. Fati Chen, Laurent Piccinini, Pascal Poncelet, Arnaud Sallaberry. (2019) Node overlap removal algorithms: A Comparative Study, arXiv: 1908.07363v2 [cs.CG]. 5 Sep 2019

  4. Lev Nachmanson, Arlind Nocaj, Sergey Bereg, Leishi Zhang, Alexander Holroyd. Node overlap removal by growing a tree [J]. Lecture Notes in Computer Science v(9801)International Symposium on Graph Drawing and Network Visualization (GD 2016): pp 33-43, DOI: https://doi.org/10.1007/978-3-319-50106-2_3

  5. Thony, Matthias, Schnurer, Raimund, Sieber, Rene, and etc. (2018) Storytelling in interactive 3D geographic visualization systems” [J]. ISPRS International Journal of Geo-Information, v7(n3): No 123 DOI: https://doi.org/10.3390/ijgi7030123

  6. Rie Ishida, Shigeo Takahashi, Hsiang-Yun Wu. (2016) Adaptive blending of multiple network layouts for overlap-free labeling [C]. 20th International Conference Information Visualization, Lisbon, Portugal, 19-22 July 2016: v1: pp 15-20, DOI: https://doi.org/10.1109/IV.2016.25

  7. Quang Vinh Nguyen, Mao Lin Huang. (2003) A fast focus+context viewing technique for the navigation of classical hierarchical layout [C]. Proceedings on Seventh International Conference on Information Visualization, 2003. IV 2003, London, UK,: July 18, 2003, v1&2 : pp 188-192, DOI:https://doi.org/10.1109/IV.2003.1217955

  8. A. Robert Marceau, B. Karen Daniels, and C. Georges Grinstein. (2016) A visualization framework to eliminate cluster overlap [C]. International Conference on Modeling, Simulation and Visualization Methods (MSV'16): pp 57-62

  9. Emden R. Gansner and Yifan Hu. (2009) Efficient node overlap removal using a proximity stress model [J]. Lecture Notes in Computer Science 5417, International Symposium on Graph Drawing 2008, Springer-Verlag Berlin Heidelberg: pp. 206-217, DOI: https://doi.org/10.1007/978-3-642-00219-9_20

  10. van Garderen, M, Pampel, B, Nocaj, A, Brandes, U. (2017) Minimum-displacement overlap removal for geo-referenced data visualization [J]. Computer Graphics Forum, v36(n3), 19th Eurographics/IEEE VGTC Conference on Visualization (EuroVis), June 2017: pp 423-433, DOI: https://doi.org/10.1111/cgf.13199

  11. Hsiang-Yun Wu, Shigeo Takahashi, Chun-Cheng Lin and Hsu-Chun Yen. (2013) voronoi-based label placement for metro maps [C]. 17th International Conference on Information Visualization, v1: pp 96-101, DOI: https://doi.org/10.1109/IV.2013.11

  12. Tim Dwyer, Kim Marriott, and Peter J. Stuckey. Fast node overlap removal [J]. (2005) Lecture Notes in Computer Science 3843, International Symposium on Graph Drawing 2005, Springer-Verlag Berlin Heidelberg: pp. 153-164

  13. Antoine L huillier, Mereke van Garderen, Daniel Weiskopf. (2019) Density-based label placement [J]. The Visual Computer 35: 1041–1052, DOI: 10.1007/ s00371-019-01686-7

  14. Meng, Y., Zhang, H., Liu, M., Liu, S. (2015) Clutter-aware label layout [C]. Proceedings of 2015 IEEE Pacific Visualization Symposium (PacificVis): pp. 207-214

  15. Kimm Arriott, Peter Stuckey,Vincent Tam, Weiqing He. (2003) Removing node overlapping in graph layout using constrained optimization [J]. Constraints, v8: pp 143–171, DOI: https://doi.org/10.1023/A:1022371615202

  16. Xiaodi Huang, A.S.M. Sajeev, Wei Lai. (2006) A scalable algorithm for adjusting node-node overlaps [C]. Proceedings of the International Conference on Computer Graphics, Imaging and Visualisation (CGIV'06), 26-28 July, Sydney, Qld., Australia, v1: pp 43-48, DOI: https://doi.org/10.1109/CGIV.2006.9

  17. Strobelt, Hendrik, Spicker, Marc, Stoffel, Andreas, Keim, Daniel, Deussen, Oliver. (2012) Rolled-out wordles: a heuristic method for overlap removal of 2D data representatives [J]. Computer Graphics Forum, v31 (n3): pp 1135-1144, DOI: https://doi.org/10.1111/j.1467-8659.2012. 03106.x

  18. Xiaodi Huang a, Wei Lai b, A.S.M. Sajeev a, Junbin Gao. (2007) A new algorithm for removing node overlapping in graph visualization [J]. Information Sciences, v177: pp 2821–2844, DOI: https://doi.org/10.1016/j.ins.2007.02.016

  19. Walter Didimo, Evgenios M. Kornaropoulos, Fabrizio Montecchiani and Ioannis G. Tollis. (2018) A visualization framework and user studies for overloaded orthogonal drawings [J]. Computer Graphics Forum, v37(n1): pp. 288-300, DOI: https://doi.org/10.1111/cgf.13266

Download references

Acknowledgements

This work was supported by National Natural Science Foundation of China Grant 31701517, Beijing Social Science Foundation Program Grant 17GLC060 and Support Project of High-Level Teachers in Beijing Municipal Universities in Period of 13th Five-Year Plan Grant CIT&TCD201704039. We thank the visualization laboratory of Beijing Technology and Business University for providing the city location data set, and thank Ms. Liu Tao for providing us with detailed grammar revision work, and thank the experts for their evaluation and suggestions on our method.

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Beijing Technology and Business University, Beijing, 100048, China

    Hongqian Chen

  2. Management College, Beijing Union University, Beijing, 100101, China

    Hui Li

  3. Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing, 100048, China

    Hongqian Chen

  4. Institute of Scientific and Technical Information of China, Beijing, 100038, China

    Hui Li

Authors
  1. Hongqian Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hui Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hui Li.

Ethics declarations

Conflict of interest

The Authors declare that they have no Conflicts of Interest

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, H., Li, H. Fast overlap removal for location-related representation elements. Neural Comput & Applic 34, 3483–3494 (2022). https://doi.org/10.1007/s00521-021-05825-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-021-05825-x

Keywords

Search

Navigation