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

• 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;
}
};
``````

• 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);
}
};
``````

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

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