Java solution by checking cross product sign


  • 0
    D

    The key point is to understand that the angle between two vectors have directions. This direction can be achieved by cross product because cross product gives us about sine(theta) instead of cosine(theta). We don't need to really calculate the cross product. Only the sign (positive or negative) is enough. Some corner cases should also be handled, e.g., some points are in one line.

    public class Solution {
        public boolean isConvex(List<List<Integer>> points) {
            assert points != null;
            List<List<Integer>> newpoints = new ArrayList<>();
            for (List<Integer> point : points) {
                if (newpoints.size() == 0) {
                    newpoints.add(point);
                } else {
                    List<Integer> lastpoint = newpoints.get(newpoints.size() - 1);
                    if (lastpoint.get(0) != point.get(0) || lastpoint.get(1) != point.get(1)) {
                        newpoints.add(point);
                    }
                }
            }
            points = newpoints;
            if (points.size() < 3) {
                return false;
            }
            SIGN firstnonzero = SIGN.NOTINIT;
            for (int i = 0, n = points.size(); i < n; i++) {
                SIGN current = crossproductsign(points.get(i), points.get((i + 1) % n), points.get((i + 2) % n));
                switch (current) {
                    case POSITIVE:
                    case NEGATIVE:
                        if (firstnonzero == SIGN.NOTINIT) {
                            firstnonzero = current;
                        } else if (firstnonzero != current) {
                            return false;
                        }
                        break;
                    case ZEROGOOD:
                        break;
                    case ZEROBAD:
                        return false;
                    case NOTINIT:
                    default:
                        assert false;
                }
            }
            return firstnonzero == SIGN.NOTINIT ? false : true;
        }
    
        private SIGN crossproductsign(List<Integer> p1, List<Integer> p2, List<Integer> p3) {
            int vec1x = p2.get(0) - p1.get(0);
            int vec1y = p2.get(1) - p1.get(1);
            int vec2x = p3.get(0) - p2.get(0);
            int vec2y = p3.get(1) - p2.get(1);
            int numerator = vec1y * vec2x - vec1x * vec2y;
            if (numerator != 0) {
                return numerator > 0 ? SIGN.POSITIVE : SIGN.NEGATIVE;
            } else {
                if (vec1x == 0) {
                    return vec1y * vec2y > 0 ? SIGN.ZEROGOOD : SIGN.ZEROBAD;
                } else {
                    return vec1x * vec2x > 0 ? SIGN.ZEROGOOD : SIGN.ZEROBAD;
                }
            }
        }
    
        private enum SIGN {
            NOTINIT, POSITIVE, NEGATIVE, ZEROGOOD, ZEROBAD
        }
    }
    

Log in to reply
 

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