Аппроксимация диаграммы вороного k-го порядка
Ключевые слова:
аппроксимация диаграммы Вороного, диаграмма Вороного k-го порядка, диаграмма минимизации, квадродерево, октодерево, предикат уточнения
Аннотация
Представлен алгоритм построения обобщенной дискретной диаграммы Вороного k-го порядка на сетке с переменным шагом, основанный на идее рекурсивного разбиения пространства. В алгоритме в качестве структуры данных используется дерево разбиения пространства (2d-дерево), также известное как квадродерево и октодерево для 2-х и 3-х мерных пространств. Алгоритм рекурсивно уточняет границы ячеек Вороного (би-секторы), используя только локальные свойства в каждой точке области построения. В результате вычисления сосредотачиваются в области границ ячеек (глубина 2d-дерева больше в области границ ячеек), и достигается существенный выигрыш производительности по сравнению с наивным алгоритмом (полным перебором). Алгоритм позволяет обобщать форму сайтов, используемую метрику, порядок диаграммы и число измерений.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Boissonnat, J. D. Effective Computational Geometry for Curves and Surfaces / J. D. Boissonnat [et al.] ; Editors J. D. Boissonnat, M. Teillaud. – Springer-Verlag Berlin Heidelberg, 2006. – 343 p. – URL: DOI: 10.1007/978-3-540-33259-6
2. Lee, D. T. Medial axis transformation of a planar shape / D. T. Lee // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 1982. – Vol. 4(4). – P. 363-369. – URL: DOI: 10.1007/978-3-540-77974-2
5. Местецкий, Л. М. Непрерывная морфология бинарных изображений. Фигуры, скелеты, циркуляры / Л. М. Местецкий. – Москва : Физматлит, 2009. – 288 с.
6. Okabe, A. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams / A. Okabe [et al.] ; with a foreword by D. G. Kendall. – 2nd ed. p. cm. – New York : John Wiley & Sons Ltd., 2008. – 671 p.
7. Everett, H. The Voronoi Diagram of Three Lines / H. Everett [at al.] // Discrete & Computational Geometry. – 2009. – Vol. 42(1). – P. 94–130. – URL: DOI: 10.1007/s00454-009-9173-3
8. Lavender, D. Voronoi Diagrams of Set-Theoretic solid Models / D. Lavender [et al.] // IEEE Computer Graphics and Applications. – 1992. – Vol. 12(5). – P. 69-77. – URL: DOI: 10.1109/38.156016
9. Vleugels, J. Approximating Generalized Vo-ronoi Diagrams in Any Dimension / J. Vleugels, M. Overmars // Technical report 14, Depart ment of Computer Science, Utrecht University. – 1995. – 21 p.
10. Vleugels, J. Approximating Voronoi Diagrams of Convex Sites in Any Dimension / J. Vleugels, M. Overmars // International Journal of Computational Geometry & Applications. – 1998. – Vol. 8(2). – P. 201–221. – URL: DOI: 10.1142/S0218195998000114
11. Teichmann, M. Polygonal approximation of Voronoi diagrams of a set of triangles in three dimensions / M. Teichmann, S. Teller // Technical Report 766, Laboratory of Computer science, MIT. – 1997. – 12 p.
12. Telea, A. Visualization of Generalized Voronoi Diagrams / A. Telea, J. J. van Wijk // Data Visualization 2001. – 2001. – P. 165–174. – URL: DOI: 10.1007/978-3-7091-6215-6_18
13. Boada, I. The Voronoi-Quadtree: construction and visualization / I. Boada, N. Coll, J. A. Sellares // Eurographics 2002. – 2002. – P. 349–355. – URL: DOI: 10.2312/egs.20021044
14. Boada, I. Approximations of 3D generalized Voronoi diagrams / I. Boada [et al.] // Proceedings of the 21st European Workshop on Computational Geometry. – 2005. – P. 163–166.
15. Boada, I. Approximations of 2D and 3D generalized Voronoi diagrams / I. Boada [et al.] // International Journal of Computer Mathematics. – 2008. – Vol. 85(7). – P. 1003–1022. – URL: DOI: 10.1080/00207160701466362
16. Yap, C. K. Towards exact numerical Voronoi diagrams / C. K. Yap, V. Sharma, J. M. Lien // Ninth International Symposium on Voronoi Diagrams in Science and Engineering. – 2012. – P. 2–16. – URL: DOI: 10.1109/ISVD.2012.31
17. Edwards, J. Approximating the Generalized Voronoi Diagram of Closely Spaced Objects / J. Edwards [et al.] // Computer Graphics Forum. – 2015. – Vol. 34(2). – P. 299–309. – URL: DOI: 10.1111/cgf.12561
18. Etzion, M. Computing Voronoi skeletons of a 3-D polyhedron by space subdivision / M. Etzion, A. Rappaport // Computational Geometry. – 2002. – Vol. 21(3). – P. 87–120. – URL: DOI: 10.1016/S0925-7721(01)00056-6
19. Foskey, M. Efficient computation of a simplified medial axis / M. Foskey, M. Lin, D. Manocha // Journal of Computing and Information Science in Engineering. – 2003. – Vol. 3(4). – P. 274–284. – URL: DOI: 10.1115/1.1631582
20. Culver, T. Exact computation of the me-dial axis of a polyhedron / T. Culver, J. Keyser, D. Manocha // Computer Aided Geometric Design. – 2004. – Vol. 21(1). – P. 65–98. – URL: DOI: 10.1016/j.cagd.2003.07.008
21. Sud, A. Homotopy-preserving medial axis simplification / A. Sud, M. Foskey, D. Manocha // International Journal of Computational Geometry & Applications. – 2007. – Vol. 17(5). – P. 423–451. – URL: DOI: 10.1142/S0218195907002434
22. Stolpner, S. Sampled Medial Loci for 3D Shape Representation / S. Stolpner, S. Whitesides, K. Siddiqi //Computer Vision and Image Understanding. – 2011. – Vol. 115(5). – P. 695–706. – URL: DOI: 10.1016/j.cviu.2010.10.014
23. Hoff, K. E. III. Fast computation of generalized Voronoi diagrams using graphics hardware / K. E. Hoff III [et al.] // Proceedings of the 26th annual conference on Computer graphics and interactive techniques. – 1999. – P. 277–286. – URL: DOI: 10.1145/311535.311567
24. Hsieh, H. A simple GPU-based approach for 3D Voronoi diagram construction and visualization / H. Hsieh, W. Tai // Simulation Modelling Practice and Theory. – 2005. – Vol. 13(8). – P. 681–692. – URL: DOI: 10.1016/j.simpat.2005.08.003
25. Fischer, I. Fast Approximation of High-Order Voronoi Diagrams and Distance Transforms on the GPU / I. Fischer, C. Gotsman // Journal of Graphics, GPU, and Game Tools. – 2006. –Vol. 11(4). – P. 39–60. – URL: DOI: 10.1080/2151237X.2006.10129229
26. Sud, A. Fast proximity computation among deformable models using discrete Voronoi diagrams / A. Sud [et al.] // ACM Transactions on Graphics (TOG). – 2006. – Vol. 25(3). – P. 1144–1153. – URL: DOI: 10.1145/1141911.1142006
27. Sud, A. Interactive 3d distance field computation using linear factorization / A. Sud [et al.] // Proceedings of the 2006 symposium on Interactive 3D graphics and games. – 2006. – P. 117–124. – URL: DOI: 10.1145/1111411.1111432
28. Rong, G. Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams / G. Rong, T. S. Tan // 4th International Symposium on Voronoi Diagrams in Sci ence and Engineering. – 2007. – P. 176–181. – URL: DOI: 10.1109/ISVD.2007.41
29. Wu, X. GPU-Based Feature-Preserving Distance Field Computation / X. Wu [et al.] // International Conference on Cyberworlds. – 2008. – Vol. 1. – P. 203–208. – URL: DOI: 10.1109/CW.2008.62
30. Cao, T. T. Parallel Banding Algorithm to compute exact distance transform with the GPU / T. T. Cao [et al.] // Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games. – 2010. – P. 83–90. – URL: DOI: 10.1145/1730804.1730818
31. Jones, M. W. 3D distance fields: a survey of techniques and applications / M. W. Jones, J. A. Baerentzen, M. Sramek // IEEE Trans Vis Comput Graph. – 2006. – Vol. 12(4). – P. 581–599. – URL: DOI: 10.1109/TVCG.2006.56
2. Lee, D. T. Medial axis transformation of a planar shape / D. T. Lee // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 1982. – Vol. 4(4). – P. 363-369. – URL: DOI: 10.1007/978-3-540-77974-2
5. Местецкий, Л. М. Непрерывная морфология бинарных изображений. Фигуры, скелеты, циркуляры / Л. М. Местецкий. – Москва : Физматлит, 2009. – 288 с.
6. Okabe, A. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams / A. Okabe [et al.] ; with a foreword by D. G. Kendall. – 2nd ed. p. cm. – New York : John Wiley & Sons Ltd., 2008. – 671 p.
7. Everett, H. The Voronoi Diagram of Three Lines / H. Everett [at al.] // Discrete & Computational Geometry. – 2009. – Vol. 42(1). – P. 94–130. – URL: DOI: 10.1007/s00454-009-9173-3
8. Lavender, D. Voronoi Diagrams of Set-Theoretic solid Models / D. Lavender [et al.] // IEEE Computer Graphics and Applications. – 1992. – Vol. 12(5). – P. 69-77. – URL: DOI: 10.1109/38.156016
9. Vleugels, J. Approximating Generalized Vo-ronoi Diagrams in Any Dimension / J. Vleugels, M. Overmars // Technical report 14, Depart ment of Computer Science, Utrecht University. – 1995. – 21 p.
10. Vleugels, J. Approximating Voronoi Diagrams of Convex Sites in Any Dimension / J. Vleugels, M. Overmars // International Journal of Computational Geometry & Applications. – 1998. – Vol. 8(2). – P. 201–221. – URL: DOI: 10.1142/S0218195998000114
11. Teichmann, M. Polygonal approximation of Voronoi diagrams of a set of triangles in three dimensions / M. Teichmann, S. Teller // Technical Report 766, Laboratory of Computer science, MIT. – 1997. – 12 p.
12. Telea, A. Visualization of Generalized Voronoi Diagrams / A. Telea, J. J. van Wijk // Data Visualization 2001. – 2001. – P. 165–174. – URL: DOI: 10.1007/978-3-7091-6215-6_18
13. Boada, I. The Voronoi-Quadtree: construction and visualization / I. Boada, N. Coll, J. A. Sellares // Eurographics 2002. – 2002. – P. 349–355. – URL: DOI: 10.2312/egs.20021044
14. Boada, I. Approximations of 3D generalized Voronoi diagrams / I. Boada [et al.] // Proceedings of the 21st European Workshop on Computational Geometry. – 2005. – P. 163–166.
15. Boada, I. Approximations of 2D and 3D generalized Voronoi diagrams / I. Boada [et al.] // International Journal of Computer Mathematics. – 2008. – Vol. 85(7). – P. 1003–1022. – URL: DOI: 10.1080/00207160701466362
16. Yap, C. K. Towards exact numerical Voronoi diagrams / C. K. Yap, V. Sharma, J. M. Lien // Ninth International Symposium on Voronoi Diagrams in Science and Engineering. – 2012. – P. 2–16. – URL: DOI: 10.1109/ISVD.2012.31
17. Edwards, J. Approximating the Generalized Voronoi Diagram of Closely Spaced Objects / J. Edwards [et al.] // Computer Graphics Forum. – 2015. – Vol. 34(2). – P. 299–309. – URL: DOI: 10.1111/cgf.12561
18. Etzion, M. Computing Voronoi skeletons of a 3-D polyhedron by space subdivision / M. Etzion, A. Rappaport // Computational Geometry. – 2002. – Vol. 21(3). – P. 87–120. – URL: DOI: 10.1016/S0925-7721(01)00056-6
19. Foskey, M. Efficient computation of a simplified medial axis / M. Foskey, M. Lin, D. Manocha // Journal of Computing and Information Science in Engineering. – 2003. – Vol. 3(4). – P. 274–284. – URL: DOI: 10.1115/1.1631582
20. Culver, T. Exact computation of the me-dial axis of a polyhedron / T. Culver, J. Keyser, D. Manocha // Computer Aided Geometric Design. – 2004. – Vol. 21(1). – P. 65–98. – URL: DOI: 10.1016/j.cagd.2003.07.008
21. Sud, A. Homotopy-preserving medial axis simplification / A. Sud, M. Foskey, D. Manocha // International Journal of Computational Geometry & Applications. – 2007. – Vol. 17(5). – P. 423–451. – URL: DOI: 10.1142/S0218195907002434
22. Stolpner, S. Sampled Medial Loci for 3D Shape Representation / S. Stolpner, S. Whitesides, K. Siddiqi //Computer Vision and Image Understanding. – 2011. – Vol. 115(5). – P. 695–706. – URL: DOI: 10.1016/j.cviu.2010.10.014
23. Hoff, K. E. III. Fast computation of generalized Voronoi diagrams using graphics hardware / K. E. Hoff III [et al.] // Proceedings of the 26th annual conference on Computer graphics and interactive techniques. – 1999. – P. 277–286. – URL: DOI: 10.1145/311535.311567
24. Hsieh, H. A simple GPU-based approach for 3D Voronoi diagram construction and visualization / H. Hsieh, W. Tai // Simulation Modelling Practice and Theory. – 2005. – Vol. 13(8). – P. 681–692. – URL: DOI: 10.1016/j.simpat.2005.08.003
25. Fischer, I. Fast Approximation of High-Order Voronoi Diagrams and Distance Transforms on the GPU / I. Fischer, C. Gotsman // Journal of Graphics, GPU, and Game Tools. – 2006. –Vol. 11(4). – P. 39–60. – URL: DOI: 10.1080/2151237X.2006.10129229
26. Sud, A. Fast proximity computation among deformable models using discrete Voronoi diagrams / A. Sud [et al.] // ACM Transactions on Graphics (TOG). – 2006. – Vol. 25(3). – P. 1144–1153. – URL: DOI: 10.1145/1141911.1142006
27. Sud, A. Interactive 3d distance field computation using linear factorization / A. Sud [et al.] // Proceedings of the 2006 symposium on Interactive 3D graphics and games. – 2006. – P. 117–124. – URL: DOI: 10.1145/1111411.1111432
28. Rong, G. Variants of Jump Flooding Algorithm for Computing Discrete Voronoi Diagrams / G. Rong, T. S. Tan // 4th International Symposium on Voronoi Diagrams in Sci ence and Engineering. – 2007. – P. 176–181. – URL: DOI: 10.1109/ISVD.2007.41
29. Wu, X. GPU-Based Feature-Preserving Distance Field Computation / X. Wu [et al.] // International Conference on Cyberworlds. – 2008. – Vol. 1. – P. 203–208. – URL: DOI: 10.1109/CW.2008.62
30. Cao, T. T. Parallel Banding Algorithm to compute exact distance transform with the GPU / T. T. Cao [et al.] // Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games. – 2010. – P. 83–90. – URL: DOI: 10.1145/1730804.1730818
31. Jones, M. W. 3D distance fields: a survey of techniques and applications / M. W. Jones, J. A. Baerentzen, M. Sramek // IEEE Trans Vis Comput Graph. – 2006. – Vol. 12(4). – P. 581–599. – URL: DOI: 10.1109/TVCG.2006.56
Опубликован
2019-04-13
Как цитировать
Хальзов, С. А., & Фертиков, В. В. (2019). Аппроксимация диаграммы вороного k-го порядка. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (2), 23-37. https://doi.org/10.17308/sait.2019.2/1287
Выпуск
Раздел
Математические методы системного анализа и управления
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
