Sorting by Polar Angle

Question

I'm trying to implement the Graham’s Scan algorithm for a convex hull in Java, and have trouble sorting the points by polar angle with respect to the point with lowest y-value.

I have found this answer and understand how to calculate the polar angle but not how to sort the points.

I have seen implementations were Collections.sort() is being used but none of them seem to work with the Point2D class which I want to use because I want to be able to have doubles as coordinates.

Basically I want to be able to sort an ArrayList<Point2D> by their polar angle to the point with the lowest y-value in the same ArrayList.

Could someone please help me with this? Thanks.

Answer 1

Let's assume that initial is the Point2D which has the lowest Y coordinate. Also, let's assume that List<Point2D> points is a list with all the other points available, but it does NOT contain the initial point.

In order to sort the list, we can use Collections.sort with the comparator:

Collections.sort(points, (a, b) -> {
    double cotanA = -(a.getX() - initial.getX()) / (a.getY() - initial.getY());
    double cotanB = -(b.getX() - initial.getX()) / (b.getY() - initial.getY());
    if (cotanA - cotanB < 0) {
        return 1;
    }
    return -1;
});

Edit:

This solution might encounter a division by zero. One way to overcome this is to use a cross product. See this answer from Erfan Alimohammadi.