Оптимизация алгоритма построения графа видимости
DOI:
https://doi.org/10.32603/2071-2340-2026-2-20-33Ключевые слова:
граф видимости, планирование пути, алгоритм Ли, заметающий луч, вычислительная геометрия, редуцированный граф видимости, дефрагментация памятиАннотация
Предложены оптимизации алгоритма Ли для построения графа видимости на плоскости с полигональными препятствиями. Оптимизации включают исключение заведомо незначащих рёбер, отсев вершин на основе геометрических свойств, дефрагментированное хранение графа в памяти и распараллеливание обработки вершин-источников. Рассмотрены различные способы представления графа и их влияние на производительность.Библиографические ссылки
N. J. Nilsson, "A mobile automaton: An application of artificial intelligence techniques," in Proceedings of the 1st International Joint Conference on Artificial Intelligence (IJCAI'69), D. E. Walker and L. M. Norton, Eds., 1969, pp. 509-520.
D. T. Lee, "Proximity and reachability in the plane," Ph.D. dissertation, University of Illinois at Urbana-Champaign, 1978.
D. Coleman, "Lee's O(n2log n) visibility graph algorithm: Implementation and analysis," University of Colorado at Boulder, Technical report, 2012.
S. K. Ghosh and D. M. Mount, "An output-sensitive algorithm for computing visibility graphs," in Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS'87). IEEE, 1987, pp. 11-19, doi: 10.1109/SFCS.1987.6.
M. H. Overmars and E. Welzl, "New methods for computing visibility graphs," in Proceedings of the fourth annual symposium on Computational geometry (SCG'88), 1988, pp. 164-171, doi: 10.1145/73393.73410.
K. Daniel, A. Nash, S. Koenig, and A. Felner, "Theta*: Any-angle path planning on grids," Journal of Artificial Intelligence Research, vol. 39, pp. 533-579, 2010, doi: 10.1613/jair.2994.
A. Nash, S. Koenig, and C. Tovey, "Lazy Theta*: Any-angle path planning and path length analysis in 3D," in Proc. of the AAAI Conference on Artificial Intelligence, M. Fox and D. Poole, Eds., vol. 24. Palo Alto, California USA: AAAI Press, 2010, pp. 147-154, doi: 10.1609/aaai.v24i1.7566.
D. Harabor and A. Grastien, "An optimal any-angle pathfinding algorithm," in Proc. of the International Conference on Automated Planning and Scheduling (ICAPS), D. Borrajo, S. Kambhampati, A. Oddi, and S. Fratini, Eds., vol. 23, 2013, pp. 308-311, doi: 10.1609/icaps.v23i1.13609.
D. Ferguson and A. Stentz, "Field D*: An interpolation-based path planner and replanner," in Robotics Research, S. Thrun, R. Brooks, and H. Durrant-Whyte, Eds. Berlin, Heidelberg: Springer, 2007, pp. 239–253, doi: 10.1007/978-3-540-48113-3_22.
J. O'Rourke and I. Streinu, "The vertex-edge visibility graph of a polygon," Computational Geometry, vol. 10, no. 2, pp. 105–120, 1998, doi: 10.1016/S0925-7721(97)00011-4.
Boost graph library: Adjacency list. [Online]. Available: https://www.boost.org/doc/libs/1_91_0/libs/graph/doc/adjacency_list.html
Boost graph library: Compressed sparse row. [Online]. Available: https://www.boost.org/doc/libs/1_91_0/libs/graph/doc/compressed_sparse_row.html
M. Besta, D. Stanojevic, T. Zivic, J. Singh, M. Hoerold, and T. Hoefler, "Log(graph): a near-optimal high-performance graph representation," in Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques, 2018, doi: 10.1145/3243176.3243198.
Egerváry Research Group. Lemon - library for efficient modeling and optimization in networks. [Online]. Available: http://lemon.cs.elte.hu/trac/lemon
D. Pavlov, M. Rybalkin, B. Karulin, M. Kozhevnikov, A. Savelyev, and A. Churinov, "Indigo: universal cheminformatics api," J Cheminform, vol. 3, no. Suppl 1, p. P4, 2011, doi: 10.1186/1758-2946-3-S1-P4.
EPAM Systems. Indigo github repository. [Online]. Available: https://github.com/epam/Indigo
U.S. Office of Coast Survey. NOAA ENC electronic navigational charts. [Online]. Available: https://charts.noaa.gov/ENCs/ENCsIndv.shtml
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2026 Maxim Barinov, Dmitry Pavlov
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
