Java Solution, Convex Hull Algorithm - Gift wrapping aka Jarvis march


  • 16

    There are couple of ways to solve Convex Hull problem. https://en.wikipedia.org/wiki/Convex_hull_algorithms
    The following code implements Gift wrapping aka Jarvis march algorithm https://en.wikipedia.org/wiki/Gift_wrapping_algorithm and also added logic to handle case of multiple Points in a line because original Jarvis march algorithm assumes no three points are collinear.
    It also uses knowledge in this problem https://leetcode.com/problems/convex-polygon . Disscussion: https://discuss.leetcode.com/topic/70706/beyond-my-knowledge-java-solution-with-in-line-explanation

    public class Solution {
        public List<Point> outerTrees(Point[] points) {
            Set<Point> result = new HashSet<>();
            
            // Find the leftmost point
            Point first = points[0];
            int firstIndex = 0;
            for (int i = 1; i < points.length; i++) {
                if (points[i].x < first.x) {
                    first = points[i];
                    firstIndex = i;
                }
            }
            result.add(first);
            
            Point cur = first;
            int curIndex = firstIndex;
            do {
                Point next = points[0];
                int nextIndex = 0;
                for (int i = 1; i < points.length; i++) {
                    if (i == curIndex) continue;
                    int cross = crossProductLength(cur, points[i], next);
                    if (nextIndex == curIndex || cross > 0 ||
                            // Handle collinear points
                            (cross == 0 && distance(points[i], cur) > distance(next, cur))) {
                        next = points[i];
                        nextIndex = i;
                    }
                }
                // Handle collinear points
                for (int i = 0; i < points.length; i++) {
                    if (i == curIndex) continue;
                    int cross = crossProductLength(cur, points[i], next);
                    if (cross == 0) {
                        result.add(points[i]);
                    }
                }
    
                cur = next;
                curIndex = nextIndex;
                
            } while (curIndex != firstIndex);
            
            return new ArrayList<Point>(result);
        }
        
        private int crossProductLength(Point A, Point B, Point C) {
            // Get the vectors' coordinates.
            int BAx = A.x - B.x;
            int BAy = A.y - B.y;
            int BCx = C.x - B.x;
            int BCy = C.y - B.y;
        
            // Calculate the Z coordinate of the cross product.
            return (BAx * BCy - BAy * BCx);
        }
    
        private int distance(Point p1, Point p2) {
            return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
        }
    }
    

  • 5
    Z

    Hi there! Your solution is good! I had no idea about those algorithms, but I have got Accepted with slow, but simple solution (apparently it is similiar to Gift Wrapping algorithm (non-optimized version)).
    The main idea is also finding convex polygon with minimal perimeter that encompasses all the points.
    Here are some observations before understanding the solution,

    • The top most, bottom most, left most and right most points lie on the border.
    • All the points lie on the same semi-plane according to lines the polygons sides belong to.

    The algorithm below is based only on that observations.
    Well, initially we find any of the top most, bottom most, left most and right most points. In my case I decided to start from top most point.
    Then starting from that point (let's call it start point) we find next point that must lie on the border of our polygon. That can be done according to our second observation. It means, according to the line defined by the current point and the start point, all the other points must lie on the same semi-plane. Consequently repeat that operation starting from the current point until we realize that the current point is already visited. Finally, we have to find the points that lie on the border, but missed in the previous stage. The latter can also be done by iterating through the points and already found points on the border. Overall time complexity of the algorithm is O(hn**2).

    public class Solution {
        public List<Point> outerTrees(Point[] points) {
            List<Point> res=  new ArrayList<>();
            if(points == null || points.length == 0) return res;
            Set<Point> visited  = new HashSet<>();
            //Find top most node
            Point start = points[0];
            for(int i = 1;i<points.length;i++){
                if(points[i].y > start.y || (points[i].y == start.y && points[i].x<start.x)){
                    start = points[i];
                } 
            }
            if(points.length == 1){
                res.add(start);
                return res;
            }
            //Find general convex hull
            Point cur = start;
            while(cur != null && visited.add(cur)){
                res.add(cur);
                for(int i = 0;i<points.length;i++){
                    if(visited.contains(points[i])) continue;
                    if(isBorder(cur, points[i], points)){
                        cur = points[i];
                        break;
                    }
                }
            }
           //Append missing points that lie on the border of polygon
            for(int i = 0;i<points.length;i++){
                if(visited.contains(points[i]) || res.contains(points[i])) continue;
                int size = res.size();
                for(int j = 0;j<size;j++){
                    Point p = res.get(j);
                    if(isBorder(p, points[i], points)) {
                        visited.add(points[i]);
                        res.add(points[i]);
                        break;
                    }
                }
            }
            return res;
        }
        
       // Find whether points lie on the same semi-plane related to the line defined by points p1 and p2
        private boolean isBorder(Point p1, Point p2, Point [] points){
            int dx = p1.x-p2.x;
            int dy = p1.y-p2.y;
            int b = p1.x*dy - p1.y*dx;
            int prev = 0;
            for(int i = 0;i<points.length;i++){
                int x = points[i].x;
                int y = points[i].y;
                int sign = dx*y-dy*x+b;
                if(sign== 0) continue;
                if(sign*prev < 0) return false;
                if(sign <0) prev = -1;
                else prev = 1;
            }
            return true;
        }
    }

  • 0
    J

    The code looks awesome. But I didn't quite understand about the variable cross.
    Can someone explain?
    For int cross = crossProductLength(cur, points[i], next);
    What is the meaning of cross>0 and cross<0?


  • 3
    A

    @jaly50 The cross product of (cur, points[i], next) here tells the direction of the "turn". When you walking from the point from cur to points[i], then walking toward to the next point, it is either left turn or right turn. We also says cur, points[i], next are in clockwise order if they form right turn and in counter-clockwise order if they form left turn.


  • 0
    H

    @shawngao How to ensure that the loop will break, in other words, that cur will finally come to first?
    For example, if we have [0, 0], [0, 1], [1, 0], [0, -1].


  • 0

    @huangw3 Good question. I think you can find the official proof in "33.3: Finding the convex hull". Introduction to Algorithms, according to https://en.wikipedia.org/wiki/Gift_wrapping_algorithm

    The rough idea is, we start from the left-most point L, it must be on the Hull (easy to prove). Also I think we can prove the uniqueness of the Hull line. Thus if we keep walking through those Hull points, we will come back to the left-most point L again.


  • 0
    T

    Thank you! Re-write your method:

    
    /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    public class Solution {
        public List<Point> outerTrees(Point[] points) {
            List<Point> list=new ArrayList<>();
            if(points==null || points.length<1) return list;
            
            int leftmost=0;
            for(int i=1;i<points.length;i++){
                if(points[leftmost].x>points[i].x){
                    leftmost=i;
                }
            }
            
           boolean[] visited=new boolean[points.length];
            
            int current=leftmost;
            int next=0;
            //list.add();
            
            do{
              // visited[current]=true;
               list.add(points[current]);
               visited[current]=true;
               next=(current+1)%points.length;
                
               for(int i=0;i<points.length;i++){
                       int val=crossproduct(points[current],points[next],points[i]);
                       if(val<0){
                           next=i;
                       }else if(val==0&&distance(points[current],points[i])>distance(points[current],points[next])){
                           next=i;
                       }
                   
               }
                
               for(int i=0;i<points.length;i++){
                   if(i!=next&&i!=current&&crossproduct(points[current],points[next],points[i])==0&&visited[i]==false){
                       visited[i]=true;
                       list.add(points[i]);
                   }
               }
                
               current=next; 
            }while(next!=leftmost);
            
                
            return list;     
        }
        
        
        public int distance(Point a,Point b){
            return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
        }
        //cross product of pq \times pi
        public int crossproduct(Point p, Point q,Point i){
            int[] vectorpq=new int[]{q.x-p.x,q.y-p.y};
            int[] vectorpi=new int[]{i.x-p.x,i.y-p.y};
            
            return vectorpq[0]*vectorpi[1]-vectorpq[1]*vectorpi[0];
        }
    }
    
    

  • 0
    A
    This post is deleted!

  • 0
    B

    @shawngao Thanks for the clear solution! One small improvement, we only need to track indices, instead of the actual Points. Here's the C++ version:

    class Solution {
    private:
        vector<Point> points;
        struct comp{
            bool operator() (Point a, Point b) {
                return a.x==b.x ? a.y<b.y : a.x<b.x;
            }
        };
        int cross(int ai,int bi,int ci) {
            int bax=points[bi].x-points[ai].x;
            int bay=points[bi].y-points[ai].y;
            int bcx=points[bi].x-points[ci].x;
            int bcy=points[bi].y-points[ci].y;
            return bax*bcy-bay*bcx;
        }
        int dist(int ai,int bi) {
            int bax=points[bi].x-points[ai].x;
            int bay=points[bi].y-points[ai].y;
            return bax*bax+bay*bay;
        }
    public:
        vector<Point> outerTrees(vector<Point>& points) {
            this->points = points;
            set<Point,comp> pset;
            vector<Point> res;
            
            int n=points.size(), fi=0, ni=-1;
            for (int i=0; i<n; i++) if (points[i].x<points[fi].x) fi=i;
            int ci=fi;
            
            pset.insert(points[fi]);
            
            while (ci!=fi || ni==-1) {
                ni=0;
                for (int i=0; i<n; i++) {
                    if (ci==i) continue;
                    if (ni==i || cross(ci,i,ni)>0 || 
                        (cross(ci,i,ni)==0 & dist(ci,i)>dist(ci,ni))) {
                        ni=i;
                    }
                }
                for (int i=0; i<n; i++) {
                    if (ci==i) continue;
                    if (cross(ci,i,ni)==0) pset.insert(points[i]);
                }
                ci=ni;
            }
            
            for (Point p:pset) res.push_back(p);
            return res;
        }
    };
    

  • 0
    A

    @shawngao thanks for this! there is a good video explanation of the algorithm here

    Hope it helps someone.


  • 0
    C

    Hi I do not understand what is Z coordinate of the cross product used for, could you please tell me more ?
    Thank you!


Log in to reply
 

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