Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 10
Алгоритм идёт от пикселя к пикселю, поэтому пути получаются соответствующие. На картинке выше, я показал в чём разница "человеческого" и "компьютерного" пути. Если мы возьмём рисунок и просто проведём линию, то получим "истинный" короткий путь.
В статье я рассчитывал абсолютную ошибку, и можно заметить, что на диагоналях она формируется максимальная.
на сетчатой поверхности есть алгоритм Брезенхэма
На самом деле, алгоритм Брезенхема даст путь такой же длины. Он же только на 8 соседних клеток может переходить. Значит там все ребра будут или по диагонали, или вдоль сетки. От перестановки слагаемых сумма не меняется, т.ч. можно сначала все вертикальные шажки сделать, а только потом все диагональные. На прямую вообще не похоже, но длина пути по пикселям та же самая.
Он может сделать сначала все шаги по диаганали, потому что это в сторону конца, а потом все по вертикали, потому что только в ту сторону кратчайший путь.
Кстати, я не автор. Похоже, у автора в статье расстояние - это именно длина пути вдоль сетки с 8 соседями. С корнями и вещественными числами.
Вдоль стенок алгоритм жмется потому, что ребра в каждой вершине перебираются в одном и том же порядке, без перемешивания и дополнительного рандома. Если и туда и сюда расстояние в итоге будет одинаковое, то берется первое попашееся. И это первое попавшееся - всегда в одну и ту же сторону, пока или до стенки не дойдет путь, или оставшийся путь не станет из одних только диагональных кусочков, и оптимальное направление не изменится.
Какой-нибуть обход в ширину или дейкстра на такой сетке найдут примерно такой же путь.
Сначала алгоритм рассчитывает поля расстояний, а затем, используя их, рассчитывает кратчайший путь. Пример на картинке.
Какой-то гибрид обхода в ширину и Дейкстры с кучей получился. Как уже заметили выше - пути оно ищет не кратчайшие. Чем оно лучше обхода в ширину по 8 соседним точкам? Оно точно медленнее а пути найдет такие же. На картинках с линиями еще и пути будут оптимальными.
Раз уж вы про алгоритм пишите, то опишите хотя бы его ассимтотическую сложность, сравните с другими алгоритмами, опишите где и когда он применим.
Спасибо за замечания. FMM в своей основе имеет алгоритм Дейкстры, но отличается от него способом расчета значений узлов(смотрите мат. описание). FMM легко расширяем, в отличие от Дейкстры. Я видел как в одной работе FMM использовали на триангулированной поверхности для рассчёта полей расстояний.
В этой статье у меня не было цели сравнивать алгоритмы. В рунете очень мало информации о FMM, и я решил это исправить.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Метод быстрого марша (Fast Marching Method)