<pre name="code" class="cpp">一、4-Way Recursive Method(FloodFill4) //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); } } 二、8-Way Recursive Method(FloodFill8) //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); } } 三、4-Way Method With Stack(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; } } } 四、8-Way Method With Stack(FloodFill8Stack) //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; } 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; } } } 五、 Recursive Scanline Floodfill Algorithm(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--; } } 六、Scanline Floodfill Algorithm With Stack(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++; } } } cc 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); } }