One Pass C++ Solution (with detailed explanations and references)


  • 0
    W

    First, let's see the description of this problem, "the given a list of points can form a polygon when joined sequentially", which means the points are already in an order so that when we traverse the list, we traverse along the perimeter of the polygon in one direction.

    Before I introduce my idea, we must be aware some geometry knowledge, i.e., orientation. With the concept of orientation in mind, we know if a polygon is convex, each three-point triplet must follow the same orientation, e.g., either clockwise or counter-clockwise (you may try to draw a polygon in counter-clockwise direction).

    In other words, if the orientation of the polygon switches at some point, we know it must not be convex. Therefore, my ideas is simple: traverse the list and calculate the orientation for each three-point triplet, if the orientation is changed, return false, otherwise, it is convex.

    class Solution {
    public:
        bool isConvex(vector<vector<int>>& points) {
            int preDir = -2, curDir, n = points.size(); // preDir: orientation of previous triplet; curDir: orientation of current triplet.
            vector<int> pre, cur, next; // Three points can determine an orientation.
            for(int i = 0; i < n; i++) {
                pre = points[(i-1+n)%n];
                cur = points[i];
                next = points[(i+1)%n];
                curDir = orientation(pre, cur, next);
                // If orientation is changed, the polygon is not convex. When current orientation is 0, we cannot make a decision, because three points are at one line.
                if(preDir != -2 && curDir != 0 && curDir != preDir) return false; 
                if(curDir != 0) preDir = curDir; // When current orientation is 0, we don't need to record it.
            }
            return true;
        }
        
    private:
        int orientation(vector<int>& p1, vector<int>& p2, vector<int>& p3) {
            int ori = (p2[1]-p1[1]) * (p3[0]-p2[0]) - (p3[1]-p2[1]) * (p2[0]-p1[0]);
            if(ori == 0) return 0;
            else return ori < 0 ? -1 : 1;
        }
    };
    

    Here are some useful links (I believe the designer of this problem was trying to make things simpler)
    http://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/
    http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/


Log in to reply
 

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