Рекурсивная заливка области , решение проблемы: переполнение стека

Часто встречал на форумах вопросы по рекурсивной заливке.

алгоритм:

залить(точка) {
    if(точка еще не закрашена и не является границей области) {
        закрасить(точка);
        залить(точка выше);
        залить(точка ниже);
        залить(точка левее);
        залить(точка правее);
    }
}

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

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

мое решение - использовать вместо стека очередь:

залить(начальная_точка) {
    push(начальная_точка);
    while(pop(точка)) {
        if(точка еще не закрашена и не является границей области) {
            закрасить(точка);
            push(точка выше);
            push(точка ниже);
            push(точка левее);
            push(точка правее);
        }
    }
}

(здесь push() и pop() - гипотетические методы очереди)

можно взять std::queue, но для ускорения лучше использовать циклический буфер.

размер буфера достаточно взять равным удвоенному периметру прямоугольника, ограничивающего
закрашиваемую область (например, окна или bitmap'а).

сэмпл прилагается (MSVC 6.0, Win98)

//////////////////////////////////////////////
// fill.cpp
//////////////////////////////////////////////
 
#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
 
void QueueFill( HDC hdc, int xStart, int yStart, RECT & Rect )
{
    POINT pt = { xStart, yStart };
 
    ULONG BufferSize = 4 * (Rect.bottom - Rect.top + Rect.right - Rect.left);
    
    POINT *pBegin = new POINT [ BufferSize ];
    POINT *pEnd   = pBegin + BufferSize;
    POINT *pFirst = pBegin;
    POINT *pLast  = pBegin;
 
    *(pLast++) = pt;
 
    while( pFirst != pLast )
    {
        pt = *(pFirst++); if( pFirst == pEnd ) pFirst = pBegin;
 
        switch( GetPixel( hdc, pt.x, pt.y ) )
        {
            case CLR_INVALID: case RGB(0,0,0): case RGB(255,0,0):
                break;
 
            default:
                SetPixel( hdc, pt.x, pt.y, RGB(0xFF,0,0) );
 
                --pt.y;         *pLast = pt; if( ++pLast == pEnd ) pLast = pBegin;
                ++pt.y; ++pt.y; *pLast = pt; if( ++pLast == pEnd ) pLast = pBegin;
                --pt.y; ++pt.x; *pLast = pt; if( ++pLast == pEnd ) pLast = pBegin;
                --pt.x; --pt.x; *pLast = pt; if( ++pLast == pEnd ) pLast = pBegin;
        }
    }
    delete [] pBegin;
}
 
BOOL  bNewLine = TRUE;
POINT Old;
 
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    PAINTSTRUCT ps;
    HDC  hdc;
    RECT Rect;
    
    switch (message)
    {
        case WM_LBUTTONDOWN:
            hdc = GetDC(hWnd);
                SelectObject(hdc, GetStockObject(BLACK_PEN));
                MoveToEx( hdc, Old.x, Old.y, NULL );
                Old.x = LOWORD(lParam);
                Old.y = HIWORD(lParam);
                if( ! bNewLine )
                    LineTo( hdc, Old.x, Old.y );
            ReleaseDC(hWnd, hdc);
            bNewLine = FALSE;
            break;
 
        case WM_RBUTTONDOWN:
            if( bNewLine )
            {
                MessageBeep(MB_OK);
                GetClientRect(hWnd, &Rect);
                InvalidateRect(hWnd, &Rect, TRUE);
                UpdateWindow(hWnd);
            }
            bNewLine = TRUE;
            break;
 
        case WM_LBUTTONDBLCLK:
            bNewLine = TRUE;
            GetClientRect(hWnd, &Rect);
            SetCursor(LoadCursor(NULL, IDC_WAIT));
                hdc = GetDC(hWnd);
                    QueueFill( hdc, LOWORD(lParam), HIWORD(lParam), Rect );
                ReleaseDC(hWnd, hdc);
            SetCursor(LoadCursor(NULL, IDC_ARROW));
            break;
 
        case WM_PAINT:  
            BeginPaint(hWnd, &ps);
            EndPaint(hWnd, &ps);
            break;
 
        case WM_DESTROY:
            PostQuitMessage(0);
            break;
 
        default:
            return DefWindowProc(hWnd, message, wParam, lParam);
   }
   return 0;
}
 
WNDCLASSEX wc = { sizeof(WNDCLASSEX), CS_DBLCLKS, (WNDPROC)WndProc };
 
int APIENTRY WinMain(HINSTANCE hInst, HINSTANCE, LPSTR, int nCmdShow)
{
    wc.hInstance        = hInst;
    wc.hCursor          = LoadCursor(NULL, IDC_ARROW);
    wc.hbrBackground    = (HBRUSH)(COLOR_WINDOW+1);
    wc.lpszClassName    = "QUEUEFILLDEMO";
 
    RegisterClassEx(&wc);
 
    ShowWindow(
        CreateWindow(wc.lpszClassName, "Queue Fill Demo", WS_OVERLAPPEDWINDOW,
            CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInst, NULL),
        nCmdShow);
 
    MSG msg;
    while (GetMessage(&msg, NULL, 0, 0))
    {
        TranslateMessage(&msg);
        DispatchMessage (&msg);
    }
 
    return msg.wParam;
}

виноват, буфер все-же лучше сделать переменного размера.
вот пример с очередью:

void QueueFill( HDC hdc, int xStart, int yStart, RECT /* & Rect */ )
{
    POINT pt = { xStart, yStart };    
    std::queue <POINT> Pts;
    Pts.push(pt);
    while( ! Pts.empty() )
    {
        pt = Pts.front(); Pts.pop();
        switch( GetPixel( hdc, pt.x, pt.y ) )
        {
            case CLR_INVALID: case RGB(0,0,0): case RGB(255,0,0):
                break;
            default:
                SetPixel( hdc, pt.x, pt.y, RGB(0xFF,0,0) );
                --pt.y;         Pts.push(pt);
                ++pt.y; ++pt.y; Pts.push(pt);
                --pt.y; ++pt.x; Pts.push(pt);
                --pt.x; --pt.x; Pts.push(pt);
        }
    }
}