Erroneous points produced on convex hull despite following Graham scan

Question

I've essentially followed the wikipedia entry for Graham scan every step of the way as I've coded this little convex hull visualizer. It generally works as intended, but at much higher input sizes there are often erroneous points.

The program starts by filling an ArrayList<Point> with a given number of randomly generated Point objects. It then finds the Point with the lowest y. If multiple Point objects share the lowest value, then the one with the lowest x is used.

Next, it generates an ArrayList<Double> of angles of every Point relative to the specific Point found above. It quicksorts these angles and their corresponding Point objects to produce an ArrayList<Point> with sorted values.

The next step is where I believe my problem lies. First, I make a copy of the ArrayList<Point> and call it edges (note that if I was not using the original ArrayList<Point> for visualization, cloning would be unnecessary) For any three ordered Point objects in edges we'll call A, B, and C, if from AB to BC there is a right turn, then B should be excluded from the hull and is removed from edges. I determine whether the turn is right or left by taking the z-value of the cross product (negative z means AB to BC is a right turn). The program removes any points which causes right turns and carries on.

// loops through the orders points. any time a right turn is
// encountered, the middle point is removed
edges = new ArrayList<Point>();
edges.addAll(points);
boolean changed = true;
while (changed) {
    changed = false;
    for (int i = 0; i < edges.size() - 2; i++) {
        if (isRightTurn(edges.get(i), edges.get(i + 1),
                edges.get(i + 2))) {
            edges.remove(i + 1);
            changed = true;
            i--;
        }
    }
    if (isRightTurn(edges.get(edges.size() - 2),
        edges.get(edges.size() - 1), edges.get(0))) {
        edges.remove(edges.size() - 1);
        changed = true;
    }
}


// uses the z-value of the cross product of AB and AC (ABxAC) to determine
// the direction of the turn.
public static boolean isRightTurn(Point a, Point b, Point c) {
    if ((b.getX() - a.getX()) * (c.getY() - a.getY())
            - (b.getY() - a.getY()) * (c.getX() - a.getX()) < 0)
        return true;
    return false;
}

I mainly added the changed variable for the sake of looping through multiple times just to verify in case something was skipped over. However, the error still persists. Sometimes, it works as intended. Successful convex hull

However, frequently there are at least a few incorrect Point objects. Unsuccessful convex hull

Now what I'm noticing is that up until the left turn occurs, there are multiple Points which properly turn left, but are still erroneous because they ultimately lie inside what should be the convex hull. Could this be an issue of backtracking? I feel like the repeated looping through should catch these cases.

kraskevich kraskevich · Accepted Answer · 2015-05-20T08:46:11

Here is the right way to build the convex hull after sorting the points:

onHull = new List()
for p <- sorted list of points(including the first one)
    while onHull.size() >= 2 && isRight(onHull[onHull.size() - 2], onHull[onHull.size() - 1], p) 
        onHull.popBack()
    onHull.pushBack(p)
return onHull

Erroneous points produced on convex hull despite following Graham scan

1 Answers