Chapter 22, Problem 22.11PE

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

   /** Return the points that form a convex hull */

   public static ArrayList<MyPoint> getConvexHull (double[][] s)

MyPoint is a static inner class defined as follows:

  private static class MyPoint implements Comparable<MyPoint> {

   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.

           }

         }

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:

How many points are in the set? 6

Enter six 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)