¿Por qué este algoritmo inundaciones relleno causar un desbordamiento de pila?

Question

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;
}

Este es mi código hasta ahora, pero cuando llega al final de la ruta que provoca un desbordamiento de pila, ¿alguien sabe cómo resolver el problema (probablemente una condición difícil)?

Answer 1

Tenga en cuenta que existe esta ruta de llamada:

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

Este es un bucle infinito, por lo que han desbordamiento de pila. Sus cheques no pueden hacer frente a esto. Usted tiene que realizar una comprobación adicional:

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

---

Incluso si ha incluido el cheque adicional por encima, tenga en cuenta que el nivel de recursividad máxima es (_mapWidth * _mapHeight), que puede ser muy profundo, incluso para un pequeño mapa de bits (por ejemplo, 100 x 100).

Answer 2

En primer lugar, usted debe asegurarse de que target!=replacement (puede hacerse una vez antes de la llamada de la inicial 'FloodFill'). Entonces, su algo puede funcionar, siempre y cuando _mapWidth y _mapHeight no son extraordinarios grande (que depende en gran medida del contenido de su gama _mapLayers). Si esto es un problema, usted debe tratar de un algoritmo no recursivo. Crear un

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

y un

 List<Point> pointList;

Coloque el punto inicial en esta lista y ejecutar algún tipo de bucle hasta PointList está vacía: tomar un punto fuera de la lista, procesarla como el anterior y en lugar de la llamada recursiva de origen encima poner de nuevo los cuatro vecinos en la lista.

Edit: aquí está el ejemplo completo, no prueba que, sin embargo:

    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: De hecho, aquí es una sugerencia para optimizar la rutina: evitar la inserción a la lista si se pone inserción sentido, por lo que:

            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));