按极角分选

Question

我试图在Java中为凸包实现格雷厄姆扫描算法，并且很难根据极角对y值最低的点进行排序。

我找到了这的答案，知道如何计算极角，但不知道如何排序点。

我已经看到了Collections.sort()正在被使用的实现，但是它们似乎没有一个能与我想要使用的Point2D类一起工作，因为我希望能够以双数作为坐标。

基本上，我希望能够对一个ArrayList<Point2D>进行排序，根据它们的极角到在同一ArrayList中y值最低的点。

有人能帮我吗？谢谢。

Answer 1

假设initial是具有最低Y坐标的Point2D。另外，让我们假设List<Point2D> points是一个包含所有其他可用点的列表，但它不包含initial点。

为了对列表进行排序，我们可以在比较器中使用Collections.sort：

Collections.sort(points, (a, b) -> {
    double cotanA = -(a.getX() - initial.getX()) / (a.getY() - initial.getY());
    double cotanB = -(b.getX() - initial.getX()) / (b.getY() - initial.getY());
    if (cotanA - cotanB < 0) {
        return 1;
    }
    return -1;
});

编辑：

这个解决方案可能会被除以零。克服这一问题的一种方法是使用交叉积。见Erfan Alimohammadi的这个答案。

Answer 2

我修改了这个问题的最后一个答案。

为Point定义一个新类

class Point {
    private long x, y;
    Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
    Point() {
        x = 0;
        y = 0;
    }
    public long getX() {
        return x;
    }
    public long getY() {
        return y;
    }
}

定义一个计算两个向量的交叉积的新函数：

public long cross(long x1, long y1, long x2, long y2) {
    return x1 * y2 - x2 * y1;
}

假设initial是具有最低Y坐标的Point。另外，让我们假设List<Point> points是一个包含所有其他可用点的列表，但它不包含initial点。

为了对列表进行排序，我们可以在比较器中使用Collections.sort：

Collections.sort(points, (a, b) -> {
    long cr = cross(a.getX() - initial.getX(), a.getY() - initial.getY(), b.getX() - initial.getX(), b.getY() - initial.getY());
    if (cr > 0)
        return 1;
    else
        return -1;
});

在这个解中，我们使用交叉积来检查两个向量是顺时针方向还是逆时针方向。这种解决方案有两个好处：

1. 当我们的坐标是整数时，就更珍贵了。当我们在其他解中计算角度时，在浮点计算中可能会有一些误差。
2. 在其他解决方案中，我们可能有“除以零”，但这里没有这个问题。