1
Я написал реализацию заливки заливки в Java (код см. Ниже). Я хочу, чтобы использовать его, чтобы заполнить внутреннюю часть следующего многоугольника (желтая область):Что случилось с моей реализацией заливки флуда?
Точка (.) представляет собой белый пиксель, X черный пиксель и + положение переменной n во время текущая итерация.
Что-то не так с этой реализацией, поскольку алгоритм заполняет всю сетку с Xes, а не только пространство внутри полигона:
Вы можете увидеть состояние сетки при различной итерации 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;
}
}
Что предлагает вам отладчик? –
@ThomasS. Я не знаю, как отладчик может помочь в диагностике этого (предложения приветствуются). –
Возможно, небольшой тестовый образец будет полезен, когда легче понять, что происходит при выполнении каждого шага и думать об этом. –