# Java Graham scan with adapted sorting to deal with collinear points

• The trick is that once all points are sorted by polar angle with respect to the reference point:

• For collinear points in the begin positions, make sure they are sorted by distance to reference point in ascending order.
• For collinear points in the end positions, make sure they are sorted by distance to reference point in descending order.

For example:
`(0, 0), (2, 0), (3, 0), (3, 1), (3, 2), (2, 2), (1, 2), (0, 2), (0, 1)`
These points are sorted by polar angle
The reference point (bottom left point) is `(0, 0)`

• In the begin positions `(0, 0)` collinear with `(2, 0), (3, 0)` sorted by distance to reference point in ascending order.
• In the end positions `(0, 0)` collinear with `(0, 2), (0, 1)` sorted by distance to reference point in descending order.

Now we can run the standard Graham scan to give us the desired result.

``````public class Solution {

public List<Point> outerTrees(Point[] points) {
if (points.length <= 1)
return Arrays.asList(points);
sortByPolar(points, bottomLeft(points));
Stack<Point> stack = new Stack<>();
stack.push(points[0]);
stack.push(points[1]);
for (int i = 2; i < points.length; i++) {
Point top = stack.pop();
while (ccw(stack.peek(), top, points[i]) < 0)
top = stack.pop();
stack.push(top);
stack.push(points[i]);
}
return new ArrayList<>(stack);
}

private static Point bottomLeft(Point[] points) {
Point bottomLeft = points[0];
for (Point p : points)
if (p.y < bottomLeft.y || p.y == bottomLeft.y && p.x < bottomLeft.x)
bottomLeft = p;
return bottomLeft;
}

/**
* @return positive if counter-clockwise, negative if clockwise, 0 if collinear
*/
private static int ccw(Point a, Point b, Point c) {
return a.x * b.y - a.y * b.x + b.x * c.y - b.y * c.x + c.x * a.y - c.y * a.x;
}

/**
* @return distance square of |p - q|
*/
private static int dist(Point p, Point q) {
return (p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y);
}

private static void sortByPolar(Point[] points, Point r) {
Arrays.sort(points, (p, q) -> {
int compPolar = ccw(p, r, q);
int compDist = dist(p, r) - dist(q, r);
return compPolar == 0 ? compDist : compPolar;
});
// find collinear points in the end positions
Point p = points[0], q = points[points.length - 1];
int i = points.length - 2;
while (i >= 0 && ccw(p, q, points[i]) == 0)
i--;
// reverse sort order of collinear points in the end positions
for (int l = i + 1, h = points.length - 1; l < h; l++, h--) {
Point tmp = points[l];
points[l] = points[h];
points[h] = tmp;
}
}
}
``````

• @yuxiangmusic Can you please explain why you sort by "compPolar"? Honestly I don't quite understand that sort. I used cos as a measure for sorting.

• @HongkunGe
When `ccw(p, r, q) < 0` that means `p-r-q` makes a clockwise turn hence `q` has greater polar angle.
When `ccw(p, r, q) > 0` that means `p-r-q` makes a counter-clockwise turn hence `p` has greater polar angle.

Wikipedia has some detailed explanation for Graham scan in general.

• Thank you for sharing the great solution. But I think it would nice to point out two things:

1. the descending order is not just for the collinear points in the end positions, but any collinear points at the largest angle should be sorted in descending order.

2. Because of (1), we can reverse the points the way implemented in this solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.