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

[Anonymous]

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

Я уже реализовал алгоритм, который частично решает проблему: он правильно идентифицирует ячейки пула через ортогональ DFS, т. е. он никогда не учитывает соседей по диагонали.
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)

Проблема заключается во второй половине алгоритма, то есть в итераторе. Я стремлюсь давать только одну ячейку на пул (это может быть любая ячейка в пуле, если она только одна). Однако прямо сейчас итератор выдаст все три ячейки из примера, поскольку он считает их отдельными, несвязанными пулами.
Я хочу, чтобы были просмотрены три ячейки в примере. как принадлежащие одному и тому же пулу, так что для каждого пула выделяется только одна ячейка.
Может кто-нибудь подсказать мне, как решить эту проблему? Могу ли я сделать это после завершения работы DFS, кластеризовав соседние по диагонали ячейки пула?
Вот тестовый пример, включающий сетку из изображения:
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