Кто-нибудь знает алгоритм поиска "фигур" в массивах 2d?

Возьмем это отображение, где '#' иллюстрирует взятый квадрат и '.' иллюстрирует свободный квадрат:

1 . # # # . .
2 . # . . # .
3 # . . . . #
4 . # # # . .
5 . . . . . .
6 . . . . . .
- 1 2 3 4 5 6

Теперь, если я наложу "#" на квадрат 4,5, область будет "заполнена" следующим образом:

1 . # # # . .
2 . # # # # .
3 # # # # # #
4 . # # # # .
5 . . . . . .
6 . . . . . .
- 1 2 3 4 5 6

Итак, что является лучшим способом найти "ограниченный квадрат", где я могу начать заливку заливом или другой алгоритм заполнения, который заполняет ограниченную область?

Ответ 1

Если вы можете преобразовать свою проблему в график, то вы должны определить связанные компоненты. И если подключенный компонент не содержит ребра, являющегося граничным краем, то вы нашли область, которая должна быть заполнена.

Если я определяю график следующим образом:

G = (V, E)
V = {r1, r2, r3, r4, r5, r6, c1, c2, c3, c4, c5, c6}
E = {(u, v) | u, v are elements of V && the cell(u, v) is not taken}

Теперь запустите DFS, чтобы найти все отключенные деревья. Алгоритм:

for each u in V:
    color[u] = white

for each u in V:
    if color[u] == white:
        contains_boundary_edge = False
        DFS-visit( u, contains_boundary_edge )

        if not contains_boundary_edge:
            Flood-fill( u )

DFS-visit( u, contains_boundary_edge ):
    color[u] = gray
    for each v in adjacent( u ):
        if color[v] == white:
            if edge(u, v) is a boundary edge: // Can be easily identified if one of u, v is start or end row/col.
                contains_boundary_edge = True

            DFS-visit( v, contains_boundary_edge )

    color[u] = black

Ответ 2

Я думаю, что этот вопрос можно свести к проблеме выпуклой оболочки, если рассматривать каждую # как точку x, y, тогда выпуклая оболочка будет давать нам x, y всех отсутствующих

http://en.wikipedia.org/wiki/Convex_hull

Я попытаюсь закодировать его на досуге.

Ответ 3

Вы можете атаковать это, обрабатывая каждый. node.

Определение: A '.' node заключен, если не существует пути от node до границы отображения.

Если вы согласны с вышеприведенным определением, алгоритм должен поддерживать график ".". узлы, где подключены соседние узлы.

Каждый раз, когда a node изменяется на '#', удалите его из этого графика и проверьте оставшиеся ".". node, чтобы узнать, существует ли путь от него к одному из узлов на границе карты.

В зависимости от размера вашей карты вам потребовалось выполнить различные оптимизации, чтобы ограничить количество поисковых запросов, выполненных за каждый ход.

Ответ 4

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

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

Комментарий @svick вдохновил этот метод.

Ответ 5

Я начинал с каждого соседа выбранного квадрата и пытался "убежать" на границу сетки. Между тем отметьте путь, за которым следует "X" . Если вы можете избежать: отмените все "X" . Если вы не можете убежать, замените каждый "X" на "#". Я сделал пример на Java, как показано ниже.

int W, H;   
char[][] input;
final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public void handle(int x, int y) {
    // try each neihgbor
    for (int[] d : directions) {
        if (canEscape(input, x, y)) {
            // if we can escape, the path found shouldn't be filled
            // so replace the Xes by '.';
            handleXes(input, false);                
        } else {
            // if we cannot escape, this is a closed shape, so
            // fill with '#'
            handleXes(input, true);
        }
        // note that this can be written more concisely as
        // handleXes(input, !canEscape(input, x, y));
    }
}    

public boolean canEscape(char[][] grid, int x, int y) {
    if (isEscape(grid, x, y))
        return true

    if (isValid(grid, x, y)) {
        // mark as visited
        grid[x][y] = 'X';
        // try each neighbor
        for (int[] d : directions) {
            if (canEscape(grid, x+d[0], y+d[1]))
                return true;
        }
    }

    return false;
}

public boolean isValid(char[][] grid, int x, int y) {
    return 0 <= x && x < W && 0 <= y && y < H && grid[x][y] == '.';
}

public boolean isEscape(char[][] grid, int x, int y) {
    return (0 == x || x == W-1 || 0 == y || y == H-1) && grid[x][y] == '.';
}   

public void handleXes(char[][] grid, boolean fill) {
    for (int x = 0; x < W; x++)
        for (int y = 0; y < H; y++)
            if (grid[x][y] == 'X')
                grid[x][y] = fill ? '#' : '.';
}