尽管遵循格雷厄姆扫描，但在凸包上产生了错误点

Question

在编写这个小凸包可视化器时，我基本上遵循了 wikipedia entry for Graham scan 的每一步。它通常按预期工作，但在更大的输入大小下通常会出现错误点。

程序首先用给定数量的随机生成的 Point 对象填充 ArrayList<Point>。然后它会找到 Point 具有最低 y 的 Point。如果多个 Point 对象共享最低值，则使用具有最低 x 的那个。

接下来，它生成每个 Point 相对于上面找到的特定 Point 的角度的 ArrayList<Double>。它对这些角度及其对应的 Point 对象进行快速排序，以生成具有排序值的 ArrayList<Point>。

下一步是我认为我的问题所在。首先，我复制了 ArrayList<Point> 并将其命名为 edges（请注意，如果我没有使用原始 ArrayList<Point> 进行可视化，则不需要克隆）对于任何三个有序的 [= edges 中的 12=] 个对象我们将调用 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 正确左转，但仍然是错误的，因为它们最终位于应该是凸包的内部。这可能是回溯的问题吗？我觉得重复循环应该能捕捉到这些情况。

Answer 1

下面是点排序后构建凸包的正确方法：

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

java

algorithm

convex-hull

grahams-scan