c++ Graham Scan/Monotone Chain dealing with collinear cases


  • 3
    A

    I implemented two different approach: 1.Graham Scan; 2. Andrew's monotone chain.

    For the Graham Scan, here is the modified implementation discussed in the following link:
    http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
    The modified part is to deal with the degenerate case. As the original algorithm outputs the extreme points instead of vertices (the difference is that a vertex can lie in between two extreme points), I added the logic for output all the vertices.
    There are two parts:

    1. During the Graham scan after the radial sorting, we don't pop the points if p[i], top, next_to_top are collinear;
    2. A special case is that in the largest radial angle, there may be several points lies on a line, we need to reverse the order of these points. In the initial radial sorting, a tie is broke by closer one comes first. But for the points in the largest radial angle, the closer one comes last.
    class Solution {
    public:
        // A utility function to return square of distance
        // between p1 and p2
        static int distSq(Point p1, Point p2) {
            return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
        }
     
        // To find orientation of ordered triplet (p, q, r).
        // The function returns following values
        // 0 --> p, q and r are colinear
        // 1 --> Clockwise
        // 2 --> Counterclockwise
        static int orientation(Point p, Point q, Point r) {
            int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
            if (val == 0) {
                return 0;  // colinear
            }
            return (val > 0) ? 1 : 2; // clock or counterclock wise
        }
    
        // A comparison function object using specified reference point
        struct pointsComparator {
            Point p0;
            bool operator() (const Point& p1, const Point& p2) {
     
                // Find orientation
                int o = orientation(p0, p1, p2);
                if (o == 0) {
                    return distSq(p0, p2) >= distSq(p0, p1);
                }
                return o == 2;
            }
            pointsComparator(Point p) : p0(p) {}
        };
        
        // Prints convex hull of a set of n points.
        vector<Point> outerTrees(vector<Point> points) {
            int n = points.size();
            if (n <= 3) {
                return points;
            }
            // Find the bottommost point
            int ymin = points[0].y, min = 0;
            for (int i = 1; i < n; i++) {
                int y = points[i].y;
                // Pick the bottom-most or chose the left most point in case of tie
                if ((y < ymin) || (ymin == y && points[i].x < points[min].x)) {
                    ymin = points[i].y, min = i;
                }
            }
     
            // Place the bottom-most point at first position
            Point temp = points[0];
            points[0] = points[min];
            points[min] = temp;
            
            // Sort n-1 points with respect to the first point.
            // A point p1 comes before p2 in sorted ouput 
            // if p2 has larger polar angle (in counterclockwise direction) than p1
            // In the tied case, the one has smaller distance from p0 comes first
            Point p0 = points[0];
            sort(points.begin(), points.end(), pointsComparator(p0));
            //As we need to output all the vertices instead of extreme points
            //We need to sort the points with the same largest polar angle w.r.p. p0 in another way to break tie
            //Closer one comes last
            Point pn = points.back();        
            if (orientation(p0, points[1], pn) != 0) {
                int idx = n-1;
                while (orientation(p0, points[idx], pn) == 0) {
                    idx--;
                }
                reverse(points.begin() + idx + 1, points.end());
            }
     
            // Create an empty stack and push first three points to it.
            vector<Point> vertices;
            vertices.push_back(points[0]);
            vertices.push_back(points[1]);
            vertices.push_back(points[2]);
            // Process remaining n-3 points
            for (int i = 3; i < n; i++) {
                // Keep removing top while the angle formed by
                // points next-to-top, top, and points[i] makes a right (in clockwise) turn
                while (orientation(vertices[vertices.size() - 2], vertices.back(), points[i]) == 1) {
                    vertices.pop_back();
                }
                vertices.push_back(points[i]);
            }
            return vertices;
        }
    };
    

    For the Andrew's monotone chain method, the only part you need to take care is one degenerate case: all the vertices lie on a single line. The others is basically two Graham Scans for upper hull and lower hull. Of course, we don't pop the top point in the stack if three points are collinear.

    class Solution {
    public:
        static bool pointCompare(const Point& a, const Point& b) {
            //Sort the points by x-coordinates, break a tie by y-coordinate
            return (a.x < b.x) || ((a.x == b.x) && (a.y < b.y));
        }
        
        bool isEqual(const Point& a, const Point& b) {
            return (a.x == b.x) && (a.y == b.y);    
        }
        
        int crossProduct(const Point& a, const Point& b, const Point& c) {
            // > 0 if a,b,c forms a counter clockwise turn
            // < 0 if a,b,c forms a clockwise turn
            // = 0 if a,b,c are collinear
            return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
        }
        
        vector<Point> outerTrees(vector<Point>& points) {
            //Sort the points
            sort(points.begin(), points.end(), pointCompare);
            vector<Point> upper;
            vector<Point> lower;
            //Find upper hull, in the dereasing order of x-coordinate
            for (int i = points.size() - 1; i >= 0; --i) {
                //Pop the top point if next_to_top, top, points[i] forms a right turn (in clockwise turn)
                while ((upper.size() > 1) 
                    && (crossProduct(upper[upper.size() - 2], upper[upper.size() - 1], points[i]) < 0)) {
                    upper.pop_back();
                }
                upper.push_back(points[i]);
            }
            //Find lower hull, in the increasing order of x-coordinate 
            for (int i=0; i<points.size(); i++) {
                //Pop the top point if next_to_top, top, points[i] forms a right turn (in clockwise turn)
                while ((lower.size() > 1) 
                    && (crossProduct(lower[lower.size() - 2], lower[lower.size() - 1], points[i]) < 0)) {
                    lower.pop_back();
                }
                lower.push_back(points[i]);            
            }
            //Check the degenerate case if the convex hull is a line
            //In this case, lower == upper, we only need to check if upper[1] == lower[lower.size() - 2]
            if ((points.size() == 1) || (isEqual(upper[1],lower[lower.size() - 2]))) {
                return vector<Point>(upper.begin(), upper.end());
            }
            //In non-degenerate case, remove the starting point for both hulls
            //The right most one and the left most one is duplicated in both hulls
            vector<Point> vertices(upper.begin() + 1, upper.end());
            vertices.insert(vertices.end(), lower.begin() + 1, lower.end());
            return vertices;
        }
    };
    

  • 1
    Z

    @actionlee0405 said in c++ Graham Scan/Monotone Chain dealing with collinear cases:

    How about checking upper.size( ) == n before finding lower hull for a line case?

    class Solution {
    public:
        vector<Point> outerTrees(vector<Point>& points) {
            // Andrew's monotone chain method
            int n = points.size();
            if (n <= 3) return points;
            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
    A

    @zestypanda Yes, you are right. It could simplify the code and save some time. Thanks!


Log in to reply
 

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