Оглавление
График видимости
-
Основы графиков видимости
- График видимости – это график промежуточных местоположений для набора точек и препятствий на плоскости.
- Каждый узел на графике представляет местоположение точки, а каждое ребро – видимую связь между ними.
- Если точки расположены на одной линии, то это можно интерпретировать как упорядоченный ряд.
-
Применение графиков видимости
- Графики видимости используются для нахождения кратчайших евклидовых путей среди многоугольных препятствий.
- Они также применяются для планирования движения роботов и в архитектуре и городском планировании.
-
Характеристики графиков видимости
- Графики видимости простых многоугольников являются гамильтоновыми, но не все графики видимости простых многоугольников индуцируют простые многоугольники.
- Они не относятся к известным семействам хорошо структурированных графов, но являются графами взаимного выигрыша.
-
Связанные задачи
- Задача о художественной галерее – это поиск набора точек, из которого видны все остальные точки.
- Касательные системы многоугольников образуют подмножество графа видимости.
- Подход к задаче о кратчайшем пути на графе видимости может быть ускорен за счет использования битангенсов вместо всех ребер видимости.
-
Дополнительные ресурсы
- VisiLibity – это бесплатная библиотека C++ с открытым исходным кодом для алгоритмов видимости.
- Она поддерживает полигональные среды с полигональными отверстиями и имеет интерфейс Matlab.
Полный текст статьи: