홍수 채우기 알고리즘

Question

메신저가 C의 터보 C++로 된 간단한 그래픽 라이브러리에서 작동합니다. 메신저가 페인트 스타일 프로그램의 매우 원시적 인 버전을 개발했기 때문에 모든 것이 잘 작동하지만 홍수 채우기 알고리즘을 사용할 수 없기 때문입니다. 4 웨이 홍수 채우기 알고리즘을 사용하여, 나는 처음에는 재귀 버전을 시도했지만 작은 영역에서만 작동하므로 큰 영역을 채우면 충돌이 발생합니다. 읽기 나는 그것의 명시적인 스택 버전을 구현하는 발견 문제를 해결하지만 정말 모르겠다.

나는이 같은 스택을 개발했다 :

struct node 
{ 
    int x, y; 
    struct node *next; 
}; 

int push(struct node **top, int x, int y) 
{ 
    struct node *newNode; 
    newNode = (struct node *)malloc(sizeof(struct node)); 
    if(newNode == NULL) //If there is no more memory 
     return 0; 
    newNode->x = x; 
    newNode->y = y; 
    newNode->next = *top; 
    *top = newNode; 
    return 1; //If we push the element correctly 
} 

int pop(struct node **top, int &x, int &y) 
{ 
    if(*top == NULL) //If the stack is empty 
     return 0; 
    struct node *temporal; 
    temporal = *top; 
    x = (*top)->x; 
    y = (*top)->y; 
    *top = (*top)->next; 
    free(temporal); 
    return 1; //If we pop an element 
} 

을 그리고 이것은 내가 홍수 채우기 기능하게 가지고있는 코드 :

void floodFill(int x, int y, int color_to_replace, int color_to_fill) 
{ 
    if(color_to_replace == color_to_fill) 
    return; 
struct node *stack = NULL; 
if(push(&stack, x, y) == 0) //If we can´t push the pixel 
      return; 
    while(pop(&stack, x, y) == 1) //While are pixels in the stack 
    { 
     pixel(x, y, color_to_fill); 
     if(x+1 < 640 && read_pixel(x+1, y) == color_to_replace) 
      if(push(&stack, x+1, y) == 0) 
       return; 
     if(x-1 >= 0 && read_pixel(x-1, y) == color_to_replace) 
      if(push(&stack, x-1, y) == 0) 
       return; 
     if(y+1 < 480 && read_pixel(x, y+1) == color_to_replace) 
      if(push(&stack, x, y+1) == 0) 
       return; 
     if(y-1 >= 0 && read_pixel(x, y-1) == color_to_replace) 
      if(push(&stack, x, y-1) == 0) 
       return; 
    } 
} 

하지만 여전히 때 메신저, 일을하지는 그냥 큰 영역을 채우기 위해 triying하고 내 프로그램에서 해상도 640 X 480로 작업하기 때문에 정말 문제가있다; 어떤 아이디어가 작동하지 않는 이유는 무엇입니까?

Answer 1

스택의 모든 픽셀을 밀어 넣는 대신 스택의 새 위치를 누르기 전에 가능한 한 많은 픽셀을 채우십시오. 자세한 내용은 Wikipedia article을 참조하십시오.

Answer 2

난 아무데도 어떤 boundschecking 표시되지 않습니다 ...

당신은 X 확실와 Y 값은 그림에서 가지 마세요?

편집 : 작동 할 수없는 이유

추가 아이디어 :

• 읽기 및 픽셀 기능 (때문에 다시 얻을 색상 값은 32 비트까지 확장되어
• 버그를 쓰기 예를 들어 사진이 16 비트입니다.) 다시 쓰고 다시 읽으려고하는 색상이 정확히 일치하지 않습니다. 예를 들어 색상을 쓰면 0xff00ff이지만 색상이 16 비트에서 확장되었으므로 0xf800f8이 돌아옵니다. 이렇게하면 홍수가 계속 채워집니다.