c++algorithmconvex-hullgrahams-scan

How Graham's scan algorithm prepares points to find a convex hull?

I wanted to solve Erect The Fence from LeetCode. That's my code:

const double PI = 3.141592653589793;

double get_angle(const vector<int>& p1, const vector<int>& p2) {
    vector<int> p{ p2[0] - p1[0], p2[1] - p1[1] };

    double angle = atan2(p[1], p[0]);
    angle = angle * 180 / PI;

    if (angle < 0)
        angle = 180 + (180 + angle);

    return angle;
}

static bool comp(const tuple<double, int, int>& k1, const tuple<double, int, int>& k2) {
    if (get<0>(k1) == get<0>(k2)) {
        if (get<2>(k1) == get<2>(k2))
            return get<1>(k1) < get<1>(k2);

        return get<2>(k1) > get<2>(k2);
    }

    return get<0>(k1) < get<0>(k2);
}

vector<vector<int>> outerTrees(vector<vector<int>> trees) {
    if (trees.size() <= 3)
        return trees;

    vector<int>* bottom_left_most_tree = &trees[0];
    int idx = 0;
    for (int i = 1; i < trees.size(); ++i) {
        if (trees[i][1] == (*bottom_left_most_tree)[1] && (trees[i][0] < (*bottom_left_most_tree)[0])
            || (trees[i][1] < (*bottom_left_most_tree)[1])) {
            bottom_left_most_tree = &trees[i];
            idx = i;
        }
    }

    vector<tuple<double, int, int>> forest(trees.size());
    for (int i = 0; i < trees.size(); ++i) {
        if (i == idx) {
            forest[i] = { -1, trees[i][0], trees[i][1] };
            continue;
        }

        double angle = get_angle(*bottom_left_most_tree, trees[i]);
        forest[i] = { angle, trees[i][0], trees[i][1] };
    }

    sort(forest.begin(), forest.end(), comp);

    stack<vector<int>> polygon_vertices;
    polygon_vertices.push(*bottom_left_most_tree);
    polygon_vertices.push({ get<1>(forest[0]), get<2>(forest[0]) });

    auto tree = forest.begin();
    ++tree;

    for (; tree != forest.end(); ++tree) {
        vector<int> mid = polygon_vertices.top();
        polygon_vertices.pop();

        vector<int> prev = polygon_vertices.top();

        polygon_vertices.push(mid);

        vector<int>const& next = { get<1>(*tree), get<2>(*tree) };

        double alpha = get_angle(prev, mid);
        double beta = get_angle(mid, next);

        while (beta < alpha) {
            polygon_vertices.pop();
            mid = polygon_vertices.top();

            polygon_vertices.pop();
            prev = polygon_vertices.top();

            polygon_vertices.push(mid);

            alpha = get_angle(prev, mid);
            beta = get_angle(mid, next);
        }

        polygon_vertices.push(next);
    }

    vector<vector<int>> result(polygon_vertices.size() - 1);
    int i = 0;
    while (polygon_vertices.size() > 1) {
        result[i] = polygon_vertices.top();
        polygon_vertices.pop();

        ++i;
    }

    return result;
}

I thought I'm able to implement Graham Scan algorithm. But after testing the code I'm not sure about one thing. How to sort the points?

As u can see, as starting point I get the most bottom (lowest Y), and if there are many, I get the one with the lowest X (most on left).

The problem with this code is that it sorts points the by angle between starting point and the point itself. Then, if there are many, by highest Y, and if there are many, then it sorts by X (most left).

And that's a problem - because if we have multiple points above starting point (like 90 degress, the same X but different Y), then we first visit the highest point - and then return back to the points with lesser Y. It produces bad results.

But sorting by highest Y is necessary so we won't come to the same problem (e.g. consider two points with the same angle between them itselfs and starting point, but with different Y. We have to visit the one with highest Y, otherwise we can get wrong result).

I thought I need to divide points on two halves by line that connects bottom most and the highest points. Then one half will have clockwise turns, and the another counterclockwise.

But because I haven't see Graham's scan algorithm explanation that behaves like that, I wonder what have I misunderstood? How to sort the points?

Solution

  • A Graham scan should successfully produce a convex hull no matter how you break ties when sorting by angle.

    If you're writing the kind of Graham scan that removes redundant points by accepting only left turns, then you should get exactly the same result no matter how you break ties when sorting points. In fact, in this case only the farthest point at any angle could possibly end up on the convex hull, so you could just get rid of all the other ones.

    Your problem requires you to keep redundant points, however, and that kind of Graham scan also accepts proceeding in the same direction in addition to turning left. In this case, it's important that the points on the hull are visited in the correct order.

    Note that this only affects the facets of the hull immediately before and after the starting point, because at all other angles, only the furthest point could possibly be on the hull.

    Since you are starting with the smallest point by (y,x) you can sort your points into the desired order using this comparison algorithm for any two points a and b:

    Now, this is how to fix a Graham scan the way you want, but it might not solve all of your problems, because you are using inexact floating point math and atan2 in your comparison function. Because of rounding errors in your computations, it's possible that points at the same angle could end up being sorted as if they were at different angles, and then the order in which you visit them could be messed up.

    You could fix this by being very careful in your comparison function to get exactly the right result. That's a little tricky, though. I would really suggest switching to the monotone chain algorithm instead. This is a lot like a Graham scan, but it doesn't involve angles or numerically unstable computations.