В вычислительном геометрии и робот планирования движения , видимость график представляет собой график из взаимовидимых мест, как правило , для множества точек и препятствий в евклидовой плоскости . Каждый узел на графике представляет местоположение точки, а каждое ребро представляет собой видимую связь между ними. То есть, если отрезок линии, соединяющий два места, не проходит через какое-либо препятствие, на графике между ними рисуется ребро. Когда набор местоположений находится в строке, это можно понимать как упорядоченную серию. Поэтому графики видимости были расширены до области анализа временных рядов .
Приложения
Графы видимости могут использоваться для поиска кратчайших евклидовых путей среди множества многоугольных препятствий на плоскости: кратчайший путь между двумя препятствиями следует по прямым отрезкам, за исключением вершин препятствий, где он может повернуться, поэтому кратчайший евклидов путь - это отрезок прямой линии. кратчайший путь в графе видимости, узлами которого являются начальная и конечная точки, а также вершины препятствий. [1] Таким образом, проблема кратчайшего евклидова пути может быть разложена на две более простые подзадачи: построение графа видимости и применение алгоритма кратчайшего пути, такого как алгоритм Дейкстры, к графу. Для планирования движения робота, который имеет существенные размеры по сравнению с препятствиями, подобный подход может использоваться после расширения препятствий, чтобы компенсировать размер робота. [1] Lozano-Pérez & Wesley (1979) приписывают метод графа видимости для кратчайших евклидовых путей исследованию Нильса Нильссона 1969 года по планированию движения для робота Шейки , а также цитируют описание этого метода в 1973 году российскими математиками М.Б. Игнатом. Ев, Ф. М. Кулаков, А. М. Покровский.
Графики видимости также могут использоваться для расчета размещения радиоантенн или в качестве инструмента, используемого в архитектуре и городском планировании посредством анализа графов видимости .
График видимости набора местоположений, лежащих на линии, можно интерпретировать как теоретико-графическое представление временного ряда. [2] Этот частный случай наводит мост между временными рядами , динамическими системами и теорией графов .
Характеристика
На графике видимости простого многоугольника вершины многоугольника являются его точками, а внешняя часть многоугольника является единственным препятствием. Графы видимости простых многоугольников должны быть гамильтоновыми графами : граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости индуцируют простой многоугольник. Фактически, графы видимости простых многоугольников не обладают характеристиками некоторых специальных классов графов. [3]
Связанные проблемы
Проблема художественной галереи - это проблема поиска небольшого набора точек, из которого видны все другие точки, не являющиеся препятствиями. Определенные формы проблемы художественной галереи можно интерпретировать как нахождение доминирующего множества в графе видимости.
В бикасательных из системы полигонов или кривых линий , которые касаются двух из них , не проникая их в точках контакта. Битовые касательные набора многоугольников образуют подмножество графа видимости, в котором вершины многоугольника являются его узлами, а сами многоугольники - препятствиями. Подход на основе графа видимости к проблеме евклидова кратчайшего пути может быть ускорен путем формирования графа из битовых касательных вместо использования всех ребер видимости, поскольку евклидов кратчайший путь может входить или выходить за границу препятствия только вдоль битового касания. [4]
Смотрите также
Заметки
- ^ а б де Берг и др. (2000) , разделы 5.1 и 5.3; Лозано-Перес и Уэсли (1979) .
- ^ Лакаса, Лукас; Луке, Бартоло; Бальестерос, Фернандо; Луке, Хорди; Нуньо, Хуан Карлос (2008). «От временных рядов к сложным сетям: график видимости» . Труды Национальной академии наук . 105 (13): 4972–4975. arXiv : 0810.0920 . DOI : 10.1073 / pnas.0709247105 . PMC 2278201 . PMID 18362361 .
- ^ Гош, СК (1997-03-01). «О распознавании и характеристике графов видимости простых многоугольников» . Дискретная и вычислительная геометрия . 17 (2): 143–162. DOI : 10.1007 / BF02770871 . ISSN 0179-5376 .
- ^ де Берг и др. (2000) , стр. 316.
Рекомендации
- де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000), «Глава 15: Графики видимости», Вычислительная геометрия (2-е изд.), Springer-Verlag , стр. 307–317 , ISBN 978-3-540-65620-3.
- Лосано-Перес, Томас; Уэсли, Майкл А. (1979), «Алгоритм планирования путей бесстолкновительности среди многогранных препятствий», коммуникаций АСМ , 22 (10): 560-570, DOI : 10,1145 / 359156,359164.
Внешние ссылки
- VisiLibity: бесплатная библиотека C ++ с открытым исходным кодом для алгоритмов видимости с плавающей запятой и поддерживающих типов данных. Это программное обеспечение можно использовать для расчета графиков видимости полигональных сред с полигональными отверстиями. Также включен интерфейс Matlab.