C++ and Python easy wiki solution


  • 6

    C++ version:

    // Ref: http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull.cpp
    class Solution {
     public:
      typedef int coord_t;  // coordinate type
      typedef long long coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2
      // 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross
      // product. Returns a positive value, if OAB makes a counter-clockwise turn,
      // negative for clockwise turn, and zero if the points are collinear.
      coord2_t cross(const Point &O, const Point &A, const Point &B) {
        return (A.x - O.x) * (coord2_t)(B.y - O.y) -
               (A.y - O.y) * (coord2_t)(B.x - O.x);
      }
    
      static bool cmp(Point &p1, Point &p2) {
        return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
      }
    
      static bool equ(Point &p1, Point &p2) { return p1.x == p2.x && p1.y == p2.y; }
      // Returns a list of points on the convex hull in counter-clockwise order.
      // Note: the last point in the returned list is the same as the first one.
      vector<Point> outerTrees(vector<Point> &P) {
        int n = P.size(), k = 0;
        vector<Point> H(2 * n);
    
        // Sort points lexicographically
        sort(P.begin(), P.end(), cmp);
    
        // Build lower hull
        for (int i = 0; i < n; i++) {
          while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
          H[k++] = P[i];
        }
    
        // Build upper hull
        for (int i = n - 2, t = k + 1; i >= 0; i--) {
          while (k >= t && cross(H[k - 2], H[k - 1], P[i]) < 0) k--;
          H[k++] = P[i];
        }
    
        // Remove duplicates
        H.resize(k);
        sort(H.begin(), H.end(), cmp);
        H.erase(unique(H.begin(), H.end(), equ), H.end());
        return H;
      }
    };
    

    Python version:

    # http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull.py
    
    
    class Solution(object):
    
        def outerTrees(self, points):
            """Computes the convex hull of a set of 2D points.
    
            Input: an iterable sequence of (x, y) pairs representing the points.
            Output: a list of vertices of the convex hull in counter-clockwise order,
              starting from the vertex with the lexicographically smallest coordinates.
            Implements Andrew's monotone chain algorithm. O(n log n) complexity.
            """
    
            # Sort the points lexicographically (tuples are compared lexicographically).
            # Remove duplicates to detect the case we have just one unique point.
            # points = sorted(set(points))
            points = sorted(points, key=lambda p: (p.x, p.y))
    
            # Boring case: no points or a single point, possibly repeated multiple times.
            if len(points) <= 1:
                return points
    
            # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
            # Returns a positive value, if OAB makes a counter-clockwise turn,
            # negative for clockwise turn, and zero if the points are collinear.
            def cross(o, a, b):
                # return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
                return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
    
            # Build lower hull
            lower = []
            for p in points:
                while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
                    lower.pop()
                lower.append(p)
    
            # Build upper hull
            upper = []
            for p in reversed(points):
                while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
                    upper.pop()
                upper.append(p)
    
            # Concatenation of the lower and upper hulls gives the convex hull.
            # Last point of each list is omitted because it is repeated at the
            # beginning of the other list.
            # return lower[:-1] + upper[:-1]
            return list(set(lower[:-1] + upper[:-1]))
    

  • 0
    L

    This solution looks more concise, I do not know why it did not get any votes or comments.


  • 0
    Z

    Great solution using Monotone Chain! Time complexity O(nlogn). I prefer this method to Jarvis Algorithm, which is O(n^2), and Graham scan, which is more difficult to prove and to implement. Thanks!

    Here is my C++ code with a little bit optimization. After lower hull, you can check whether answer.size() == n for the single line case/duplicates.

    class Solution {
    public:
        vector<Point> outerTrees(vector<Point>& points) {
            // Andrew's monotone chain method
            int n = points.size();
            vector<Point> ans;
            sort(points.begin(), points.end(), mycompare);
            // left to right
            for (int i = 0; i < n; ++i) {
                while (ans.size() > 1 && orientation(ans[ans.size()-2], ans.back(), points[i]) < 0) 
                    ans.pop_back();
                ans.push_back(points[i]);
            }
            // if all points along a line, ans.size() is n after left to right procedure
            if (ans.size() == n) return ans;
            // right to left
            for (int i = n-2; i >= 0; --i) {
                while (ans.size() > 1 && orientation(ans[ans.size()-2], ans.back(), points[i]) < 0) 
                    ans.pop_back();
                ans.push_back(points[i]);
            }
            ans.pop_back();
            return ans;
        }
    private:
        static bool mycompare(Point& a, Point& b) {
            return a.x < b.x || (a.x == b.x && a.y < b.y);
        }
        int orientation(Point& a, Point& b, Point& c) {
            return (b.x-a.x)*(c.y-b.y) - (b.y-a.y)*(c.x-b.x);
        }
    };
    

  • 0
    L

    @zestypanda wow, impressive, your solution is even more self-explained.


Log in to reply
 

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