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

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Рұқсат ақылы немесе тек жазылушылар үшін

Аннотация

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.

Негізгі сөздер

Толық мәтін

Рұқсат жабық

Авторлар туралы

L. Mestetskiy

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

Хат алмасуға жауапты Автор.
Email: mestlm@mail.ru
Ресей, Leninskie Gory 1, GSP-1, Moscow, 119991; Pokrovsky Boulevard 11, Moscow, 109028

D. Koptelov

Lomonosov Moscow State University

Email: dimitar98@list.ru
Ресей, Leninskie Gory 1, GSP-1, Moscow, 119991

Әдебиет тізімі

  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

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу
2. Fig. 1. (a) Raster image of text, (b) polygonal shapes and their skeletons.

Жүктеу (92KB)
Метадеректер
3. Fig. 2. Internal Voronoi diagram of a polygonal shape.

Жүктеу (66KB)
Метадеректер
4. Fig. 3. Monotone branches of the shape boundary: 1–12–11–10–9, 7–6–5, 7–8–9, 3–4–5, 1–2, 3–2, 13–14–15, 13–16–15.

Жүктеу (65KB)
Метадеректер
5. Fig. 4. Zones of site-segments s1, s2. Tangent circles of zone s1 – dashed, zone s2 – dotted, common circle of both zones – solid line.

Жүктеу (150KB)
Метадеректер
6. Fig. 5. Types of vertices of a polygonal shape: left (a, b), passing (c, d, e, f), right (g, h), convex (a, c, e, g), concave (b, d, f, h), lower (d, e) and upper (c, f). The interior of the polygonal shape is shaded gray.

Жүктеу (52KB)
Метадеректер
7. Fig. 6. Status change during 'Left vertex' events: (a) convex, (b) concave.

Жүктеу (61KB)
Метадеректер
8. Fig. 7. Status change during 'Passing vertex' events: (a) upper convex, (b) lower convex, (c) upper concave, (d) lower concave.

Жүктеу (82KB)
Метадеректер
9. Fig. 8. Status change during 'Right vertex' events: (a) convex, (b) concave.

Жүктеу (52KB)
Метадеректер
10. Fig. 9. Sweeping a quadrilateral, vertex events – A, B, C, G, circle events – D, E, F, status changes by events.

Жүктеу (133KB)
Метадеректер
11. Fig. 10. Geometric problems of constructing a tangent circle for points and segments.

Жүктеу (77KB)
Метадеректер
12. Fig. 11. Calculation of a tangent circle for two sites and a sweeping line: (a) site-points, (b, c) site-point and site-segment, (d) two site-segments.

Жүктеу (54KB)
Метадеректер
13. Fig. 12. Test examples of polygonal shapes: horse (1 polygon, 374 vertices), neuron (7, 3449), tree (6373, 175375), plan (5395, 185115).

Жүктеу (339KB)
Метадеректер
14. Fig. 13. Total Dictation page – example of a set of polygonal shapes approximating a handwritten text image.

Жүктеу (425KB)
Метадеректер

© Russian Academy of Sciences, 2024