Convex Hull - Graham Scan algorithm implementation in C++17

kennfatt_convex_hull.cc

#include <iostream>
#include <stack>
#include <stdlib.h>

struct Point {
    int x, y;

    Point() = delete;

    Point(int _x, int _y) : x(_x), y(_y) {}
};

/**
 * Assume we have 3 points A, B, and C.
 * Vector V is from A -> B or AB.
 * Vector w is from A -> C or AC.
 *
 * Cross Product V x W:
 *  (Vx . Wy) - (Wx . Vy)
 *
 * Then the orientation is:
 *  (Bx - Ax) * (Cy - Ay) - (Cx - Ax) * (By - Ay)
 * 
 * @return int 0 -> Colinear, 1 -> Clockwise, 2 -> Counter Clockwise
 */
int orientation(Point a, Point b, Point c) {
    int value = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);

    /** Colinear case */
    if (value == 0) {
        return 0;
    }

    /**
     * 1 -> Clockwise
     * 2 -> Counter clockwise
     */
    return value < 0 ? 1 : 2;
}

/**
 * Find the most bottom (or left, if they has same Y value) point
 * and swap it into the first element of `points[]`.
 * 
 * Complexity: O(n)
 */
void findStartPoint(Point points[], unsigned n) {
    Point tmp = points[0];
    unsigned tmpIndex = 0;
    for (unsigned i = 1; i < n; ++i) {
        if (points[i].y <= tmp.y) {
            if (points[i].y < tmp.y) {
                tmp = points[i];
                tmpIndex = i;
            } else if (points[i].x < tmp.x) {
                tmp = points[i];
                tmpIndex = i;
            }
        }
    }
    
    /** Swap */
    Point first = points[0];
    points[0] = tmp;
    points[tmpIndex] = first;
}

Point nextToTop(std::stack<Point> &s) {
    Point p = s.top();
    s.pop();
    Point res = s.top();
    s.push(p);
    return res;
}

Point start = {0, 0};

// dirty mode
void ConvexHull(Point points[], unsigned n) {
    // Prevent to calculate invalid points.
    if (n < 3) {
        return;
    }

    // Create the stack
    std::stack<Point> stack;

    // Find the starting point
    findStartPoint(points, n);
    start = points[0]; // Put the start to global variable.

    // Sort all points respect to points[0]
    qsort(&points[1], n - 1, sizeof(Point), [](const void *a, const void *b) -> int {
        Point aa = *((Point *) a);
        Point bb = *((Point *) b);

        int o = orientation(start, aa, bb);

        // Colinear case
        if (o == 0) {
            // If both in the same x-asis, then find the lower (y-axis) first.
            if (aa.x == bb.x) {
                return aa.y < bb.y ? -1 : 1;
            }

            // let the nearest point from the start come first.
            return aa.x < bb.x ? -1 : 1;
        }
        
        // Prioritize the counter clockwise.
        return o == 2 ? -1 : 1;
    });

    int m = 1;    // Initialize size of modified array
    
    for (unsigned i = 1; i < n; i++) {
        // Keep removing i while angle of i and i+1 is same
        // with respect to p0
        while (i < n - 1 && orientation(start, points[i], points[i + 1]) == 0) {
            i++;
        }

        points[m] = points[i];
        m++;    // Update size of modified array
    }

    if (m < 3) {
        return;
    }

    stack.push(points[0]);
    stack.push(points[1]);

    for (unsigned i = 2; i < m; ++i) {
        while (orientation(nextToTop(stack), stack.top(), points[i]) != 2) {
            stack.pop(); // remove the elment from stack if they are not counter clockwise.
        }

        stack.push(points[i]);
    }

    // Last time checking for colinear case
    Point p = stack.top();
    stack.pop();
    if (orientation(stack.top(), p, points[0]) == 2) {
        stack.push(p); // put it back.
    }

    // Print the result
    std::cout << "Hull: " << std::endl;
    while (!stack.empty()) {
        Point top = stack.top();
        std::cout << "- {" << top.x << ", " << top.y << "}" << std::endl;
        stack.pop();
    }
}

int main() {
    Point pts[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    ConvexHull(pts, (sizeof(pts) / sizeof(pts[0])));
}