使用数据结构中的Queue来填充图像，代写一个Java小程序。
Overview
If you have ever used a paint program (such as Microsoft Windows’ Paint, or the multi-platform GIMP), you have probably used the ‘fill’ tool that lets you easily fill a bounded region with a color. One way to implement such a tool is with an algorithm known as Boundary-Fill. For this assignment, you will implement a version that uses a queue to remember work that still needs to be done.
Boundary-Fill requires an image, a location within the image, and a new color to be used for filling. To keep things simple, we will use a 2D array of characters as our image, meaning that locations will be (row,column) pairs and colors will be represented by different characters. Our goal is to replace all locations in the connected region defined by the initial location’s character with the new character. Matching characters are part of the same region if one can be reached from the other by following a path that consists of only that same character and that can be traversed without following a diagonal direction (that is, without moving NE, SE, SW, or NW). For example, consider Figure 1, below. The ‘^’ at (3,1) is not part of the region defined by the other ‘^’ characters. The ‘@’ at (3,2) is part of the region of ‘@’ characters because it’s ‘north’ of the ‘@’ at (4,2). A change of the ‘@’ at (4,2) to another character would turn the current completely connected region of ‘@’ into three separate regions.
The version of Boundary-Fill that we will use for this assignment uses a queue to keep track of the left-most endpoints of horizontal spans of characters that still need to be changed. Here’s how it works. In Figure 1, let’s start with location (3,0), which is an ‘@’. We add it to the queue, shown below the figure. The rest of the algorithm continues so long as there are locations held in the queue. After removing (3,0) from the queue, we change it and all of the ‘@’s directly connected to it on row 3 to the new character (‘.’). Here, only (3,0) is changed. Next, we look for connected spans of ‘@’ both directly above and directly below the span of ‘@’ that we just changed. In this case, there is a span above and a span below. We enqueue the left-most location of those spans (in this case, (2,0) and (4,0), marked with ‘1’ and ‘2’ for illustration purposes only), as shown in Figure 2. In processing row 2, we find no new spans of ‘@’ (Figure 3), and so no locations are added to the queue, leaving just (4,0) on the queue. Dequeuing and processing (4,0) reveals two new spans (Figure 4). From there, the algorithm concludes quickly, leaving the queue empty and the image in the state shown in Figure 5.
Assignment
Write a complete, well-documented Java program that implements the version of the Boundary-Fill algorithm described above. The image format is described in the Data section, below. We know that Java does not provide a dedicated queue class, so we will write our own, with our own queue interface. You are to implement a queue interface named CS127BQueueInterface and a queue class named CS127BQueue that implements your interface, and represents queues using the circular array queue representation we just learned. (This means no JCF classes; you are restricted to ordinary arrays.) The exact method names, method arguments, etc., are up to you. The Boundary-Fill algorithm will be implemented as part of the Program7 class, and will, of course, make use of your queue class.
Write your main method in the Program7 class to accept the name of the file holding the image, the row and column coordinates of the starting point, and the character to be used to fill the area from the command line. For example:
java Program7 pretty.dat 23 7 "*"
(The asterisk is in quotes because punctuation symbols on the command line can cause strange behaviors otherwise.) If the user does not give all four parts, prompt the user for the information:
Enter the name of the image file: pretty.dat
Enter the row,col starting location of the fill area, comma-separated: 23,7
Enter the character to be used for filling: *
Data
A sample ‘image’ is available from D2L: prog7sample.dat. The first line has two integers, separated by at least one space. The first number is the number of rows in the image, the second the number of columns. The rest of the lines consist of characters, one image row per line.
As usual, create your own images for testing purposes. Feel free to share your testing images with classmates. The section leaders will create their own set of testing images to use when they grade your programs, and no, those will not be shared with you before the due date.
Output
For each image, location, and fill character specified, your program is to: (a) display the original image, location, character at that location, and the new character to be used for filling; (b) display the queue content after each pixel span has been filled and the left ends of all adjacent pixel spans have been queued (similar to the queue content given in the examples above); and (c) display the final image and the counts of both (i) the number of pixel spans filled and (ii) the total number of pixels that were modified. You need not display the row and column labels or the borders that appear in the samples, but you may if you wish to.
The file prog7sample.out on D2L shows an example of the expected output. This example used the provided prog7sample.dat file as input.
Turn In
When you are done with the assignment and are ready to submit it, turn in all of your files (Program7.java, CS127BQueueInterface, and CS127BQueue) to the Program7 folder on D2L. If you are submitting your program late, put the file(s) in the Program7-Late folder.
Want to Learn More?
- Filling regions with color (or a ‘texture’ of a pattern of colors) is a common graphics operation for which multiple algorithms exist. Any comprehensive computer graphics text will cover Boundary-Fill (sometimes under the name ‘Flood-Fill’).
Hints, Reminders, and Other Requirements
As the queue needs to hold locations, you may use Java’s Point class to hold the coordinates. Thus, your queue would be represented by an array of Point objects. You may write your own location class, if you prefer.
If you get ambitious, you can replace the text output with a graphical representation of the image. This could allow the user to watch the image being filled. No extra credit, of course, but it would be fun to do and would impress your SL.