Поиск смежных элементов в массиве 1D numpy

Question

У меня есть 1D numpy массив bools, представляющий матрицу NxN (например, матрица 10x10 имеет значения от 0 до 9, затем от 10 до 19 и т. Д.) Моя цель - найти число «истинных» элементов, которые смежны - вверху, внизу, влево, вправо или по диагонали.

Мой план решения этой проблемы состоит в том, чтобы перебирать массив (для x в my_array), и когда встречается элемент 'true', введите шаблон поиска для окружающих элементов. Если один из окружающих элементов также верен, он затем ищет свои окружающие элементы. Однако я не уверен, что это оптимизированный поиск, и его реализация рекурсивно оказывается сложной.

Любые рекомендации по алгоритмам или методам поиска массива 1D numpy для смежных элементов?

EDIT:

Поскольку глубина первых поисков я видел использование словарей, чтобы установить пути между элементами, я попытался создать функцию, чтобы определить это (ниже).

Я упростил его только для рассмотрения слева, справа, сверху и снизу (без диагоналей), но краевые случаи не работают.

С этим я бы надеялся использовать функцию «Глубина первого поиска», рекурсивно вызывающую себя, когда найден «истинный» элемент.

def getgraph(lst): 
    #print('here2') 
    for x in lst: 
     if x is 0: 
      graph[x] = set([x+1, x+n]) 
      x = x+1 
     while (x > 0) and (x < (n-1)): #first row, excluding edges 
      graph[x] = set([(x-1),(x+1),(x+n)]) 
      x= x+1 

     while x >= (n-1) and x < ((n-1)*n): #second to second last row, with edge cases 
      v = x%n 
      width = n-1 
      print('XN: %f' %v) 
      if (x % n) == 0: 
       graph[x] = set([x+1, x+n]) 
       x = x+1 
      if (v) is width: 
       graph[x] = set([(x-1),(x+n)]) 
       x = x+1 
      else: 
       graph[x] = set([(x-1), (x+1), (x+n), (x-n)]) 
       x= x+1 

     while x >= (n-1)*n and x <= ((n*n)-1): 
      value = ((n*n)-1) 
      if x is value: # works with manually inputting last element number 
       graph[x] = set([(x-1),(x-n)]) 
       x = x+1 
      else: 
       graph[x] = set([(x-1),(x+1),(x-n)]) 
       x= x+1 

    print(graph) 
    return graph 

Answer 1

Проблема вы описываете называется «связное этикетирование компонент» в обработке изображений - вы просто массив 1D вместо матрицы (который, кстати, был обычный случай в старые времена обработки изображений).

Если преобразовать в 2D массив, вы можете применить scipy.ndimage.measurements.label (docs) (например, как описано в этой answer)

Если вы все еще хотите реализовать его самостоятельно, a 2-pass algorithm известен как стандартное решение. Много дополнительной информации in this other answer.