[Not using cross product] Easy understanding solution with explanation.


  • 0

    I didn't know about the cross product as the same as some of you.
    The program is a bit lengthy, but the idea is simple.
    Lots of lines the code is just the flip side the other logic.
    We can shorten the code significantly by joining some logic , but I think it's more clear to discuss each case separately.

    /*
        Observation:
        
        1. Every 3 points can either form a line or a triangle, but never a concave polygon
        2. Clockwise or counter-clockwise matters. 
           In the question's example, [[0,0],[0,10],[10,10],[10,0],[5,5]], 
           these 3 consecutive points break the convex rule, [10,0], [5,5], [0,0] 
           They break the convex rule because the points given are in clockwise. 
           If these 3 points were in a counter-clockwise sequence, such as in [10,0],[5,5],[0,0],[0,-5],[10,-5], 
           it is indeed a valid convex a polygon. 
        
        Alogrithm:
            1. We pick any 3 consecutive given points, find whether we should go clockwise or counter-clockwise
                with these 3 points to make them part of a convex polygon.
            2. Then use the conclusion from step 1(clock or counter-clock) to check all other 3 consecutive points.
               If all 3 points group can form a convex using the same order, return true, otherwise return false
    */
    
    
    public class Solution {
        public boolean isConvex(List<List<Integer>> points) {
            if(points == null || points.size() < 3) return false;
            /*Determine whehther we should try to go in clock or conter-clock wise*/
            boolean clock = checkPoints(points.get(points.size() - 2), points.get(points.size() - 1), points.get(0), true);
            
            /*check the sequence form by last poitns in the last and first 2 points in the list*/
            if(!checkPoints(points.get(points.size() - 1), points.get(0), points.get(1), clock)) return false;
            
            /*check the rest of points*/
            for(int i = 2; i < points.size(); i++){
                if(!checkPoints(points.get(i-2), points.get(i-1), points.get(i), clock)) return false;
            }
            return true;
        }
        
        /*checks whether the 3 given points can form a convex shape based on given order(clock or counter-clock)*/
        public boolean checkPoints(List<Integer> p1, List<Integer> p2, List<Integer> p3, boolean clk){
            /*if first 2 points has the same x value*/
            if(p2.get(0) - p1.get(0) == 0){
                /*p2's y is greater than p1's y, meaning we are going uphill*/
                if(p2.get(1) > p1.get(1)){
                    /*if going clockwise, p3 should be on the right of p1 and p2,
                      if going counter-clockwise, p3 should be on the left of p1 and p2 */
                    if((clk && p3.get(0) >= p2.get(0)) || (!clk && p3.get(0) <= p2.get(0))) {
                        return true;
                    }else{
                        return false;
                    }
                    /*flip side*/
                }else{
                    if((clk && p3.get(0) <= p2.get(0)) || (!clk && p3.get(0) >=  p2.get(0))){
                        return true;
                    }else{
                        return false;
                    }
                }
            }
            /*if the first 2 points has the same y value, similar logic as above*/
            if(p2.get(1) - p1.get(1) == 0){
                if(p2.get(0) > p1.get(0)){
                    if( (clk &&p3.get(1) <= p2.get(1)) || (!clk && p3.get(1) >= p2.get(1))) {
                        return true;
                    }else{
                        return false;
                    }
                }else{
                    if( (clk && p3.get(1) >= p2.get(1)) || (!clk && p3.get(1) <= p2.get(1))){
                        return true;
                    }else{
                        return false;
                    }
                }
            }        
            
            /*p1 and p2's x and y value are different, calulate the line formular formed by p1 and p2 
                y = m * x + n*/
            double m = ((double)(p2.get(1) - p1.get(1))) / (p2.get(0) - p1.get(0));
            double n = (p1.get(0) == 0 && p1.get(1) == 0) ?p2.get(1) - m * p2.get(0) : p1.get(1) - m * p1.get(0);
            /*If going clockwise*/
            if(clk){
                /*if p3 is on the right side of p1, no matter whether the slope is positive or negative,
                  plug in p3's x value to the line formula, p3's y value should be smaller than that*/
                if(p2.get(0) > p1.get(0)) {
                    return ( (m * p3.get(0) + n) >= p3.get(1));
                }else{
                    return ( (m * p3.get(0) + n) <= p3.get(1));
                }
            /*flip of the logic*/    
            }else{
                if(p2.get(0) > p1.get(0)) {
                    return ( (m * p3.get(0) + n) <= p3.get(1));
                }else{
                    return ( (m * p3.get(0) + n) >= p3.get(1));            
                }
            }
        }
    }

Log in to reply
 

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