Почему этот алгоритм заливки вызывает переполнение стека?

void FloodFill(int layer, int x, int y, int target, int replacement)
{
    if (x < 0) return;
    if (y < 0) return;
    if (x >= _mapWidth) return;
    if (y >= _mapHeight) return;

    if (_mapLayers[layer, x, y] != target) return;

    _mapLayers[layer, x, y] = replacement;

    FloodFill(layer, x - 1, y, target, replacement);
    FloodFill(layer, x + 1, y, target, replacement);
    FloodFill(layer, x, y - 1, target, replacement);
    FloodFill(layer, x, y + 1, target, replacement);

    return;
}

Пока это мой код, но когда он достигает конца карты, он вызывает переполнение стека. Кто-нибудь знает, как решить проблему (возможно, сложное условие)?


c# algorithm map tiles
person Community    schedule 17.01.2010    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Обратите внимание, что этот путь вызова существует:

(x, y) -> (x+1, y) -> (x+1-1, y) -> (x+1-1+1, y) -> ...

Это бесконечная рекурсия, поэтому у вас переполнение стека. Ваши чеки с этим не справятся. Вам необходимо выполнить одну дополнительную проверку:

if (_mapLayers[layer, x, y] == replacement) return;

Даже если вы включили дополнительную проверку выше, обратите внимание, что максимальная глубина рекурсии составляет (_mapWidth * _mapHeight), что может быть очень большим даже для небольшого растрового изображения (например, 100 x 100).

person kennytm    schedule 17.01.2010
comment
максимальная глубина рекурсии фактически равна _mapWidth * _mapHeight. 200 не очень глубокий (опечатка наверное) :). 100 * 100 также не должно вызывать переполнения (если в памяти уже есть чертовски много других вещей), но что-то вроде 10 000 * 10 000 будет. Но дополнительная проверка, вероятно, то, что нужно OP, +1. - person MAK; 17.01.2010
comment
-1, этот ответ неверен более чем в одном отношении. Линейный поиск не соответствует окрестности точек. Тестовая _mapLayers [layer, x, y] == замена не требуется, если есть тестовая цель! = Замена до того, как сначала вызывается FloodFill. И максимальная глубина рекурсии не будет больше _mapWidth * _mapHeight / 2 (для какого-то спирального изображения). - person Doc Brown; 17.01.2010
comment
@DocBrown: 'if (_mapLayers [layer, x, y]! = Target) return;' не обрабатывает (по общему признанию маловероятный) случай, когда target == replace. Да, (_mapWidth * _mapHeight) не является точной глубиной, но глубина все равно будет O (_mapWidth * _mapHeight), поэтому поднятая точка все еще действительна. Единственное, что действительно неверно в ответе, - это часть о линейном поиске. - person MAK; 17.01.2010
comment
@MAK: я не писал 'if (_mapLayers [layer, x, y]! = Target)' обрабатывает допустимый случай, я написал: 'нужно добавить недостающий тест для' target == replace '(но не внутри рекурсивного процедура, тест должен выполняться вызывающим FloodFill). И в текущем ответе нет большого O. И для замены target! = Указанный путь вызова не будет выполняться, как показано, поскольку рекурсия остановится раньше. ИМХО, ответ верен лишь отчасти и немного вводит в заблуждение. - person Doc Brown; 17.01.2010

arrow_upward
2
arrow_downward

Прежде всего, вы должны убедиться, что target!=replacement (может быть выполнено один раз перед первоначальным вызовом 'FloodFill'). Тогда ваш алгоритм может работать, если _mapWidth и _mapHeight не слишком большие (это сильно зависит от содержимого вашего массива _mapLayers). Если это проблема, вам следует попробовать нерекурсивный алгоритм. Создать

class Point
{ 
    public int x, y;
    public Point(int newX, int newY)
    {
         x=newX;
         y=newY;
    }
}

и

 List<Point> pointList;

Поместите начальную точку в этот список и запустите какой-то цикл, пока pointList не станет пустым: возьмите одну точку из списка, обработайте ее, как указано выше, и вместо исходного рекурсивного вызова выше снова поместите четырех соседей в список.

РЕДАКТИРОВАТЬ: вот полный пример, но не тестировал:

    void FloodFill2(int layer, int xStart, int yStart, int target, int replacement)
    {
        if(target==replacement)
            return;
        List<Point> pointList = new List<Point>();

        pointList.Add(new Point(xStart,yStart));
        while(pointList.Count>0)
        {
            Point p = pointList[pointList.Count-1];
            pointList.RemoveAt(pointList.Count-1);
            if (p.x < 0) continue;
            if (p.y < 0) continue;
            if (p.x >= _mapWidth) continue;
            if (p.y >= _mapHeight) continue;
            if (_mapLayers[layer, p.x, p.y] != target) continue;
            _mapLayers[layer, p.x, p.y] = replacement;

            pointList.Add(new Point(p.x - 1, p.y));
            pointList.Add(new Point(p.x + 1, p.y));
            pointList.Add(new Point(p.x, p.y - 1));
            pointList.Add(new Point(p.x, p.y + 1));
        }
    }

EDIT2: Фактически, вот предложение по оптимизации процедуры: избегайте вставки в список, если вставка становится бессмысленной, поэтому:

            if(p.x>=0) 
                 pointList.Add(new Point(p.x - 1, p.y));
            if(p.x<_mapWidth-1) 
                 pointList.Add(new Point(p.x + 1, p.y));
            if(p.y>=0) 
                 pointList.Add(new Point(p.x, p.y - 1));
            if(p.y<_mapHeight-1) 
                 pointList.Add(new Point(p.x, p.y + 1));
person Doc Brown    schedule 17.01.2010