Compute Convex Hull

Question

The question asks to compute the convex hull of a set of 2D points. A convex hull is basically a series of consecutive line segments that suffice to enclose all the points in the area. In this exercise, I am using Jarvis's March algorithm.

Here is the code:

#include <iostream>
#include <fstream>
#include <string>

#include <vector>
#include <algorithm>

using uint = unsigned int;

struct Vector2D
{   
    int x_;
    int y_;
    Vector2D() : x_(0), y_(0) {}
    Vector2D(int x, int y) : x_(x), y_(y) {}
    Vector2D operator+(const Vector2D & vec) const
    {
        return Vector2D(x_ + vec.x_, y_ + vec.y_);
    }
    Vector2D operator-(const Vector2D & vec) const
    {
        return Vector2D(x_ - vec.x_, y_ - vec.y_);
    }
};

using itVector2D = std::vector<Vector2D>::iterator;

enum RelativePosition { Clockwise, CounterClockwise };

RelativePosition ComparePosition(Vector2D target, Vector2D reference);
itVector2D findeNextVertex(std::vector<Vector2D> & coords, itVector2D itSource);

int main()
{
    std::ifstream file;
    file.open("data.txt");
    if (!file.is_open())
    {   
        std::cerr << "unable to open file" << std::endl;
        return -1;
    }

    // total number of points
    uint nPoints = 0;
    file >> nPoints;

    // creating data set
    std::vector<Vector2D> coords;
    coords.reserve(nPoints);

    // reading data set
    Vector2D temp;
    for (uint i = 0; i < nPoints; ++i)
    {
        file >> temp.x_ >> temp.y_;
        coords.push_back(temp);
    }

    // find the topmost
    itVector2D itTopMost = std::max_element(coords.begin(), coords.end(),
        [](const Vector2D & a, const Vector2D & b) { return a.y_ < b.y_; });



    // while it doesnt trace back to origin 
    // perform algorithm once to get to the next vertex
    itVector2D itCurrent = itTopMost;

    do
    {
        itCurrent = findeNextVertex(coords, itCurrent);
        std::cout << itCurrent->x_ << " " << itCurrent->y_ << std::endl;
    } while (itCurrent != itTopMost);

    return 0;
}

RelativePosition ComparePosition(Vector2D target, Vector2D reference)
{
    // compute determinant to determine if it is CW or CCW
    return reference.y_ * target.x_ - reference.x_ * target.y_ > 0 ? Clockwise : CounterClockwise;
}

// find next convex hull vertex
itVector2D findeNextVertex(std::vector<Vector2D> & coords, itVector2D itSource)
{
    for (itVector2D itTarget = coords.begin(); itTarget != coords.end(); ++itTarget)
    {
        // if itTarget is the same point as itSource, skip this case
        if (itTarget == itSource)
        {
            continue;
        }

        // assume itTarget is counterclockwise to all itReference
        bool allCC = true;

        // for other cases, find out if itTarget is counter-clockwise to all the itReference
        for (itVector2D itReference = coords.begin(); itReference != coords.end(); ++itReference)
        {   
            if (itReference == itTarget || itReference == itSource)
            {
                continue;
            }

            Vector2D vecTarget = *itTarget - *itSource;
            Vector2D vecReference = *itReference - *itSource;

            if (ComparePosition(vecTarget, vecReference) != CounterClockwise)
            {
                allCC = false;
                break;
            }
        }

        // if this itTarget is counter-clockwise to all the itReference
        if (allCC)
        {
            return itTarget;
        }

    }
}

I have tested one set of data below (named as "data.txt" in the code), which is correct.

12
5 19
33 2
-5 88
54 5
12 13
18 39
15 42
17 -5
-3 23
9 29
-8 17
-1 25

I am quite new to C++, so any feedback is appreciated. Here are some questions that I have after writing this code:

1. I encountered many cases where data type is unsigned int, especially for the case, for(unsigned int i = ...; i < ....; ++i) So I use using uint = unsigned int. Is it necessary to do so? Especially for the "for() loop" case, because it bothers me quite often.

2. I only check if file can be correctly read at the very beginning, but have no idea about how to safely read the following content. A general guidance covering this would be appreciated.

3. I created a temp Vector2D object to store a pair of coordinate temporarily and push it into the vector afterwards. Can I avoid creating this temp object?

4. When finding the topmost vertex, I used std::max_element. However I found that it doesn't really depend on this function but the lambda function I wrote after. If I flip the comparative "return a.y_ < b.y_;" to greater than, it gives me different answer. So what does std::max_element really do?

5. I have seen people say underscore after or before variable name is reserved. However, others don't really think it causes trouble in scope. Is it okay to use it as I did in the code for Vector2D? A recommended way is to use m_variableName, but I don't really like this format.

Any other feedback or comments are also welcome!

Answer 1

Handle an edge case

Firstly, let's fix this compiler warning:

190179.cpp: In function ‘itVector2D findeNextVertex(std::vector<Vector2D>&, itVector2D)’:
190179.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

We should only reach this in the degenerate case where there are no candidate points (e.g. we've provided only 1 input to the algorithm). In that case, the most appropriate iterator to return is the starting point:

return itSource;

A convenience for debugging

To save depending on an external resource, I embedded test data into the program (just to make it easier to experiment):

#ifdef DEBUG
    std::istringstream file{""
            "12\n"
            "5 19\n"
            "33 2\n"
            "-5 88\n"
            "54 5\n"
            "12 13\n"
            "18 39\n"
            "15 42\n"
            "17 -5\n"
            "-3 23\n"
            "9 29\n"
            "-8 17\n"
            "-1 25\n"
            };
#else
    std::ifstream file;
    file.open("data.txt");
    if (!file.is_open())
    {
        std::cerr << "unable to open file" << std::endl;
        return 1;
    }
#endif

I'm not suggesting you do the same - but you might find it useful, so I'm showing it here.

Something that might be worthwhile, though, is to separate the input and output from your processing. In this case, consider the benefit of

const std::vector<Vector2D> coords = readInputPoints();

We can easily replace that function to read from a different source, and it's enabled us to have an immutable list of coordinates, reducing the potential for accidentally modifying them.

Check errors when reading inputs

After file >> nPoints, it's essential to check that this succeeded before attempting to use nPoints. Fortunately the streaming operator returns a reference to the input stream, and that converts to bool, so we can use a simple if statement, like this:

uint nPoints = 0;
if (file >> nPoints) {
    coords.reserve(nPoints);
    // then read each point and insert it
}

We should do the same for each point, as well:

    for (uint i = 0; i < nPoints; ++i) {
        int x, y;
        if (file >> x >> y) {
            coords.emplace_back(x, y);
        }
    }

In passing, here I've used emplace_back to create the object directly in the vector.

Vector2D structure

This structure is the minimum necessary for this application (possibly too minimal; as I'll show), but the name is popular, and may collide if used in a larger program. We can put it into a namespace to avoid this problem. For this program, an anonymous namespace will be sufficient.

We can add some members to make the rest of the code simpler. Let's start with an ordering, that allows us to remove the lambda function from our std::max_element() call:

auto tie() const { return std::tie(y_, x_); }

// "less-than" means lower, with leftmost breaking ties
bool operator<(const Vector2D& other) const
{
    return tie() < other.tie();
}

We really could do with a print operator:

friend std::ostream& operator<<(std::ostream& os, const Vector2D& v)
{
    return os << v.x_ << ' ' << v.y_ << '\n';
}

The other computation that requires access to the member variables is calculating direction. Let's make that a member, too:

bool is_clockwise_to(const Vector2D& other) const
{
    // a positive determinant indicates clockwise, and negative anticlockwise
    // zero implies collinear
    return y_ * other.x_ - x_ * other.y_ > 0;
}

Now we can make x_ and y_ private.

Prefer using values to iterators

We actually care more about the values of the points we're bounding than their identities. By that, I mean that in tests such as (itReference == itTarget || itReference == itSource), we actually want to reject any points on those spots, not just the specific instances. This obviously isn't a problem if there are no duplicates in the input, but we don't know that to be true.

Simplify with a standard algorithm

We have a loop updating allCC, which we can replace with a std::all_of() call.

Minor quibbles

• Spelling - there's an extra e in findeNextVertex()
• I prefer not to have trailing underscores - if you need a reminder of what's a member in your classes, it suggests that you have too many members, probably doing more than it should (read about the Single-Responsibility Principle of OO design).
• std::size_t is the natural type for counts of things, rather than unsigned int (though if you have more than 65536 points, you've likely chosen the wrong algorithm).
• Prefer to use std::endl only when you need the stream to be flushed, and plain old '\n' otherwise. Unnecessary flushing can be a real performance killer at times!

---

Modified code

#include <fstream>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#include <algorithm>

namespace {

    class Vector2D
    {
        int x;
        int y;

        // For sorting - lowest y first, then lowest x
        auto tie() const { return std::tie(y, x); }

    public:
        Vector2D(int x, int y) : x(x), y(y) {}

        Vector2D operator-(const Vector2D& other) const
        {
            return {x - other.x, y - other.y};
        }

        bool operator<(const Vector2D& other) const
        {
            return tie() < other.tie();
        }
        bool operator==(const Vector2D& other) const
        {
            return tie() == other.tie();
        }

        bool is_clockwise_to(const Vector2D& other) const
        {
            // a positive determinant indicates clockwise, and negative anticlockwise
            // zero means collinear (which we consider "not clockwise")
            return y * other.x - x * other.y > 0;
        }

        friend std::ostream& operator<<(std::ostream& os, const Vector2D& v)
        {
            return os << v.x << ' ' << v.y << '\n';
        }
    };

    using namespace std::rel_ops;
}

// find next convex hull vertex
Vector2D nextVertex(const std::vector<Vector2D> & coords, const Vector2D& source)
{
    for (auto const& target: coords)
    {
        auto const vecTarget = target - source;
        if (vecTarget != Vector2D{ 0, 0 } &&
            std::all_of(coords.begin(), coords.end(),
                        [&](const auto& c) {
                            return c == target
                                || c == source
                                || (c - source).is_clockwise_to(vecTarget);}))
        {
            return target;
        }
     }

    // degenerate case
    return source;
}


std::vector<Vector2D> readInputPoints()
{
    std::ifstream file;
    file.open("data.txt");
    if (!file.is_open()) {
        std::cerr << "unable to open file" << std::endl;
        return {};
    }

    std::vector<Vector2D> coords;

    // total number of points
    std::size_t nPoints = 0;
    file >> nPoints;
    if (!file) return {};

    coords.reserve(nPoints);

    while (--nPoints) {
        int x, y;
        file >> x >> y;
        if (!file) return {};

        coords.emplace_back(x, y);
    }

    return coords;
}


int main()
{
    const std::vector<Vector2D> coords = readInputPoints();

    if (coords.empty()) {
        std::cerr << "Could not read inputs!" << std::endl;
        return 1;
    }

    // find the topmost
    auto const& topMost = *std::max_element(coords.begin(), coords.end());
    auto current = topMost;

    do {
        current = nextVertex(coords, current);
        std::cout << current;
    } while (current != topMost);
}

---

Improve the algorithm

The current algorithm looks at the next two points from each vertex, so it scales as O(hn²) where n is the number of points and h the number of bounding points.

We can use the knowledge that all points lie on the same side of some line through any bounding point to only test each candidate once - if it's further to the left (or right, depending which way round the hull we want to go) of the previous best candidate, then it's a better choice. This, of course, is simply choosing the maximum of a new criterion, and it makes our code scale as O(hn).

Here's what I mean:

Vector2D nextVertex(const std::vector<Vector2D> & coords, const Vector2D& source)
{
    // order by direction from source - this works because we know that all
    // points lie on the same side of a line through source.
    auto const by_angle = [&source](const Vector2D& a, const Vector2D& b) {
        return (a - source).is_clockwise_to(b - source);
    };

    return *max_element(coords.begin(), coords.end(), by_angle);
}

Notice that this came out simpler than my first improved version above, and much simpler than the original. (The lambda that captures a reference to source might be more advanced than you're used to, though).

You might want to make a refinement so that collinear points sort in order of distance from point (use std::hypot() in the <cmath> header to add a member to Vector2D). Without that, we could have source be directly between two other bounding points, and they would compare equal.

Consider adding some test cases with collinear bounding points and some with trivial point sets (1 or 2 points), as these will probably require minor modifications.

Answer 2

I'm new to this SE community and I'm not sure I can address all your questions, but here's my two cents about it, edits and comments are welcomed:

1. If you want to avoid typing unsigned int every time you use it, you can create an alias by either typing using just like you do (I'm not familiar with this one, I only use it for namespaces), or you could use the following:

   typedef unsigned int uint;
   

   typedef is especially used for giving another name to a given data type in C and C++.

2. is_open() returns whether the stream is currently associated to a file. You could use the fail() method instead. This one checks the overall health of the stream, for example checking if the stream has entered a fail state from trying to read an invalid value. is_open() does not check this kind of things.

3. I'll skip this part.

4. max_element() returns an iterator to the largest element in the range [first, last]. There are 2 prototype for this function, based on different concepts. The one you're using has 3 parameters and is based on comp, and not on operator< as explained here. I don't know much about comp but my guess is that his behavior is different from operator<, which explains why you have different results when comparing both computing methods.

5. Usage of the underscore symbol is something ruled by conventions. I'm not sure about this but IMO you used it well and prevented confusion between the constructors parameters and your object attributes. I've seen it written this way lots of times on tutorials so I don't know why it would be wrong to do it. And just for the record, I hate the m_my_variable syntax as well. To me, the m, l and g letters don't bring anything more except confusion. But again, it's a convention and surely many people like it a lot :)

Answer 3

Some answer to your explicit questions:

1. unsigned int

• I personally do not like such typedefs purely for brevity; however they are fine for defining types like distance if you ever think of changing it to double
• Unsigned vs. signed and compiling warning-free - this is already spoiled by the libraries. Use unsigned only for bit fiddling. Listen to the C++ gurus discussing this (minute 12:15, minute 42:40 and 1:02:50)

5. underscores or marking members

• When reading code it is useful to have members marked as such. Especially constructors with params named like the members may be error-prone.
• _[a-z] is fine for members. but it is reserved in global namespace. Also _[_A-Z] is reserved (see answer to "What are the rules about using an underscore in a C++ identifier?"). So a leading underscore is safe here; it depends on your coding standards whether it is allowed.

4. std::max_element

This does for a range what std::max does for two values: delivering the biggest by making use of "less than" comparison. if your type is not comparable out of the box or if you want to override the default comparison you can provide a custom Compare which must be implemented as custom "less than". If you provide a "greater than" the sort order is reversed. Your max_element guarantees a maximum y not considering x values. If your data set contains coordinates with the same value for y but different x values those coordinates are equal from the point of view of the comparison function. The first of those equally max y coordinates is returned.