Ошибочные точки на выпуклой оболочке, несмотря на сканирование по Грэму.

По сути, я следил за записью в Википедии для сканирования Грэма на каждом этапе, поскольку закодировал этот маленький визуализатор выпуклой оболочки. Обычно он работает так, как задумано, но при гораздо больших размерах ввода часто возникают ошибочные точки.

Программа начинается с заполнения ArrayList<Point> заданным числом случайно сгенерированных Point объектов. Затем он находит Point с наименьшим y. Если несколько объектов Point разделяют самое низкое значение, то используется тот, у которого наименьшее значение x.

Затем он генерирует ArrayList<Double> углов каждого Point относительно конкретного Point, найденного выше. Он быстро сортирует эти углы и соответствующие им Point объекты для создания ArrayList<Point> с отсортированными значениями.

На следующем этапе, как я считаю, моя проблема. Сначала я делаю копию ArrayList<Point> и называю ее edges (обратите внимание, что если бы я не использовал исходный ArrayList<Point> для визуализации, клонирование было бы ненужным) Для любых трех упорядоченных Point объектов в edges мы будем называть A, B, и C, если с AB на BC есть поворот направо, то B следует исключить из корпуса и снять с edges. Я определяю, является ли поворот правым или левым, взяв значение z перекрестного произведения (отрицательное значение z означает, что от AB до BC - поворот направо). Программа удаляет все точки, вызывающие повороты вправо, и продолжает движение.

// 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;
}

В основном я добавил переменную changed для многократного прохождения цикла, просто чтобы убедиться, что что-то было пропущено. Однако ошибка все еще сохраняется. Иногда это работает так, как задумано.

Однако часто бывает по крайней мере несколько неверных Point объектов.

Теперь я замечаю, что до тех пор, пока не произойдет левый поворот, есть несколько Points, которые правильно поворачивают налево, но по-прежнему ошибочны, потому что в конечном итоге они лежат внутри того, что должно быть выпуклой оболочкой. Может быть проблема с возвратом? Я чувствую, что повторяющийся цикл должен уловить эти случаи.