在Java中按极角对点进行排序 [英] Sorting points by their polar angle in Java

问题描述

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

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).

我已经写过的内容是这样的：

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));
}

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

where Coord is the class where I have X and Y coordinates as double.

我还查看了其中一篇类似的帖子Stack Overflow有人试图用C ++实现这个角度，但我不明白 qsqrt 。我们在Java中有这样的东西吗？

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?

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.

推荐答案

您无需计算极角来进行排序。由于三角函数在象限内是单调的（总是递增或总是递减），所以只需按函数本身排序，例如，在你的情况下棕褐色。如果你从最下面的点开始实现Graham扫描，你只需要查看前两个象限，因此最容易按照cotan进行排序，因为它在两个象限上都是单调的。

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.

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

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.

这篇关于在Java中按极角对点进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！