Java Graham scan with adapted sorting to deal with collinear points


  • 11
    Y

    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;
            }
        }
    }
    

  • 0
    H

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


  • 0
    Y

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


Log in to reply
 

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