Intelligent scissors Опции

[wiz29]

Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)

[ufna]

А просчет дейкстры - это как раз часть прокладки маршрута, поэтому я об этом речь и завел.


A* - наверное самый популярный алгоритм в геймдеве. Описание ниже. Если нужно, могу скинуть код с классами для Open, Closed и сам алгоритм в Qt.

/*
приоритетная очередь Open
список Closed

ПоискАЗвездочка
   s.g = 0  // s - стартовый узел
   s.h = ЭвристическаяОценка( s )
   s.f = s.g + s.h
   s.родитель = null
   добавить s в Open
   пока очередь Open не пуста
      извлечь n из Open  // n - узел с наименьшей стоимость в Open
      если n целевой узел
         сконструировать путь
         выйти с кодом "успешное завершение"
      для каждого наследника n' узла n
         newg = n.g + стоимость(n,n')
         если n' в Open или Closed, и n'.g <= newg
             пропустить n'
         n'.родитель = n
         n'.g = newg
         n'.h = ЭвристическаяОценка( n' )
         n'.f = n'.g + n'.h
         если n' в Closed
            удалить n' из Closed
         если n' не в Open
            положить n' в Open
      положить n в Closed
   выйти с кодом "путь не найден"
*/