我的洪水填充实施有什么问题？
What's wrong with my flood fill implementation?
我在Java中写了一个flood fill实现（代码见下文）。我想用它来填充以下多边形（黄色区域）的内部：
一个点 (.) 代表一个白色像素，X 一个黑色像素和 + 当前迭代期间变量 n 的位置。
这个实现有问题，因为算法用 X 填充了整个网格，而不仅仅是多边形内的 space：
您可以在 this PDF file 中查看网格在各种迭代中的状态。第一页显示调用 floodFill 方法之前的网格，所有后续的 - 调用 visualizer.visualize(grid, n);.
时的状态
我的算法（方法 floodFill）有什么问题，我该如何解决？
代码
protected void floodFill(final FloodFillGridPoint[][] grid,
final FloodFillGridPoint centroid, IFloodFillGridVisualizer visualizer) {
final Queue<FloodFillGridPoint> queue = new LinkedList<>();
queue.add(centroid);
while (!queue.isEmpty()) {
final FloodFillGridPoint n = queue.poll();
if ((n.color() == COLOR_WHITE) && !n.isProcessed()) {
n.markProcessed();
final FloodFillGridPoint west = getWestBoundary(grid, n);
final FloodFillGridPoint east = getEastBoundary(grid, n);
for (int x=west.x(); x <= east.x(); x++) {
final FloodFillGridPoint n2 = getPoint(grid, x, n.y());
n2.setColor(COLOR_BLACK);
final FloodFillGridPoint n2North = getPoint(grid, n2.x(),
n2.y()-1);
if ((n2North != null) && (n2North.color() == COLOR_WHITE)) {
queue.add(n2North);
}
final FloodFillGridPoint n2South = getPoint(grid, n2.x(),
n2.y()+1);
if ((n2South != null) && (n2South.color() == COLOR_WHITE)) {
queue.add(n2South);
}
}
visualizer.visualize(grid, n);
}
}
}
private FloodFillGridPoint getEastBoundary(final FloodFillGridPoint[][] grid, final FloodFillGridPoint n) {
FloodFillGridPoint east = n;
while (east.color() == COLOR_WHITE) {
final FloodFillGridPoint newNode =
getPoint(grid, east.x()+1, east.y());
if (newNode == null) {
break;
}
east = newNode;
}
return east;
}
private FloodFillGridPoint getWestBoundary(final FloodFillGridPoint[][] grid, final FloodFillGridPoint n) {
FloodFillGridPoint west = n;
while (west.color() == COLOR_WHITE) {
final FloodFillGridPoint newNode =
getPoint(grid, west.x()-1, west.y());
if (newNode == null) {
break;
}
west = newNode;
}
return west;
}
private FloodFillGridPoint getPoint(final FloodFillGridPoint[][] grid,
final int x, final int y) {
if (x < 0) {
return null;
}
if (y < 0) {
return null;
}
if (x >= grid.length) {
return null;
}
if (y >= grid[0].length) {
return null;
}
return grid[x][y];
}
public class FloodFillGridPoint {
private final int x;
private final int y;
private int color;
private boolean processed = false;
public FloodFillGridPoint(final int x, final int y, final int color) {
this.x = x;
this.y = y;
this.color = color;
}
public void setColor(final int ncolor) {
this.color = ncolor;
}
public int color() {
return this.color;
}
public void markProcessed() {
this.processed = true;
}
public int x() {
return this.x;
}
public int y() {
return this.y;
}
public boolean isProcessed() {
return this.processed;
}
}
算法将其视为边界上的一个洞：
..........
....X.....
..XX.XXX..
..X....X..
..X....X..
..X....X..
..X....X..
..XXXXXX..
..........
..........
你看到顶部的裂缝了吗？洪水从那里溢出，
并最终覆盖整个网格。
鉴于此网格，它工作正常，并且能够从内部正方形的内部或外部正确填充，它做了正确的事情：
..........
..........
..XXXXXX..
..X....X..
..X....X..
..X....X..
..X....X..
..XXXXXX..
..........
..........
因此，如果您想将第一个示例中的正方形视为 已关闭，
并防止洪水斜向溢出，
然后检查您的实施并进行必要的更改。
不应将边界像素南边和北边的像素放入队列，因为这可能会导致 "diagonal steps"，如 PDF 第 4 页所示。 IE。你可能想试试
for (int x=west.x()+1; x <= east.x()-1; x++) {
从递归中排除边界像素。
其他人关于您的对角线问题的一部分是正确的 - 您的东西边界是实际出现黑色的点，从这些点之一向北或向南可能会导致您到达白色，实际上在容器外面。我自己快速 运行 似乎也表明了其他问题 - 我注意到如果您将东西边界的定义调整为仅指向 [=22= 的 left/right ] 边界，它不会填满一些容器。这是对您的算法的调整，它既使算法更简单（通过避免明确找到 east/west 边界）又更容易看出逻辑上是正确的。对于对角角问题也是安全的：
protected void floodFill(final FloodFillGridPoint[][] grid,
final FloodFillGridPoint centroid, IFloodFillGridVisualizer visualizer) {
final Queue<FloodFillGridPoint> queue = new LinkedList<>();
queue.add(centroid);
while (!queue.isEmpty()) {
final FloodFillGridPoint n = queue.poll();
if ((n.color() == COLOR_WHITE) && !n.isProcessed()) {
n.markProcessed();
n.setColor(COLOR_BLACK);
final FloodFillGridPoint west = getPoint(grid,n.x()-1,n.y());
final FloodFillGridPoint east = getPoint(grid,n.x()+1,n.y());
final FloodFillGridPoint north = getPoint(grid,n.x(),n.y()-1);
final FloodFillGridPoint south = getPoint(grid,n.x(),n.y()+1);
for(FloodFillGridPoint neighbor : Arrays.asList(west,east,north,south)){
if(neighbor!=null && neighbor.color()!=COLOR_BLACK){
queue.add(neighbor);
}
}
visualizer.visualize(grid, n);
}
}
}
例子的结果运行：
.........
.........
....x....
...x.x...
..x.+.x..
...x.x...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...xxx...
..x+x.x..
...x.x...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...xxx...
..x.x+x..
...xxx...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...x+x...
..xxx.x..
...xxx...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...xxx...
..xxxxx..
...x+x...
....x....
.........
.........
------------------------------------------------
*此外，请注意：您已经定义了 两个 考虑点位置的位置。一个位于网格数据结构中的实际位置（由网格中的索引定义），另一个位于点本身（在其 x 和 y 字段中）。软件中有一个原则 "Don't Repeat Yourself" (DRY)，意思是每条信息都应该有一个表示。在像这样的简单情况下，这可能是值得的，但我认为值得一提，因为我遇到了一个错误，其中点的内部 (x,y) 是从网格转置的——这导致了各种奇怪的情况。如果您仍然遇到问题，请自行检查。如果您的其他约束允许，并重构重复项。
我在Java中写了一个flood fill实现（代码见下文）。我想用它来填充以下多边形（黄色区域）的内部：
一个点 (.) 代表一个白色像素，X 一个黑色像素和 + 当前迭代期间变量 n 的位置。
这个实现有问题，因为算法用 X 填充了整个网格，而不仅仅是多边形内的 space：
您可以在 this PDF file 中查看网格在各种迭代中的状态。第一页显示调用 floodFill 方法之前的网格，所有后续的 - 调用 visualizer.visualize(grid, n);.
我的算法（方法 floodFill）有什么问题，我该如何解决？
代码
protected void floodFill(final FloodFillGridPoint[][] grid,
final FloodFillGridPoint centroid, IFloodFillGridVisualizer visualizer) {
final Queue<FloodFillGridPoint> queue = new LinkedList<>();
queue.add(centroid);
while (!queue.isEmpty()) {
final FloodFillGridPoint n = queue.poll();
if ((n.color() == COLOR_WHITE) && !n.isProcessed()) {
n.markProcessed();
final FloodFillGridPoint west = getWestBoundary(grid, n);
final FloodFillGridPoint east = getEastBoundary(grid, n);
for (int x=west.x(); x <= east.x(); x++) {
final FloodFillGridPoint n2 = getPoint(grid, x, n.y());
n2.setColor(COLOR_BLACK);
final FloodFillGridPoint n2North = getPoint(grid, n2.x(),
n2.y()-1);
if ((n2North != null) && (n2North.color() == COLOR_WHITE)) {
queue.add(n2North);
}
final FloodFillGridPoint n2South = getPoint(grid, n2.x(),
n2.y()+1);
if ((n2South != null) && (n2South.color() == COLOR_WHITE)) {
queue.add(n2South);
}
}
visualizer.visualize(grid, n);
}
}
}
private FloodFillGridPoint getEastBoundary(final FloodFillGridPoint[][] grid, final FloodFillGridPoint n) {
FloodFillGridPoint east = n;
while (east.color() == COLOR_WHITE) {
final FloodFillGridPoint newNode =
getPoint(grid, east.x()+1, east.y());
if (newNode == null) {
break;
}
east = newNode;
}
return east;
}
private FloodFillGridPoint getWestBoundary(final FloodFillGridPoint[][] grid, final FloodFillGridPoint n) {
FloodFillGridPoint west = n;
while (west.color() == COLOR_WHITE) {
final FloodFillGridPoint newNode =
getPoint(grid, west.x()-1, west.y());
if (newNode == null) {
break;
}
west = newNode;
}
return west;
}
private FloodFillGridPoint getPoint(final FloodFillGridPoint[][] grid,
final int x, final int y) {
if (x < 0) {
return null;
}
if (y < 0) {
return null;
}
if (x >= grid.length) {
return null;
}
if (y >= grid[0].length) {
return null;
}
return grid[x][y];
}
public class FloodFillGridPoint {
private final int x;
private final int y;
private int color;
private boolean processed = false;
public FloodFillGridPoint(final int x, final int y, final int color) {
this.x = x;
this.y = y;
this.color = color;
}
public void setColor(final int ncolor) {
this.color = ncolor;
}
public int color() {
return this.color;
}
public void markProcessed() {
this.processed = true;
}
public int x() {
return this.x;
}
public int y() {
return this.y;
}
public boolean isProcessed() {
return this.processed;
}
}
算法将其视为边界上的一个洞：
.......... ....X..... ..XX.XXX.. ..X....X.. ..X....X.. ..X....X.. ..X....X.. ..XXXXXX.. .......... ..........
你看到顶部的裂缝了吗？洪水从那里溢出， 并最终覆盖整个网格。
鉴于此网格，它工作正常，并且能够从内部正方形的内部或外部正确填充，它做了正确的事情：
.......... .......... ..XXXXXX.. ..X....X.. ..X....X.. ..X....X.. ..X....X.. ..XXXXXX.. .......... ..........
因此，如果您想将第一个示例中的正方形视为 已关闭， 并防止洪水斜向溢出， 然后检查您的实施并进行必要的更改。
不应将边界像素南边和北边的像素放入队列，因为这可能会导致 "diagonal steps"，如 PDF 第 4 页所示。 IE。你可能想试试
for (int x=west.x()+1; x <= east.x()-1; x++) {
从递归中排除边界像素。
其他人关于您的对角线问题的一部分是正确的 - 您的东西边界是实际出现黑色的点，从这些点之一向北或向南可能会导致您到达白色，实际上在容器外面。我自己快速 运行 似乎也表明了其他问题 - 我注意到如果您将东西边界的定义调整为仅指向 [=22= 的 left/right ] 边界，它不会填满一些容器。这是对您的算法的调整，它既使算法更简单（通过避免明确找到 east/west 边界）又更容易看出逻辑上是正确的。对于对角角问题也是安全的：
protected void floodFill(final FloodFillGridPoint[][] grid,
final FloodFillGridPoint centroid, IFloodFillGridVisualizer visualizer) {
final Queue<FloodFillGridPoint> queue = new LinkedList<>();
queue.add(centroid);
while (!queue.isEmpty()) {
final FloodFillGridPoint n = queue.poll();
if ((n.color() == COLOR_WHITE) && !n.isProcessed()) {
n.markProcessed();
n.setColor(COLOR_BLACK);
final FloodFillGridPoint west = getPoint(grid,n.x()-1,n.y());
final FloodFillGridPoint east = getPoint(grid,n.x()+1,n.y());
final FloodFillGridPoint north = getPoint(grid,n.x(),n.y()-1);
final FloodFillGridPoint south = getPoint(grid,n.x(),n.y()+1);
for(FloodFillGridPoint neighbor : Arrays.asList(west,east,north,south)){
if(neighbor!=null && neighbor.color()!=COLOR_BLACK){
queue.add(neighbor);
}
}
visualizer.visualize(grid, n);
}
}
}
例子的结果运行：
.........
.........
....x....
...x.x...
..x.+.x..
...x.x...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...xxx...
..x+x.x..
...x.x...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...xxx...
..x.x+x..
...xxx...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...x+x...
..xxx.x..
...xxx...
....x....
.........
.........
------------------------------------------------
.........
.........
....x....
...xxx...
..xxxxx..
...x+x...
....x....
.........
.........
------------------------------------------------
*此外，请注意：您已经定义了 两个 考虑点位置的位置。一个位于网格数据结构中的实际位置（由网格中的索引定义），另一个位于点本身（在其 x 和 y 字段中）。软件中有一个原则 "Don't Repeat Yourself" (DRY)，意思是每条信息都应该有一个表示。在像这样的简单情况下，这可能是值得的，但我认为值得一提，因为我遇到了一个错误，其中点的内部 (x,y) 是从网格转置的——这导致了各种奇怪的情况。如果您仍然遇到问题，请自行检查。如果您的其他约束允许，并重构重复项。