График видимости
В вычислительной геометрии планировании роботов движения и [1] Граф видимости — это граф взаимовидимых местоположений, обычно для набора точек и препятствий на евклидовой плоскости . Каждый узел графа представляет собой местоположение точки, а каждое ребро представляет видимую связь между ними. То есть, если отрезок линии, соединяющий две локации, не проходит через какое-либо препятствие, между ними на графике рисуется ребро. Когда набор локаций лежит в линию, это можно понимать как упорядоченную серию. Таким образом, графики видимости были расширены до области анализа временных рядов .
Приложения
[ редактировать ]Графы видимости можно использовать для поиска евклидовых кратчайших путей среди множества многоугольных препятствий на плоскости: кратчайший путь между двумя препятствиями следует по отрезкам прямых линий, за исключением вершин препятствий , где он может поворачивать, поэтому евклидов кратчайший путь - это кратчайший путь в графе видимости, узлами которого являются начальная и конечная точки, а также вершины препятствий. [2] Следовательно, евклидову задачу о кратчайшем пути можно разложить на две более простые подзадачи: построение графа видимости и применение алгоритма кратчайшего пути, такого как алгоритм Дейкстры к графу . Для планирования движения робота, размер которого не пренебрежимо мал по сравнению с препятствиями, можно использовать аналогичный подход после расширения препятствий для компенсации размера робота. [2] Лозано-Перес и Уэсли (1979) приписывают метод графа видимости для евклидовых кратчайших путей исследованиям Нильса Нильссона в 1969 году по планированию движения робота Шейки , а также цитируют описание этого метода в 1973 году российскими математиками М.Б. Игнатьевым, Ф.М. Кулаков и А.М. Покровский.
Графики видимости также могут использоваться для расчета размещения радиоантенн или в качестве инструмента, используемого в архитектуре и городском планировании посредством анализа графиков видимости .
График видимости набора местоположений, лежащих на линии, можно интерпретировать как теоретико-графовое представление временного ряда. [3] Этот конкретный случай строит мост между временными рядами , динамическими системами и теорией графов .
Характеристика
[ редактировать ]Граф видимости простого многоугольника имеет вершины многоугольника в качестве точек, а внешнюю часть многоугольника - в качестве единственного препятствия. Графы видимости простых многоугольников должны быть гамильтоновыми графами : граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости порождают простой многоугольник. Однако эффективная алгоритмическая характеристика графов видимости простых многоугольников остается неизвестной. Эти графы не попадают во многие известные семейства хорошо структурированных графов: они могут не быть совершенными графами , круговыми графами или хордальными графами . [4] Исключением из этого явления является то, что графы видимости простых многоугольников являются графами «коп-выигрыш» . [5]
Связанные проблемы
[ редактировать ]Задача художественной галереи — это проблема поиска небольшого набора точек, из которого видны все остальные точки, не являющиеся препятствиями. Определенные формы проблемы художественной галереи можно интерпретировать как поиск доминирующего множества в графе видимости.
Бикасательные системы многоугольников или кривых — это линии, которые касаются двух из них, не пересекая их в точках соприкосновения. Биткасательные набора многоугольников образуют подмножество графа видимости, в котором вершины многоугольника являются узлами, а сами многоугольники - препятствиями. Подход к задаче евклидова кратчайшего пути с использованием графа видимости можно ускорить за счет формирования графа из бикасательных вместо использования всех ребер видимости, поскольку евклидов кратчайший путь может входить или выходить из границы препятствия только по бикасательной. [6]
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Ню, Ханлин; Савварис, Ал; Цурдос, Антониос; Цзи, Зе (2019). «Алгоритм планирования пути для беспилотных надводных транспортных средств на основе дорожной карты Вороного-Visibility» (PDF) . Журнал навигации . 72 (4): 850–874. дои : 10.1017/S0373463318001005 . ISSN 0373-4633 . S2CID 67908628 .
- ^ Перейти обратно: а б Берг и др. (2000) , разделы 5.1 и 5.3; Лозано-Перес и Уэсли (1979) .
- ^ Лакаса, Лукас; Луке, Бартоло; Баллестерос, Фернандо; Люке, Хорди; Нуньо, Хуан Карлос (2008). «От временных рядов к сложным сетям: график видимости» . Труды Национальной академии наук . 105 (13): 4972–4975. arXiv : 0810.0920 . Бибкод : 2008PNAS..105.4972L . дои : 10.1073/pnas.0709247105 . ПМК 2278201 . ПМИД 18362361 .
- ^ Гош, СК (1 марта 1997 г.). «О распознавании и характеристике графов видимости простых многоугольников» . Дискретная и вычислительная геометрия . 17 (2): 143–162. дои : 10.1007/BF02770871 . ISSN 0179-5376 .
- ^ Любив, Анна ; Снойинк, Джек; Восупур, Хамиде (2017). «Графики видимости, демонтаж и игра в полицейских и грабителей». Вычислительная геометрия . 66 : 14–27. arXiv : 1601.01298 . дои : 10.1016/j.comgeo.2017.07.001 . МР 3693353 .
- ^ от Берга и др. (2000) , с. 316.
Ссылки
[ редактировать ]- де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000), «Глава 15: Графы видимости», Вычислительная геометрия (2-е изд.), Springer-Verlag , стр. 307–317 , ISBN 978-3-540-65620-3 .
- Лосано-Перес, Томас; Уэсли, Майкл А. (1979), «Алгоритм планирования путей без столкновений среди многогранных препятствий», Communications of the ACM , 22 (10): 560–570, doi : 10.1145/359156.359164 , S2CID 17397594 .