DFS算法在形状填充中的应用

Question

我正在做一个工程，这个项目一定有点像窗户的油漆。我已经实现了8个工具(它们是刷，矩形，椭圆形，多边形，三角形，直线，喷雾和填充工具)。现在我想做一个“桶”工具，它必须充满周围的区域。对于这个工具，我使用DFS算法，但是当区域很大时，gdb给出以下错误：

Program received signal SIGSEGV, Segmentation fault.
0xb7c47f9d in _IO_new_file_xsputn (f=0xb7d82ac0 <_IO_2_1_stdout_>, data=0xbf80009e, n=6)
    at fileops.c:1273
1273    fileops.c: No such file or directory.

有人知道这个错误是什么意思吗？您可以在下面看到bucket.h和bucket.cpp：

桶h：

#ifndef BUCKET_H
#define BUCKET_H

#include "tool.h"

#include "SDL/SDL.h"
#include "SDL/SDL_gfxPrimitives.h"

#include <cmath>

class Bucket : public Tool {
    private:
        bool **mark;
        Color selectedPointColor;
    public:
        Bucket( bool state, SDLKey key ) : Tool( state, key ) {}

        virtual void draw( SDL_Surface*, int, int, int, int, int, Color color );

        friend void DFS( SDL_Surface*, int, int, Color, bool** );
        friend Color getColor( SDL_Surface*, int, int );
};

inline Color getColor( SDL_Surface *screen, int x, int y ){
    Uint32* pixel = (Uint32*) screen->pixels;
    Uint8* color = (Uint8*) &( pixel[ y * screen->w + x ] );
    return Color( (int) color[2], (int) color[1], (int) color[0] );
}

inline void DFS( SDL_Surface *screen, int x, int y, Color color, Color selectedPointColor ){
    static int counter;
    counter++;
    cout << counter << endl;
    pixelRGBA( screen, x, y, color.red(), color.green(), color.blue(), 255 );

    if ( x + 1 < screen->w && getColor( screen, x + 1, y ) == selectedPointColor )
        DFS( screen, x + 1, y, color, selectedPointColor );

    if ( y + 1 < screen->h && getColor( screen, x, y + 1 ) == selectedPointColor )
        DFS( screen, x, y + 1, color, selectedPointColor );

    if ( x - 1 >= 0 && getColor( screen, x - 1, y) == selectedPointColor )
        DFS( screen, x - 1, y, color, selectedPointColor );

    if ( y - 1 >= 0 && getColor( screen, x, y - 1) == selectedPointColor )
        DFS( screen, x, y - 1, color, selectedPointColor );
}

#endif

bucket.cpp：

#include "bucket.h"

void Bucket::draw( SDL_Surface *screen, int x, int y, int, int, int, Color color ){
    selectedPointColor = getColor( screen, x, y );
    if ( selectedPointColor == color )
        return;
    DFS( screen, x, y, color, this->selectedPointColor );
}

任何帮助都将不胜感激。

Answer 1

是堆栈溢出。如果你填充一个形状简单的大空间(如矩形)，递归的深度将大致等于该空间的面积，因为它几乎总是到某个分支而不返回。

也就是说，如果图像为例如1000x1000，则递归的深度约为100万，这太大了。

您不应该使用DFS来填充洪水，而应该使用BFS。