Алгоритм обнаружения пулов нулей в матрице
Я пишу алгоритм, который обнаруживает области смежных пустых ячеек, которые полностью окружены (ортогонально) заполненными ячейками и не доходят до края сетки. Назовем такие регионы «бассейнами».
Как вы можете видеть на приведенной ниже визуализации, есть три ячейки пула — (1, 1), (1, 3) и (2, 2) — образующие единственный пул в сетке. То есть как ортогонально, так и диагонально соседние ячейки пула следует считать частью единого пула.
Я уже реализовал алгоритм, который частично решает проблему: он правильно идентифицирует ячейки пула через ортогональную 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):
nonlocal visited
nonlocal edge_reached
if cell is None: # Reached grid boundary, not a pool
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")) and is_enclosed
is_enclosed = is_pool(cell.get_neighbor(grid, "TOP")) and is_enclosed
is_enclosed = is_pool(cell.get_neighbor(grid, "RIGHT")) and is_enclosed
is_enclosed = is_pool(cell.get_neighbor(grid, "BOTTOM")) and is_enclosed
return is_enclosed and not edge_reached
visited = set()
edge_reached = False
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:
edge_reached = False
if is_pool(cell) and not 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}")
@nocomment Причина, по которой эти три ячейки нарисованы как связанные, заключается в том, что я хочу рассматривать диагональные пустые ячейки как связанные только в том случае, если они образуют пул внутри «острова» заполненных ячеек. Поскольку другие пустые ячейки «выливаются» к краю сетки, они не отображаются как связанные с этими тремя, поскольку не образуют с ними пул.
Хороший способ отладки подобных вещей — иметь красивую функцию печати для вашей сетки и печатать сетку после каждой итерации цикла. Кроме того, вы можете установить точку останова после каждой итерации или вручную остановить выполнение, дождавшись input(...) возможности пошаговой отладки. Если информации в сетке недостаточно, сохраните больше отладочной информации в отдельных сетках, а также распечатывайте их после каждой итерации.
Странно, что три ячейки пула соединены, но две верхние не связаны ни с одной в ряду над ними. Это правило (?) в вопросе не объяснено.
@trincot Я полагаю, что диагональное соединение применяется только к ячейкам, если они уже признаны ячейками пула. Возможно, мне следует сначала создать полную DFS, сохранив все ячейки пула в массиве, а затем сгруппировать их на основе как ортогональной, так и диагональной связности.
Да, кажется, есть много способов приблизиться к этому.
Ответы 1
Есть много способов приблизиться к этому. Хотя на первом этапе это работает, я бы предложил создать график таким образом, чтобы ячейкам больше не требовался доступ к сетке, а они напрямую ссылались друг на друга. Для данной ячейки можно определить два типа соседей: список соседей с «прямым» соединением и еще один список соседей с диагональным соединением.
Второй список затем будет использоваться на заключительном этапе определения пулов.
Вот реализация этого:
class Cell:
def __init__(self, x, y, west, nw, north, ne):
self.x = x
self.y = y
self.neighbors = list(filter(None, [west, north]))
self.diagonals = list(filter(None, [nw, ne]))
for neighbor in self.neighbors:
neighbor.neighbors.append(self)
for neighbor in self.diagonals:
neighbor.diagonals.append(self)
def __repr__(self):
return f"({self.y},{self.x})"
def create_cells(grid):
leak_cells = set() # 0-cells at the boundary
water_cells = set() # internal 0-cells
height = len(grid)
width = len(grid[0])
above = [None] * (width + 2)
for y, row in enumerate(grid):
current = [None]
for x, is_land in enumerate(row):
cell = None if is_land else Cell(x, y, current[-1], *above[x:x+3])
if cell:
if x in (0, width - 1) or y in (0, height - 1):
leak_cells.add(cell)
else:
water_cells.add(cell)
current.append(cell)
current.append(None)
above = current
return leak_cells, water_cells
def apply_leaks(leak_cells, water_cells):
# Flood the "leak" into water cells, converting them
while leak_cells:
new_leak_cells = set()
for leak in leak_cells:
for neighbor in leak.neighbors:
if neighbor in water_cells:
new_leak_cells.add(neighbor)
water_cells.remove(neighbor)
leak_cells = new_leak_cells
def collect_pools(water_cells):
for cell in list(water_cells):
if cell in water_cells:
water_cells.remove(cell)
pool = [cell]
for cell in pool:
for neighbor in cell.neighbors + cell.diagonals:
if neighbor in water_cells:
pool.append(neighbor)
water_cells.remove(neighbor)
yield pool
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 ],
]
leak_cells, water_cells = create_cells(grid)
apply_leaks(leak_cells, water_cells)
pools = list(collect_pools(water_cells))
print(pools)
Но, конечно, вы могли бы оставить свой код таким, какой он есть, и реализовать поиск по пулу с использованием 8-соседства, как в приведенном выше коде, где у меня есть:
for neighbor in cell.neighbors + cell.diagonals
Ячейки соединены по диагонали или нет? Почему эти три ячейки соединены так, как вы нарисовали, но не соединены по диагонали с другими пустыми ячейками?