Skip to content

Instantly share code, notes, and snippets.

@daltondotgd
Last active Aug 29, 2015
Embed
What would you like to do?
/*
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment