A very concise c++ Graham Algorithm with explaination


  • 0
    X

    A very concise c++ Graham Algorithm. Reference https://segmentfault.com/a/1190000000488339 if you can read Chinese :)
    steps:

    1. sort the points by x, y
    2. start from the first point on the left lower corner and scan the lower chain of the convex hull
    3. start from the last point on the right upper corner and scan the upper chain of the convex hull
     //Graham Algorithm
     //ref https://segmentfault.com/a/1190000000488339
    bool PointLess(const Point &a, const Point &b)
    {
    	if (a.x == b.x)
    		return a.y < b.y;
    
    	return a.x < b.x;
    }
    
    class Solution {
    public:
        vector<Point> outerTrees(vector<Point>& points) {
    	int len = points.size();
    	if (len < 4)
    		return points;
    	//sort the points by x as first key, y as second key
    	vector<Point> convexHull;
    	sort(points.begin(), points.end(), PointLess);
        
        //find the lower chain
    	for (int i = 0; i < len; ++i)
    	{
    		
    		while (convexHull.size()  > 1)
    		{
    			int n = convexHull.size();
    			Point vec1(convexHull[n-1].x - convexHull[n-2].x, convexHull[n-1].y - convexHull[n-2].y);
    			Point vec2(points[i].x - convexHull[n-1].x, points[i].y - convexHull[n-1].y);
    			//the cross product is negative, a concave inner angle is found, should pop the last point
    			if ((vec1.x*vec2.y - vec2.x*vec1.y) < 0)
    				convexHull.pop_back();
    			else
    				break;
    		}
    		convexHull.push_back(points[i]);
    	}
    	
    	// find the upper chain
    	int lower = convexHull.size();
    	for (int i = len - 2; i >= 0; --i)
    	{
    		while (convexHull.size()  > lower)
    		{
    			int n = convexHull.size();
    
    			Point vec1(convexHull[n - 1].x - convexHull[n - 2].x, convexHull[n - 1].y - convexHull[n - 2].y);
    			Point vec2(points[i].x - convexHull[n - 1].x, points[i].y - convexHull[n - 1].y);
    			
    			//the cross product is negative, a concave inner angle is found, should pop the last point
    			if ((vec1.x*vec2.y - vec2.x*vec1.y) < 0)
    				convexHull.pop_back();
    			else
    				break;
    		}
    		convexHull.push_back(points[i]);
    
    	}
    	//pop the last one because it is same as first one
    	convexHull.pop_back();
    
    	return convexHull;        
        }
    

Log in to reply
 

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