Flood Fill in Java

Does anyone know of a routine to do a flood fill in Java?  By flood fill I mean the same as "paint can" fill in a graphics program.  Basically, a flood fill identifies the key color at a specified coordinate.  The routine then changes pixels of the key color to a new color spreading in all directions until a pixel not the key color is found.
bmccorkleAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

remboCommented:

When you say flood fill, do you mean filling a region
with color?  If so, then you want the fillRect() method
in the Graphics class.  If you mean something else, could
you clarify a bit?

-Tony

0
bmccorkleAuthor Commented:
Edited text of question
0
russgoldCommented:
The biggest problem you will have with this is that Java has no way to read the current screen, so you have to use offscreen bitmaps.
0
Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

remboCommented:

Well, it depends completely on what else on the screen,
and how you have stored that information.  

If you're doing a drawing program that has other items
on the screen, then you'll need to store them some how
(at least a description of them) so you can redraw them
when you repaint the background.  

Say you have a bunch of rectangles and you want to fill
the background.  

You can do this:

public void paint(Graphics g)
{
  Image img = createImage(size().width, size().height);
  Graphics goff = img.getGraphics();
 
  goff.setColor(//set fill color here);
  goff.fillRect(0,0,size().width, size().height);
 
  //Then here you redraw all the stored rectangles - or other shapes

  g.drawImage(img, 0,0,size().width,size().height);
}

I have a paint program that does this sort of stuff if you
need more info.

-Tony


 
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
jpk041897Commented:
Actually, there is a way to get a pixels color in Java, its just not an obvious way:

public int getPixel(Graphics img, int x, int y, int w, int h){
// under ordinary circumstances w and h will be = 1 unless you need a larger pixel for some reason. Of course, you would then have to return either an int[] or the average of the pixel colors (after breaking them down to their rgb component and reconstituting) depending on your need.

   int[] pixels = new int[w * h];
   PixelGrabber pg = new PixelGrabber(img, x, y, w, h, pixels, 0, w);
   return pixels[0];
}

the return value contains an rgb value that contains the color of the pixel. channels and I'll post some more code).

Once you know how to read a pixel from the immage, doing a flood fill is fairly easy. Just use the following algorithm:

//Point Seed(x,y) is the seed pixel, i.e.: a coordinate pair known to be inside the surface to be filled.

//int colorNew = Is the fill color, Int colorBorder is the boundry color

//In a normal flood fill, you would not need the background color , but here you want to respect the shadows if they were drawn before hand
// so we will need to have a flag to treat shadows as background color (when drawing shadows) or as borders when drawing the points) bool flag;

// Say flag = false means overwrite the shadows.

// g is a Graphics param obtained from the pannels paint() method.

Stack St;
Point pixel(Seed);
St.Push(pixel);
while (St.empy()){
   pixel = St.Pop();
   setColor(colorNew);
   int c = getPixel(g, pixel.x, pixel.y, 1, 1);
   if ((c <> colorNew) and !flag) img.drawLine(pixel.x, pixel.y, pixel.x, pixel.y);
   else{
      int c = getPixel(img, pixel.x + 1, pixel.y, 1, 1);
      if ((c <> colorNew) and ( c <> color Border)){
         Point newPixel(pixel);
         newPixel.x += 1;
         St.Push(newPixel);
      }

      int c = getPixel(img, pixel.x, pixel.y + 1, 1, 1);
      if ((c <> colorNew) and ( c <> color Border)){
         Point newPixel(pixel);
         newPixel.y += 1;
         St.Push(newPixel);
      }

      int c = getPixel(img, pixel.x - 1, pixel.y, 1, 1);
      if ((c <> colorNew) and ( c <> color Border)){
         Point newPixel(pixel);
         newPixel.x -= 1;
         St.Push(newPixel);
      }

      int c = getPixel(img, pixel.x, pixel.y - 1, 1, 1);
      if ((c <> colorNew) and ( c <> color Border)){
         Point newPixel(pixel);
         newPixel.y -= 1;
         St.Push(newPixel);
      }
   }
}

Hope this added input helps.
0
remboCommented:

The biggest problem with an approach like that is that
the PixelGrabber is *slow*.  If you have to do that on
any kind of a regular basis, your application or applet
will just *grind* to a halt.  At least, that's been my
experience.  

When managing a screen like that, keeping track of what
you need to redraw will perform much better.


0
jpk041897Commented:
As rembo states quite correctly, pixelGrabber IS slow, and even if it were not, it is always wise to keep track of what your drawing whenever possible.

In a freehand draw program though, this is not always practical, so flood fills become more important. Regarding the grinding to a halt though, that would depend on how big a graphics area is beeing filled in. Since the pixelGrabber is beeing used to read the value of a single pixel, most of the delay will be caused by stack code overhead, rather than the method itself, so for small graphics areas it should work well enough.

At any rate, the purpose of my posting was to rectify russgold's comment regarding Java not beeing able to read the screen. It can, albeit not in an efficient manner.

 Since that kind of comment has caused confusion in the past in some questions from the Previously Answered list, I felt it was justified to clarify that particular point.
0
remboCommented:

jpk is absolutely correct.  Unfortunately, these being
the only two solutions to this kind of problem is something
we should really bring up with JavaSoft.  Trying to do things
like real, useful paint programs in Java is a bit painful.

Sounds like you've done some stuff like this, I wrote a
paint program, and I had to store all this stuff in a Vector.
There really should be a better way.

Just venting :)

0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.