Paint Fill multidimensional array

Question

My goal is a "paint fill" function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.

I've implemented it for a 2D array, and here is the code :

public static void paint (int [][] screen,int OldColor,int NewColor,int y,int x)
    {   
        if(y>screen.length-1||y<0||x>screen[0].length||x<0||screen[y][x]!=OldColor)
          return;
        screen[y][x]=NewColor;
        paint(screen,OldColor,NewColor,y-1,x);
        paint(screen, OldColor, NewColor, y+1, x);
        paint(screen, OldColor, NewColor, y, x-1);
        paint(screen, OldColor, NewColor, y, x+1);
    }

But I want to implement it for multidimensional arrays like 3D that could be solved by adding:

paint(screen, OldColor, NewColor, y, x,z-1);
paint(screen, OldColor, NewColor, y, x,z+1);

But imagine the array is 100 D... How can I solve this problem?

First thing you need, is to avoid recursive functions! Use a queue instead. — Soley, May 03 '15 at 18:26

score 2 · Answer 1 · answered May 04 '15 at 11:22

Thanks to @Spektre's suggestion about the structure of the points, I managed to write a simple N-Dimensional floodfill.

Instead of images, I used char matrix to simplify the coding. Changing it to int as color value and some changes in other matrix's data type, will do the 100D for you :)

In this simple program, I try to fill all "A"'s with "B" and it fill all of connected char values similar to ants nest. You can trace the connections between A's using other layers to see the fill path.

In second image (Im1, add intentionally added a B and then added an A above it which is not accessible from fill point) and it worked fine as well.

package test;

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author Pasban
 */
public class NDFloodFill {

    public int N1 = 8; // width
    public int N2 = 6; // height
    public int N = 3; // number of layers
    public ImageData[] images = new ImageData[N];

    public static void main(String[] args) {
        NDFloodFill ndf = new NDFloodFill();

        //print original data
        //ndf.print();
        ndf.fill(0, 0, 0, 'A', 'B');
        ndf.print();
    }

    public NDFloodFill() {
        String im0 = ""
                + "AA...A..\n"
                + ".....A..\n"
                + "....AA..\n"
                + "........\n"
                + "........\n"
                + "...AA.AA";

        String im1 = ""
                + ".A..A...\n"
                + "....B...\n"
                + "..AAA...\n"
                + "........\n"
                + "...AA.A.\n"
                + "..AA..A.";

        String im2 = ""
                + ".A......\n"
                + ".AA.....\n"
                + "..A.....\n"
                + "..A.....\n"
                + "..A.AAA.\n"
                + "..A.....";

        images[0] = new ImageData(im0, 0);
        images[1] = new ImageData(im1, 1);
        images[2] = new ImageData(im2, 2);
    }

    private void print() {
        for (int i = 0; i < N; i++) {
            System.out.println(images[i].getImage());
        }
    }

    private void fill(int x, int y, int index, char original, char fill) {
        Queue<PixFill> broadCast = new LinkedList<>();
        broadCast.add(new PixFill(new Point(x, y), index));
        for (int i = 0; i < N; i++) {
            images[i].reset();
        }
        while (!broadCast.isEmpty()) {
            PixFill pf = broadCast.remove();
            Queue<PixFill> newPoints = images[pf.index].fillArea(pf.xy, original, fill);
            if (newPoints != null) {
                broadCast.addAll(newPoints);
            }
        }
    }

    public class PixFill {

        Point xy;
        int index;

        public PixFill(Point xy, int index) {
            this.xy = xy;
            this.index = index;
        }

        @Override
        public String toString() {
            return this.xy.x + " : " + this.xy.y + " / " + this.index;
        }
    }

    public class ImageData {

        char[][] pix = new char[N1][N2];
        boolean[][] done = new boolean[N1][N2];
        int index;

        public ImageData(String image, int index) {
            int k = 0;
            this.index = index;
            for (int y = 0; y < N2; y++) { // row
                for (int x = 0; x < N1; x++) { // column
                    pix[x][y] = image.charAt(k++);
                }
                k++; // ignoring the \n char
            }
        }

        public void reset() {
            for (int y = 0; y < N2; y++) {
                for (int x = 0; x < N1; x++) {
                    done[x][y] = false;
                }
            }
        }

        public String getImage() {
            String ret = "";
            for (int y = 0; y < N2; y++) { // row
                String line = "";
                for (int x = 0; x < N1; x++) { // column
                    line += pix[x][y];
                }
                ret += line + "\n";
            }
            return ret;
        }

        public Queue<PixFill> fillArea(Point p, char original, char fill) {
            if (!(p.x >= 0 && p.y >= 0 && p.x < N1 && p.y < N2) || !(pix[p.x][p.y] == original)) {
                return null;
            }

            // create queue for efficiency
            Queue<Point> list = new LinkedList<>();
            list.add(p);

            // create broadcasting to spread filled points to othwer layers
            Queue<PixFill> broadCast = new LinkedList<>();
            while (!list.isEmpty()) {
                p = list.remove();
                if ((p.x >= 0 && p.y >= 0 && p.x < N1 && p.y < N2) && (pix[p.x][p.y] == original) && (!done[p.x][p.y])) {
                    //fill
                    pix[p.x][p.y] = fill;
                    done[p.x][p.y] = true;
                    //look for neighbors

                    list.add(new Point(p.x - 1, p.y));
                    list.add(new Point(p.x + 1, p.y));
                    list.add(new Point(p.x, p.y - 1));
                    list.add(new Point(p.x, p.y + 1));
                    // there will not be a duplicate pixFill as we always add the filled points that are not filled yet,
                    // so duplicate fill will never happen, so do pixFill :)

                    // add one for upper layer
                    if (index < N - 1) {
                        broadCast.add(new PixFill(p, index + 1));
                    }

                    // add one for lower layer
                    if (index > 0) {
                        broadCast.add(new PixFill(p, index - 1));
                    }

                    //layers out of range <0, N> can be filtered
                }
            }

            return broadCast;
        }
    }
}

score 1 · Answer 2 · edited May 23 '17 at 12:06

1

Avoid recursive functions! Use a queue instead to flood fill the image ith.
On which image you want to start filling?
check the image color on ith image and add that point to your list.
Later on check if you can go up or down from the stored point to (i+1)th or (i-1)th image and repeat this process from there.

This is a raw idea, but all you may need is this.

Plus, you need to have an array for each level to check if you have filled that pixel for that image or not. So you will escape from infinite loop :)

Check this for flood fill using queue: Flood Fill Optimization: Attempting to Using a Queue

edited May 23 '17 at 12:06

Community

1
1

answered May 03 '15 at 18:32

Soley

1,716
1
19
33

(+1) for optimization suggestions (needed in N-D because recursion is not possible due to lack of memory) but this does not answer the OP question of how to do arbitrary dimension flood fill – Spektre May 04 '15 at 06:55

Spektre · Answer 3 · 2019-07-25T11:01:07.717

Salivan is right with his suggestions but he did not grasp the real problem you are asking about. For arbitrary dimensionality you need to change the point structure from notation like pnt.x,pnt.y,pnt.z to pnt[0],pnt[1],pnt[2] then there are few approaches how to handle this:

fixed limit size padded with zeros

so handle all like 10D (if 10D is maximal dimensionality used) and fill unused axises with zeros. This is slow ugly,painfully demanding on memory and limiting max dimensionality.
use nested for loop (for initializations and more)

look here: rasterize and fill a hypersphere

many multidimensional operations require nested loops this one has arbitrary depth. You can look at it as an increment function of multi digit number where each digit represents axis in your space.

use normal for loop for neighbors generation in N-D

// point variables
int p[N],q[N];
// here you have actual point p and want to find its neighbors
for (int i=0;i<N;i++)
 {
 for (int j=0;i<N;i++) q[j]=p[j]; // copy point
 q[i]--;
 // add q to flood fill
 q[i]+=2;
 // add q to flood fill
 }

Paint Fill multidimensional array

3 Answers3