使用 DFS 算法对形状进行泛洪填充

Question

我正在做一个项目，该项目一定类似于 windows 的绘画。我已经实现了 8 个工具（它们是画笔、矩形、椭圆形、多边形、三角形、线条、喷涂和填充工具）。现在我想制作一个 "bucket" 工具，它必须填充其周围的区域。我为此工具使用 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：

bucket.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

这是堆栈溢出。如果你填充一个大的space，它有一个简单的形状（比如矩形），递归的深度将大致等于那个space的面积，因为它几乎总是会去到一些分支和不是 return.

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

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

使用 DFS 算法对形状进行泛洪填充

Using DFS algorithm to flood-fill a shape

c++

sdl

depth-first-search