Convex hull / Graham scan

graham.cxx

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