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.

Disendow

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.

Squaw

If a point shares an X value of the initial point, you'll get a divide by zero error – Fabre

@Fabre - Y is in the denominator. Did you mean a shared Y value? Fix might be Math.max(a.getY() - initial.getY(), 1) – Defensible

Answer 2

I modified the last answer to this question.

Define a new class for Point:

class Point {
    private long x, y;
    Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
    Point() {
        x = 0;
        y = 0;
    }
    public long getX() {
        return x;
    }
    public long getY() {
        return y;
    }
}

Define a new function for calculating the cross product of two vectors:

public long cross(long x1, long y1, long x2, long y2) {
    return x1 * y2 - x2 * y1;
}

Let's assume that initial is the Point which has the lowest Y coordinate. Also, let's assume that List<Point> 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) -> {
    long cr = cross(a.getX() - initial.getX(), a.getY() - initial.getY(), b.getX() - initial.getX(), b.getY() - initial.getY());
    if (cr > 0)
        return 1;
    else
        return -1;
});

In this solution, we used the cross product to check whether two vectors are positioned clockwise or counter-clockwise. This solution has two benefits:

1. It's more precious when our coordinates are integer numbers. When we calculate angles in other solutions, we may have some errors in floating point calculations.
2. In other solutions we may have "division by zero", but we don't have this problem here.

Haphazard

what if they are collinear? – Diffuser

@GarvitKhamesra In my method, collinear points don't have priority to each other. So, we didn't set their final ordering. If this matters to you, you can edit the last code to handle the cr == 0 case in the "if". You may compare their distance to the initial point or whatever you consider. It's up to you. – Haphazard

Yup, that should handle the case. – Diffuser