Sorting points by their polar angle in Java

问题:

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.

回答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.

回答2:

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

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 Point class. Basically I have overloaded the ^ operator to return the cross product. The rest is evident, hope this helps!

回答3:

Math.atan() returns an angle between -pi/2 to pi/2. You'll have to adjust the results for the other two coordinates.

If you want the angle from the center of the convex hull, you'll have to first translate the coordinates so that the centroid is the origin.