Skip to content

Instantly share code, notes, and snippets.

@max-dark
Created Nov 21, 2020
Embed
What would you like to do?
Convex hull / Graham scan
auto comparePoints(const QPointF& a, const QPointF& b)
{
return a.x() < b.x() || (a.x() == b.x() && a.y() < b.y());
}
auto convex_hull_graham(QPolygonF& points)
{
if (points.size() <= 1) return points;
QPolygonF result, up, down;
std::sort(points.begin(), points.end(), comparePoints);
auto p1 = points.front();
auto p2 = points.back();
up.push_back(p1);
down.push_back(p1);
for(auto i = 1; i < points.size(); ++i)
{
auto is_last = i == points.size() - 1;
if (is_last || is_cw_rotation(p1, points[i], p2))
{
while (up.size() >= 2 && !is_cw_rotation(
up[up.size() - 2], up[up.size() - 1], points[i])) {
up.pop_back();
}
up.push_back(points[i]);
}
if (is_last || is_ccw_rotation(p1, points[i], p2))
{
while (down.size() >= 2 && !is_ccw_rotation(
down[down.size() - 2], down[down.size() - 1], points[i])) {
down.pop_back();
}
down.push_back(points[i]);
}
}
result.append(up);
for(auto i = down.size() - 2; i > 0; --i)
{
result.push_back(down[i]);
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment