Алгоритм обнаружения пулов нулей в матрице ⇐ Python

[Anonymous]

Я пишу алгоритм, который обнаруживает области смежных пустых ячеек, которые полностью окружены заполненными ячейками и не доходят до края сетки. Назовем такие регионы «пулами».
Как вы можете видеть на приведенной ниже визуализации, существует три ячейки пула – (1, 1), (1, 3)< /code> и (2, 2) – образуют единственный пул в сетке.
[img]https://i .sstatic.net/26zRzgNM.png[/img]

Я уже реализовал алгоритм, который частично решает проблему: он правильно идентифицирует ячейки пула.
class Cell:
x: int
y: int
is_filled: bool

def __init__(self, x, y, is_filled):
self.x = x
self.y = y
self.is_filled = is_filled

def get_neighbor(self, grid, direction):
if direction == "LEFT" and self.y > 0:
return Cell(self.x, self.y - 1, grid[self.x][self.y - 1] == 1)
if direction == "TOP" and self.x > 0:
return Cell(self.x - 1, self.y, grid[self.x - 1][self.y] == 1)
if direction == "RIGHT" and self.y < len(grid[0]) - 1:
return Cell(self.x, self.y + 1, grid[self.x][self.y + 1] == 1)
if direction == "BOTTOM" and self.x < len(grid) - 1:
return Cell(self.x + 1, self.y, grid[self.x + 1][self.y] == 1)
return None

def iterate_pool_cells(grid):
def is_pool(cell, is_edge):
if cell is None: # Reached grid boundary, not a pool
is_edge["reached"] = True
return False
if (cell.x, cell.y) in visited or cell.is_filled: # Already visited or is land
return True
visited.add((cell.x, cell.y)) # Mark as visited
is_enclosed = True
is_enclosed = is_pool(cell.get_neighbor(grid, "LEFT"), is_edge) and is_enclosed
is_enclosed = is_pool(cell.get_neighbor(grid, "TOP"), is_edge) and is_enclosed
is_enclosed = is_pool(cell.get_neighbor(grid, "RIGHT"), is_edge) and is_enclosed
is_enclosed = is_pool(cell.get_neighbor(grid, "BOTTOM"), is_edge) and is_enclosed
return is_enclosed and not is_edge["reached"]

visited = set()
for x in range(len(grid)):
for y in range(len(grid[0])):
cell = Cell(x, y, grid[x][y] == 1)
if (x, y) not in visited and not cell.is_filled:
is_edge = {"reached": False}
if is_pool(cell, is_edge) and not is_edge["reached"]:
yield (x, y)

Проблема заключается во второй половине алгоритма, то есть в итераторе. Я стремлюсь получать только ячейки, которые запускают пул (т. е. только верхнюю левую ячейку в данном пуле). Однако, поскольку сейчас диагональная смежность не учитывается, итератор вернет все три ячейки из примера, даже если все они принадлежат одному пулу.
В другими словами, единственная полученная ячейка должна быть первой в пуле: (1, 1).
Я пробовал подходы как с изменением итератора, так и с isPool. , но ничего не помогло. Проблема либо остается, либо я получаю ложноотрицательные результаты во всех ячейках пула.
Может кто-нибудь подсказать мне правильное направление решения этой проблемы?
Вот тестовый пример с использованием сетки из изображения:
grid = [
[ 0, 1, 0, 1, 0 ],
[ 1, 0, 1, 0, 1 ],
[ 1, 1, 0, 1, 1 ],
[ 1, 0, 1, 0, 1 ],
[ 0, 0, 1, 0, 0 ],
[ 1, 0, 1, 0, 1 ],
]

for pool_cell in iterate_pool_cells(grid):
print(f"Pool starts at cell: {pool_cell}")


Подробнее здесь: https://stackoverflow.com/questions/786 ... n-a-matrix