代写Convex Hull算法，然后将计算得到的边界画图显示出来。
Project Overview
In this project, you are asked to implement Graham’s scan and Javis’ march to
construct the convex hull of an input set of points in the plane, and compare
their execution times. For a description of the algorithm, please refer to the
lecture notes “convex-hull.pptx”.
We make the following two assumptions:
- a) All the input points have integral coordinates ranging between 50 and 50.
- b) The input points may have duplicates.
In a), integral coordinates are assumed to avoid issues with floating-point
arithmetic. The rectangular range [50, 50] [50, 50] is big enough to contain
10,201 points with integral coordinates. Since the input points will be either
generated as pseudo-random points or read from an input file, duplicates may
appear.
The classes PureStack and ArrayBasedStack should not be modified. Four classes
from Project 2 will be modified or reused for this project: Segment, Plot,
Point, and PolarAngleComparator,. No need to modify Segment and Plot.
Modify your implementation of the class Point so that the compareTo() method
now compares y-coordinate first. The class PolarAngleComparator has an
additional instance variable flag used for breaking a tie between two points
which have the same polar angle with respect to the reference point (stored in
the instance variable referencePoint). When flag == true, the point closer to
referencePoint is considered smaller; when flag == false, the further point is
considered smaller.
ConvexHull Class
Convex hull construction is implemented by the abstract class ConvexHull,
which has two constructors:
public ConvexHull(Point[] pts) throws IllegalArgumentException
public ConvexHull(String inputFileName) throws FileNotFoundException, InputMismatchException
—|—
The first constructor takes an array pts[] of points and copy them over to the
array points[]. The array pts[] may consist of random points, or more
precisely, points whose coordinates are pseudo-random numbers within the range
[50, 50] [50, 50]. After Project 2, you are assumed to be familiar with random
point generation. (Just in case not, please read Section 5.)
The second constructor reads points from an input file of integers. Every pair
of integers represents the and -coordinates of a point. A
FileNotFoundException will be thrown if no file with the inputFileName exists,
and an InputMismathException will be thrown if the file consists of an odd
number of integers. (There is no need to check if the input file contains
unneeded characters like letters since they can be taken care of by the
hasNextInt() and nextInt() methods of a Scanner object.)
For example, suppose a file points.txt has the following content (this was the
same example file used in the description of Project 2):
0 0 -3 -9 0 -10
8 4 3 3
-6 3
-2 1
10 5
-7 -10
5 -2
7 3 10 5
-7 -10 0 8
-1 -6
-10 0
5 5
There are 34 integers in the file. A constructor call ConvexHull(“points.txt”)
will initialize the array points[] to store 17 points below (aligned with five
points per row just for display clarity here):
(0, 0) (-6, 3) (7, 3) (-10, 0) (3, 3)
(-3, -9) (-2, 1) (10, 5) (5, 5) (5, -2)
(0, -10) (10, 5) (-7, -10) (-1, -6)
(8, 4) (-7, -10) (0, 8)
Note that the points (-7, -10) and (10, 5) each appear twice in the input, and
thus their second appearances are duplicates. The 15 distinct points are
plotted in Fig.1 by Mathematica.
There is a non-negligible chance that duplicates occur among the input points,
whether they are from the input file or randomly generated from the range [50,
50] [50, 50]. For a fair comparison between Graham’s scan and Javis’ march,
both assuming their input points to be distinct, all the duplicates should be
eliminated before the convex hull construction. This is done by the
constructors via calling the method removeDuplicates().
The method removeDuplicates() performs quicksort on all the points by
y-coordinate. After the sorting, equal points will appear next to each other
in points[]. The method creates an object of the class QuickSortPoints to
carry out quicksort using a provided Comparator object, which invokes the
compareTo() method in the class Point. After the sorting, identical points
will appear together, and duplicates will be easily removed. Distinct points
are then saved to the array pointsNoDuplicate[] with the element at index 0
assigned to lowestPoint.
In the previous example, quicksort produces the following sequence:
(-7, -10) (5, -2) (3, 3) (10, 5)
(-7, -10) (-10, 0) (7, 3) (0, 8)
(0, -10) (0, 0) (8, 4)
(-3, -9) (-2, 1) (5, 5)
(-1, -6) (-6, 3) (10, 5)
The two (-7, -10)s appear together, so do the two (10, 5)s. After removal of
duplicates, the remaining points are copied over to the array
pointsNoDuplicate[]:
(-7, -10) (-10, 0) (7, 3)
(0, -10) (0, 0) (8, 4)
(-3, -9) (-2, 1) (5, 5)
(-1, -6) (-6, 3) (10, 5)
(5, -2) (3, 3) (0, 8)
The variable lowestPoint is set to (-7, -10).
The array pointsNoDuplicate[] will be the input of a convex hull algorithm.
The class
ConvexHull has an abstract method constructHull() which will be implemented by
its subclasses to carry out convex hull construction using either Graham’s
scan or Jarvis’ march.
public abstract void constructHull();
—|—
The vertices of the constructed convex hull will be stored in the array
hullVertices[] in counterclockwise order starting with lowestPoint.
Convex Hull Construction
Two algorithms, Graham’s scan and Jarvis’ march, are respectively implemented
by the subclasses GrahamScan and JarvisMarch of the abstract class ConvexHull.
Both subclasses must handle the special case of one or two points only in the
array pointsNoDuplicates[], where the corresponding convex hull is the sole
point or the segment connecting the two points.
Graham’s scan
The class GrahamScan sorts all the points in points[] by polar angle with
respect to lowestPoint. Point comparison is done using a Comparator object
generated by the constructor call PolarAngleComparator(lowestPoint, true). The
second argument true ensures that points with the same polar angle are ordered
in increasing distance. (In case your previous implementation did not work
well, this is a chance to make it up. ) The compare() method must be
implemented using cross and dot products not any trigonometric or square root
functions. (Please read the Javadoc for the compare() method carefully.)
Point sorting above is carried out by quicksort as follows. Create an object
of the QuickSortPoint class and have it call the quicksort() method using the
PolarAngleComparator object mentioned in the above paragraph. The comparator
uses lowestPoint as the reference point. Note that quicksort has the expected
running time ( log ) and the worst-case running time (2 ), which will
respectively be the expected and worst-case running times for this
implementation of Graham’s scan for convex hull construction.
Sorting is performed within the method setUpScan(). In the array
pointsNoDuplicate[], (1, -6) and (5, -2) have the same polar angle with
respect to (-7, -10). That (-1, -6) appears before (5, -2) is because it is
closer to (-7, -10). Graham’s scan is performed within the method
constructHull() on the array pointsNoDuplicate[] using a private stack
vertexStack. As the scan terminates, the vertices of the constructed convex
hull are on vertexStack. Pop them out one by one and store them in a new array
hullVertices[], starting at the highest index. When the stack becomes empty,
the elements in the array, in increasing index, are the hull vertices in
counterclockwise order.
Jarvis’ March
This algorithm of the gift wrapping style is implemented in the class
JarvisMarch. There are three private instance variables.
private Point highestPoint;
private PureStack leftChain;
private PureStack rightChain;
—|—
The algorithm builds the right chain from lowerestPoint to highestPoint and
then the left chain from highestPoint downward to lowestPoint. Two stacks,
leftChain and rightChain, are used respectively to store the chains during the
construction. The convex hull vertices on the stacks are later merged into the
array hullVertices[].
The convex hull construction is described with more details in the PowerPoint
notes “convex hull.pptx”. At each step, the method
private Point nextVertex(Point v)
—|—
determines, given the current vertex v, the next vertex to be the point which
has the smallest polar angle with respect to v. In the situation where
multiple points attain the smallest polar angle, the one that is the furthest
from v is the next vertex. Hence, the comparator used in this construction
step should be generated by the call PolarAngleCompartor(v, false).
Display the Convex Hull
The constructed convex hull will be displayed again using Java graphics
package Swing. Please refer to Section 4 in the description of Project 2 for a
brief introduction to Swing. The outputs by the two convex hull algorithms are
displayed in separate windows. For display, a separate thread is created
inside the method myFrame() in the class Plot. Please do not modify this class
for better display unless you understand what is going on there.
The class Segments has been implemented for creating specific line segments to
connect the input points so you can see the correctness of the sorting result.
The output of each algorithm can be displayed by calling the partially
implemented method draw() in the ConvexHull class, only after constructHull()
is called, via the statement below:
Plot.myFrame(pointsNoDuplicate, segments, getClass().getName());
—|—
where the first two parameters have types Point[] and Segment[], respectively.
The call getClass().getName() simply returns the name of the convex hull
algorithm used. From hullVertices[] you will generate the edges of the convex
hull as line segments and store them in the array segments[]. This can be done
by iterating through the element in the array in one loop. Do not forget to
generate a segment connecting the last element with the first point at index
0, that is, lowestPoint.
For the example in Section 1, the array Segment[] contains 5 segments below
(where each element is shown as a pair of points):
((-7, -10), (0, -10))
((0, -10), (10, 5))
((10, 5), (0, 8))
((0, 8), (-10, 0))
((-10, 0), (-7, -10))
Compare Convex Hull Algorithms
The class CompareHullAlgorithms executes Graham’s scan and Jarvis’ march on
points randomly generated or read from files. If the input points are not from
an existing file, , its main() method calls the method generateRandomPoints()
to supply an array of random points Over each input set of points, the method
compares the execution times of these algorithms in multiple rounds. Each
round proceeds as follows:
- a) Create an array of randomly generated integers, if needed.
- b) For each of GrahamScan and JavisMarch, create an object from the above array or an input file.
- c) Have the two created objects call the construcHull() method and store the results in hullVertices[].
Random Point Generation
To test your code, you may generate random points within the range [50, 50]
[50, 50].
Such a point has its - and -coordinates generated separately as pseudo-random
numbers within the range [50, 50]. You already had experience with random
number generation from Project 1. Import the Java package java.util.Random.
Next, declare and initiate a Random object like below
Random generator = new Random();
—|—
Then, the expression
generator.nextInt(101) - 50
—|—
will generate a pseudo-random number between -50 and 50 every time it is
executed.
