检测矩阵中 0 池的算法

Question

我正在编写一种算法，用于检测被填充单元完全包围（正交）并且不延伸到网格边缘的连续空单元区域。我们将这些区域称为“池”。

正如您在下面的可视化中所看到的，共有三个池单元 –

(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, 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}")

Answer 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-neighborhood 实现池搜索，就像上面的代码一样：

for neighbor in cell.neighbors + cell.diagonals