Граф видимости
В алгоритмической геометрии и планировании движения робота (англ. robot)[1] граф видимости (фр. graphe de visibilité, англ. visibility graph) — это граф, построенный на основе взаимной видимости между точками, обычно заданными среди множества препятствий в евклидовой плоскости. Каждый узел графа представляет точку, а каждое ребро обозначает видимое соединение между двумя точками. Граф видимости содержит ребро между двумя вершинами, если отрезок, соединяющий соответствующие точки, не пересекает ни одного препятствия.
Алгоритмы построения
Наиболее простой алгоритм построения графа видимости имеет временную сложность O(n3) и заключается в переборе всех пар вершин с проверкой пересечения соединяющего их отрезка с каждым из рёбер препятствий. Алгоритм на основе вращающейся прямой (англ. Rotational Sweep) выполняет построение за время O(n2 log n), а его оптимизированные версии достигают сложности O(n2)[2][3]. Для разреженных графов применяется оптимальный выходно-чувствительный алгоритм со сложностью O(n log n + e), где e — количество рёбер в итоговом графе[4]. В трёхмерном пространстве задача нахождения кратчайшего пути среди полиэдральных препятствий является NP-трудной[5]. Для решения задач видимости в 3D-пространстве используются специализированные структуры данных, такие как трёхмерный псевдограф (англ. 3D Pseudo-graph) и скелет видимости (англ. Visibility Skeleton)[6].
Характеристики
Граф видимости простого многоугольника строится по его вершинам, а в качестве препятствия выступает внешняя область многоугольника. Графы видимости простых многоугольников всегда гамильтоновы, поскольку граница многоугольника образует гамильтонов цикл в графе видимости. При этом не любой граф видимости задаёт некоторый простой многоугольник. В то же время эффективной алгоритмической характеристики графов видимости простых многоугольников на сегодняшний день не существует. Такие графы не обязательно принадлежат к известным структурированным семействам: они могут не относиться к перфектным графам, круговым графам или кордальным графам[7]. Исключением является то, что графы видимости простых многоугольников всегда cop-win-графы[8]. Проблема эффективной алгоритмической характеризации графов видимости для произвольных простых многоугольников остаётся открытой. Для многоугольников с отверстиями задача распознавания является ∃R-полной.
Связанные задачи
Задача о галерее состоит в нахождении минимального множества точек (охранников), из которых видна вся область с учётом препятствий. Некоторые формулировки этой задачи могут быть сведены к поиску доминирующего множества в графе видимости.
Битангента системы многоугольников или кривых — это прямая, касающаяся одновременно двух многоугольников (или кривой в двух точках) и не пересекающая другие. Битангенты среди вершин задают подмножество графа видимости, в котором вершины многоугольника служат узлами, а сами многоугольники — препятствиями. Построение графа видимости на основе битангент ускоряет поиск кратчайших евклидовых путей, так как кратчайший путь в плоскости может входить и выходить из границы препятствия только вдоль битангенты.
Применения
Планирование движения и робототехника
Графы видимости применяются для поиска кратчайших евклидовых путей между полигональными препятствиями на плоскости: кратчайший путь между двумя препятствиями состоит из прямолинейных сегментов, за исключением случаев поворота на вершинах препятствий. Следовательно, кратчайший евклидов путь соответствует кратчайшему пути в графе видимости, построенном по начальной и конечной точке и вершинам препятствий. Поэтому задача поиска кратчайшего евклидова пути разбивается на две стадии: построение графа видимости и применение алгоритма поиска кратчайшего пути, например алгоритма Дейкстры. Для планирования движения робота, размеры которого сравнимы с размерами препятствий, используется аналогичный подход, предварительно «увеличив» препятствия на размер робота[9]. Метод графа видимости для поиска кратчайших евклидовых путей был впервые исследован Нильсом Нильссоном (англ. Nils Nilsson) в 1969 году при разработке планирования движения для Shakey, а также описан в 1973 году российскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским.
Архитектура и градостроительство
Графы видимости используются также для расчёта расположения радиоантенн, а также в архитектуре и градостроительстве в рамках анализа графов видимости. В городском планировании и при разработке цифровых двойников городов применяется 3D-анализ видимости. Этот инструмент позволяет оценивать влияние новой застройки на существующий городской ландшафт, а также моделировать городской микроклимат за счёт анализа инсоляции и доли видимой части небесной полусферы[10].[11][12].
Анализ временных рядов
Граф видимости множества точек на одной прямой может быть рассмотрен как графическое представление временного ряда. Такой подход связывает временные ряды, динамические системы и теорию графов. Метод применяется в сфере кибербезопасности для анализа временных рядов с целью обнаружения аномалий и DoS-атак[13].[14] Для решения проблемы потери информации в стандартном алгоритме был предложен метод Complementary Visibility Graph (CVG), а для задач классификации изображений — его модификация Image Complementary Visibility Graph (ICVG).
Примечания
Литература
- de Berg, Mark. Глава 15: Graphs of Visibility // Computational Geometry : [англ.] / Mark de Berg, Marc van Kreveld, Mark Overmars … [et al.]. — Springer-Verlag, 2000. — Vol. 2. — P. 307–317. — ISBN 978-3-540-65620-3.
- Lozano-Pérez, Tomás; Wesley, Michael A. (1979). “An algorithm for planning collision-free paths among polyhedral obstacles”. Communications of the ACM [англ.]. 22 (10): 560—570. DOI:10.1145/359156.359164. Дата обращения 2024-06-09.
|access-date=требует|url=(справка)