3

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

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。AB我通过取叉积的 z 值来确定转弯是右转还是左转（负 z 表示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正确地左转，但仍然是错误的，因为它们最终位于应该是凸包的内部。这可能是回溯的问题吗？我觉得重复循环应该可以捕捉到这些情况。

4

1 回答 1

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
于 2015-05-20T08:46:11.540 回答