Суть метода: на квадратной матрице отмечено некоторое количество точек, для каждой из НЕ отмеченных точек нужно посчитать расстояние до ближайшей отмеченной и вывести результат в виде матрицы. Вообще я бы хотел сам написать реализацию, но сколько не сижу в голову не приходит ничего лучше алгоритма который работает за 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. ]])
