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 or Fee 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

Full Text

Restricted Access

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
2. Fig. 1. (a) Raster image of text, (b) polygonal shapes and their skeletons.

Download (92KB)
Indexing metadata
3. Fig. 2. Internal Voronoi diagram of a polygonal shape.

Download (66KB)
Indexing metadata
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.

Download (65KB)
Indexing metadata
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.

Download (150KB)
Indexing metadata
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.

Download (52KB)
Indexing metadata
7. Fig. 6. Status change during 'Left vertex' events: (a) convex, (b) concave.

Download (61KB)
Indexing metadata
8. Fig. 7. Status change during 'Passing vertex' events: (a) upper convex, (b) lower convex, (c) upper concave, (d) lower concave.

Download (82KB)
Indexing metadata
9. Fig. 8. Status change during 'Right vertex' events: (a) convex, (b) concave.

Download (52KB)
Indexing metadata
10. Fig. 9. Sweeping a quadrilateral, vertex events – A, B, C, G, circle events – D, E, F, status changes by events.

Download (133KB)
Indexing metadata
11. Fig. 10. Geometric problems of constructing a tangent circle for points and segments.

Download (77KB)
Indexing metadata
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.

Download (54KB)
Indexing metadata
13. Fig. 12. Test examples of polygonal shapes: horse (1 polygon, 374 vertices), neuron (7, 3449), tree (6373, 175375), plan (5395, 185115).

Download (339KB)
Indexing metadata
14. Fig. 13. Total Dictation page – example of a set of polygonal shapes approximating a handwritten text image.

Download (425KB)
Indexing metadata

Copyright (c) 2024 Russian Academy of Sciences