Sorting points by their polar angle in Java

Question

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

where Coord is the class where I have X and Y coordinates as 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?

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.

Answer 1

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.

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.