Finding convex hull using gift-wrapping algorithm

Question

Here's the pseudocode for finding convex hull using Gift-Wrapping Algorithm:

Step 1: Given a list of points S, let the points in S be labeled s0, s1, ..., sk. Select the rightmost lowest point S. As shown in Figure 24.9a, h0 is such a point. Add h0 to list H. (H is initially empty. H will hold all points in the convex hull after the algorithm is finished.) Let t0 be h0.

Step 2: Let t1 be s0. For every point p in S, if p is on the right side of the direct line from t0 to t1, then let t1 be p. (After Step 2, no points lie on the right side of the direct line from t0 to t1, as shown in Figure 24.9b.)

Step 3: If t1 is h0 (see Figure 24.9d), the points in H form a convex hull for S. Otherwise, add t1 to H, let t0 be t1, and go back to Step 2 (see Figure 24.9c).

Here's what I've managed to do so far:

public void getConvexHull(ArrayList<Point> points) {
    ArrayList<Point> h = new ArrayList<Point>();
    points.sort(new YComparator());
    h.add(points.get(points.size()-1)); // Add the rightmost lowest point to h
    Point t0 = h.get(0);
    Point t1 = points.get(0);
    while(true) {
        for(int i = 0; i<points.size(); i++) {
            if(isRight(t0,t1,points.get(i)) == 1) {
                t1 = points.get(i);
            }
        }
        if(t1.equals(h.get(0))) {
            break;
        }
        h.add(t1); // The exception occurs at this line
        t0 = t1;
        t1 = points.get(0);
    }
    for(Point x: h)
        System.out.println(x);
}

The isRight() method:

public int isRight(Point a, Point b, Point c){
    int pos = ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x));
    if(pos < 0) {
        return 1;
    }
    else if(pos > 0) {
        return -1;
    }
    else {
        return 0;
    }
}

This method returns true if Point c lies on the right of the line formed by joining Point a and Point b.

[I think something is wrong with this method]

The YComparator class:

public class YComparator implements Comparator<Point>{
@Override
public int compare(Point a, Point b) {
    if(a.y > b.y) {
        return 2;
    }
    else if(a.y < b.y) {
        return -2;
    }
    else if(a.y == b.y) {
        if(a.x > b.x) {
            return 1;
        }
        else if(a.x < b.x) {
            return -1;
        }
    }
    return 0;
}
}

When I run the program, it throws java.lang.OutOfMemoryError: Java heap space exception.

Answer 1

Try this:

while(flag) { ...

And move this:

if(t1.equals(h.get(0))) {
    flag = false;
}

into your for loop.