This lab starts from the simple "blob counting" example in Section 9.1 and builds it into an interesting GUI program for investigating ideas related to "percolation" and phase transition. Percolation here refers to the idea that a liquid can flow though porous rock, as long as there are enough connections between the pores. The theory says that as porosity increases, there is a point (a phase transition) where it suddenly becomes possible for liquid to flow.
In the program, you will word with a very simple two-dimensional model. In this model, there is a large grid of squares. Each square can be either "solid" or "empty." The empty squares model pores in rock. Liquid can flow from one empty square to neighboring empty squares. (We consider two squares to be neighbors if they are next to each other vertically or horizontally.) We say that percolation occurs if liquid can flow from the top of the grid of squares to the bottom, that is, if there is a path consisting entirely of empty squares that leads from an empty square at the top of the grid to a square at the bottom of the grid.
There are related questions about "blobs," where a blob is defined as an empty square together with all the empty squares that can be reached from that square by a sequence of vertical and horizontal moves. The idea is that liquid can spread throughout a blob, so the general size of the blobs give us some idea of how far liquid can flow, in general, in the grid.
The lab is about more than percolation. You will use a queue, rather than recursion, to implement blob counting. You will build a GUI to allow the user to run experiments and see the results. And you will learn about BufferedImages and will use one to represent the grid of squares.
A complete, compiled version of the program can be found in the jar file PercolationComplete.jar in the directory /classes/s11/cs225. There is also a second version, PercolationComplete_AltUI.jar, which is identical except that the user interface components are arranged differently.
By the beginning of lab next week, you must have completed at least Parts 1 through 4 of this lab. You must have a working version of the program with those parts complete. You will turn in that version by sharing it in a CVS repository to which I have access. You will learn about CVS and how to use it in next week's lab. Your final version of the completed program will be due within the following week.
A BufferedImage is an object that represents a rectangular drawing surface that is stored in the computer's memory but is not shown on the screen. You can obtain a graphics context for drawing on the image, and you can easily copy the image onto the screen (or into another BufferedImage). The BufferedImage class is in the package java.awt.image.
If image is a variable of type BufferedImage, you can create a buffered image that is width pixels wide and height pixels tall by saying:
image = new BufferedImage( width, height, BufferedImage.TYPE_INT_ARGB );
The third parameter is a constant that says how the colors of pixels in the image are represented. There are other types of images, but INT_ARGB is the most common. For this type of image, a color is represented as a 32-bit integer with 8 bits for each color component, alpha, red, green, and blue. Colors are usually written as hexadecimal numbers such as 0xFFFF0000, which represents a pure red. (The alpha component has to do with transparency and should always be hexadecimal FF for standard opaque colors.)
You can get a graphics context of type Graphics2D for drawing on the buffered image by calling image.createGraphics(). However, for this program, you will be getting and setting the colors of individual pixels. For that, you can use
int color = image.getRGB(x,y);
to get the integer that codes the color of the pixel at position (x,y), that is, in row y and column x of the image; and you can use
image.setRGB( x, y, color );
where color is an int, to set the color of the pixel at (x,y). These methods will throw an exception if x or y is outside the valid range for the width and height of the image.
For this program, you will only need three colors, to represent a solid square, an empty square, and an empty square that has been "marked" as part of blob-counting or percolation testing. You should define them as constants:
private static final int COLOR_SOLID = 0xFF000000; // Black.
private static final int COLOR_EMPTY = 0xFFFFFFFF; // White.
private static final int COLOR_SOLID = 0xFFFF0000; // Red.
You can then use a test such as "image.getRGB(x,y) == COLOR_EMPTY" to test whether a square is empty.
By the way, you will probably want to open this lab in a web browser so that you can copy-and-paste into your program.
It's time to start your program. Start a new project and create a class. You could name it, for example, Percolation. You will be writing a GUI program, so you might want to add the appropriate imports at the start of the file:
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
Your class will represent the main JPanel for the program and so should be declared with "extends JPanel". You will need a standard main program to create a window and add the main panel to it. For example:
public static void main(String[] args) {
JFrame window = new JFrame("Percolation");
Percolation board = new Percolation();
window.setContentPane(board);
window.pack();
window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
window.setLocation( (screenSize.width - window.getWidth()) / 2,
(screenSize.height - window.getHeight()) / 2 );
window.setVisible(true);
}
You should add a BufferedImage instance variable to your program, named (for example) image. You will need a way to display the image on the screen. For that, you can use a small nested class that exists only to display a copy of the image. It should be a subclass of JPanel whose paintComponent() method simply fills the panel with the image:
private class Display extends JPanel {
protected void paintComponent(Graphics g) {
g.drawImage(image,0,0,getWidth(),getHeight(),null);
}
}
You will need an instance variable of type Display. Then, you can write the constructor for your class. It should create a 2048-by-2048 image, which is big but small enough that the operations that you will do on it won't take too long. You should also create the display. Since the image will be too big for the screen, you should put the display into a scroll pane, which will show part of the display and allow the user to scroll to view other parts. The preferred size of the display should be the same size as the image. The preferred size of the scroll pane should be just as large as you would like it to appear on the screen. For example:
display.setPreferredSize( new Dimension(2048,2048) );
JScrollPane scroller = new JScrollPane( display );
scroller.setPreferredSize( new Dimension( 750, 750 );
Set the main panel that you are constructing to use a BorderLayout, and add the scroll pane -- not the display -- to the panel in the BorderLayout.CENTER position.
Finally, for this part of the lab, you should write a method to fill the image with a random pattern of solid and empty pixels. The probability that each pixel is empty should be given by the value of an instance variable, fillRatio, whose value should be in the range 0 to 1. (You can just use nested for loops to go to each pixel and set its color.)
You should call the fill method in the constructor
At this point, you should be able to run the program and see the random pattern of pixels in the image. The window should have scroll bars that you can use to scroll to other parts of the image.
You will need some way for the program to display messages to the user. An easy way to do that is with a JLabel; use the setText() method of the label to show a message. The JLabel will have to be an instance variable. You can create the label in the construtor and add it to the SOUTH (or NORTH) position in the border layout. In my program, I configured the JLabel to increase the text size and change its color:
message = new JLabel("Click the image, or use the controls!", JLabel.CENTER);
message.setFont( new Font("Serif", Font.BOLD, 24) );
message.setForeground( new Color(180,0,0) );
message.setBorder(BorderFactory.createEmptyBorder(7,7,7,7));
Now, it's time to start adding interaction to the program. The program should respond to a mouse click on the display by marking and counting the blob at the (x,y) position where the user clicked. You will have to add a mouse listener to the display. There are at least three ways to define listeners: (1) by declaring that the main class itself "implements MouseListener", and using this as the listener object; (2) by using a separate class to represent the listener; and (3) by using an anonymous inner class. Using the last technique, you can do the following in the constructor:
display.addMouseListener( new MouseAdapter() {
public void mousePressed(MouseEvent e) {
int x = e.getX();
int y = e.getY();
.
.
.
}
});
If the user has clicked an empty pixel in the image, you want to mark all the empty pixels that can be reached from the initial pixel by sequences of horizontal and vertical moves. You mark a pixel by changing its color to COLOR_MARKED. You also want to count the number of pixels that you mark; that number is the size of the "blob" at (x,y). You should tell the user the size of the blob by setting the text in the JLabel. (If the user clicks a solid pixel, or one that is already marked, don't do anything except to show a message to the user.)
You should also call display.repaint() after marking the blob, in order for the change to appear on the screen. Whenever you change the image, you have to call display.repaint(). I won't point this out again.
You will need a method to mark and count a blob. The recursive method in Section 9.1 has a problem: In this very large image, the recursion can go too deep. With a fill ratio of 0.6 or higher, you would be very likely to get stack overflow errors in the recursion. It's possible to increase the stack size in the Java Virtual Machine, but a better solution in this case, I think, is to use a queue to implement the algorithm. I used a queue of Points. Point is a built-in class. An object pt of type Point has two public instance variables, pt.x and pt.y, of type int, so you can use an object of type Point to represent the coordinates of a pixel. The file QueueOfInt.java, which you can find in /classes/s11/cs225 defines a queue of ints. You can easily modify it to implement a queue of Points.
Here is the algorithm for blob counting using a queue, assuming that (x,y) is the position in the image where you want to count the blob:
if there is not an empty square at (x,y)
return 0
count = 0
create a queue of Points
mark position (x,y)
add (x,y) to the queue
while the queue is not empty {
remove a point, (x,y), from the queue
count++
if (x-1,y) is in the image and is empty
mark position (x-1,y)
add (x-1,y) to the queue
if (x+1,y) is in the image and is empty
mark position (+-1,y)
add (x+1,y) to the queue
if (x,y-1) is in the image and is empty
mark position (x-1,y)
add (x,y-1) to the queue
if (x,y+1) is in the image and is empty
mark position (x,y+1)
add (x,y+1) to the queue
}
return count
You should write a method to implement this algorithm, and you should call that method in your mouse handler when the user clicks an empty pixel in the image. (You will need the method again later for other purposes.)
At this point, you should be able to run the program and click the image. If you click an empty square, the blob at that position should turn red, and you should be told the number of pixels in the blob. I suggest that you try it for several different fill ratios: 0.55, 0.59, 0.6, and 0.7. (And maybe even for fill ratio 1.0.)
Our goal is to experiment with percolation, which means trying to find a path of empty squares from the top of the image to the bottom. But with the blob marking method in hand, this is easy! Just go across the top row of pixels, and call the blob-marking method for each pixel in that row. Then go along the bottom row of pixels, and check whether any them have been marked, that is, whether their color is red. If so, you have percolation. (Really, before running this test, you should go through the image and change any pixel that has already been marked back to empty.)
So, the main question is when to test for percolation. The GUI needs some way of letting the user ask for a percolation test to be run. There are basically two ways to do that: With a menu command or with a button. For this program, we will use buttons.
Eventually, you will have to add several GUI components to the interface. Laying out GUI components is non-trivial. We will come back to it later. For now, you could just add a simple JPanel to the interface and use it to hold all the other components. Create the JPanel in the constructor, and add it to the NORTH position of the main panel's layout. As you create other components in the constructor, add them to this panel.
You will need instance variables for all the GUI components. For now, declare the following: (1) a JButton to run the percolation test; (2) a JTextField where the user can enter a value for the fill ratio; (3) a JButton that will fill the image with a new random pattern, using the fill ratio from the text field; and (4) a JButton that will remove the mark from any pixel that has been marked. You will need methods to carry out the commands from the JButtons. None of them are difficult. I've already discussed (1). (4) can be implemented with simple nested for loops. For (3), you have to get the fill ratio from the text field. (This is a pretty standard operation: Use the getText() method of the text field. This returns the content as a String. You can convert that string to a double with the method Double.parseDouble(), which can throw a NumberFormatException. Remember that the fill ratio needs to be in the range 0.0 to 1.0. If there is an error, you should show an error message.)
The text field and button objects can be created in the constructor and added to the small panel. For the buttons to do anything, you will have to attach an ActionListener to each button. Again, there are multiple ways to do this, but using an anonymous inner class, it would look something like this example:
percolateButton.addActionListener( new ActionListener() {
public void actionPerformed(ActionEvent e) {
runPercolationTest();
}
} );
You can also add an action listener to the JTextField. If you do that, an action event will be generated when the user presses return while typing in the text field. You could use this as a signal to re-fill the image using the new fill ratio. (This would be redundant with one of the buttons, but it doesn't hurt to have several ways to do something.)
Once you have the three buttons working, you have a pretty usable program. This is as much as you need to have done by next week.
The only piece of functionality that is still missing in the program is the ability to gather some statistics about the blobs. You should add a "Blob Stats" button to your interface, and you should write a method to implement it. The goal is to count the blobs in the image, find their average size, and find something that I call the average neighborhood. The average size is the total number of pixels in all the blobs, divided by the number of blobs. However, there is a problem with this statistic: What I really want to know is, if I click a blob, how big should I expect it to be? That's not the same as the average size, since you are more likely to click on a large blob than a small blob. Suppose that there is one giant blob and a large number of much smaller blobs (which is pretty much what happens when the fill ratio is large). In that case, the average blob size can be pretty small. But a random click is very likely to land in the single giant blob, which means that the expected blob size should be pretty large.
To get a better statistic, we can do the following: For each pixel that is in some blob, take the size of the blob that contains that pixel (that is, the size of that pixel's "neighborhood"). Add up all these numbers, and divide by the number of pixels in all the blobs. If a blob contains N pixels, than the number N gets added into the sum not just once but N times, once for each pixel in the blob. N is added to the sum N times -- another way to do the same thing is to simply add N2 to the sum. So to compute the average neighborhood size, we need to find the sum of all the squared sizes of the blobs as well as the sum of all the sizes. (The second sum gives the total number of pixels in all the blobs.) The average neighborhood size is the sum of the squared sizes divided by the sum of the sizes.
Anyway, the blob stats method should do the following:
clear any existing marks from the image
count = 0
sizeSum = 0
squaredSizeSum = 0
for each pixel
if that pixel is empty
count++
call the method to mark the blob and find its size
add the size to sizeSum
add the square of the size to squaredSizeSum
the average blob size is sizeSum divided by count
the average neighborhood size is squaredSizeSum divided by sizeSum
report the results in a message to the user
One warning: When you compute the square of the size, you will be working with large numbers that can exceed the capacity of a 32-bit integer. In particular, if size is of type int, then the value of size*size might be incorrect because the correct value can't be represented as an int. Saying ((double)size)*size would give the correct value.
One final remark: To output double numbers nicely on the command line, you would probably use System.out.printf. You can't do that in a GUI. However, the String class contains a static method
String.format(formatString, val1, val2, ...)
that returns the same string that would be printed out by
System.out.printf(formatString, val1, val2, ...)
You should have enough information to get the blob stats command working. The results that you can get from this command are interesting. In particular, the average neighborhood size shows a very sharp increase between fill ratios of about 0.59 and 0.60. This is the phase transition. The average neighborhood is the real measure of how far you can expect liquid to be able to spread through the grid. On an infinite grid, the average neighborhood size actually becomes infinite at the phase transition, and the transition is infinitely sharp. For finte grids, the larger the grid, the sharper the phase transition.
If someone wants to do it, perhaps even for a final projet, there are a lot of experiments that could be run. You might, for example, create many grids for each fill ratio and find and graph the average of their average neighborhood sizes. You could also graph the probability of percolation. You could see how the graphs depend on grid size. You might see how different types of grid change the result. For example, what if we allow neighbors in the diagonal directions? You might even look at the three-dimensional cases. For these experiments, you would presumably want non-GUI programs that could do a lot of calculations and save the results.
Probably, your GUI is actually not too bad at this point. However, since the image is too big to show on the screen all at once, I would like you to add a small overview panel to display a reduced-size copy of the image. It won't fit into the simple layout that you are using now. (By the way, I expected the overview to be an averaged-out gray, but apparently Java "samples" pixels from the image, so the overview actually shows -- somewhat deceptively -- the same sort of random colors as the full image. You could probably get the averaging effect by turing on anti-aliasing, but I don't think it would look as good.)
You are required to include an overview display, but you are not required to use a particular layout. I will discuss the two approaches that I took in my two versions of the user interface.
For the overview, you can use a second object of type Display, the same class that is used for the big image. You just have to set the preferred size of the overview display to be something like 128-by-128. Remember that any time you change the main image, you also have to call the repaint() method of the overview display so that it will also reflect the change.
The "AltUI" version of the program places the overview display, the message label, and all the controls at the top of the window:
This layout is easier to make, but not, I think, as nice as my first version of the interface. For the "AltUI" version, you need four JPanels. There is one big JPanel to hold everything else; that JPanel is placed into the NORTH position of the main BorderLayout. And it itself also uses a BorderLayout. The EAST position of that BorderLayout holds the overview display, while the CENTER position is occupied by another JPanel which in turn holds the message label and controls.
The controls/message JPanel uses a GridLayout with three rows and one column. In the top two rows are JPanels (with the default layout) holding the controls. The third row contains the JLabel.
I added a few spacers to my small JPanels, to leave space between some of the controls. You can make a horizontal spacer of length x pixels by calling Box.createHorizontalStrut(x). This makes a component that you can add to a panel just like any other component:
panel.add(Box.createHorizontalStrut(x))
These struts were designed mostly for use with Box and BoxLayout, but in fact they work in any panel.
My first UI version, in PercolateComplete.jar, uses a Box to hold everything except for the main image. A Box is a simple container that can hold either a vertical or a horizontal strip of components. (Internally, it uses a BoxLayout to lay out the components, but you don't have to know that to use a Box.) To create a vertical box, you should use the static method:
Box box = Box.createVerticalBox();
Then, you just have to add the components to the box in the usual way, using box.add(component). You can add vertical spacers to the box by saying, for example,
box.add( Box.createVerticalStrut(30) );
The thing that make boxes not-so-easy to use is that they can do strange things when sizing and lining up components. A component might, for example, end up much larger than you would like and have its center lined up with the left edges of other components. (That's what I found happened when I added a panel to a box.) To fix the size problem, you might have to set a maximum and/or a minimum size for the component. Here's what I had to do with the overview display:
overviewDisplay.setMinimumSize(new Dimension(128,128));
overviewDisplay.setMaximumSize(new Dimension(128,128));
Furthermore, to get the overview display to align properly with the other components, I had to say,
overviewDisplay.setAlignmentX(LEFT_ALIGNMENT);
The other problem was with the fill ratio: I wanted to have the text field and the fill button on the same line. To do this, I put them into a JPanel and added that panel to the box. For this subpanel, I got things to work by saying:
fillRatioPanel.setMaximumSize(fillRatioPanel.getPreferredSize());
fillRatioPanel.setAlignmentX(LEFT_ALIGNMENT);
You might have to do some experimenting to get just the result that you want!
The box should be added to the EAST (or WEST) position in the main border layout.