Кратчайший путь внутри алгоритма многоугольника / псевдокод

Question

У меня есть многоугольник (в PHP), представленный массивом точек X, Y.Я хочу найти кратчайший путь внутри многоугольника между точкой A и точкой B. На практике у меня есть произвольная область, определенная как простой многоугольник, через которую я хочу узнать расстояние (например, представь, что это многоугольник, представляющийтрейл - я хочу оценить, как долго тянется трейл).

Нужен псевдокод или несколько советов, с чего начать.Я искал в интернете и, кажется, мне не повезло, за исключением некоторых трудных для понимания работ по триангуляции и воронкообразным алгоритмам.

Answer 1

Простой алгоритм использует тот факт, что путь должен проходить от рефлекторной вершины к рефлексной вершине (за исключением первого и последнего шагов).Поэтому сделайте график, используя все рефлекторные вершины, а также начальную и конечную точки, и используйте стандартный алгоритм кратчайшего пути, чтобы найти кратчайший путь.У меня есть довольно короткий код Mathematica, который делает все это, и скоро опубликую демо на сайте демонстрации.wolfram.com.Отправьте мне сообщение, если хотите код.

Answer 2

Поиск в Google по кратчайшему пути через многоугольник вызывает много полезных ссылок.Хорошее описание одного алгоритма находится здесь (в комплекте с апплетом, оживляющим алгоритм в действии).Многие из алгоритмов предназначены для более сложной задачи, которая учитывает дыры в многоугольнике.Они могут быть использованы без изменений для вашего случая простого многоугольника.(На самом деле вашу проблему можно рассматривать как особый случай нахождения пути через общий многоугольник, в котором все дыры (препятствия) разделяют точку с краем.)

Я думаю, что лучший подход - этоA * поиск в пространстве, определенном графом видимости вершин многоугольника плюс начальная и конечная точки (если они еще не вершины).