按极角排序

Question

我正在尝试为 Java 中的凸包实施 Graham’s Scan algorithm，但无法根据相对于 y 值最低的点的极角对点进行排序。

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

我看到正在使用 Collections.sort() 的实现，但其中 none 似乎可以与我想使用的 Point2D class 一起使用，因为我希望能够拥有兼作坐标。

基本上我希望能够根据极角对同一 ArrayList 中具有最低 y 值的点进行排序 ArrayList<Point2D>。

有人可以帮我解决这个问题吗？谢谢。

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:

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

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

当我们的坐标是整数时，它更珍贵。我们在其他解算角度的时候，可能会出现一些浮点数计算的错误。
在其他解决方案中我们可能有"division by zero"，但我们这里没有这个问题。

按极角排序

Sorting by Polar Angle

java

sorting

convex-hull

grahams-scan