flodfill 알고리즘

8648 단어 floodfill만수 충전 법
글:http://blog.sina.com.cn/s/blog_7506816f0100pqzn.html  
           외국 사이트 에서 flodfill 에 관 한 몇 가지 코드 를 보 았 는데 느낌 이 좋 습 니 다. 여러분 께 공유 할 수 있 습 니 다. 주로 다음 과 같은 몇 가지 로 나 뉘 는데 구체 적 으로 소개 하지 않 아 도 됩 니 다. 절 차 는 보면 알 수 있 습 니 다.
           1, 4 - Way Recursive Method (FloodFill 4)
//Recursive 4-way floodfill, crashes if recursion stack is full 
void floodFill4(int x, int y, int newColor, int oldColor) 
{ 
    if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor) 
    { 
        screenBuffer[x][y] = newColor; //set color before starting recursion
        
        floodFill4(x + 1, y,     newColor, oldColor);
        floodFill4(x - 1, y,     newColor, oldColor);
        floodFill4(x,     y + 1, newColor, oldColor);
        floodFill4(x,     y - 1, newColor, oldColor);
    }     
}
          2. 8 - 방법 재 귀 방법 (FloodFill 8)
//Recursive 8-way floodfill, crashes if recursion stack is full
void floodFill8(int x, int y, int newColor, int oldColor)
{
    if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[x][y] == oldColor && screenBuffer[x][y] != newColor)
    {
        screenBuffer[x][y] = newColor; //set color before starting recursion!
        
        floodFill8(x + 1, y,     newColor, oldColor);
        floodFill8(x - 1, y,     newColor, oldColor);
        floodFill8(x,     y + 1, newColor, oldColor);
        floodFill8(x,     y - 1, newColor, oldColor);
        floodFill8(x + 1, y + 1, newColor, oldColor);
        floodFill8(x - 1, y - 1, newColor, oldColor);
        floodFill8(x - 1, y + 1, newColor, oldColor);
        floodFill8(x + 1, y - 1, newColor, oldColor);
    }    
}
          3, 4 - 방법 스 택 (FloodFill4Stack)
//4-way floodfill using our own stack routines
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
    if(newColor == oldColor) return; //avoid infinite loop
    emptyStack();
      
    if(!push(x, y)) return; 
    while(pop(x, y))
    {
        screenBuffer[x][y] = newColor;
        if(x + 1 < w && screenBuffer[x + 1][y] == oldColor)
        {          
            if(!push(x + 1, y)) return;           
        }    
        if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor)
        {
            if(!push(x - 1, y)) return;           
        }    
        if(y + 1 < h && screenBuffer[x][y + 1] == oldColor)
        {
            if(!push(x, y + 1)) return;           
        }    
        if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor)
        {
            if(!push(x, y - 1)) return;           
        }    
    }     
}
          4, 8 - 스 택 방법 (FloodFill8Stack)
//8-way floodfill using our own stack routines
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
    if(newColor == oldColor) return; //avoid infinite loop
    emptyStack();
      
    if(!push(x, y)) return; 
    while(pop(x, y))
    {
        screenBuffer[x][y] = newColor;
        if(x + 1 < w && screenBuffer[x + 1][y] == oldColor)
        {          
            if(!push(x + 1, y)) return;
        }    
        if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor)
        {
            if(!push(x - 1, y)) return;
        }    
        if(y + 1 < h && screenBuffer[x][y + 1] == oldColor)
        {
            if(!push(x, y + 1)) return;
        }    
        if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor)
        {
            if(!push(x, y - 1)) return;
        }
        if(x + 1 < w && y + 1 < h && screenBuffer[x + 1][y + 1] == oldColor)
        {      
            if(!push(x + 1, y + 1)) return;
        }        
        if(x + 1 < w && y - 1 >= 0 && screenBuffer[x + 1][y - 1] == oldColor)
        {  
            if(!push(x + 1, y - 1)) return;
        } 
        if(x - 1 >= 0 && y + 1 < h && screenBuffer[x - 1][y + 1] == oldColor)
        {          
            if(!push(x - 1, y + 1)) return;
        }
        if(x - 1 >= 0 && y - 1 >= 0 && screenBuffer[x - 1][y - 1] == oldColor)
        {
            if(!push(x - 1, y - 1)) return;
        }
    }
}
         5. 재 귀 스 캔 라인 Floodfill 알고리즘 (floodFillScanline)
//stack friendly and fast floodfill algorithm
void floodFillScanline(int x, int y, int newColor, int oldColor)
{
    if(oldColor == newColor) return;
    if(screenBuffer[x][y] != oldColor) return;
      
    int y1;
    
    //draw current scanline from start position to the top
    y1 = y;
    while(y1 < h && screenBuffer[x][y1] == oldColor)
    {
        screenBuffer[x][y1] = newColor;
        y1++;
    }    
    
    //draw current scanline from start position to the bottom
    y1 = y - 1;
    while(y1 >= 0 && screenBuffer[x][y1] == oldColor)
    {
        screenBuffer[x][y1] = newColor;
        y1--;
    }
    
    //test for new scanlines to the left
    y1 = y;
    while(y1 < h && screenBuffer[x][y1] == newColor)
    {
        if(x > 0 && screenBuffer[x - 1][y1] == oldColor) 
        {
            floodFillScanline(x - 1, y1, newColor, oldColor);
        } 
        y1++;
    }
    y1 = y - 1;
    while(y1 >= 0 && screenBuffer[x][y1] == newColor)
    {
        if(x > 0 && screenBuffer[x - 1][y1] == oldColor) 
        {
            floodFillScanline(x - 1, y1, newColor, oldColor);
        }
        y1--;
    } 
    
    //test for new scanlines to the right 
    y1 = y;
    while(y1 < h && screenBuffer[x][y1] == newColor)
    {
        if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor) 
        {           
            floodFillScanline(x + 1, y1, newColor, oldColor);
        } 
        y1++;
    }
    y1 = y - 1;
    while(y1 >= 0 && screenBuffer[x][y1] == newColor)
    {
        if(x < w - 1 && screenBuffer[x + 1][y1] == oldColor) 
        {
            floodFillScanline(x + 1, y1, newColor, oldColor);
        }
        y1--;
    }
}
          6. 스 택 (floodFillScanlineStack) 이 있 는 스 캔 라인 홍수 방지 알고리즘
//The scanline floodfill algorithm using our own stack routines, faster
void floodFillScanlineStack(int x, int y, int newColor, int oldColor)
{
    if(oldColor == newColor) return;
    emptyStack();
    
    int y1; 
    bool spanLeft, spanRight;
    
    if(!push(x, y)) return;
    
    while(pop(x, y))
    {    
        y1 = y;
        while(y1 >= 0 && screenBuffer[x][y1] == oldColor) y1--;
        y1++;
        spanLeft = spanRight = 0;
        while(y1 < h && screenBuffer[x][y1] == oldColor )
        {
            screenBuffer[x][y1] = newColor;
            if(!spanLeft && x > 0 && screenBuffer[x - 1][y1] == oldColor) 
            {
                if(!push(x - 1, y1)) return;
                spanLeft = 1;
            }
            else if(spanLeft && x > 0 && screenBuffer[x - 1][y1] != oldColor)
            {
                spanLeft = 0;
            }
            if(!spanRight && x < w - 1 && screenBuffer[x + 1][y1] == oldColor) 
            {
                if(!push(x + 1, y1)) return;
                spanRight = 1;
            }
            else if(spanRight && x < w - 1 && screenBuffer[x + 1][y1] != oldColor)
            {
                spanRight = 0;
            } 
            y1++;
        }
    }
}
          그리고 몇 가지 보조 함수 의 소스 코드 가 있 습 니 다.
bool pop(int&x, int &y) 
{ 
    if(stackPointer > 0) 
    { 
        int p = stack[stackPointer]; 
        x = p / h; 
        y = p % h; 
        stackPointer--; 
        return 1; 
    }     
    else 
    { 
        return 0; 
    }    
}    

bool push(int x, int y) 
{ 
    if(stackPointer < stackSize - 1) 
    { 
        stackPointer++; 
        stack[stackPointer] = h * x + y; 
        return 1; 
    }     
    else 
    { 
        return 0; 
    }    
}     

void emptyStack() 
{ 
    int x, y; 
    while(pop(x, y)); 
}
void clearScreenBuffer(ColorRGB color) 
{ 
    for(int x = 0; x < w; x++) 
    for(int y = 0; y < h; y++) 
    { 
        screenBuffer[x][y] = RGBtoINT(color); 
    }     
}

작성 자:
kezunhai
 출처:
http://blog.csdn.net/kezunhai 
전재 나 공 유 를 환영 하지만, 반드시 글 의 출처 를 밝 혀 주 십시오.
CnBlogsDotText 사용 실례
ios 가 실제 컴퓨터 와 시 뮬 레이 터 를 합 친 a 파일 (lipo)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage