Constructing the internal Voronoi diagram of a polygonal figure using the sweep method

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The article considers the problem of constructing the internal Voronoi diagram of a polygonal figure – a polygon with polygonal holes. A method based on the flat sweeping paradigm is proposed. Direct construction of only the internal part of the Voronoi diagram allows us to reduce the amount of calculations and increase robustness compared to known solutions. Another factor in reducing computational complexity is the use of the property of pairwise incidence of linear segments formed by the sides of a polygonal figure. To take these features into account, it is proposed to build the data structure Status of the sweeping line in the form of an ordered set of sites’ areas of responsibility. The structure is implemented as a combination of a balanced tree and a bidirectional list. Computational experiments illustrate the numerical reliability and efficiency of the proposed method.

Keywords

About the authors

L. М. Mestetskiy

Lomonosov Moscow State University; National Research University Higher School of Economics

Author for correspondence.
Email: mestlm@mail.ru
Russian Federation, Leninskie Gory 1, GSP-1, Moscow, 119991; Pokrovsky Boulevard 11, Moscow, 109028

D. А. Koptelov

Lomonosov Moscow State University

Email: dimitar98@list.ru
Russian Federation, Leninskie Gory 1, GSP-1, Moscow, 119991

References

  1. Mestetskiy L.M. Continuous morphology of binary images: figures, skeletons, circulars. Moscow, Fizmatlit, 2009 (in Russian).
  2. Oturgasheva N.V. URBI ET ORBI message: total dictation. as a cultural project. Bulletin of Tomsk State University. 2019. No. 35. p. 105–113 (in Russian). https://doi.org/10.17223/22220836/35/10
  3. Fortune S. A sweepline algorithm for Voronoi diagrams. Algorithmica. 2 (1987). P. 153–174.
  4. Yap C.K. An O(n log n) algorithm for the Voronoi diagram of the set of simple curve segments. Discrete Comput. Geom. 2 (1987). P. 365–393.
  5. Mestetskiy L.M. Skeletonization of a multiconnect-ed polygonal figure based on the adjacency tree of its boundary // Sibirsk. magazine Comput. Mat. 2006. V. 9. No. 3. P. 299–314 (in Russian).
  6. Fortune, S. (1996). Robustness issues in geometric algorithms. In: Lin, M.C., Manocha, D. (eds) Applied Computational Geometry Towards Geometric Engineering. WACG 1996. Lecture Notes in Computer Science. V. 1148. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014476
  7. Shewchuk J.R. (2013). Lecture Notes on Geometric Robustness. University of California at Berkeley, Berkeley, CA 94720.
  8. Lagno D., Sobolev A. Modified Fortune and Lee algorithms for skeletonization of a polygonal figure. Graphicon-2001, Nizhny Novgorod (in Russian).
  9. Preparata F., Sheimos M. Computational geometry: Introduction: Transl. from English. – M.: Mir, 1989. – 478 p.
  10. Lee D.T. Medial axes transform of planar shape // IEEE Trans. Patt. Anal. Mach. Intell. PAMI-4. 1982. P. 363–369.
  11. Srinivasan V., Nackman L.R. Voronoi diagram for multiply-connected polygonal domains I: Algorithm // in IBM Journal of Research and Development, V. 31. No. 3. P. 361–372. May 1987. https://doi.org/10.1147/rd.313.0361.
  12. Held M. Vroni: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments // Computational Geometry. 2001. V. 18. P. 95–123.
  13. Sugihara K., Iri M., Inagaki H. et al. Topology-Oriented Implementation – An Approach to Robust Geometric Algorithms. Algorithmica 27, 5–20 (2000). https://doi.org/10.1007/s004530010002
  14. Karavelas M.I. A robust and efficient implementation for the segment Voronoi diagram. In Proc. Internat. Symp. on Voronoi diagrams in Science and Engineering (VD2004), 2004. P. 51–62.
  15. Imai T. A topology oriented algorithm for the voronoi diagram of polygons. cccg1996, 1996. P. 107–112.
  16. Bae, S.W. (2015). An Almost Optimal Algorithm for Voronoi Diagrams of Non-disjoint Line Segments. In: Rahman M.S., Tomita E. (eds) WALCOM: Algorithms and Computation. WALCOM 2015. Lecture Notes in Computer Science. V. 8973. Springer, Cham. P. 34–43.
  17. Marsden D. Exact Generalized Voronoi Diagram Computation using a Sweepline Algorithm (2020). All Graduate Theses and Dissertations. 7947. https://digitalcommons.usu.edu/etd/7947
  18. https://www.boost.org/doc/libs/1_59_0/libs/polygon/doc/voronoi_main.htm

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences