Quickhull:

(a) Implement the Quickhull algorithm described in class to compute the convex hull of a set of points in 2D space. Create a method that takes an ArrayList of Point objects and returns an ArrayList of Points on the convex hull. This method should

find the points with minimum and maximum x coordinates (a, b)

create two ArrayLists: upper containing points above line ab and lower containing points below line ab

create an ArrayList of Points that will store the points of the convex hull

make two calls to a recursive method that computes the upper and lower hulls (upper is the input to compute the upper hull and lower to compute the lower hull).

See hints for more details on the recursive method.

(b) Verify expected running time by generating array of Point objects of varying sizes. The points should have a random x and y coordinate values. (note that you don't need to draw the output when you are trying to determine running time since the arrays will be of large size).

Hints:

Here is some pseudocode for the recursive method that computes upper hull: QuickHull(S, a, b, Result) Furthest = furthest away from line ab Add Furthest to Result Create two arrays to store points: left and right for each point p in S Add p to left array if p is to the left of line from a to furthest Add p to right array if p is to the right of line from b to furthest QuickHull(left, a, furthest, result) QuickHull(right, furthest, b, result)

How do we determine the distance from point p to line ab? Notice that the points a, b, p form a triangle. The area of the triangle is 0.5 * base * height. Also note that height is the distance from point p to ab. Since all points share the same base ab, the triangle with the largest area is indeed the point furthest away from line ab (see figure).

Cross product can be used to compute a value that corresponds to twice the area of triangle:

(Optional) If you want to draw the lines of the convex hull (it looks better) then instead of storying all points of the convex hull in the same array, create two arrays (upperHull and lowerHull) then after you compute the two hulls, sort the points in the result arrays with respect to x coordinate. Then you can draw a line between each two consecutive points in the upper hull and each two consecutive points in the lower hull.

Programming language: Java Eclipse

valueBasedOnLineDistance(a, b, p) vlx = b.x - a.x vly = b.y - a.y v2x = p.x - a.x v2y = p.y - a.y return abs (vlx * v2y - vly * v2x) valueBasedOnLineDistance(a, b, p) vlx = b.x - a.x vly = b.y - a.y v2x = p.x - a.x v2y = p.y - a.y return abs (vlx * v2y - vly * v2x)