问题描述
我正在使用格雷厄姆扫描算法来找到点集的凸壳
我正试图按极角对点进行排序但我不知道该怎么做(我已经按照Y坐标对点集进行排序。)
I'm using Graham scan algorithm to find the convex-hull of set of pointsI'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中按极角对点进行排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!