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.

Chlorine

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.

Caudad

and what should I use in java to find the formula for the cotan? just replace my code by: public double angle(Coord o, Coord a) { return 1.0/Math.tan((double)(a.y - o.y) / (double)(a.x - o.x)); } – Chlorine

for the point to start, every where it's written different thing. does it matter where to start ? – Chlorine

(x - x1) / (y - y1) is the formula for cotan (1/tan) -- adjacent over opposite. I only made in negative so that it increases with the angle. I hadn't heard of a Graham scan, so I based my response on the Wikipedia article, which suggests starting with the bottom-most point. The idea wouldn't change if you started with, say, the left-most point. In that case it'd be easiest to use the tangent: (y - y1) / (x - x1) – Caudad

necessary to have the negative sign? cause I used your formula but without the negative sign – Chlorine

It just switches the sort order. Conventional angles increase in the counterclockwise direction, but the cotangent increases in the clockwise direction. – Caudad

so you mean like this? public double angle(Coord base, Coord p) { return -1.0/Math.tan((double)(p.y - base.y) / (double)(p.x - base.x)); } sorry I ask a lot but I want to get sure :) – Chlorine

No, I mean you don't have to use the tan or atan functions at all. You already have the components for the tangent or cotangent (y/x or x/y). You could, as you have been, pass the tangent to the atan function to get the angle (after adjusting for the sign of x if necessary). But, since a bigger tangent means a bigger angle, or a smaller cotangent means a bigger angle, if you sort by the tangent or cotangent then you're also sorting by angle, without having to calculate it. – Caudad

Answer 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!

Crippling

Don't you need to normalize the cross product some how because cross-products have a magnitude if you are going to sort? i.e. lets say you have origin po(-1,-4) then you have one point at p1(-1,4) and another point at p2(-2,-3). Graphically p2 has larger polar angle. The "cross product" (in quotes since cross products are only done on vectors not on points) of origin and first point is (-1*4 - -1*-4) = -8 but the cross product of origin and second point (because the distance is smaller) is (-1*3 - -2*-4) = -5 which isn't more negative and is sorted incorrectly. Dividing by distance works. – Linnealinnean

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

Orit