How to fill with color a random shape?

Java 2D
#1

Hi,

I have a map made out of provinces. Those provinces look like this, for example:

http://upl.silentwhisper.net/uplfolders/upload0/shape_7428.gif

For filling the interrior of this shape I think the only solution is using flood fill. Since there isn’t any such method in Java, I made one myself

    public void floodFill(BufferedImage img, int x, int y, Color color, Color stopColor)
    {
        img.setRGB(x,y,color.getRGB());
        if ( (x-1 >= 0) && (img.getRGB(x-1,y) != stopColor.getRGB()) && (img.getRGB(x-1,y) != color.getRGB()) )
            floodFill(img,x-1,y,color,stopColor);
        if ( (x+1 < img.getWidth()) && (img.getRGB(x+1,y) != stopColor.getRGB()) && (img.getRGB(x+1,y) != color.getRGB()) )
            floodFill(img,x+1,y,color,stopColor);
        if ( (y-1 >= 0) && (img.getRGB(x,y-1) != stopColor.getRGB()) && (img.getRGB(x,y-1) != color.getRGB()) )
            floodFill(img,x,y-1,color,stopColor);
        if ( (y+1 < img.getHeight()) && (img.getRGB(x,y+1) != stopColor.getRGB()) && (img.getRGB(x,y+1) != color.getRGB()) )
            floodFill(img,x,y+1,color,stopColor);
    }

This does work in some cases, but in “larger” shapes (a little bit larger than the image I posted) I get a StackOverflowError. Obviously, I cannot fill the provinces like this.
And I would be doing this frequently, as the provinces change ownership, so I’d have to fill them with different color. I noticed that the Graphics2D class has a fill(Shape s) method, so prhaps this would be useful? But then I’d have to detect the edges of each province.

Any advice? ???

#2

a simple trick : use two versions of the image : reference (memory only) and working (on screen)
the reference version will have a different color for the interior of the shape, and you’ll take it as a reference to fill your working image (replacing working image pixels with your new color when the reference image pixel is of the right color.

Lilian

#3

Take a look at the traversing all pixels in an area thread. The last post contains the complete code for a very fast flood fill that don’t overflow the stack as easily, because it uses less recursion. There is also a discussion on how to use a stack instead of recursion.

#4

Well, using a stack instead of recursion does indeed help, so now I don’t get any StackOverFlow errors, and the map is filled using my method. It is terribly slow though.
I tried using that algorithm you posted, but it doesn’t work. If I want to fill an area with blue, I only get one pixel filled with blue, and nothing else happens. This is the modified code, could you look at it and tell me what’s wrong? ???

           /* this is how I call your code */
        // offscreen contains the blank provinces
        DataBuffer dbuffer = offscreen.getRaster().getDataBuffer();
        int[] imageData = ((DataBufferInt)dbuffer).getData();

        // I only fill the first province map for testing
        linearFloodFill4(provinces[0].fillX,      // x coordinate
                          provinces[0].fillY,      // y coordinate
                           -1, -1, -2,                  
                          offscreen.getWidth(),    // entire map width, ~1500
                          offscreen.getHeight(),  // map height, ~1000
                          imageData,                    // array of pixels
                          Color.BLUE.getRGB(),    // fill color
                          offscreen.getRGB(provinces[0].fillX,provinces[0].fillY));   // get starting color from (x,y)

// your modified function ------------->

    private int linearFloodFill4(int x, int y, int prevleft, int prevright, int prevy, 
            int width, int height, int[] image, int fillcolor, int startcolor) 
    {
      // exactly the same
    }
#5

Ah okay, it works now! Interesting, this one works:

linearFloodFill4(provinces[0].fillX,provinces[0].fillY,-1,-1,-2,offscreen.getWidth(),offscreen.getHeight(),
                imageData,Color.BLUE.getRGB(),imageData[provinces[0].fillX+provinces[0].fillY*mapImage.getWidth()]);

and this one doesn’t:

linearFloodFill4(provinces[0].fillX,provinces[0].fillY,-1,-1,-2,offscreen.getWidth(),offscreen.getHeight(),
                imageData,Color.BLUE.getRGB(),offscreen.getRGB(provinces[0].fillX,provinces[0].fillY));

So obviously imageData[x,y] returns a different value than offscreen.getRGB(x,y). Any idea why? Perhaps the getRGB() method doesn’t return the alpha value?

#6

I also wouldn’t use floodfill at all in this case. Instead I would use one big background image (with all those provinces) and highlighted versions of all those provinces (with bounding dimensions… not full background size).

Those single province images would use an indexed color mode with bitmask transparency and they contain all pixels which would change in case of a highlight… eg if you would use some antialiasing they would also contain a bit of the outlines (those blended pixels).

The alpha of each province can be also used for determining which one you have to highlight. Iterate across all provinces, check if you are within the bounds… if so check the alpha… if opaque… stop - you found it… otherwise continue.

Its pretty straigtforward, but it looks good (antialiasing) and its fast (both - drawing and “collisions”), too. The tricky bit, which remains is the art creation process. You have countless options here, but I would use a semi-automatic process like:

-create the background
-copy the background… draw the highlighting… save
-repeat until you’ve done that for all provinces

[Easy enough so far, huh?]
Write a small tool, which can compare two images… it needs to:
-determine the bounds of the changed pixels (eg x 203, y 150, w 50, h 75)
-create an (full alpha) image with that bounds
-copy those differency-pixels
-save that new image and also save those bounds (you’ll need em later)

Then you use that tool with background & background_with_highlighted_province1… background & background_with_highlighted_province2 etc and at the very end you batch convert those differency images to 8bit png (bitmask transparency and no dither).

Using those images and bounds should be very easy then. And don’t worry about that fart more image data. It will compress down to basically nothing with tools like pngout.