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

我正在使用格雷厄姆扫描算法来找到一组点的凸包我试图按极角对点进行排序但是我不知道怎么做（我已经按照他们的方式对点集进行了排序） Y坐标）。

我已经写过的是这样的：

public double angle(Coord o, Coord a) { return Math.atan((double)(ay - oy) / (double)(ax - ox)); } 

其中Coord是我有X和Y坐标为double 。

我还查看了Stack Overflow中的一个类似post，其中有人试图用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扫描，您只需要查看前两个象限，因此最容易按照cotan排序，因为它在两个象限上都是单调的。

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

Answer 2

如上所述，计算极角本身就是一种非常草率的事情。 您可以定义一个简单的比较器并使用交叉乘积来按极角进行排序。 这是C ++中的代码（我用于我自己的Graham扫描）：

 struct Point { int x, y; } int operator^(Point p1, Point p2) { return p1.x * p2.y - p1.y * p2.x; } bool operator<(Point p1, Point p2) { if(p1.y == 0 && p1.x > 0) return true; //angle of p1 is 0, thus p2 > p1 if(p2.y == 0 && p2.x > 0) return false; //angle of p2 is 0 , thus p1 > p2 if(p1.y > 0 && p2.y < 0) return true; //p1 is between 0 and 180, p2 between 180 and 360 if(p1.y <0 && p2.y > 0) return false; return (p1 ^ p2) > 0; //return true if p1 is clockwise from p2 } 

您可以通过定义Point类在Java中实现相同的function。 基本上我已经重载^运算符以返回交叉产品。 其余的很明显，希望这有帮助！

Answer 3

Math.atan()返回-pi / 2到pi / 2之间的角度。 您必须调整其他两个坐标的结果。

如果你想要从凸包中心的角度，你必须首先平移坐标，以便质心是原点。