- PII
- 10.31857/S0132347424040026-1
- DOI
- 10.31857/S0132347424040026
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume / Issue number 4
- Pages
- 13-26
- 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
- Date of publication
- 17.09.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 17
References
- 1. Местецкий Л.М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. М.: Физматлит, 2009.
- 2. Отургашева Н.В. Послание URBI ET ORBI: тотальный диктант как культурный проект // Вестник Томского государственного университета. 2019. № 35. C. 105–113. 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. Местецкий Л.М. Скелетизация многосвязной многоугольной фигуры на основе дерева смежности ее границы // Сиб. журн. вычисл. матем. 2006. Т. 9. № 3. С. 299–314.
- 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. Лагно Д., Соболев А. Модифицированные алгоритмы Форчуна и Ли скелетизации многоугольной фигуры. Графикон-2001, Н. Новгород.
- 9. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. – М.: Мир, 1989. – 478 с.
- 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
