Convex Hull

/*
 * Copyright (c) 2014 Krzysztof Pachulski
 * License: The MIT License (MIT)
 * MIT License page: http://opensource.org/licenses/MIT
 *
 * getConvexHull() function calculates a convex hull of a cloud
 * of points defined as a vector of points.
 *
 * getConvexHull() function uses Point and Edge classes
 * provided below.
 *
 */

struct Point
{
    float x;
    float y;

    float getAngle() const
    {
        return atan2(this->y, this->x);
    }

    bool operator==(Point other) const
    {
        return this->x == other.x && this->y == other.y;
        //return (*this - other).magnitude() <= 0.0001f;
    }

    bool operator<(Point other) const
    {
        return this->x < other.x && this->y < other.y;
    }

    bool operator!=(Point other) const
    {
        return this->x != other.x && this->y != other.y;
        //return (*this - other).magnitude() > 0.0001f;
    }
    
    Point operator+(Point other) const
    {
        Point point;
        point.x = this->x + other.x;
        point.y = this->y + other.y;
        return point;
    }

    Point operator-(Point other) const
    {
        Point point;
        point.x = this->x - other.x;
        point.y = this->y - other.y;
        return point;
    }

    float magnitude()
    {
        return sqrtf(powf(this->x, 2) + powf(this->y, 2));
    }
};

struct Edge
{
    Point start;
    Point end;

    bool isPointOnTheLeft(Point point)
    {
        int val = (start.y - end.y) * (point.x - end.x) - (start.x - end.x) * (point.y - end.y);

        if (val == 0) return false;
        return (val > 0) ? false : true;
    }

};

std::vector<Point> getConvexHull(const std::vector<Point>& points)
{
    std::vector<Point> convexHull;

    int min = 0;
    for (int i = 0; i < points.size(); ++i)
    {
        if (points[i].y < points[min].y)
            min = i;
    }

    std::swap(points[min], points[0]);

    std::sort(points.begin() + 1, points.end(), [&](const Point p1, const Point p2)
    {
        return (points[0] - p1).getAngle() > (points[0] - p2).getAngle();
    });

    std::stack<int> stack;
    int next = 2;
    stack.push(0);
    stack.push(1);

    do
    {
        Edge edge;
        edge.start = points[Utils::getFirstBelowTop(stack)];
        edge.end = points[stack.top()];

        while (!edge.isPointOnTheLeft(points[next]))
        {
            stack.pop();
            edge.start = points[Utils::getFirstBelowTop(stack)];
            edge.end = points[stack.top()];
        }

        stack.push(next);
        ++next;

    } while (next < points.size());
    stack.push(0);

    while (!stack.empty())
    {
        convexHull.push_back(points[stack.top()]);
        stack.pop();
    }

    return convexHull;
}