通过在Java中的极角排序分(Sorting points by their polar angle

我使用的是格雷厄姆扫描算法来找出设定点我想通过自己的极角的积分排序的凸包，但我不知道如何做到这一点（我已经排序的点的集合他们的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 。

我也看了在堆栈溢出类似的帖子，其中有人曾试图实现与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:

你并不需要计算的极角通过它来进行排序。由于三角函数是单调的函数本身，如你的情况棕褐色（一直增大或减小总是）一个象限内，只是排序。如果您正在实施的格雷厄姆与最底层的点开始扫描，你只需要看看第一个两个象限，所以它会是最容易被科坦进行排序，因为它是在两个象限单调。

换句话说，你可以通过排序- (x - x1) / (y - y1)其中（X1，Y1）是你的起点坐标），这将是更快的计算。首先，您需要单独在那里点y == y1 ，当然，并将它们添加到顶部或取决于符号列表的底部（X - X1）'，但它们很容易识别，因为你“VE已经由Y排序，以找到你的出发点。

Answer 2:

如上所述，计算极角本身就是处理事情相当草率的方式。您可以定义一个简单的比较，并利用跨产品的极角排序。这是在C ++（我用我自己的格雷厄姆扫描）的代码：

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
}

您可以实现同样的事情在Java中，通过定义一个Point类。基本上我有重载^运算符返回叉积。其余的是明显的，希望这有助于！