Solved

Flood Fill in Java

Posted on 1997-11-18
8
3,056 Views
Last Modified: 2008-03-10
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.
0
Comment
Question by:bmccorkle
8 Comments
 
LVL 4

Expert Comment

by:rembo
ID: 1230872

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
 

Author Comment

by:bmccorkle
ID: 1230873
Edited text of question
0
 
LVL 4

Expert Comment

by:russgold
ID: 1230874
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
Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

 
LVL 4

Accepted Solution

by:
rembo earned 100 total points
ID: 1230875

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
 
LVL 6

Expert Comment

by:jpk041897
ID: 1230876
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
 
LVL 4

Expert Comment

by:rembo
ID: 1230877

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
 
LVL 6

Expert Comment

by:jpk041897
ID: 1230878
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
 
LVL 4

Expert Comment

by:rembo
ID: 1230879

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

Featured Post

Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
servlet requestdispatcher include and forward differences 1 39
session migration servlets 2 42
java jdbc batch example 8 41
Html Table Looping (part 2) 5 27
An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

830 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question