Спасибо за замечания. FMM в своей основе имеет алгоритм Дейкстры, но отличается от него способом расчета значений узлов(смотрите мат. описание). FMM легко расширяем, в отличие от Дейкстры. Я видел как в одной работе FMM использовали на триангулированной поверхности для рассчёта полей расстояний.
В этой статье у меня не было цели сравнивать алгоритмы. В рунете очень мало информации о FMM, и я решил это исправить.
Алгоритм идёт от пикселя к пикселю, поэтому пути получаются соответствующие. На картинке выше, я показал в чём разница "человеческого" и "компьютерного" пути. Если мы возьмём рисунок и просто проведём линию, то получим "истинный" короткий путь.
В статье я рассчитывал абсолютную ошибку, и можно заметить, что на диагоналях она формируется максимальная.
Спасибо за замечания. FMM в своей основе имеет алгоритм Дейкстры, но отличается от него способом расчета значений узлов(смотрите мат. описание). FMM легко расширяем, в отличие от Дейкстры. Я видел как в одной работе FMM использовали на триангулированной поверхности для рассчёта полей расстояний.
В этой статье у меня не было цели сравнивать алгоритмы. В рунете очень мало информации о FMM, и я решил это исправить.
Сначала алгоритм рассчитывает поля расстояний, а затем, используя их, рассчитывает кратчайший путь. Пример на картинке.
Алгоритм идёт от пикселя к пикселю, поэтому пути получаются соответствующие. На картинке выше, я показал в чём разница "человеческого" и "компьютерного" пути. Если мы возьмём рисунок и просто проведём линию, то получим "истинный" короткий путь.
В статье я рассчитывал абсолютную ошибку, и можно заметить, что на диагоналях она формируется максимальная.