java 在Java中按极角对点进行排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16509100/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting points by their polar angle in Java
提问by Navid Koochooloo
I'm using Graham scan algorithm to find the convex-hull of set of points I'm trying to sort the points by their polar angle but I have no idea how to do it (I've already sorted the set of points by their Y coordinates).
我正在使用 Graham 扫描算法来找到一组点的凸包Y 坐标）。
What I've already wrote is like this:
我已经写的是这样的：
public double angle(Coord o, Coord a)
{
return Math.atan((double)(a.y - o.y) / (double)(a.x - o.x));
}
where Coordis the class where I have X and Y coordinates as double.
这里Coord是我有X和Y坐标作为类double。
I also looked at one of the similar posts in Stack Overflow where someone had tried to implement this angle with C++, but I don't understand qsqrt. Do we have something like this in Java?
我还查看了 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()));
}
I'll be glad if anyone can help me.
如果有人能帮助我，我会很高兴。
回答by maybeWeCouldStealAVan
You don't need to calculate the polar angle to sort by it. Since trig functions are monotonic (always increasing or always decreasing) within a quadrant, just sort by the function itself, e.g. the tan in your case. If you're implementing the Graham scan by starting with the bottom-most point, you only need to look at the first two quadrants, so it'd be easiest to sort by cotan, since it's monotonic over both quadrants.
您无需计算极角即可对其进行排序。由于三角函数在象限内是单调的（总是增加或总是减少），只需按函数本身排序，例如在您的情况下为棕褐色。如果您从最底部开始实施 Graham 扫描，则只需查看前两个象限，因此最容易按 cotan 排序，因为它在两个象限上都是单调的。
In other words, you can just sort by - (x - x1) / (y - y1)(where (x1, y1) are the coordinates of your starting point), which will be faster to calculate. First you'll need to separate points where y == y1, of course, and add them to the top or bottom of the list depending on the sign of (x - x1)`, but they're easy to identify, since you've already sorted by y to find your starting point.
换句话说，您可以按- (x - x1) / (y - y1)（其中 (x1, y1) 是起点的坐标）进行排序，这样计算起来会更快。首先，您需要将其中的点分开y == y1，当然，然后根据 (x - x1)` 的符号将它们添加到列表的顶部或底部，但它们很容易识别，因为您已经进行了排序按 y 找到您的起点。
回答by akshat
As mentioned above, calculating the polar angle itself is a pretty sloppy way of going about things. You can define a simple comparator and use cross products to sort by polar angle. Here is code in C++ (which I use for my own Graham scan):
如上所述，计算极角本身是一种非常草率的处理方式。您可以定义一个简单的比较器并使用叉积按极角排序。这是 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
}
You can implement the same thing in Java, by defining a Pointclass. Basically I have overloaded the ^operator to return the cross product. The rest is evident, hope this helps!
通过定义一个Point类，您可以在 Java 中实现相同的功能。基本上我已经重载了^操作符来返回叉积。其余的很明显，希望这会有所帮助！
回答by Andy Thomas
Math.atan()returns an angle between -pi/2 to pi/2. You'll have to adjust the results for the other two coordinates.
Math.atan()返回 -pi/2 到 pi/2 之间的角度。您必须调整其他两个坐标的结果。
If you want the angle from the center of the convex hull, you'll have to first translate the coordinates so that the centroidis the origin.
如果您想要与凸包中心的角度，则必须首先平移坐标，使质心成为原点。
