Erroneous dots released on the convex hull despite Graham's next scan

I essentially followed the wikipedia entry to scan Graham every step of the way as I coded this little convex corpus renderer. It usually works as intended, but erroneous points often occur at much higher input sizes.

The program starts by filling in a ArrayList<Point>

given number of randomly generated objects Point

. Then he finds Point

with the smallest y

. If multiple objects Point

have the lowest value, then the one with the lowest is used x

.

It then generates the ArrayList<Double>

angles of each Point

relative to the specific Point

one found above. It quickly sorts these corners and their corresponding objects Point

to create ArrayList<Point>

with sorted values.

The next step is where I believe my problem lies. First, I make a copy ArrayList<Point>

and name it edges

(note that if I hadn't used the original one ArrayList<Point>

for rendering, cloning would be unnecessary) For any three ordered objects Point

in edges

we will name A

, B,

and C

if from AB

to BC

is right rotation then B

it follows exclude from the body and remove from edges

. I determine if the turn is right or left by taking the z value of the cross product (negative z means AB

before BC

- right turn). The program removes any points that cause correct turns and continues.

// 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 basically added a variable changed

to loop through a few times, just to check if something was missing. However, the error still persists. Sometimes it works as intended.

However, there are often at least a few incorrect objects Point

.

Now I notice that until the left turn occurs, there are a few Points

that properly turn left but are still wrong because they end up lying inside what should be a convex hull. Could this be a return problem? I feel like repeating the loop should catch these cases.