java - 按极角排序

Question

我正在尝试为 Java 中的凸包实现Graham 扫描算法，并且无法通过相对于 y 值最低的点按极角对点进行排序。

我找到了这个答案并了解如何计算极角，但不了解如何对点进行排序。

我已经看到Collections.sort()正在使用实现，但它们似乎都不能与我想使用的 Point2D 类一起使用，因为我希望能够将双打作为坐标。

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

有人可以帮我吗？谢谢。

Answer 1

让我们假设initial它Point2D具有最低的 Y 坐标。另外，让我们假设这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;
});

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它Point具有最低的 Y 坐标。另外，让我们假设这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. 在其他解决方案中，我们可能有“除以零”，但我们这里没有这个问题。