График видимости - Visibility graph
В вычислительная геометрия и робот планирование движения, а график видимости это график невидимых мест, как правило, для набора точек и препятствий в Евклидова плоскость. Каждый узел на графике представляет собой точку, и каждый край представляет видимая связь между ними. То есть, если отрезок прямой, соединяющий два места, не проходит через какое-либо препятствие, на графике между ними рисуется ребро. Когда набор местоположений находится в строке, это можно понимать как упорядоченную серию. Поэтому графики видимости были расширены до области Временные ряды анализ.
Приложения
Графики видимости могут быть использованы для поиска Евклидовы кратчайшие пути среди набора многоугольный препятствия на плоскости: кратчайший путь между двумя препятствиями следует по отрезкам прямой, за исключением вершины препятствий, куда он может повернуть, поэтому евклидов кратчайший путь - это кратчайший путь в графе видимости, узлами которого являются начальная и конечная точки, а также вершины препятствий.[1] Следовательно, проблема кратчайшего евклидова пути может быть разложена на две более простые подзадачи: построение графа видимости и применение алгоритма кратчайшего пути, такого как Алгоритм Дейкстры к графику. Для планирования движения робота, который имеет существенные размеры по сравнению с препятствиями, аналогичный подход может использоваться после расширения препятствий, чтобы компенсировать размер робота.[1] Лозано-Перес и Уэсли (1979) приписывают метод графа видимости кратчайших евклидовых путей исследованиям в 1969 г. Нильс Нильссон по планированию движения для Встряхните робота, а также процитируем описание этого метода в 1973 г. российскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским.
Графики видимости также могут использоваться для расчета размещения радиоантенны, или как инструмент, используемый в архитектура и городское планирование через анализ графа видимости.
График видимости набора местоположений, которые лежат на линии, можно интерпретировать как теоретико-графическое представление временного ряда.[2] Этот конкретный случай наводит мост между Временные ряды, динамические системы и теория графов.
Характеристика
График видимости простой многоугольник вершины многоугольника являются его точками, а внешняя часть многоугольника - единственным препятствием. Графики видимости простых многоугольников должны быть Гамильтоновы графы: граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости индуцируют простой многоугольник. Фактически, графы видимости простых многоугольников не обладают характеристиками некоторых специальных классов графов.[3]
Связанные проблемы
В проблема художественной галереи - это проблема поиска небольшого набора точек, из которого видны все другие точки, не являющиеся препятствиями. Определенные формы проблемы художественной галереи можно интерпретировать как поиск доминирующий набор на графике видимости.
В битангенты Системы многоугольников или кривых - это линии, которые касаются двух из них, но не проходят через них в точках соприкосновения. Битовые касательные набора многоугольников образуют подмножество графа видимости, вершины которого являются его узлами, а сами многоугольники - препятствиями. Подход на основе графа видимости к проблеме евклидова кратчайшего пути может быть ускорен за счет формирования графа из битовых касательных вместо использования всех ребер видимости, так как евклидов кратчайший путь может входить или выходить за границу препятствия только вдоль битового касания.[4]
Смотрите также
Примечания
- ^ а б de Berg et al. (2000), разделы 5.1 и 5.3; Лозано-Перес и Уэсли (1979).
- ^ Лакаса, Лукас; Луке, Бартоло; Бальестерос, Фернандо; Луке, Хорди; Нуньо, Хуан Карлос (2008). «От временных рядов к сложным сетям: график видимости». Труды Национальной академии наук. 105 (13): 4972–4975. arXiv:0810.0920. Дои:10.1073 / pnas.0709247105. ЧВК 2278201. PMID 18362361.
- ^ Гош, С. К. (1 марта 1997 г.). «О распознавании и характеристике графиков видимости простых многоугольников». Дискретная и вычислительная геометрия. 17 (2): 143–162. Дои:10.1007 / BF02770871. ISSN 0179-5376.
- ^ de Berg et al. (2000), п. 316.
Рекомендации
- де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк; Шварцкопф, Отфрид (2000), "Глава 15: Графики видимости", Вычислительная геометрия (2-е изд.), Springer-Verlag, стр.307–317, ISBN 978-3-540-65620-3.
- Лозано-Перес, Томас; Уэсли, Майкл А. (1979), "Алгоритм планирования путей без столкновений между многогранными препятствиями", Коммуникации ACM, 22 (10): 560–570, Дои:10.1145/359156.359164.