@Ra1n98

Есть ли реализация на с++ метода из SciPy ndimage.distance_transform_edt?

Суть метода: на квадратной матрице отмечено некоторое количество точек, для каждой из НЕ отмеченных точек нужно посчитать расстояние до ближайшей отмеченной и вывести результат в виде матрицы. Вообще я бы хотел сам написать реализацию, но сколько не сижу в голову не приходит ничего лучше алгоритма который работает за O(N*M), где N число элементов матрицы, а M число отмеченных точек. Для меня это слишком медленно, так как массивы будут большие и количество отмеченных точек соответственно тоже. Хотел свести задачу к динамке, но там нужно от чего-то отталкиваться, а здесь не понятно от чего это делать.
Думал посмотреть как это реализовано в самой библиотеке и переписать на с++, но там в идет переход в функцию в другом модуле _nd_image.euclidean_feature_transform реализацию которого я не смог найти в источнике.
https://github.com/scipy/scipy/blob/v0.14.0/scipy/...

Пример работы метода:
Исходный массив
a([0,1,1,1,1],
                      [0,0,1,1,1],
                      [0,1,1,1,1],
                      [0,1,1,1,0],
                      [0,1,1,0,0]))

ndimage.distance_transform_edt(a)
вывод
([[ 0.    ,  1.    ,  1.4142,  2.2361,  3.    ],
           [ 0.    ,  0.    ,  1.    ,  2.    ,  2.    ],
           [ 0.    ,  1.    ,  1.4142,  1.4142,  1.    ],
           [ 0.    ,  1.    ,  1.4142,  1.    ,  0.    ],
           [ 0.    ,  1.    ,  1.    ,  0.    ,  0.    ]])
  • Вопрос задан
  • 102 просмотра
Решения вопроса 1
@Andy_U
Смотрите по ссылке в конце:

https://github.com/scipy/scipy/blob/v0.14.0/scipy/...
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы