Граф видимости: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Луговкин (обсуждение | вклад) |
Спасено источников — 2, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.6 |
||
| (не показано 7 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
В [[Вычислительная геометрия|вычислительной геометрии]] и {{не переведено 5|Планирование движений|планировании движений||motion planning}} [[робот]]ов '''граф видимости''' — это [[Граф (математика)|граф]] взаимной видимости точек пространства, обычно для множества точек и преград на [[Двумерное пространство|евклидовой плоскости]]. Любая [[Вершина (теория графов)|вершина]] в графе представляет точку пространства, а любое [[Теория графов|ребро]] представляет |
В [[Вычислительная геометрия|вычислительной геометрии]] и {{не переведено 5|Планирование движений|планировании движений||motion planning}} [[робот]]ов '''граф видимости''' — это [[Граф (математика)|граф]] взаимной видимости точек пространства, обычно для множества точек и преград на [[Двумерное пространство|евклидовой плоскости]]. Любая [[Вершина (теория графов)|вершина]] в графе представляет точку пространства, а любое [[Теория графов|ребро]] представляет [[Видимость (геометрия)|прямую видимость]] между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность. Графы видимости, таким образом, распространяются на область анализа [[Временной ряд|временных рядов]]. |
||
== Приложения == |
== Приложения == |
||
Графы видимости можно использовать для поиска {{не переведено 5|Кратчайший путь в евклидовом пространстве|кратчайших путей||Euclidean shortest path}} среди [[Многоугольник|многоугольных]] препятствий на плоскости — кратчайший путь между двумя препятствиями проходит по прямой и поворачивает в вершинах препятствий, так что кратчайший путь является кратчайшим путём в графе видимости, вершинами которого являются начальная и конечная точки и вершины препятствий |
Графы видимости можно использовать для поиска {{не переведено 5|Кратчайший путь в евклидовом пространстве|кратчайших путей||Euclidean shortest path}} среди [[Многоугольник|многоугольных]] препятствий на плоскости — кратчайший путь между двумя препятствиями проходит по прямой и поворачивает в вершинах препятствий, так что кратчайший путь является кратчайшим путём в графе видимости, вершинами которого являются начальная и конечная точки и вершины препятствий{{sfn|de Berg, van Kreveld, Overmars, Schwarzkopf|2000|с=sections 5.1, 5.3}}{{sfn|Lozano-Pérez, Wesley|1979}}. Таким образом, задача о кратчайшем пути может быть разбита на две более простые задачи — построение графа видимости и применение к графу алгоритма кратчайшего пути, такого как [[алгоритм Дейкстры]]. Для планирования движения робота, который имеет заметный размер по сравнению с препятствиями, может быть использован похожий подход путём увеличения препятствий для компенсации размера робота{{sfn|de Berg, van Kreveld, Overmars, Schwarzkopf|2000|с=sections 5.1, 5.3}}{{sfn|Lozano-Pérez, Wesley|1979}}. Лозано-Перец и Весли{{sfn|Lozano-Pérez, Wesley|1979}} приписывают метод графа видимости для кратчайшего пути на евклидовой плоскости исследованию 1969 года Нильса Нильссона по планированию движения [[Shakey|робота Шеки]] и цитируют описание этого метода в 1973-м году русскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским. |
||
Графы видимости могут быть использованы также для вычисления положения [[Антенна|радиоантенн]] или как средство в [[Архитектура|архитектуре]] и [[Градостроительство|градостроительстве]] при {{не переведено 5|Анализ видимости|анализе видимости||visibility graph analysis}}. |
Графы видимости могут быть использованы также для вычисления положения [[Антенна|радиоантенн]] или как средство в [[Архитектура|архитектуре]] и [[Градостроительство|градостроительстве]] при {{не переведено 5|Анализ видимости|анализе видимости||visibility graph analysis}}. |
||
Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность |
Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность<ref>{{cite web|title=Lacasa et al., From time series to complex networks: the visibility graph, PNAS 105, 13 (2008)|url=http://www.pnas.org/content/105/13/4972|access-date=2016-12-08|archive-date=2017-06-13|archive-url=https://web.archive.org/web/20170613011350/http://www.pnas.org/content/105/13/4972|deadlink=no}}</ref>. Этот частный случай строит мост между [[Временной ряд|временными рядами]], [[Динамическая система|динамическими системами]] и [[Теория графов|теорией графов]]. |
||
== Характеризация == |
== Характеризация == |
||
Граф видимости простого многоугольника (т.е. без пересечения сторон) имеет вершины в качестве точек в пространстве и внешнюю область многоугольника в качестве препятствия. Графы видимости простых многоугольников должны быть [[Гамильтонов граф|гамильтоновыми]] — граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости образуют простой многоугольник. Фактически, графы видимости простых многоугольников не обладают характеристиками какого-то класса графов |
Граф видимости простого многоугольника (т.е. без пересечения сторон) имеет вершины в качестве точек в пространстве и внешнюю область многоугольника в качестве препятствия. Графы видимости простых многоугольников должны быть [[Гамильтонов граф|гамильтоновыми]] — граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости образуют простой многоугольник. Фактически, графы видимости простых многоугольников не обладают характеристиками какого-то класса графов{{sfn|Ghosh|1997|с=143–162}}. |
||
== Связанные задачи == |
== Связанные задачи == |
||
[[Задача о картинной галерее]] — это задача поиска небольшого набора точек, таких, что все другие точки видны из точек этого набора. Некоторые формы задачи о картинной галерее можно интерпретировать как поиск [[Доминирующее множество|доминирующего множества]] в графе видимости. |
|||
[[Бикасательная|Бикасательные]] системы многоугольников или кривых — это прямые, которые касаются двух многоугольников. Бикасательные множества многоугольников образует подмножество графа видимости, который имеет вершины многоугольников в качестве вершин графа (точек пространства), многоугольники служат препятствиями. Граф видимости для задачи поиска кратчайшего пути может быть улучшен путём формирования бикасательных вместо всех рёбер видимости, поскольку кратчайший путь может проходить только вдоль бикасательных{{sfn|de Berg, van Kreveld, Overmars, Schwarzkopf|2000|с=316}}. |
|||
== См. также == |
== См. также == |
||
| Строка 49: | Строка 49: | ||
*{{статья |
*{{статья |
||
|заглавие = On recognizing and characterizing visibility graphs of simple polygons |
|заглавие = On recognizing and characterizing visibility graphs of simple polygons |
||
|url = |
|url = https://link.springer.com/article/10.1007/BF02770871 |
||
|издание = Discrete & Computational Geometry |
|издание = Discrete & Computational Geometry |
||
|год=1997 |
|год=1997 |
||
| Строка 62: | Строка 62: | ||
== Ссылки == |
== Ссылки == |
||
*[http://www.VisiLibity.org VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software can be used for calculating visibility graphs of polygonal environments with polygonal holes. A Matlab interface is also included.] |
*[http://www.VisiLibity.org VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software can be used for calculating visibility graphs of polygonal environments with polygonal holes. A Matlab interface is also included.] {{Wayback|url=http://www.visilibity.org/ |date=20180118030603 }} |
||
[[Категория:Геометрические графы]] |
[[Категория:Геометрические графы]] |
||
{{rq|checktranslate|style |
{{rq|checktranslate|style}} |
||
Текущая версия от 11:53, 28 марта 2022
В вычислительной геометрии и планировании движений[англ.] роботов граф видимости — это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. Любая вершина в графе представляет точку пространства, а любое ребро представляет прямую видимость между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность. Графы видимости, таким образом, распространяются на область анализа временных рядов.
Приложения
[править | править код]Графы видимости можно использовать для поиска кратчайших путей[англ.] среди многоугольных препятствий на плоскости — кратчайший путь между двумя препятствиями проходит по прямой и поворачивает в вершинах препятствий, так что кратчайший путь является кратчайшим путём в графе видимости, вершинами которого являются начальная и конечная точки и вершины препятствий[1][2]. Таким образом, задача о кратчайшем пути может быть разбита на две более простые задачи — построение графа видимости и применение к графу алгоритма кратчайшего пути, такого как алгоритм Дейкстры. Для планирования движения робота, который имеет заметный размер по сравнению с препятствиями, может быть использован похожий подход путём увеличения препятствий для компенсации размера робота[1][2]. Лозано-Перец и Весли[2] приписывают метод графа видимости для кратчайшего пути на евклидовой плоскости исследованию 1969 года Нильса Нильссона по планированию движения робота Шеки и цитируют описание этого метода в 1973-м году русскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским.
Графы видимости могут быть использованы также для вычисления положения радиоантенн или как средство в архитектуре и градостроительстве при анализе видимости[англ.].
Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность[3]. Этот частный случай строит мост между временными рядами, динамическими системами и теорией графов.
Характеризация
[править | править код]Граф видимости простого многоугольника (т.е. без пересечения сторон) имеет вершины в качестве точек в пространстве и внешнюю область многоугольника в качестве препятствия. Графы видимости простых многоугольников должны быть гамильтоновыми — граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости образуют простой многоугольник. Фактически, графы видимости простых многоугольников не обладают характеристиками какого-то класса графов[4].
Связанные задачи
[править | править код]Задача о картинной галерее — это задача поиска небольшого набора точек, таких, что все другие точки видны из точек этого набора. Некоторые формы задачи о картинной галерее можно интерпретировать как поиск доминирующего множества в графе видимости.
Бикасательные системы многоугольников или кривых — это прямые, которые касаются двух многоугольников. Бикасательные множества многоугольников образует подмножество графа видимости, который имеет вершины многоугольников в качестве вершин графа (точек пространства), многоугольники служат препятствиями. Граф видимости для задачи поиска кратчайшего пути может быть улучшен путём формирования бикасательных вместо всех рёбер видимости, поскольку кратчайший путь может проходить только вдоль бикасательных[5].
См. также
[править | править код]Примечания
[править | править код]- ↑ 1 2 de Berg, van Kreveld, Overmars, Schwarzkopf, 2000, с. sections 5.1, 5.3.
- ↑ 1 2 3 Lozano-Pérez, Wesley, 1979.
- ↑ Lacasa et al., From time series to complex networks: the visibility graph, PNAS 105, 13 (2008). Дата обращения: 8 декабря 2016. Архивировано 13 июня 2017 года.
- ↑ Ghosh, 1997, с. 143–162.
- ↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000, с. 316.
Литература
[править | править код]- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry // 2nd. — Springer-Verlag, 2000. — С. 307–317. — ISBN 3-540-65620-0.
- Tomás Lozano-Pérez, Michael A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles // Communications of the ACM. — 1979. — Т. 22, вып. 10. — С. 560–570. — doi:10.1145/359156.359164.
- S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons // Discrete & Computational Geometry. — 1997. — Т. 17, вып. 2. — С. 143–162. — ISSN 0179-5376. — doi:10.1007/BF02770871.
Ссылки
[править | править код]- VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types. This software can be used for calculating visibility graphs of polygonal environments with polygonal holes. A Matlab interface is also included. Архивная копия от 18 января 2018 на Wayback Machine
 | Для улучшения этой статьи желательно:
|