在Java中按极角对点进行排序

Question

我正在使用Graham扫描算法来查找点集的凸包，我试图按其极角对点进行排序，但我不知道如何做到这一点（我已经按点对点集进行了排序Y坐标）。

我已经写的是这样的：

public double angle(Coord o, Coord a)
{
    return Math.atan((double)(a.y - o.y) / (double)(a.x - o.x));
}

这里Coord是我有X和Y坐标作为类double。

我还查看了Stack Overflow中的类似文章之一，有人尝试使用C ++实现这种角度，但我不理解qsqrt。我们在Java中有类似的东西吗？

qreal Interpolation::dp(QPointF pt1, QPointF pt2)
{
    return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y()));
}

如果有人可以帮助我，我会很高兴。

Answer 1

您无需计算极角即可对其进行排序。由于触发函数在一个象限内是单调的（总是增加或总是减小），因此只需按函数本身进行排序即可，例如，您所用的棕褐色。如果您要从最底端开始进行Graham扫描，则只需查看前两个象限，因此按tan曲进行排序最容易，因为它在两个象限中都是单调的。

换句话说，您可以按- (x - x1) / (y - y1)（其中（x1，y1）是起点的坐标）进行排序，这样可以更快地进行计算。首先，您需要分隔点y == y1，当然，然后根据（x-x1）`的符号将它们添加到列表的顶部或底部，但是由于您已经对它们进行了排序，因此它们很容易识别按y查找您的起点。