Порівняльний аналіз алгоритмів спрощення многокутників та ламаних ліній

  • Дмитро Вікторович Коцур Київський національний університет імені Тараса Шевченка
Ключові слова: многокутник, ламана лінія, візуалізація, алгоритм спрощення

Анотація

У статті проаналізовано існуючі на сьогодні алгоритми спрощення многокутників та ламаних ліній на площині. Проведено порівняльний аналіз оцінок складності алгоритмів, експериментально встановлено час виконання алгоритмів та побудовано криві залежності ступені спрощеності многокутника від значень похибки алгоритму.

Біографія автора

Дмитро Вікторович Коцур, Київський національний університет імені Тараса Шевченка

аспірант кафедри математичної інформатики, факультету комп’ютерних наук та кібернетики

Посилання

1. B. P. Buttenfield, R. B. McMaster, (1991). Map Generalization: making rules for knowledge representation. New York: John Wiley & Sons.
2. V. Tereshchenko, Y. Tereshchenko, (2017). Triangulating a region between arbitrary Polygons. International Journal of Computing, 16, 3, 160-165.
3. M. Berg, O. Cheong, M. Kreveld, M. Overmars, (2008). Computational Geometry: Algorithms and Applications, (3rd ed.). Berlin: Springer.
4. N. Mustafa, S. Krishnan, G. Varadhan, S. Venkatasubramanian, (2006). Dynamic simplification and visualization of large maps. International Journal of Geographical Information Science, 20, 3, 273-302.
5. D. Douglas, T. Peucker, (1973). Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10, 2, 112–122. doi:10.3138/FM57-6770-U75U-7727
6. M. Visvalingam, J. D. Whyatt, (1993). Line generalisation by repeated elimination of points. Cartographic Journal, 30, 46-51.
7. K. Reumann, A. P. M. Witkam, (1973). Optimizing curve segmentation in computer graphics. In Proc. International Computing Symposium, 467–472.
8. H. Opheim, (1982). Fast data reduction of a digitized curve. Geo-Processing, 2, 33–40.
9. T. Lang, (1969). Rules for robot draughtsman. Geographical Magazine, 42, 50-51.
10.Z. Zhao, A. Saalfeld, (1997). Linear-time sleeve-fitting polyline simplification algorithms. InProc. Annual Convention and Exposition Technical Papers, 214-223.
11.J. Song, R. Miao, (2016). A Novel Evaluation Approach for Line Simplification Algorithmstowards Vector Map Visualization. International Journal of Geo-Information, 5, 12, 223. doi: 10.3390/ijgi5120223
12.C. Maple, (2003). Geometric design and space planning using the marching squares andmarching cube algorithms. In Proc. International Conference on Geometric Modeling and Graphics, 90-95. doi: 10.1109/GMAG.2003.1219671
13.P. Cignoni, C. Rocchini, R. Scopigno, (1998). Metro: Measuring Error on Simplified Surfaces.Computer Graphics Forum, 17, 2, 167–174.
Опубліковано
2019-07-08
Як цитувати
[1]
Д. Коцур, Порівняльний аналіз алгоритмів спрощення многокутників та ламаних ліній, ОЕІЕТ, vol 36, № 2, с. 5-13, Лип 2019.
Розділ
Методи та системи оптико-електронної і цифрової обробки зображень та сигналів