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

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅或者付费存取

详细

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