Section 22.10.2 introduced Graham?s algorithm for finding a convex hull for a set of points. Assume that the Java?s coordinate system is used for the points. Implement the algorithm using the following method:

Write a test program that prompts the user to enter the set size and the points and displays the points that form a convex hull. Here is a sample run:

Transcribed Image Text:

/** Return the points that form a convex hull */ public static ArrayList getConvexHul1 (double[][] s) MyPoint is a static inner class defined as follows : private static class MyPoint implements Comparable { double x, y; MyPoint rightMostLowestPoint; MyPoint (double x, double y) { this.x = x; this.y = y; public void setRightMostLowestPoint(MyPoint p) { rightMostLowestPoint = p; @Override public int compareTo(MyPoint o) { // Implement it to compare this point with point o // angularly along the x-axis with rightMostLowestPoint // as the center, as shown in Figure 22.10b. By implementing // the Comparable interface, you can use the Array.sort // method to sort the points to simplify coding. } How many points are in the set? 6 -Enter Enter Enter 6 points: 1 2.4 2.5 2 1.5 34.5 5.5 6 6 2.4 5.5 9 The convex hull is (1.5, 34.5) (5.5, 9.0) (6.0, 2.4) (2.5, 2.0) (1.0, 2.4)