按极角排序

Question

我正在尝试实现Graham\xe2\x80\x99s 扫描算法，并且无法按相对于 y 值最低的点的极角对点进行排序。

\n\n

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

\n\n

我见过的实现是Collections.sort()使用的实现，但它们似乎都不适用于我想要使用的 Point2D 类，因为我希望能够将双精度作为坐标。

\n\n

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

\n\n

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

\n

Answer 1

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

定义一个新类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. 在其他解决方案中，我们可能有“除以零”，但我们这里没有这个问题。

Answer 2

我们假设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;
});

编辑：

此解决方案可能会遇到被零除的情况。克服这个问题的一种方法是使用叉积。请参阅Erfan Alimohammadi 的回答。