Chapter 22, Problem 22.9PE

(Geometry: gift-wrapping algorithm for finding a convex hull) Section 22.10.1 introduced the gift-wrapping 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<Point2D> getConvexHull(double[][] s)

Point2D is defined in Section 9.6.3.

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