Граф видимости
В вычислительной геометрии и планировании движений роботов граф видимости — это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. Любая вершина в графе представляет точку пространства, а любое ребро представляет прямую видимость между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность. Графы видимости, таким образом, распространяются на область анализа временных рядов.
Приложения[править | править код]
Графы видимости можно использовать для поиска кратчайших путей среди многоугольных препятствий на плоскости — кратчайший путь между двумя препятствиями проходит по прямой и поворачивает в вершинах препятствий, так что кратчайший путь является кратчайшим путём в графе видимости, вершинами которого являются начальная и конечная точки и вершины препятствий[1][2]. Таким образом, задача о кратчайшем пути может быть разбита на две более простые задачи — построение графа видимости и применение к графу алгоритма кратчайшего пути, такого как алгоритм Дейкстры. Для планирования движения робота, который имеет заметный размер по сравнению с препятствиями, может быть использован похожий подход путём увеличения препятствий для компенсации размера робота[1][2]. Лозано-Перец и Весли[2] приписывают метод графа видимости для кратчайшего пути на евклидовой плоскости исследованию 1969 года Нильса Нильссона по планированию движения робота Шеки и цитируют описание этого метода в 1973-м году русскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским.
Графы видимости могут быть использованы также для вычисления положения радиоантенн или как средство в архитектуре и градостроительстве при анализе видимости.
Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность[3]. Этот частный случай строит мост между временными рядами, динамическими системами и теорией графов.
Характеризация[править | править код]
Граф видимости простого многоугольника (т.е. без пересечения сторон) имеет вершины в качестве точек в пространстве и внешнюю область многоугольника в качестве препятствия. Графы видимости простых многоугольников должны быть гамильтоновыми — граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости образуют простой многоугольник. Фактически, графы видимости простых многоугольников не обладают характеристиками какого-то класса графов[4].
Связанные задачи[править | править код]
Задача о картинной галерее — это задача поиска небольшого набора точек, таких, что все другие точки видны из точек этого набора. Некоторые формы задачи о картинной галерее можно интерпретировать как поиск доминирующего множества в графе видимости.
Бикасательные системы многоугольников или кривых — это прямые, которые касаются двух многоугольников. Бикасательные множества многоугольников образует подмножество графа видимости, который имеет вершины многоугольников в качестве вершин графа (точек пространства), многоугольники служат препятствиями. Граф видимости для задачи поиска кратчайшего пути может быть улучшен путём формирования бикасательных вместо всех рёбер видимости, поскольку кратчайший путь может проходить только вдоль бикасательных[5].
См. также[править | править код]
Примечания[править | править код]
- ↑ 1 2 de Berg, van Kreveld, Overmars, Schwarzkopf, 2000, с. sections 5.1, 5.3.
- ↑ 1 2 3 Lozano-Pérez, Wesley, 1979.
- ↑ Lacasa et al., From time series to complex networks: the visibility graph, PNAS 105, 13 (2008). Дата обращения: 8 декабря 2016. Архивировано 13 июня 2017 года.
- ↑ Ghosh, 1997, с. 143–162.
- ↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000, с. 316.
Литература[править | править код]
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry // 2nd. — Springer-Verlag, 2000. — С. 307–317. — ISBN 3-540-65620-0.
- Tomás Lozano-Pérez, Michael A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles // Communications of the ACM. — 1979. — Т. 22, вып. 10. — С. 560–570. — doi:10.1145/359156.359164.
- S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons // Discrete & Computational Geometry. — 1997. — Т. 17, вып. 2. — С. 143–162. — ISSN 0179-5376. — doi:10.1007/BF02770871.
Ссылки[править | править код]
- VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software can be used for calculating visibility graphs of polygonal environments with polygonal holes. A Matlab interface is also included. Архивная копия от 18 января 2018 на Wayback Machine
 | Для улучшения этой статьи желательно:
|