Java Flood Fill issue

Question

I need to write a flood fill algorithm to color pixels of an image which are inside black borders. I've wrote the following based on some posts here on SO:

private Queue<Point> queue = new LinkedList<Point>();
private int pickedColorInt = 0;

private void floodFill(Pixmap pixmap, int x, int y){
    //set to true for fields that have been checked
    boolean[][] painted  = new boolean[pixmap.getWidth()][pixmap.getHeight()];

    //skip black pixels when coloring
    int blackColor = Color.rgba8888(Color.BLACK);

    queue.clear();
    queue.add(new Point(x, y));

    while(!queue.isEmpty()){
        Point temp = queue.remove();
        int temp_x = temp.getX();
        int temp_y = temp.getY();

        //only do stuff if point is within pixmap's bounds
        if(temp_x >= 0 && temp_x < pixmap.getWidth() && temp_y >= 0 && temp_y < pixmap.getHeight()) {
            //color of current point
            int pixel = pixmap.getPixel(temp_x, temp_y);
            if (!painted[temp_x][temp_y] && pixel != blackColor) {
                painted[temp_x][temp_y] = true;
                pixmap.drawPixel(temp_x, temp_y, pickedColorInt);

                queue.add(new Point(temp_x + 1, temp_y));
                queue.add(new Point(temp_x - 1, temp_y));
                queue.add(new Point(temp_x, temp_y + 1));
                queue.add(new Point(temp_x, temp_y - 1));

            }
        }
    }
}

This doesn't work as expected. For example, on following test image: enter image description here

Random rectangles will get recolored depending of where I've clicked. For example, clicking anywhere below purple rectangle will recolor purple rectangle. Clicking inside purple rectangle recolors the green rectangle. I've checked it and I'm passing right parameters to method so the issue is probably somewhere inside my loop.

I think you are not passing in the correct parameters. It sounds like your Y coordinate is wrong, because some coordinate system you are using is Y-up and another is Y-down. Try y = pixmap.getHeight() - y at the beginning of your method to invert y. — noone
Wow, that didn't even cross my mind. This is a libGDX project where for example scene coordinates, sprites, rectangles and similar objects have a (0, 0) coordinate in lower left. But I guess Pixmap uses top left for (0, 0). Thanks! — Tomislav Turcic
Did that solve your problem? If it did, I'll write it as an answer, so it won't appear unanswered. — noone

noone noone · Accepted Answer · 2015-06-05T09:34:00

Your algorithm is correct, only your input parameters are not.

Random rectangles will get recolored depending of where I've clicked. For example, clicking anywhere below purple rectangle will recolor purple rectangle. Clicking inside purple rectangle recolors the green rectangle.

If you look at the picture, the colored rectangles are not really random. The real problem is an incorrect Y-coordinate. Specifically your Y-coordinate is inverted.

That's because most of the time LibGDX uses a lower-left, y-up coordinate system, but in case of Pixmap it is top-left y-down.

A simple fix for this is to just invert the Y-value by doing y = pixmap.getHeight() - y.

Java Flood Fill issue

1 Answers