Нахождение кратчайшего пути с обходом препятствий в плоском пространстве
Задача: найти самый короткий путь в обход многоугольника GFEJIH из точки A в точку C.
Процесс решения задачи можно разделить на 2 части:
- Формирование набора вершин графа и ребер, соединяющих вершины на основании исходных данных;
- Нахождение кратчайшего пути используя алгоритм нахождения кратчайшего пути в графе.
Для решения первой части задачи необходимы знания из области геометрии. Более конкретно - алгоритм определения пересечения отрезков в Евклидовом пространстве.
Необходимо сформировать все возможные комбинации отрезков в данном пространстве и выполнить проверку для каждого отрезка на пересечение с отрезками, принадлежащими к многоугольнику GFEJIH. Другими словами, выполнить проверку на наличие геометрической видимости между точками. Если проверяемый отрезок пересекается с одной из сторон многоугольника, это значит, что точки, которые он соединяет не находятся в геометрической видимости относительно друг друга, следовательно, не могут быть соединены напрямую и этот отрезок не может быть ребром графа для нахождения кратчайшего пути. И наоборот: если проверяемый отрезок не имеет пересечений со сторонами многоугольника, то точки находятся в геометрической видимости относительно друг друга, такое ребро может быть использовано для нахождения кратчайшего пути в данном контексте.
Стоит отметить, что в граф добавляются все отрезки (вершины и ребра), которые не имеют пересечений со сторонами многоугольника, а также отрезки, формирующие стороны многоугольника.
Необходимо сформировать все возможные комбинации отрезков в данном пространстве и выполнить проверку для каждого отрезка на пересечение с отрезками, принадлежащими к многоугольнику GFEJIH. Другими словами, выполнить проверку на наличие геометрической видимости между точками. Если проверяемый отрезок пересекается с одной из сторон многоугольника, это значит, что точки, которые он соединяет не находятся в геометрической видимости относительно друг друга, следовательно, не могут быть соединены напрямую и этот отрезок не может быть ребром графа для нахождения кратчайшего пути. И наоборот: если проверяемый отрезок не имеет пересечений со сторонами многоугольника, то точки находятся в геометрической видимости относительно друг друга, такое ребро может быть использовано для нахождения кратчайшего пути в данном контексте.
Стоит отметить, что в граф добавляются все отрезки (вершины и ребра), которые не имеют пересечений со сторонами многоугольника, а также отрезки, формирующие стороны многоугольника.
Далее, на основании данных, полученных в ходе решения первой части задачи составляем математический граф.
Так, к примеру, согласно данным изображенным на рисунке выше, из точки A в точку C можно попасть тремя возможными путями:
- AFEJC
- AGHIC
- AHIC
Для нахождения кратчайшего пути в графе я применяю алгоритм Дейкстры. Алгоритм находит кратчайшее расстояние между каждой последующей вершиной, принимая во внимание вес ребер (в этом примере вес ребра - Евклидово расстояние между двумя вершинами; длина отрезков). Набор ребер соединяющих вершины графа, между которыми и происходит поиск кратчайшего пути, а также обладающий наименьшим суммарным весом, является кратчайшим путем между двумя вершинами.
Реализация алгоритма на чуть более чем двух десятках языков программирования есть на Rosetta Code.
Интересное обучающее видео от Google по поиску пути. Видео на чужеземном языке, но с иллюстрациями, общий ход мыслей понятен.
Реализация алгоритма на чуть более чем двух десятках языков программирования есть на Rosetta Code.
Интересное обучающее видео от Google по поиску пути. Видео на чужеземном языке, но с иллюстрациями, общий ход мыслей понятен.
0 коммент. :
Отправить комментарий