Sort points by their polar angle in Java

Question

I use Graham's scanning algorithm to find the convex hull of many points. I try to sort the points by their polar angle, but I have no idea how to do this (I already sorted the many points by their Y coordinates).

What I have already written is as follows:

public double angle(Coord o, Coord a) { return Math.atan((double)(ay - oy) / (double)(ax - ox)); } 

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

I also looked at one of these entries in Stack Overflow, where someone was trying to implement this angle with C ++, but I don't understand qsqrt . Do we have something similar 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 would be glad if someone can help me.

Answer 1

You do not need to calculate the polar angle to sort by it. Since the trigger functions are monotonous (always increasing or always decreasing) inside the quadrant, just sort by the function itself, for example. tan in your case. If you are performing a Graham scan from the lowest point, you only need to look at the first two quadrants, so it’s easiest to sort by kotan, as it is monotonous for both quadrants.

In other words, you can simply sort by - (x - x1) / (y - y1) (where (x1, y1) are the coordinates of your starting point), which will be faster to calculate. First you need to separate the points where y == y1 , and add them to the top or bottom of the list depending on the sign (x - x1) `, but they are easy to identify, you are already sorted by y to find your starting point.

Answer 2

As mentioned above, calculating the polar angle itself is a pretty messy way to go about things. You can define a simple comparator and use cross-products to sort by polar angle. Here is the code in C ++ (which I use for Graham's own 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 the Point class. Basically, I overloaded the ^ operator to return the cross product. The rest is obvious, hope this helps!

Answer 3

Math.atan() returns the angle between -pi / 2 and pi / 2. You will need to adjust the results for the other two coordinates.

If you need an angle from the center of the convex hull, you need to first translate the coordinates so that centroid is the source.