使用数据结构中的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.
